A two-stage flow shop scheduling problem with transportation considerations. (English) Zbl 1328.90046
Summary: This paper considers a two-stage robotic flow shop scheduling problem of which the objective is to minimize the maximum completion time of all the jobs. The problem consists of two dedicated machines at the first stage and a single machine at the second stage. Each job is defined by two operations processed in series on two stages. Depending on the job type, each job is processed on a dedicated machine at the first stage, and is then transported, by a robot or a conveyor, to be processed on a single machine at the second stage. To tackle the problem, a mixed integer programming model is proposed, which is solved by CPLEX. This model is improved using valid inequalities based on three lower bounds. In addition, we establish the complexity of several variations of the problem and we identify special cases that can be solved in polynomial time. Furthermore due to the NP-hardness of the problem, two heuristics are proposed to solve approximately large-sized problems. The results indicate that the solutions obtained are of high quality and the corresponding CPU time is acceptable.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C11 | Mixed integer programming |
Software:
CPLEXReferences:
| [1] | Ahmadizar F, Shahmaleki P (2014) Group shop scheduling with sequence-dependent setup and transportation times. Appl Math Model 38(21):5080-5091 · Zbl 1428.90066 · doi:10.1016/j.apm.2014.03.035 |
| [2] | Behnamian J, Fatemi Ghomi S, Jolai F, Amirtaheri O (2012) Realistic two-stage flowshop batch scheduling problems with transportation capacity and times. Appl Math Model 36(2):723-735 · Zbl 1236.90049 · doi:10.1016/j.apm.2011.07.011 |
| [3] | Centeno G, Armacost RL (2004) Minimizing makespan on parallel machines with release time and machine eligibility restrictions. Int J Prod Res 42(6):1243-1256 · Zbl 1176.90155 · doi:10.1080/00207540310001631584 |
| [4] | Chikhi N, Abbas M, Bekrar A, Benmansour R, Hanafi S (2014) On the complexity of robotic flow shop with transportation constraints. In: ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision, Bordeaux, France · Zbl 1328.90046 |
| [5] | Elmi A, Topaloglu S (2013) A scheduling problem in blocking hybrid flow shop robotic cells with multiple robots. Comput Oper Res 40(10):2543-2555 · Zbl 1348.90254 · doi:10.1016/j.cor.2013.01.024 |
| [6] | Graham RL, Lawler EL, Lenstra JK, Kan A (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287-326 · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [7] | Gupta JN (1988) Two-stage, hybrid flowshop scheduling problem. J Oper Res Soc 39(4):359-364 · Zbl 0639.90049 · doi:10.1057/jors.1988.63 |
| [8] | Hurink J, Knust S (2001) Makespan minimization for flow-shop problems with transportation times and a single robot. Discrete Appl Math 112(1):199-216 · Zbl 0990.90041 · doi:10.1016/S0166-218X(00)00316-4 |
| [9] | Hwang H-C, Chang SY, Lee K (2004) Parallel machine scheduling under a grade of service provision. Comput Oper Res 31(12):2055-2061 · Zbl 1074.68529 · doi:10.1016/S0305-0548(03)00164-3 |
| [10] | Kise H (1991) On an automated two-machine flowshop scheduling problem with infinite buffer. J Oper Res Soc Japan 34(3):354-361 · Zbl 0747.90048 |
| [11] | Lee CY, Chen ZL (2001) Machine scheduling with transportation considerations. J Sched 4(3):24 · Zbl 0979.90055 |
| [12] | Levner E, Kogan K, Levin I (1995) Scheduling a two-machine robotic cell: a solvable case. Ann Oper Res 57(1):217-232 · Zbl 0831.90075 · doi:10.1007/BF02099699 |
| [13] | Lin BM (1999) The strong np-hardness of two-stage flowshop scheduling with a common second-stage machine. Comput Oper Res 26(7):695-698 · Zbl 0957.90062 · doi:10.1016/S0305-0548(98)00080-X |
| [14] | Maggu PL, Das G, Kumar R (1981) On equivalent-job for job-block in \[2\times \]× n sequencing problem with transportation-times. J Oper Res Soc Japan 24(2):136-146 · Zbl 0459.90033 |
| [15] | Oĝuz C, Lin BM, Edwin Cheng T (1997) Two-stage flowshop scheduling with a common second-stage machine. Computers & Operations Research 24(12):1169-1174 · Zbl 0883.90067 |
| [16] | Panwalkar S (1991) Scheduling of a two-machine flowshop with travel time between machines. J Oper Res Soc 42(7):609-613 · Zbl 0727.90037 · doi:10.1057/jors.1991.121 |
| [17] | Riane F, Artiba A, Elmaghraby SE (2002) Sequencing a hybrid two-stage flowshop with dedicated machines. Int J Prod Res 40(17):4353-4380 · Zbl 1064.90545 · doi:10.1080/00207540210159536 |
| [18] | Tang L, Liu P (2009) Two-machine flowshop scheduling problems involving a batching machine with transportation or deterioration consideration. Appl Math Model 33(2):1187-1199 · Zbl 1168.90473 · doi:10.1016/j.apm.2008.01.013 |
| [19] | Wang S, Liu M (2013) A heuristic method for two-stage hybrid flow shop with dedicated machines. Comput Oper Res 40(1):438-450 · Zbl 1349.90413 · doi:10.1016/j.cor.2012.07.015 |
| [20] | Yang J (2013) A two-stage hybrid flow shop with dedicated machines at the first stage. Comput Oper Res 40(12):2836-2843 · Zbl 1348.90332 · doi:10.1016/j.cor.2013.05.020 |
| [21] | Yao FS, Zhao M, Zhang H (2012) Two-stage hybrid flow shop scheduling with dynamic job arrivals. Comput Oper Res 39(7):1701-1712 · Zbl 1251.90203 · doi:10.1016/j.cor.2011.10.006 |
| [22] | Zhong W-Y, Lv L-H (2014) Hybrid flowshop scheduling with interstage job transportation. J Oper Res Soc China 2(1):109-121 · Zbl 1308.90158 · doi:10.1007/s40305-014-0040-4 |
| [23] | Zhu H (2012) A two stage scheduling with transportation and batching. Inf Process Lett 112(19):728-731 · Zbl 1248.68227 · doi:10.1016/j.ipl.2012.06.013 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
