A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs

In this paper we consider a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job we mean that the job's processing time is an increasing function of its starting time. We model job deterioration as a function that is proportional to a linear function of time. The objective is to find a sequence that minimizes the total completion time of the jobs. For the general case, we derive several dominance properties, some lower bounds, and an initial upper bound by using a heuristic algorithm, and apply them to speed up the elimination process of a branch-and-bound algorithm developed to solve the problem.     

A two-machine flowshop makespan scheduling problem with deteriorating jobs

In traditional scheduling problems, the job processing times are assumed to be known and fixed from the first job to be processed to the last job to be completed. However, in many realistic situations, a job will consume more time than it would have consumed if it had begun earlier. This phenomenon is known as deteriorating jobs. In the science literature, the deteriorating job scheduling problems are relatively unexplored in the flowshop settings. In this paper, we study a two-machine flowshop makespan scheduling problem in which job processing times vary as time passes, i.e. they are assumed as increasing functions of their starting times. First, an exact algorithm is established to solve most of the problems of up to 32 jobs in a reasonable amount of time. Then, three heuristic algorithms are provided to derive the near-optimal solutions. A simulation study is conducted to evaluate the performances of the proposed algorithms. In addition, the impact of the deterioration rate is also investigated.     

Two-machine flow shop scheduling with linear decreasing job deterioration

In this paper, we consider a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job, we mean that the processing time is a decreasing function of its execution start time. A proportional linear decreasing deterioration function is assumed. The objective is to find a sequence that minimizes total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational results for randomly generated problem instances are presented, which show that the heuristic algorithm effectively and efficiently in obtaining near-optimal solutions.     

Flow shop scheduling to minimize makespan with decreasing time-dependent job processing times

In this study, we consider an n-job, m-machine flow shop scheduling problem with decreasing time-dependent job processing times. By the decreasing time-dependent job processing times, we mean that the processing time is a decreasing function of its execution starting time. When some dominant relationships between m − 1 machines can be satisfied, we show that the makespan minimization problem can be solved in polynomial time.     

An improved NEH heuristic to minimize makespan in permutation flow shops

For over 20 years the NEH heuristic of Nawaz, Enscore, and Ham [A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, The International Journal of Management Science 1983;11:91–5] has been commonly regarded as the best heuristic for solving the NP-hard problem of minimizing the makespan in permutation flow shops. The strength of NEH lies mainly in its priority order according to which jobs are selected to be scheduled during the insertion phase. Framinan et al. [Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idle time or flowtime in the static permutation flowshop problem. International Journal of Production Research 2003;41:121–48] presented the results of an extensive study to conclude that the NEH priority order is superior to 136 different orders examined. Based upon the concept of Johnson's algorithm, we propose a new priority order combined with a simple tie-breaking method that leads to a heuristic that outperforms NEH for all problem sizes.     

Minimizing the total completion time in permutation flow shop with machine-dependent job deterioration rates

Deteriorating jobs scheduling problems can be found in many practical situations. Due to the essential complexity of the problem, most of the research focuses on the single-machine setting. In this paper, we address a total completion time scheduling problem in the m$m$-machine permutation flow shop. First of all, we propose a dominance rule and an efficient lower bound to speed up the searching for the optimal solution. Second, several deterioration patterns, which include an increasing, a decreasing, a constant, a V-shaped, and a Λ$\Lambda$-shaped one, are investigated in order to study the impact of the deterioration rates. Finally, the performance of some well-known heuristics under various deterioration patterns is evaluated.     

Two-machine flow shop problem with effects of deterioration and learning

In this paper we consider a two-machine flow shop scheduling problem with effects of deterioration and learning. By the effects of deterioration and learning, we mean that the processing time of a job is a function of its execution starting time and its position in a sequence. The objective is to find a sequence that minimizes the total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed, which is shown by computational experiments to perform effectively and efficiently in obtaining near-optimal solutions.     

Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine

The scheduling problem with deteriorating jobs to minimize the makespan on a single machine where the facility has an availability constraint is studied in this paper. By a deteriorating job we mean that the processing time for the job is a function of its starting time. Even with the introduction of the availability to a facility, the linear deteriorating model can be solved using the 0-1 integer programming technique if the actual job processing time is proportional to the starting time.     

A new ant colony algorithm for makespan minimization in permutation flow shops

The problem of scheduling in permutation flow shop with the objective of minimizing the maximum completion time, or makespan, is considered. A new ant colony optimization algorithm is developed for solving the problem. A novel mechanism is employed in initializing the pheromone trails based on an initial sequence. Moreover, the pheromone trail intensities are limited between lower and upper bounds which change dynamically. When a complete sequence of jobs is constructed by an artificial ant, a local search is performed to improve the performance quality of the solution. The proposed ant colony algorithm is applied to Taillard’s benchmark problems. Computational experiments suggest that the algorithm yields better results than well-known ant colony optimization algorithms available in the literature.     

Single-machine scheduling problems with deteriorating jobs and learning effects

In this paper, we introduce a new scheduling model in which deteriorating jobs and learning effect are both considered simultaneously. By deterioration and the learning effect, we mean that the actual processing time of a job depends not only on the processing time of the jobs already processed but also on its scheduled position. For the single-machine case, we show that the problems of makespan, total completion time and the sum of the quadratic job completion times remain polynomially solvable, respectively. In addition,we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain conditions.     

Minimizing makespan on a three-machine flowshop batch scheduling problem with transportation using genetic algorithm

