Minimizing makespan in a three-stage hybrid flow shop with dedicated machines

Abstract: In recent years, many studies on scheduling problems with dedicated machines have been carried out. But, few of them have considered the case of more than two stages. This paper aims at filling this gap by addressing the three-stage hybrid flow shop scheduling problem with two dedicated machines in stage 3. Each job must be processed, consecutively, on the single machines of stages 1 and 2, and depending on its type, it will be further processed on one of the two dedicated machines of stage 3. The objective is to find an optimal schedule that minimizes the maximum completion time (makespan). Since this problem is strongly NP-hard, we first provide some basic results including solutions for several variations of the problem. Then, for the general case we adapt a set of lower bounds from the literature and propose a heuristic approach that is based on the dynamic programming technique, which uses a local search procedure. Finally, various experimentations on several problems with different sizes are conducted and the computational results of the heuristic show that the mean percentage deviation value from the lower bound was lower than 0.8 percent for some instances with 40 to 200 jobs in size.

How to cite this paper

 bedhief, A & Dridi, N. (2019). Minimizing makespan in a three-stage hybrid flow shop with dedicated machines.International Journal of Industrial Engineering Computations , 10(2), 161-176.

Refrences

Campbell, H. G., Dudek, R. A., & Smith, M. L. (1970). A heuristic algorithm for the n job, m machine sequencing problem. Management science, 16(10), B-630.
Chen, B., Glass, C. A., Potts, C. N., & Strusevich, V. A. (1996). A new heuristic for three-machine flow shop scheduling. Operations Research, 44(6), 891-898.
Cheng, T. E., Lin, B. M., & Tian, Y. (2009). Scheduling of a two-stage differentiation flowshop to minimize weighted sum of machine completion times. Computers & Operations Research, 36(11), 3031-3040.
Conway, R. W., Maxwell, W. L., & Miller, L. W. (2003). Theory of scheduling. Courier Corporation.
Dridi, N., Hadda, H., & Hajri-Gabouj, S. (2009). Méthode heuristique pour le problème de flow shop hybride avec machines dédiées. RAIRO-Operations Research, 43(4), 421-436.
Fattahi, P., Hosseini, S. M. H., Jolai, F., & Tavakkoli-Moghaddam, R. (2014). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations. Applied Mathematical Modelling, 38(1), 119-134.
Framinan, J. M., Gupta, J. N., & Leisten, R. (2004). A review and classification of heuristics for permutation flow-shop scheduling with makespan objective. Journal of the Operational Research Society, 55(12), 1243-1255.
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117-129.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287-326.
Gupta, J. N. (1971). A functional heuristic algorithm for the flowshop scheduling problem. Journal of the Operational Research Society, 22(1), 39-47.
Gupta, J. N. (1988). Two-stage, hybrid flowshop scheduling problem. Journal of the Operational Research Society, 39(4), 359-364.
Gupta, J. N., Hariri, A. M. A., & Potts, C. N. (1997). Scheduling a two-stage hybrid flow shop with parallel machines at the first stage. Annals of Operations Research, 69, 171-191.
Gupta, J. N., & Stafford Jr, E. F. (2006). Flowshop scheduling research after five decades. European Journal of Operational Research, 169(3), 699-711.
Hadda, H., Dridi, N., & Hajri-Gabouj, S. (2012). A note on the two-stage hybrid flow shop problem with dedicated machines. Optimization Letters, 6(8), 1731-1736.
Hadda, H., Dridi, N., & Hajri-Gabouj, S. (2014). Exact resolution of the two-stage hybrid flow shop with dedicated machines. Optimization Letters, 8(8), 2329-2339.
Hadda, H., Hajji, M. K., & Dridi, N. (2015). On the two-stage hybrid flow shop with dedicated machines. RAIRO-Operations Research, 49(4), 795-804.
Haouari, M., & Daouas, T. (1999). Optimal scheduling of the 3-machine assembly-type flow shop. RAIRO-Operations Research, 33(4), 439-445.
Huang, T. C., & Lin, B. M. (2013). Batch scheduling in differentiation flow shops for makespan minimisation. International Journal of Production Research, 51(17), 5073-5082.
Kise, H. (1991). On an automated two-machine flowshop scheduling problem with infinite buffer. Journal of the Operations Research Society of Japan, 34(3), 354-361.
Koulamas, C., & Kyparisis, G. J. (2001). The three-stage assembly flowshop scheduling problem. Computers & Operations Research, 28(7), 689-704.
Johnson, S. M. (1954). Optimal two‐and three‐stage production schedules with setup times included. Naval research logistics quarterly, 1(1), 61-68.
Lee, C. Y., Cheng, T. C. E., & Lin, B. M. T. (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Management Science, 39(5), 616-625.
Lin, B. M. (1999). The strong NP-hardness of two-stage flowshop scheduling with a common second-stage machine. Computers & Operations Research, 26(7), 695-698.
Lin, B.M.T. (2015). Two-stage flow shop scheduling with dedicated machines. International Journal of Production Research, 53(4), 1094–1097.
Lin, H. T., & Liao, C. J. (2003). A case study in a two-stage hybrid flow shop with setup time and dedicated machines. International Journal of Production Economics, 86(2), 133-143.
Linn, R., & Zhang, W. (1999). Hybrid flow shop scheduling: a survey. Computers & Industrial Engineering, 37(1-2), 57-61.
Mosheiov, G., & Sarig, A. (2010). Minimum weighted number of tardy jobs on an m-machine flow-shop with a critical machine. European Journal of Operational Research, 201(2), 404-408.
Nawaz, M., Enscore Jr, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.
Oguz, C, Lin, B. M. T., & Cheng, T. C. E. (1997). Two-stage flow shop scheduling problem with a common second-stage machine. Computers & Operations Research 24, 1169–1174.
Palmer, D. S. (1965). Sequencing jobs through a multi-stage process in the minimum total time—a quick method of obtaining a near optimum. Journal of the Operational Research Society, 16(1), 101-107.
Potts, C. N., Sevast'Janov, S. V., Strusevich, V. A., Van Wassenhove, L. N., & Zwaneveld, C. M. (1995). The two-stage assembly scheduling problem: complexity and approximation. Operations Research, 43(2), 346-355.
Riane, F., Artiba, A., and Elmaghraby, S. E. (1997). A two-stage hybrid flow shop problem to minimize makespan. Research Report No 310-97WR214, FUCaM, Mons, Belgium.
Riane, F., Artiba, A., & Elmaghraby, S. E. (1998). A hybrid three-stage flow shop problem: Efficient heuristics to minimize makespan. European Journal of Operational Research 109(2), 321–329.
Riane, F., Artiba, A., & Elmaghraby, S. E. (2002). Sequencing a hybrid two-stage flowshop with dedicated machines. International Journal of Production Research, 40(17), 4353-4380.
Ruiz, R., & Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2), 479-494.
Ruiz, R., & Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European Journal of Operational Research, 205(1), 1-18.
Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47(1), 65-74.
Wang, S., & Liu, M. (2013). A heuristic method for two-stage hybrid flow shop with dedicated machines. Computers & Operations Research, 40(1), 438-450.
Yang, J. (2011). Minimizing total completion time in two-stage hybrid flow shop with dedicated machines. Computers and Operations Research, 38, 1045–53.
Yang, J. (2013). A two-stage hybrid flow shop with dedicated machines at the first stage. Computers & Operation Research, 40, 2836–2843.
Yang J. (2015). Minimizing total completion time in two-stage hybrid flow shop with dedicated machines at the first stage. Computers & Operations Research, 58, 1–8
Yenisey, M. M., & Yagmahan, B. (2014). Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends. Omega, 45, 119-135.
Yokoyama, M., & Santos, D. L. (2005). Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times. European Journal of Operational Research, 161(3), 754-770.