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

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.