Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times

Concepts

ManagementIndustrial EngineeringOperations ManagementInventory ManagementProduction PlanningSchedulingJob SchedulingJob SequencingMachine SchedulingProduction SchedulingSequencingMachine SequencingRelease Date ConstraintsRelease DatesScheduling With Release DatesSingle-machine Scheduling

Abstract

The single machine sequencing problem is considered in which each job has a release date, a processing time and a delivery time. The objective is to find a sequence of jobs which minimizes the time by which all jobs are delivered. A heuristic is presented which never deviates by more than 50% from the optimum.

References

On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness

Graham McMahon, Michaël Florian · Operations Research · 1975 · 232 citations

Computing, Computer Engineering, Computer Science +14

Sequencing with due‐dates and early start times to minimize maximum tardiness

Kenneth R. Baker, Zaw‐Sing Su · Naval Research Logistics Quarterly · 1974 · 138 citations

Management, Decision Sciences, Scheduling +9

Performance Guarantees for Scheduling Algorithms

M. R. Garey, Ronald Graham, David S. Johnson · Operations Research · 1978 · 130 citations

Management, Computer Engineering, Computer Science +15

Worst-Case Analysis of Heuristic Algorithms

Marshall L. Fisher · Management Science · 1980 · 126 citations

Business, Computer Science, Algorithms +15