Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
475337 | Computers & Operations Research | 2009 | 6 Pages |
Motivated by the real-life scheduling problem in a steel-wire factory in China, this paper studies the problem of minimizing the maximum lateness on a single machine with family setups. In view of the NP-hard nature of the problem, neighborhood properties of the problem are investigated. It is found that the traditional move-based neighborhood is inefficient to search. Then a new neighborhood, which is based on batch destruction and construction, is developed. A simulated annealing algorithm with the new neighborhood is proposed. Experiments are carried out on the randomly generated problems and the real-life instances from a factory in China. Computational results show that the proposed algorithm can obtain better near optimal solutions than the existing algorithm.