Paper Info
Title
A GRASP for single machine scheduling with sequence dependent setup costs and linear delay penalties
Abstract
The single machine scheduling (SMS) problem with sequence dependent setup costs and linear delay penalties is readily found in industrial environments. The problem is of interest in manufacturing because any increase in the efficiency of a heavily utilized machine translates directly into cost savings. However, finding good solutions to this NP-hard combinatorial optimization problem has challenged researchers for years in industry and academia. A novel methodology, Greedy Randomized Adaptive Search Procedure (GRASP), is used in this paper to develop an efficient heuristic for the SMS problem. The empirical results of other researchers are used to validate the heuristic's performance. Previous exact approaches using dynamic programming (DP) with branch and bound provide optimal solutions to SMS instances with up to 20 jobs. A clever implementation of tabu search shows success for problems possessing up to 100 jobs. Our heuristic compares favorably to both the DP and tabu search methods with respect to the solution values obtained and the CPU times required.
Year
DOI
Venue
1996
10.1016/0305-0548(95)00084-4
Computers & OR
Keywords
DocType
Volume
sequence dependent setup cost,linear delay penalty,single machine scheduling
Journal
23
Issue
ISSN
Citations 
9
Computers and Operations Research
14
PageRank 
References 
Authors
1.87
4
3
Name
Order
Citations
PageRank
Thomas A. Feo116323.88
Kishore Sarathy2141.87
John McGahan3141.87