Scheduling flowshops with limited in-process wait

The flowshop problem has been studied for decades since Johnson published his two-machine and three-machine optimal algorithms in 1954. The static deterministic permutation flowshop problem is one of scheduling N jobs in a shop containing M machines, where each job with fixed processing times has to be processed on every machine, each job is processed on one machine at a time without preemption, and each job follows the same ordering of machines as it is processed. The above flowshop problem is identified as the conventional flowshop problem. This research involves the problem of scheduling a new static deterministic permutation flowshop in which, after processing on a machine, each job has to be processed by the next machine before an allowable waiting time is passed. The objective is to minimize the makespan. This new flowshop problem is identified as the limited in-process wait flowshop problem.

The flowshop scheduling problem in this study is found to be NP-complete. A branch and bound algorithm based on a composite bound is presented, and 18 heuristic algorithms are proposed. The heuristics are compared by the nonparametric Friedman test in terms of makespan, average job waiting time, and CPU time consumed, and a sensitivity analysis on the relative performance of the heuristics is conducted.

The research shows that the heuristics which use simulated annealing or tabu search technique usually have the best performance in minimizing the makespan, but the disadvantage is that large computation efforts are necessary.