Symmetry and optimally properties of the single machine problem

Abstract

Abstract This paper develops some useful concepts and properties for the problem of sequencing n jobs on one machine so as to minimize the maximum lateness when the jobs may have unequal ready times, processing times, and due dates, and pre-emption is not permitted. The properties established include the equivalence among three versions of the problem, the symmetrical nature of the problem and the additive and multiplicative characteristics of the job set parameters. These properties are applied to forward and backward sequencing. A strong sufficient optimality condition is developed and used to obtain tight lower bounds on the optimal solution. The paper demonstrates the applicability of the concepts and properties to the development of efficient optimal and heuristic procedures and to the design of experiments for evaluating the relative performance of solution procedures. Optimal single-pass solutions for special cases of the problem are given.