Improved bounded dynamic programming algorithm for solving the blocking flow shop problem. (English) Zbl 07024038
Summary: In this paper, the blocking flow shop problem is considered. An exact algorithm for solving the blocking flow shop problem is developed by means of the bounded dynamic programming approach. The proposed algorithm is tested on several well-known benchmark instances. Computational results show that the presented algorithm outperforms all the state-of-the-art exact algorithms known to the author. Additionally, the optimality is proven for 26 previously open instances. Furthermore, we provide new lower bounds for several benchmark problem sets of Taillard requiring a relatively short CPU time.
MSC:
| 90Bxx | Operations research and management science |
References:
| [1] | Bautista J, Cano A, Companys R, Ribas I (2012) Solving the \[Fm|block|CmaxFm\]|block|Cmax problem using bounded dynamic programming. Eng Appl Artif Intell 25(6):1235-1245 · doi:10.1016/j.engappai.2011.09.001 |
| [2] | Companys R, Mateo M (2007) Different behaviour of a double branch-and-bound algorithm on \[Fm|prmu|CmaxFm\]|prmu|Cmax and \[Fm|block|CmaxFm\]|block|Cmax problems. Comput Oper Res 34(4):938-953 · Zbl 1107.90016 · doi:10.1016/j.cor.2005.05.018 |
| [3] | Companys R, Ribas I (2011) New insights on the blocking flow shop problem. Best solutions update. Tech. rep., working paper |
| [4] | Gilmore P, Gomory R (1964) Sequencing a one state-variable machine: a solvable case of the traveling salesman problem. Oper Res 12(5):655-679 · Zbl 0126.36006 · doi:10.1287/opre.12.5.655 |
| [5] | Grabowski J, Pempera J (2007) The permutation flow shop problem with blocking. A tabu search approach. Omega 35(3):302-311 |
| [6] | Gromicho J, Van Hoorn J, Saldanha-da Gama F, Timmer G (2012) Solving the job-shop scheduling problem optimally by dynamic programming. Comput Oper Res 39(12):2968-2977 · Zbl 1349.90348 · doi:10.1016/j.cor.2012.02.024 |
| [7] | Hall N, Sriskandarajah C (1996) A survey of machine scheduling problems with blocking and no-wait in process. Oper res 44(3):510-525 · Zbl 0864.90060 · doi:10.1287/opre.44.3.510 |
| [8] | Heller J (1960) Some numerical experiments for an \[M\times J\] M×J flow shop and its decision-theoretical aspects. Oper Res 8(2):178-184 · Zbl 0092.27910 · doi:10.1287/opre.8.2.178 |
| [9] | Lenstra J, Rinnooy Kan A, Brucker P (1977) Complexity of machine scheduling problems. Ann Discrec Math 1:343-362 · Zbl 0353.68067 · doi:10.1016/S0167-5060(08)70743-X |
| [10] | Lin S, Ying K (2013) Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm. Omega 41(2):383-389 · doi:10.1016/j.omega.2012.03.006 |
| [11] | Pan Q, Wang L, Sang H, Li J, Liu M (2013) A high performing memetic algorithm for the flowshop scheduling problem with blocking. IEEE Trans Auto Sci Eng 10(3):741-756 · doi:10.1109/TASE.2012.2219860 |
| [12] | Papadimitriou C, Kanellakis P (1980) Flowshop scheduling with limited temporary storage. J ACM (JACM) 27(3):533-549 · Zbl 0475.68014 · doi:10.1145/322203.322213 |
| [13] | Reddi S, Ramamoorthy C (1972) On the flow-shop sequencing problem with no wait in process. Oper Res Quart pp 323-331 · Zbl 0238.90080 |
| [14] | Reeves C (1995) A genetic algorithm for flowshop sequencing. Comput Oper Res 22(1):5-13 · Zbl 0815.90097 · doi:10.1016/0305-0548(93)E0014-K |
| [15] | Ribas I, Companys R, Tort-Martorell X (2011) An iterated greedy algorithm for the flowshop scheduling problem with blocking. Omega 39(3):293-301 · doi:10.1016/j.omega.2010.07.007 |
| [16] | Ronconi D (2005) A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking. Ann Oper Res 138(1):53-65 · Zbl 1091.90075 · doi:10.1007/s10479-005-2444-3 |
| [17] | Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64(2):278-285 · Zbl 0769.90052 · doi:10.1016/0377-2217(93)90182-M |
| [18] | Tasgetiren M, Pan Q, Suganthan P, Buyukdagli O (2013) A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem. Comput Oper Res 40(7):1729-1743 · Zbl 1348.90316 · doi:10.1016/j.cor.2013.01.005 |
| [19] | Tasgetiren M, Pan Q, Kizilay D, Suer G (2015) A populated local search with differential evolution for blocking flowshop scheduling problem. In: 2015 IEEE Congress on Evolutionary Computation (CEC), pp 2789-2796 |
| [20] | Tasgetiren M, Kizilay D, Pan Q, Suganthan P (2017) Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion. Comput Oper Res 77:111-126 · Zbl 1391.90323 · doi:10.1016/j.cor.2016.07.002 |
| [21] | van Hoorn JJ (2016) Dynamic programming for routing and scheduling: Optimizing sequences of decisions |
| [22] | van Hoorn JJ, Nogueira A, Ojea I, Gromicho JA (2016) An corrigendum on the paper: solving the job-shop scheduling problem optimally by dynamic programming. Comput Oper Res · Zbl 1391.90335 |
| [23] | Wang L, Pan Q, Suganthan P, Wang W, Wang Y (2010) A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems. Comput Oper Res 37(3):509-520 · Zbl 1175.90199 · doi:10.1016/j.cor.2008.12.004 |
| [24] | Zhang C, Xie Z, Shao X, Tian G (2015) An effective VNSSA algorithm for the blocking flowshop scheduling problem with makespan minimization. In: 2015 International Conference on Advanced Mechatronic Systems (ICAMechS), IEEE, pp 86-89 |
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.
