Batch scheduling in a two-stage flexible flow shop problem

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

Abstrakty

EN

We study a special two-stage flexible flowshop, which consists of several parallel identical machines in the first stage and a single machine in the second stage. We assume identical jobs, and the option of batching, with a required setup time prior to the processing of a new batch. We also consider the option to use only a subset of the available machines. The objective is minimum makespan. A unique optimal solution is introduced, containing the optimal number of machines to be used, the sequence of batch sizes, and the batch schedule. The running time of our proposed solution algorithm is independent of the number of jobs, and linear in the number of machines.

Słowa kluczowe

EN

Deterministic Scheduling; flexible flow shop; Batch Scheduling

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2014
• Tom: Vol. 39, No. 1
• Strony: 3--16
• Opis fizyczny: Bibliogr. 25, poz., rys.

Twórcy

autor

Gerstl E.

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

autor

Mosheiov G.

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

autor

Sarig A.

• The Center for Academics Studies, Or Yehuda, Israel

Bibliografia

• [1] Allahverdi, A., Ng, C.T., Cheng, T.C.E., Kovalyov, M.Y., A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187, 2008, 985-1032.
• [2] Baptiste, P., Brucker, P., Scheduling equal processing time jobs. In: Leung J.Y.T. (Ed.), Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman & HALL/CRC, 2004.
• [3] Cao, D., Chen, M., Wan, G., Parallel machine selection and job scheduling to minimize machine cost and job tardiness, Computers & Operations Research, 32, 2005, 1995-2012.
• [4] Chen, Z.L., Li, C.L., Scheduling with subcontracting options. IIE Transactions, 40, 2008, 1171-1184.
• [5] Cheng, T.C.E., 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.
• [6] Cheng, T.C.E., Kovalyov, M.Y., Chakhlevich, K.N., Batching in a two-stage flowshop with dedicated machines in second stage. IIE Transactions, 36, 2004, 87-93.
• [7] Fanjul-Peyro, L., Ruiz, R., Scheduling unrelated parallel machines with optional machines and jobs selection, Computers and Operational Research, 39, 2012, 1745-1753.
• [8] Finke, G., Lemaire, P., Proth, J. M., Queyranne, M., Minimizing the number of machines for minimum length schedules, European Journal of Operational Research, 199, 2009, 702-705.
• [9] Gerstl, E., Mosheiov, G., A two-stage flow shop scheduling with a critical machine and batch availability, Foundations of Computing and Decision Sciences, 37, 2012, 39-56.
• [10] Gerstl, E., Mosheiov, G., The optimal number of used machines in a two-stage flexible flowshop scheduling problem, Journal of Scheduling, 2013, DOI 10.1007/s10951-013-0343-z.
• [11] Hoogeveen J.A., Lenstra, J.K., Veltman, B., Preemptive scheduling in a two-stage multi-processor flow-shop is NP-hard, European Journal of Operational Research, 89, 1996, 172-175.
• [12] Kravchenko, S.A., Werner, F., Minimizing the number of machines for scheduling jobs with equal processing times, European Journal of Operational Research, 199, 2009, 595-600.
• [13] Kravchenko, S.A., Werner, F., Parallel machine problems with equal processing times: a survey, Journal of Scheduling, 14, 2011, 435-444.
• [14] 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.
• [15] Lee C.-Y., Vairaktarakis, G.L., Performance comparison of some classes of flexible flowshops and jobshops, The International Journal of Flexible Manufacturing Systems, 10, 1998, 379-405.
• [16] Lin, M.T.B., The strong NP-hardness of two-stage flowshop scheduling with common second-stage machine. Computers and Operations Research, 26, 1999, 695-69.
• [17] 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.
• [18] Monma, C.L., Potts, C.N., On the complexity of scheduling with batch setup times.Operations Research, 37, 1989, 789-804.
• [19] Mosheiov, G., Oron, D., A note on flow-shop and job-shop batch scheduling with identical processing-time jobs, European Journal of Operational Research, 161, 2005, 285-291.
• [20] Mosheiov, G., Oron, D., Ritov, Y., Minimizing flowtime on a single machine with integer batch sizes, Operations Research Letters, 33, 2005, 497-501.
• [21] 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.
• [22] Oguz, C., Ercan, M.F., A Genetic Algorithm for Hybrid Flow-Shop Scheduling with Multiprocessor Tasks, Journal of Scheduling, 8, 2005, 323-351.
• [23] Oguz, C., Lin, M.T.B., Cheng, T. C. E., Two-stage scheduling with a common secondstage machine, Computers and Operations Research, 24, 1997, 1169-1174.
• [24] Pinedo, M., Scheduling: Theory, Algorithms, and Systems. Prentice-Hall, 1995.
• [25] Ruiz, R., Vazquez-Rodriguez, J.A., The hybrid flow shop scheduling problem, European Journal of Operational Research, 205, 2010, 1-18.