A hybrid differential evolution and tree search algorithm for the job shop scheduling problem.

*(English)*Zbl 1235.90068Summary: The job shop scheduling problem (JSSP) is a notoriously difficult problem in combinatorial optimization. In terms of the objective function, most existing research has been focused on the makespan criterion. However, in contemporary manufacturing systems, due-date-related performances are more important because they are essential for maintaining a high service reputation. Therefore, in this study we aim at minimizing the total weighted tardiness in JSSP. Considering the high complexity, a hybrid differential evolution (DE) algorithm is proposed for the problem. To enhance the overall search efficiency, a neighborhood property of the problem is discovered, and then a tree search procedure is designed and embedded into the DE framework. According to the extensive computational experiments, the proposed approach is efficient in solving the job shop scheduling problem with total weighted tardiness objective.

##### Software:

DeMat
PDF
BibTeX
XML
Cite

\textit{R. Zhang} and \textit{C. Wu}, Math. Probl. Eng. 2011, Article ID 390593, 20 p. (2011; Zbl 1235.90068)

Full Text:
DOI

**OpenURL**

##### References:

[1] | J. K. Lenstra, A. H. G. R. Rinnooy Kan, and P. Brucker, “Complexity of machine scheduling problems,” Annals of Discrete Mathematics, vol. 1, pp. 343-362, 1977. · Zbl 0353.68067 |

[2] | I. Essafi, Y. Mati, and S. Dauzère-Pérès, “A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem,” Computers and Operations Research, vol. 35, no. 8, pp. 2599-2616, 2008. · Zbl 1177.90155 |

[3] | H. Zhou, W. Cheung, and L. C. Leung, “Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm,” European Journal of Operational Research, vol. 194, no. 3, pp. 637-649, 2009. · Zbl 1163.90004 |

[4] | E. Nowicki and C. Smutnicki, “An advanced tabu search algorithm for the job shop problem,” Journal of Scheduling, vol. 8, no. 2, pp. 145-159, 2005. · Zbl 1154.90479 |

[5] | J. Q. Li, Q. K. Pan, P. N. Suganthan, and T. J. Chua, “A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem,” The International Journal of Advanced Manufacturing Technology, vol. 52, no. 5-8, pp. 683-697, 2011. |

[6] | D. Y. Sha and C.-Y. Hsu, “A hybrid particle swarm optimization for job shop scheduling problem,” Computers & Industrial Engineering, vol. 51, no. 4, pp. 791-808, 2006. |

[7] | G. Moslehi and M. Mahnam, “A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search,” International Journal of Production Economics, vol. 129, no. 1, pp. 14-22, 2011. |

[8] | M. Seo and D. Kim, “Ant colony optimisation with parameterised search space for the job shop scheduling problem,” International Journal of Production Research, vol. 48, no. 4, pp. 1143-1154, 2010. · Zbl 1197.90228 |

[9] | L. N. Xing, Y. W. Chen, P. Wang, Q. S. Zhao, and J. Xiong, “A knowledge-based ant colony optimization for flexible job shop scheduling problems,” Applied Soft Computing Journal, vol. 10, no. 3, pp. 888-896, 2010. · Zbl 05739878 |

[10] | K. L. Huang and C. J. Liao, “Ant colony optimization combined with taboo search for the job shop scheduling problem,” Computers and Operations Research, vol. 35, no. 4, pp. 1030-1046, 2008. · Zbl 1180.90123 |

[11] | J. Gao, L. Sun, and M. Gen, “A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems,” Computers & Operations Research, vol. 35, no. 9, pp. 2892-2907, 2008. · Zbl 1144.90379 |

[12] | R. Tavakkoli-Moghaddam, M. Azarkish, and A. Sadeghnejad-Barkousaraie, “A new hybrid multi-objective Pareto archive PSO algorithm for a bi-objective job shop scheduling problem,” Expert Systems with Applications, vol. 38, no. 9, pp. 10812-10821, 2011. · Zbl 1202.68075 |

[13] | M. Singer and M. Pinedo, “A computational study of bound techniques for the total weighted tardiness in job shops,” IIE Transactions, vol. 30, no. 2, pp. 109-118, 1998. |

[14] | E. Kutanoglu and I. Sabuncuoglu, “An analysis of heuristics in a dynamic job shop with weighted tardiness objectives,” International Journal of Production Research, vol. 37, no. 1, pp. 165-187, 1999. · Zbl 0939.90008 |

[15] | S. J. Mason, J. W. Fowler, and W. M. Carlyle, “A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops,” Journal of Scheduling, vol. 5, no. 3, pp. 247-262, 2002. · Zbl 1009.90045 |

[16] | L. Mönch and R. Drießel, “A distributed shifting bottleneck heuristic for complex job shops,” Computers and Industrial Engineering, vol. 49, no. 3, pp. 363-380, 2005. |

[17] | S. Kreipl, “A large step random walk for minimizing total weighted tardiness in a job shop,” Journal of Scheduling, vol. 3, no. 3, pp. 125-138, 2000. · Zbl 0969.90045 |

