×

A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems. (English) Zbl 1175.90199

Summary: This paper proposes a novel hybrid discrete differential evolution (HDDE) algorithm for solving blocking flow shop scheduling problems to minimize the maximum completion time (i.e., makespan). Firstly, in the algorithm, the individuals are represented as discrete job permutations, and new mutation and crossover operators are developed for this representation, so that the algorithm can directly work in the discrete domain. Secondly, a local search algorithm based on insert neighborhood structure is embedded in the algorithm to balance the exploration and exploitation by enhancing the local searching ability. In addition, a speed-up method to evaluate insert neighborhood is developed to improve the efficiency of the whole algorithm. Computational simulations and comparisons based on the well-known benchmark instances of E. Taillard [Eur. J. Oper. Res. 64, No. 2, 278–285 (1993; Zbl 0769.90052)], by treating them as blocking flow shop problem instances with makespan criterion, are provided. It is shown that the proposed HDDE algorithm not only generates better results than the existing tabu search (TS) and TS with multi-moves (TS+M) approaches proposed by J. Grabowski and J. Pempera [Omega 35, No. 3, 302–311 (2007)], but also outperforms the hybrid differential evolution (HDE) algorithm developed by B. Qian et al. [Comput. Oper. Res. 36, No. 1, 209–233 (2009; Zbl 1163.90507)] in terms of solution quality, robustness and search efficiency. Ultimately, 112 out of 120 best known solutions provided by Grabowski and Pempera [loc. cit.] and D. P. Ronconi [Ann. Oper. Res. 138, 53–65 (2005; Zbl 1091.90075)] are further improved by the proposed HDDE algorithm.

MSC:

