Minimizing makespan in a two-machine flowshop scheduling with batching and release time

This paper studies two-machine flowshop scheduling with batching and release time, whose objective is to minimize the makespan. We formulate the scheduling problem as a mixed integer programming model and show that it is a strongly NP-hard problem. We derive a lower bound and develop dynamic programming-based heuristic algorithms to solve the scheduling problem. Computational experiments are carried out to evaluate the performance of the heuristic algorithms. The numerical results show that some of the heuristic algorithms can indeed find effective solutions for the scheduling problem.     

Minimizing makespan on a two-machine re-entrant flowshop

This paper focuses on a two-machine re-entrant flowshop scheduling problem with the objective of minimizing makespan. In the re-entrant flowshop considered here, all jobs must be processed twice on each machine, that is, each job should be processed on machine 1, machine 2 and then machine 1 and machine 2. We develop dominance properties, lower bounds and heuristic algorithms for the problem, and use these to develop a branch and bound algorithm. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 200 jobs in a reasonable amount of CPU time.     

Minimizing makespan with multiple-orders-per-job in a two-machine flowshop

We investigate a new scheduling problem, multiple-orders-per-job (MOJ), in the context of a two-machine flowshop. Lower bounds for the makespan performance measure are provided for combinations of lot-processing and item-processing machines. An optimization model is presented that addresses both job formation and job sequencing. We define a heuristic to minimize the makespan for the MOJ problem for two-machine item-processing flowshops. The heuristic obtains solutions within 2% of a tight lower bound and runs in O(HF) time, where H is the number of orders and F is the restricted number of jobs.     

Minimizing the makespan in a two-machine cross-docking flow shop problem

This paper studies a two-machine cross-docking flow shop scheduling problem in which a job at the second machine can be processed only after the processing of some jobs at the first machine has been completed. The objective is to minimize the makespan. We first show that the problem is strongly NP-hard. Some polynomially solvable special cases are provided. We then develop a polynomial approximation algorithm with an error-bound analysis. A branch-and-bound algorithm is also constructed. Computational results show that the branch-and-bound algorithm can optimally solve problems with up to 60 jobs within a reasonable amount of time.     

A bi-criteria two-machine flowshop scheduling problem with a learning effect

This paper addresses a bi-criteria two-machine flowshop scheduling problem when the learning effect is present. The objective is to find a sequence that minimizes a weighted sum of the total completion time and the maximum tardiness. In this article, a branch-and-bound method, incorporating several dominance properties and a lower bound, is presented to search for the exact solution for small job-size problems. In addition, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm for large job-size problems. Finally, computational results for this problem are provided to evaluate the performance of the proposed algorithms.     

Minimizing total tardiness on a two-machine re-entrant flowshop

We present a branch and bound algorithm for a two-machine re-entrant flowshop scheduling problem with the objective of minimizing total tardiness. In the re-entrant flowshop considered here, all jobs must be processed twice on each machine, that is, each job should be processed on machine 1, machine 2 and then machine 1 and machine 2. By regarding a job as a pair of sub-jobs, each of which represents a pass through the two machines, we develop dominance properties, a lower bound and heuristic algorithms for the problem, and use these to develop a branch and bound algorithm. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems and results are reported. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 20 sub-jobs in a reasonable amount of CPU time, and the average percentage gap of the heuristic solutions is about 13%.     

Bicriterion scheduling in the two-machine flowshop

Bicriterion scheduling problems have attracted the attention of many researchers, especially in the past decade. Although more than fifty papers have been published on this topic, most studies done so far focus only on a single machine. In this paper, we extend the development to the two-machine case and present algorithms for the bicriterion of minimising makespan and number of tardy jobs and of makespan and total tardiness. Computational results are also presented.     

A two-machine flowshop scheduling problem with a truncated sum of processing-times-based learning function

Scheduling with learning effects has received continuing attention in the recent days. However, it can be found that the actual processing time of a given job drops to zero precipitously as the job has a big processing time or the number of jobs increases. Moreover, most researchers paid more attention to single-machine settings, and the flowshop settings then are relatively unexplored. Motivated by these observations, we consider a two-machine total completion time flowshop problem in which the actual job processing time is a function depending on the jobs that have already been processed and a control parameter. In this paper, we develop a branch-and-bound and a genetic heuristic-based algorithm for the problem. In addition, the experimental results of all proposed algorithms are also provided.     

A branch-and-bound algorithm for a two-machine flowshop scheduling problem with limited waiting time constraints

In this paper, we consider a two-machine flowshop scheduling problem in which the waiting time of each job between the two machines cannot be greater than a certain time period. For the problem with the objective of minimizing makespan, we identify several dominance properties of the problem and develop a branch-and-bound (B&B) algorithm using the dominance properties. Computational tests are performed on randomly generated test problems for evaluation of performance of the B&B algorithm, and results show that the algorithm can solve problems with up to 150 jobs in a reasonable amount of CPU time.     