[18] | M. Singer, “Decomposition methods for large job shops,” Computers & Operations Research, vol. 28, no. 3, pp. 193-207, 2001. · Zbl 0964.90020 |

[19] | K. M. J. Bontridder, “Minimizing total weighted tardiness in a generalized job shop,” Journal of Scheduling, vol. 8, no. 6, pp. 479-496, 2005. · Zbl 1123.90022 |

[20] | R. Tavakkoli-Moghaddam, M. Khalili, and B. Naderi, “A hybridization of simulated annealing and electromagnetic-like mechanism for job shop problems with machine availability and sequence-dependent setup times to minimize total weighted tardiness,” Soft Computing, vol. 13, no. 10, pp. 995-1006, 2009. · Zbl 05586571 |

[21] | R. Storn and K. Price, “Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces,” Journal of Global Optimization, vol. 11, no. 4, pp. 341-359, 1997. · Zbl 0888.90135 |

[22] | E. Mezura-Montes, J. Velázquez-Reyes, and C. A. Coello Coello, “Modified differential evolution for constrained optimization,” in Proceedings of the IEEE Congress on Evolutionary Computation, pp. 25-32, July 2006. |

[23] | L. Wang and L.-P. Li, “Fixed-structure H\infty controller synthesis based on differential evolution with level comparison,” IEEE Transactions on Evolutionary Computation, vol. 15, no. 1, pp. 120-129, 2011. · Zbl 05890033 |

[24] | M. Vasile, E. Minisci, and M. Locatelli, “An inflationary differential evolution algorithm for space trajectory optimization,” IEEE Transactions on Evolutionary Computation, vol. 15, no. 2, pp. 267-281, 2011. · Zbl 05921262 |

[25] | M. Sharma, M. Pandit, and L. Srivastava, “Reserve constrained multi-area economic dispatch employing differential evolution with time-varying mutation,” International Journal of Electrical Power and Energy Systems, vol. 33, no. 3, pp. 753-766, 2011. |

[26] | V. C. Mariani, L. S. Coelho, and P. K. Sahoo, “Modified differential evolution approaches applied in exergoeconomic analysis and optimization of a cogeneration system,” Expert Systems with Applications, vol. 38, no. 11, pp. 13886-13893, 2011. |

[27] | N. Noman and H. Iba, “Accelerating differential evolution using an adaptive local search,” IEEE Transactions on Evolutionary Computation, vol. 12, no. 1, pp. 107-125, 2008. · Zbl 05516156 |

[28] | C.-W. Chiang, W.-P. Lee, and J.-S. Heh, “A 2-Opt based differential evolution for global optimization,” Applied Soft Computing Journal, vol. 10, no. 4, pp. 1200-1207, 2010. |

[29] | W. Gong, Z. Cai, and L. Jiang, “Enhancing the performance of differential evolution using orthogonal design method,” Applied Mathematics and Computation, vol. 206, no. 1, pp. 56-69, 2008. · Zbl 1157.65384 |

[30] | G. Onwubolu and D. Davendra, “Scheduling flow shops using differential evolution algorithm,” European Journal of Operational Research, vol. 171, no. 2, pp. 674-692, 2006. · Zbl 1090.90090 |

[31] | B. Qian, L. Wang, R. Hu, W.-L. Wang, D.-X. Huang, and X. Wang, “A hybrid differential evolution method for permutation flow-shop scheduling,” The International Journal of Advanced Manufacturing Technology, vol. 38, no. 7, pp. 757-777, 2008. |

[32] | Q.-K. Pan, M. F. Tasgetiren, and Y.-C. Liang, “A discrete differential evolution algorithm for the permutation flowshop scheduling problem,” Computers & Industrial Engineering, vol. 55, no. 4, pp. 795-816, 2008. |

[33] | L. Wang, Q.-K. Pan, P. N. Suganthan, W.-H. Wang, and Y.-M. Wang, “A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems,” Computers &Operations Research, vol. 37, no. 3, pp. 509-520, 2010. · Zbl 1175.90199 |

[34] | S. D. Wu, E. S. Byeon, and R. H. Storer, “A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness,” Operations Research, vol. 47, no. 1, pp. 113-124, 1999. · Zbl 0979.90030 |

[35] | K. V. Price, R. M. Storn, and J. A. Lampinen, Differential Evolution: A Practical Approach to Global Optimization, Springer, Berlin, Germany, 2005. · Zbl 1186.90004 |

[36] | C. Rego and R. Duarte, “A filter-and-fan approach to the job shop scheduling problem,” European Journal of Operational Research, vol. 194, no. 3, pp. 650-662, 2009. · Zbl 1162.90016 |

[37] | R. Bellman, “On a routing problem,” Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87-90, 1958. · Zbl 0081.14403 |

[38] | U. K. Chakraborty, Advances in Differential Evolution, Springer, Berlin, Germany, 2008. · Zbl 1153.68510 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.