AnnJob, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs

Abstract

An algorithm, computationally feasible for large problems, has been formulated for sequencing n jobs through a single facility to minimize the number of late jobs. This algorithm is then extended to solve the problem in which each job is associated with a continuous, monotone non-decreasing deferral cost function. The object is to produce a schedule where the maximum deferral cost incurred is minimal.