Some aspects of scatter search in the flow-shop problem |
| |
| Institution: | 1. Department of Civil and Environmental Engineering, Virginia Tech, Blacksburg, VA 24061, USA;2. Department of Mechanical Engineering and Materials Science, Duke University, Durham, NC 27708, USA;1. Department of Materials Science and Engineering, Pohang University of Science and Technology (POSTECH), 77 Cheongam-ro, Pohang 790-784, Republic of Korea;2. Graduate School of Energy Environment Water and Sustainability, Korea Advanced Institute of Science & Technology (KAIST), 291 Daehak-ro, Daejeon 305-701, Republic of Korea;3. Department Materials Physics, Montanuniversität Leoben, Jahnstraße 12, 8700 Leoben, Austria;4. Graduate Institute of Ferrous Technology, Pohang University of Science and Technology (POSTECH), 77 Cheongam-ro, Pohang 790-784, Republic of Korea;1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, PR China;2. College of Information and Management Science, Henan Agricultural University, Zhengzhou, Henan 450003, PR China;3. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang, Jiangxi 330013, PR China |
| |
| Abstract: | The flow-shop scheduling problem with the makespan criterion is a certain strongly NP-hard case from the domain of OR. This problem, having simple formulation contrasting with its troublesome, complex and time-consuming solution methods, is ideal for testing the quality of advanced combinatorial optimization algorithms. Although many excellent approximate algorithms for the flow-shop problem have been provided, up till now, in the literature, some theoretical and experimental problems associated with an algorithm’s activity still remain unexamined. In this paper, we provide a new view on the solution space and the search process. Relying upon it, we are proposing the new approximate algorithm, which applies some properties of neighborhoods, refers to the big valley phenomenon, uses some elements of the scatter search as well as the path relinking technique. This algorithm shows up to now unprecedented accuracy, obtainable within a short time on a PC, which has been confirmed in a wide variety of computer tests. Good properties of the algorithm remain scalable if the size of instances increases. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
