Analysis of Heuristics for Sequencing Jobs on One Machine with Release Dates and Delivery Times

摘要

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 percent from the optimum.