90B35 Deterministic scheduling theory in operations research
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 278-285 (1993) · Zbl 0769.90052
[2] Grabowski, J.; Pempera, J., The permutation flow shop problem with blocking, A tabu search approach, 35, 302-311 (2007)
[3] Qian, B.; Wang, L.; Huang, D. X.; Wang, W. L.; Wang, X., An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers, Computers and operations research, 36, 1, 209-233 (2009) · Zbl 1163.90507
[4] Ronconi, D. P., A branch-and-bound algorithm to minimize the makespan in a flowshop problem with blocking, Annals of Operations Research, 138, 1, 53-65 (2005) · Zbl 1091.90075
[5] Pinedo, M., Scheduling: theory, algorithms and systems (2002), Prentice-Hall: Prentice-Hall NJ · Zbl 1145.90394
[6] Wang, L.; Zheng, D. Z., An effective hybrid heuristic for flow shop scheduling, International Journal of Advanced Manufacturing Technology, 21, 38-44 (2003)
[7] Pan, Q.-K.; Wang, L., No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm, International Journal of Advanced Manufacturing Technology, 39, 796-807 (2008)
[8] Pan, Q.-K.; Tasgetiren, M. F.; Liang, Y.-C., A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem, Computers and Operations Research, 35, 9, 2807-2839 (2008) · Zbl 1144.90393
[9] Ronconi, D. P., A note on constructive heuristics for the flowshop problem with blocking, International Journal of Production Economics, 87, 39-48 (2004)
[10] Grabowski, J.; Pempera, J., Sequencing of jobs in some production system, European Journal of Operational Research, 125, 535-550 (2000) · Zbl 0967.90045
[11] Hall, N. G.; Sriskandarajah, C., A survey of machine scheduling problems with blocking and no-wait in process, Operations Research, 44, 510-525 (1996) · Zbl 0864.90060
[12] Tonconi, D. P.; Henriques, L. R.S., Some heuristic algorithms for total tardiness minimization in a flowshop with blocking, OMEGA—International Journal of Management Science, 37, 2, 272-281 (2009)
[13] McCormich, S. T.; Pinedo, M. L.; Shenker, S.; Wolf, B., Sequencing in an assembly line with blocking to minimize cycle time, Operations Research, 37, 925-936 (1989) · Zbl 0689.90048
[14] Leisten, R., Flowshop sequencing problems with limited buffer storage, International Journal of Production Research, 28, 2085-2100 (1990) · Zbl 0707.90054
[15] Ronconi, D. P.; Armentano, V. A., Lower bounding schemes for flowshops with blocking in-process, Journal of the Operational Research Society, 52, 1289-1297 (2001) · Zbl 1181.90125
[16] Nawaz, M.; Enscore, E. E.J.; Ham, I., A heuristic algorithm for the m-machine, \(n\)-job flow shop sequencing problem, OMEGA—International Journal of Management Science, 11, 91-95 (1983)
[17] Abadi, I. N.K.; Hall, N. G.; Sriskandarajh, C., Minimizing cycle time in a blocking flowshop, Operations Research, 48, 177-180 (2000) · Zbl 1106.90334
[18] Caraffa, V.; Ianes, S.; Bagchi, T. P.; Sriskandarajah, C., Minimizing makespan in a blocking flowshop using genetic algorithms, International Journal of Production Economics, 70, 101-115 (2001)
[19] Storn, R.; Price, K., Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces, Journal of Global Optimization, 11, 341-359 (1997) · Zbl 0888.90135
[20] Chang, F. P.; Hwang, C., Design of digital PID controllers for continuous-time plants with integral performance criteria, Journal of the Chinese Institute of Chemical Engineers, 35, 683-696 (2004)
[21] Ilonen, J.; Kamarainen, J. K.; Lampinen, J., Differential evolution training algorithm for feed-forward neural networks, Neural Process Letters, 17, 93-105 (2003)
[22] Storn, R., Designing digital filters with differential evolution, (Corne, D.; Dorigo, M.; Glover, F., New ideas in optimization (1999), McGraw-Hill: McGraw-Hill London, UK)
[23] Ruzek, B.; Kvasnicka, M., Differential evolution in the earthquake hypocenter location, Pure and Applied Geophysics, 158, 667-693 (2001)
[24] Qian, B.; Wang, L.; Hu, R., A hybrid differential evolution for permutation flow-shop scheduling, International Journal of Advanced Manufacturing Technology, 38, 7-8, 757-777 (2008)
[25] Onwubolu, G. C.; Davendra, D., Scheduling flow shops using differential evolution algorithm, European Journal of Operational Research, 171, 2, 674-692 (2006) · Zbl 1090.90090
[26] Tasgetiren MF, Pan QK, Suganthan PN, Liang YC. A discrete differential evolution algorithm for the no-wait flowshop problem with total flowtime criterion. In: Proceedings of the 2007 IEEE symposium on computational intelligence in scheduling. p. 251-8.; Tasgetiren MF, Pan QK, Suganthan PN, Liang YC. A discrete differential evolution algorithm for the no-wait flowshop problem with total flowtime criterion. In: Proceedings of the 2007 IEEE symposium on computational intelligence in scheduling. p. 251-8.
[27] Tasgetiren, M. F.; Sevkli, M.; Liang, Y. C., A particle swarm optimization and differential algorithm for job shop scheduling problem, International Journal of Operations Research, 3, 120-135 (2006) · Zbl 1175.90194
[28] Qian, B.; Wang, L.; Huang, D. X.; Wang, X., An effective hybrid DE-based algorithm for flow shop scheduling with limited buffers, International Journal of Production Research, 36, 1, 209-233 (2009) · Zbl 1163.90507
[29] Pan, Q.-K.; Wang, L., A novel differential evolution algorithm for the no-idle permutation flow shop scheduling problems, European Journal of Industrial Engineering, 2, 3, 279-297 (2008)
[30] Pan Q-K, Tasgetiren MF, Liang Y-C. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. In: Proceedings of the Ninth annual conference on genetic and evolutionary computation, London, England; 2007. p. 126-33.; Pan Q-K, Tasgetiren MF, Liang Y-C. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. In: Proceedings of the Ninth annual conference on genetic and evolutionary computation, London, England; 2007. p. 126-33.
[31] Tasgetiren MF, Pan Q-K, Liang Y-C. A discrete particle swarm optimization algorithm for the generalized traveling salesman problem. In: Proceedings of the ninth annual conference on genetic and evolutionary computation, London, England; 2007. p. 158-67.; Tasgetiren MF, Pan Q-K, Liang Y-C. A discrete particle swarm optimization algorithm for the generalized traveling salesman problem. In: Proceedings of the ninth annual conference on genetic and evolutionary computation, London, England; 2007. p. 158-67.
[32] Grabowski, J.; Pempera, J., Some local search algorithms for no-wait flow-shop problem with makespan criterion, Computers and Operations Research, 32, 2197-2212 (2005) · Zbl 1068.90058
[33] Taillard, E., Some efficient heuristic methods for the flow shop sequencing problems, European Journal of Operational Research, 47, 65-74 (1990) · Zbl 0702.90043
[34] Smutncki C. A two-machine permutation flow shop scheduling problem with buffers. OR Spectrum; 1998.; Smutncki C. A two-machine permutation flow shop scheduling problem with buffers. OR Spectrum; 1998.
[35] Zhu, Q.-Y.; Qin, A. K.; Suganthan, P. N.; Huang, G.-B., Evolutionary extreme learning machine, Pattern Recognition, 38, 10, 1759-1763 (2005) · Zbl 1077.68791
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.