A new ILS algorithm for parallel machine scheduling problems

Lixin Tang

doi:10.1007/s10845-006-0032-2

Return

A new ILS algorithm for parallel machine scheduling problems

2006-10-01

PRE

Lixin Tang *

罗

罗家祥 (Jiaxiang Luo)

DOI：10.1007/s10845-006-0032-2

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

parallel machine scheduling

iterated local search

cyclic exchange neighborhood

approximately dynamic programming

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.