Single machine scheduling with sequence-dependent family setups to minimize maximum lateness |
| |
Authors: | F Jin J N D Gupta S Song C Wu |
| |
Institution: | 1.IBM China Research Lab,Shanghai,P.R. China;2.Tsinghua University,Beijing,P.R. China;3.University of Alabama in Huntsville,Huntsville,USA |
| |
Abstract: | Motivated by a real-life scheduling problem in a steel wire factory in China,this paper considers the single machine scheduling problem with sequence-dependent family setup times to minimize maximum lateness. In view of the NP-hard nature of the problem, structural (dominance and neighbourhood)properties of the problem are described and used in the tabu search algorithms to find optimal or near-optimal schedules. These proposed structural properties quickly exclude unpromising and/or non-improving neighbours from further search.Empirical results on the randomly generated and real-life problem instances from a factory in China show that the proposed heuristic algorithms utilizing the structural properties can obtain optimal or near optimal solutions with a reasonable computational effort. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|