A new ILS algorithm for parallel machine scheduling problems |
| |
Authors: | Lixin Tang Jiaxiang Luo |
| |
Affiliation: | (1) The Logistics Institute, Faculty of Information Science and Engineering, Northeastern University, Shenyang, China |
| |
Abstract: | This paper addresses the non-preemptive scheduling problem of scheduling jobs on identical parallel machines to minimize the
maximum completion time or makespan. The problem has been proved to be NP-hard in the strong sense. The NP-hardness of the problem motivates us to develop a
new methodology to obtain near-optimal solutions. We formulate the problem as an integer programming and then propose a new
iterated local search (ILS) algorithm based on a variable number of cyclic exchanges to solve it. The properties of the solutions
are derived and the results are used to improve the computational efficiency of our algorithm. Computational experiments show
that the cyclic exchange neighborhood embedded in an iterated local search framework is effective for solving the scheduling
problems with up to 1000 jobs and 40 machines within a reasonable amount of computation time.
Received: April 2005 / Accepted: January 2006 |
| |
Keywords: | Parallel machine scheduling Iterated local search Cyclic exchange neighborhood Approximately dynamic programming |
本文献已被 SpringerLink 等数据库收录! |