A grasp for single machine scheduling with sequence dependent setup costs and linear delay penalties

A grasp for single machine scheduling with sequence dependent setup costs and linear delay penalties

0.00 Avg rating0 Votes
Article ID: iaor1997111
Country: United Kingdom
Volume: 23
Issue: 9
Start Page Number: 881
End Page Number: 895
Publication Date: Sep 1996
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
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, 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 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. The present heuristic compares favorably to both the DP and tabu search methods with respect to the solution values obtained and the CPU times required.

Reviews

Required fields are marked *. Your email address will not be published.