An improved scatter search algorithm for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times |
| |
| Affiliation: | 1. Institute of Industrial Engineering & Logistics Optimization, Northeastern University, Shenyang 110819, China;2. State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang 110819, China;1. School of Information Science & Engineering, Central South University, Changsha, Hunan 410083, China;2. Research Organization of Information and Systems, 4-3-13 Toranomon, Minato-ku, Tokyo 105-0001, Japan;3. The Institute of Statistical Mathematics, 10-3 Midori-cho, Tachikawa, Tokyo 190-8562, Japan;4. Hunan Province Higher Education Key Laboratory of Power System Safety Operation and Control, Changsha University of Science and Technology, Changsha, Hunan 410004, China;5. School of Business, Central South University, Changsha, Hunan 410083, China;6. Collaborative Innovation Center of Resource-Conserving & Environment-Friendly Society and Ecological Civilization, Changsha, Hunan 410083, China;1. Samsung Electronics, Republic of Korea;2. Intelligent Systems and Emotional Engineering (ISEE) Laboratory, Department of Mechatronics Engineering, Chungnam National University, Republic of Korea;1. International Islamic University, Islamabad, Pakistan;2. Gwangju Institute of Science and Technology, South Korea;1. Department of Economics, Ca’ Foscari University of Venice, Italy;2. Department of Management, Ca’ Foscari University of Venice, Italy;1. College of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China;2. School of Statistics, Jiangxi University of Finance and Economics, Nanchang 330013, China;3. Research Center of Applied Statistics, Jiangxi University of Finance and Economics, Nanchang 330013, China |
| |
| Abstract: | In this paper, a scatter search algorithm with improved component modules is proposed to solve the single machine total weighted tardiness problem with sequence-dependent setup times. For diversification generation module, both random strategy based heuristics and construction heuristic are adopted to generate the diversified population. For improvement module, variable neighborhood search based local searches are embedded into the algorithm to improve the trial solutions and the combined solutions. For reference set update module, the number of edges by which the two solutions differ from each other is counted to measure the diversification value between two solutions. We also propose a new strategy in which the length of the reference set could be adjusted adaptively to balance the computing time and solving ability. In addition, a discrete differential evolution operator is proposed with another two operators constitute the combination module to generate the new trial solutions with the solutions in the subsets. The proposed algorithm is tested on the 120 benchmark instances from the literature. Computational results indicate that the average relative percentage deviations of the improved algorithm from the ACO_AP, DPSO, DDE and GVNS are ?5.16%, ?3.33%, ?1.81% and ?0.08%, respectively. Comparing with the state-of-the-art and exact algorithms, the proposed algorithm can obtain 78 optimal solutions out of 120 instances within a reasonable computational time. |
| |
| Keywords: | Improved scatter search Variable neighborhood search Variable-length reference set Discrete differential evolution Total weighted tardiness scheduling |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