This paper studies the minimization of makespan in a three-machine flowshop scheduling problem in which a batch processing machine is located between two single processing machines on first and third stages. In this study also transportation capacity and transportation among machines times are explicitly considered.We establish a mixed integer programming model and propose a heuristic algorithm based on the basic idea of Johnson's algorithm. Since the problem under study is NP-hard, a genetic algorithm is also proposed to minimize makespan. The effectiveness of our solution procedures is evaluated through computational experiments. The results obtained from the computational study have shown that the genetic algorithm is a viable and effective approach that is capable to produce consistently good results.     

Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs

This paper considers single machine scheduling problems with setup times and deteriorating jobs. The setup times are proportional to the length of the already processed jobs, that is, the setup times are past-sequence-dependent (p-s-d). It is assumed that the job processing times are defined by functions dependent on their starting times. The following objectives are considered: the makespan, the total completion time, and the sum of earliness, tardiness, and due-window starting time and size penalties. We propose polynomial time algorithms to solve these problems.     

Some scheduling problems with deteriorating jobs and learning effects

Although scheduling with deteriorating jobs and learning effect has been widely investigated, scheduling research has seldom considered the two phenomena simultaneously. However, job deterioration and learning co-exist in many realistic scheduling situations. In this paper, we introduce a new scheduling model in which both job deterioration and learning exist simultaneously. The actual processing time of a job depends not only on the processing times of the jobs already processed but also on its scheduled position. For the single-machine case, we derive polynomial-time optimal solutions for the problems to minimize makespan and total completion time. In addition, we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain agreeable conditions. For the case of an m-machine permutation flowshop, we present polynomial-time optimal solutions for some special cases of the problems to minimize makespan and total completion time.     

Scheduling a variable maintenance and linear deteriorating jobs on a single machine

We investigate a single machine scheduling problem in which the processing time of a job is a linear function of its starting time and a variable maintenance on the machine must be performed prior to a given deadline. The goals are to minimize the makespan and the total completion time. We prove that both problems are NP-hard. Furthermore, we show that there exists a fully polynomial time approximation scheme for the makespan minimization problem. For the total completion time minimization problem we point out that there exists a fully polynomial time approximation scheme for a special case.     

Single-machine group scheduling with both learning effects and deteriorating jobs

In the paper two resource constrained single-machine group scheduling problems with both learning effects and deteriorating jobs are considered. By learning effects, deteriorating jobs and group technology assumption, we mean that the processing time of a job is defined by the function of its starting time and position in the group, and the group setup times of a group is a positive strictly decreasing continuous function of the amount of consumed resource. We present polynomial solutions for the makespan minimization problem under the constraint that the total resource consumption does not exceed a given limit, and the total resource consumption minimization problem under the constraint that the makespan does not exceed a given limit, respectively.     

Flowshop scheduling of deteriorating jobs on dominating machines

In this paper we consider the general, no-wait and no-idle permutation flowshop scheduling problem with deteriorating jobs, i.e., jobs whose processing times are increasing functions of their starting times. We assume a linear deterioration function with identical increasing rates for all the jobs and there are some dominating relationships between the machines. We show that the problems to minimize the makespan and the total completion time remain polynomially solvable when deterioration is considered, although these problems are more complicated than their classical counterparts without deterioration.     

Minimizing the number of tardy jobs under piecewise-linear deterioration

In this paper, we consider a single machine scheduling problem with piecewise-linear deterioration where its objective is to minimize the number of tardy jobs, in which the processing time of each job depends on its starting time where all the jobs have a specific deterioration rate. The problem is known to be NP-hard; therefore a Branch and Bound algorithm and a heuristic algorithm with O(n²) are proposed. The proposed heuristic algorithm has been utilized for solving large scale problems and upper bound of the B&B algorithm. Computational experiments on 1840 problems demonstrate that the Branch and Bound procedure can solve problems with 28 jobs and 85.4% of all the sample problems optimally showing the high capability of the proposed procedure. Also it is shown that the average value of the ratio of optimal answer to the heuristic algorithm result with the objective ∑(1-_Ui)$\sum (1-U_i)$ is at last 1.08 which is more efficient in contrast to other proposed algorithms in related studies in the literature. According to high efficacy of the heuristic algorithm, large scale samples are also being solved and the results are presented. A specific form of this problem is also being considered and it is proven that the B&B procedure can handle problems with more jobs even up to 44 jobs.     

Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing

This paper aims at minimizing the makespan of two batch-processing machines in a flow shop. The processing times and the sizes of the jobs are known and non-identical. The machines can process a batch as long as its capacity is not exceeded. The processing time of a batch is the longest processing time among all the jobs in that batch. The problem under study is NP-hard for makespan objective. Consequently, a heuristic based on Johnson's algorithm and a simulated annealing (SA) algorithm is proposed. Random instances were generated to verify the effectiveness of the proposed approaches. The results obtained from SA were compared with the proposed heuristic and a commercial solver. The SA outperformed both the heuristic and the commercial solver. On larger problem instances, the heuristic outperformed the commercial solver.     

A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity

This note considers a single machine scheduling and due-window assignment problem, in which the processing time of a job is a linear function of its starting time and the job-independent deterioration rates are identical for all jobs. We allow an option for performing a rate-modifying activity for changing the normal processing times of the jobs following this activity. The objective is to schedule the jobs, the due-window and the rate-modifying activity so as to minimize the sum of earliness, tardiness and due-window starting time and due-window size costs. We introduce a polynomial solution for the problem.     

Heuristic algorithms for two machine re-entrant flow shop

This paper focuses on a two machine re-entrant flow shop scheduling problem with the objective of minimizing makespan. In the re-entrant flow shop considered here, each job has the processing route (M₁, M₂, M₁, M₂, …, M₁, M₂). We present heuristic algorithms, some are modified from existing algorithms and some are newly developed. Extensive computational experiments are performed to evaluate the performance of the heuristics. Results of the experiments show that the performance of heuristics is significantly affected by the distribution of workloads on machines and some of them are excellent.