Minimizing makespan in a two-machine flow shop with effects of deterioration and learning

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 makespan. Several dominance properties and two lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm proposed to solve the problem. Two heuristic algorithms are also proposed to obtain near-optimal solutions. Computational results are presented to evaluate the performance of the proposed algorithms.     

Single-machine and two-machine flowshop scheduling with general learning functions

We show that the O(n log n) (where n is the number of jobs) shortest processing time (SPT) sequence is optimal for the single-machine makespan and total completion time minimization problems when learning is expressed as a function of the sum of the processing times of the already processed jobs. We then show that the two-machine flowshop makespan and total completion time minimization problems are solvable by the SPT sequencing rule when the job processing times are ordered and job-position-based learning is in effect. Finally, we show that when the more specialized proportional job processing times are in place, then our flowshop results apply also in the more general sum-of-job-processing-times-based learning environment.     

Minimizing the total completion time in a two-machine flowshop with sequence-independent setup times

We consider the problem of minimizing the sum of completion times in a two-machine permutation flowshop subject to setup times. We propose a new priority rule, several constructive heuristics, local search procedures, as well as an effective multiple crossover genetic algorithm. Computational experiments carried out on a large set of randomly generated instances provide evidence that a constructive heuristic based on newly derived priority rule dominates all the proposed constructive heuristics. More specifically, we show that one of our proposed constructive heuristics outperforms the best constructive heuristic in the literature in terms of both error and computational time. Furthermore, we show that one of our proposed local search-based heuristics outperforms the best local search heuristic in the literature in terms of again both error and computational time. We also show that, in terms of quality-to-CPU time ratio, the multiple crossover genetic algorithm performs consistently well.     

The two-machine flowshop scheduling problem with sequence-independent setup times: New lower bounding strategies

The two-machine flowshop environment with sequence-independent setup times has been intensely investigated both from theoretical and practical perspectives in the scheduling literature. Nevertheless, very scant attention has been devoted to deriving effective lower bounding strategies. In this paper, we propose new lower bounds for the total completion time minimization criterion. These bounds are based on three relaxation schemes, namely the waiting time-based relaxation scheme, the single machine-based relaxation scheme, and the Lagrangian relaxation scheme. Extensive computational study carried on instances with up to 500 jobs reveals that embedding the waiting time-based bounding strategy within the Lagrangian relaxation framework yields the best performance while requiring negligible CPU time.     

Minimizing the makespan in a 2-machine flowshop with time lags and setup conditions

A special case of the flowshop problem of sequencingn jobs on two machines, to minimize the makespan, is solved under setup considerations and with time lags.

---

Zusammenfassung In dieser Arbeit wird die Minimierung der Fertigstellungsdauer vonn Aufträgen auf 2 Maschinen behandelt, wobei auch Umrüstzeiten für die Maschinen und Aufbereitungszeiten für die Aufträge in Betracht gezogen werden.

     

Approximability of two-machine no-wait flowshop scheduling with availability constraints

We consider in this paper the two-machine no-wait flowshop scheduling problem in which each machine may have an unavailable interval. We present a polynomial time approximation scheme for the problem when the unavailable interval is imposed on only one machine, or the unavailable intervals on the two machines overlap.     

Minimizing makespan in a two-stage hybrid flow shop scheduling problem with open shop in one stage

This paper considers a scheduling problem in two-stage hybrid flow shop, where the first stage consists of two machines formed an open shop and the other stage has only one machine. The objective is to minimize the makespan, i.e., the maximum completion time of all jobs. We first show the problem is NP-hard in the strong sense, then we present two heuristics to solve the problem. Computational experiments show that the combined algorithm of the two heuristics performs well on randomly generated problem instances.     

Single-machine and two-machine flowshop scheduling problems with truncated position-based learning functions

Scheduling with learning effects has received growing attention nowadays. A well-known learning model is called ‘position-based learning’ in which the actual processing time of a job is a non-increasing function of its position to be processed. However, the actual processing time of a given job drops to zero precipitously as the number of jobs increases. Motivated by this observation, we propose two truncated learning models in single-machine scheduling problems and two-machine flowshop scheduling problems with ordered job processing times, respectively, where the actual processing time of a job is a function of its position and a control parameter. Under the proposed learning models, we show that some scheduling problems can be solved in polynomial time. In addition, we further analyse the worst-case error bounds for the problems to minimize the total weighted completion time, discounted total weighted completion time and maximum lateness.     

Minimization of the makespan in a two-machine problem under given resource constraints

In the paper the classical two-machine flow-shop problem was generalized to the case when job processing times may be reduced linearly by the application of a limited, continuously divisible resource, e.g. financial outlay, energy, fuel, catalyzer etc. It is proved that the decision form of this problem is NP-complete even for the fixed job processing times on one of the machines and identical job reduction rates on another. Some polynomially solvable cases of the problem are identified. Four simple and modified approximate algorithms are presented together with their worst case and experimental analysis. Also, a fast exact algorithm of the branch and bound type based on the shown elimination properties of the problem considered is presented. Some computational results and generalizations (e.g. bicriterial approach) are included as well.