Makespan minimization in the two-machine flowshop batch scheduling problem

T. C.E. Cheng*, Bertrand M.T. Lin, A. Toker

*Corresponding author for this work

研究成果: Article同行評審

49 引文 斯高帕斯(Scopus)


In this paper we consider a practical scheduling problem commonly arising from batch production in a flexible manufacturing environment. Different part-types are to be produced in a flexible manufacturing cell organized into a two-stage production line. The jobs are processed in batches on the first machine, and the completion time of a job is defined as the completion time of the batch containing it. When processing of all jobs in a batch is completed on the first machine, the whole batch of jobs is transferred intact to the second machine. A constant setup time is incurred whenever a batch is formed on any machine. The tradeoff between the setup times and batch processing times gives rise to the batch composition decision. The problem is to find the optimal batch composition and the optimal schedule of the batches so that the makespan is minimized. The problem is shown to be strongly NP-hard. We identify some special cases by introducing their corresponding solution methods. Heuristic algorithms are also proposed to derive approximate solutions. We conduct computational experiments to study the effectiveness of the proposed heuristics.

頁(從 - 到)128-144
期刊Naval Research Logistics
出版狀態Published - 31 一月 2000

指紋 深入研究「Makespan minimization in the two-machine flowshop batch scheduling problem」主題。共同形成了獨特的指紋。