Jackson’s Rule for single-machine scheduling: Making a good heuristic better

Jackson’s Rule for single-machine scheduling: Making a good heuristic better

0.00 Avg rating0 Votes
Article ID: iaor19921341
Country: United States
Volume: 17
Issue: 1
Start Page Number: 22
End Page Number: 35
Publication Date: Feb 1992
Journal: Mathematics of Operations Research
Authors: ,
Keywords: combinatorial analysis, heuristics
Abstract:

The authors consider the scheduling problem in which jobs with release dates and delivery times are to be scheduled on one machine. They present a 4/3-approximation algorithm for the problem with precedence constraints among the jobs, and two polynomial approximation schemes for the problem without precedence constraints. At the core of each of the algorithms presented is Jackson’s Rule-a simple but seemingly robust heuristic for the problem.

Reviews

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