A two-stage flow shop scheduling with a critical machine and batch availability

• Autorzy: Gerstl E. , Mosheiov G.
• Języki publikacji: EN

Abstrakty

EN

We study a two-stage flowshop, where each job is processed on the first (critical) machine, and then continues to one of two second-stage (dedicated) machines. We assume identical (but machine-dependent) job processing times. Jobs are processed on the critical machine in batches, and a setup time is required when starting a new batch. The setting assumes batch-availability, i.e., jobs become available for the second stage only when their entire batch is completed on the critical machine. We consider three objective functions: minimum makespan, minimum total load, and minimum weighted flow-time. Polynomial time dynamic programming algorithms are introduced, which are numerically shown to be able to solve problems of medium size in reasonable time. A heuristic for makespan minimization is presented and shown numerically to be both accurate and efficient.

Słowa kluczowe

EN

batch scheduling; makespan; Flowtime; total load; flow shop; Critical Machine; dynamic programming; heuristics

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2012
• Tom: Vol. 37, No. 1
• Strony: 39--56
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Gerstl E.

autor

Mosheiov G.

• Enrique Gerstl, School of Business Administration, The Hebrew University, Jerusalem, Israel

Bibliografia

• [1] Cheng T.C.E. and Kovalyov M. Y., An exact algorithm for batching and scheduling two part types in a mixed shop: A technical note, International Journal of Production Economics, 55, 1998, 53-56.
• [2] Cheng T.C.E., Kovalyov M.Y. and Chakhlevich K. N., Batching in a two-stage flowshop with dedicated machines in second stage. HE Transactions, 36, 2004, 87-93.
• [3] Cheng T.C.E., Lin B.M.T. and Tian Y., Scheduling of a two-stage differentiation flowshop to minimize weighted sum of machine completion times, Computers & Operations Research, 36, 2009, 3031-3040.
• [4] Ching C. Y., Liao, Wu C. J., Batching to minimize total production time for two part types, International Journal of Production Economics, 48, 1997, 63-72.
• [5] Drobouchevitch I. G., Strusevich V. A., Heuristics for the two-stage job shop scheduling problem with a bottleneck machine, European Journal of Operational Research, 123, 2000, 229-240.
• [6] Kyparisis G. J., Koulamas, C., Flow shop and open shop scheduling with a critical machine and two operations per job, European Journal of Operational Research, 127, 2000, 120-125.
• [7] Lin H.-T., Liao, C. -J., A case study in a two-stage hybrid flow shop with setup time and dedicated machines, International Journal of Production Economics, 86, 2003, 133-143.
• [8] Linn R., Zhang W., Hybrid flow shop scheduling: A survey, Computers & Industrial Engineering, 37,1999, 57-61.
• [9] Mosheiov G., Yovel U., Comments on "Flow shop and open shop scheduling with critical machine and two operations per job", European Journal of Operational Research, 157, 2004, 257-261.
• [10] Oguz C., Ercan, M. F., A Genetic Algorithm for Hybrid Flow-Shop Scheduling with Multiprocessor Tasks, Journal of Scheduling, 8, 2005, 323-351.
• [11] Ruiz, R., Vazquez-Rodriguez J.A., The hybrid flow shop scheduling problem, European Journal of Operational Research, 205,2010, 1-18.