Iterative Local Search Heuristic for the Single Machine Scheduling Problem with Sequence Dependent Setup Times and Due Dates

摘要：

In this paper the NP-hard problem of scheduling jobs in a single machine with sequence dependent setup times is considered with the objective of minimizing the total tardiness with respect to the due dates. An Iterative Local Search (ILS) heuristic is proposed which uses a GRASP (Greedy Randomized Adaptive Search Procedure) algorithm to generate an initial solution. The ILS heuristic is compared with the GRASP algorithm proposed by Gupta and Smith (2006) and with the Ant Colony Optimization (ACO) algorithm of Ching and Hsiao (2007). These algorithms obtained better solutions than other algorithms from the literature. Computational tests, on a set of test problems involving up to 85 jobs, show that our ILS heuristic is very efficient and competitive.

关键词： single machine scheduling heuristics ILS GRASP

作者: José Elias C. Arroyo Gilberto Vinicius P. Nunes Edmar Hell Kamke

作者单位: Departamento de Informáica Universidade Federal de Vicsa 36570-00, Vicosa, MG, Brazil

会议类型: 国际会议

会议名称: 2009 Ninth International Conference on Hybrid Intelligent Systems(第九届混合智能系统国际会议 HIS 2009)

会议地点: 沈阳

会议语种:英文

页码: 1-6

在线出版日期: 2009-08-12（万方平台首次上网日期，不代表论文的发表时间）