Single machine scheduling with early and tardy completion costs

The authors address a single-machine scheduling problem in which penalities are assigned for early and tardy completion of jobs. These penalties are common in industrial settings where early job completion can cause the cash commitment to resources in a time frame earlier than needed, giving rise to early completion penalities. Tardiness penalities arise from a variety of sources, such as loss of customer goodwill, opportunity costs of lost sales, and direct cash penalities. Accounting for earliness cost makes the performance measure nonregular, and this nonregularity has apparently discouraged researchers from seeking solutions to this problem. The authors found that it is not much more difficult to design an enumerative search for this problem than it would be if the performance measure were regular. They present and demonstrate an efficient timetabling procedure which can be embedded in an enumerative algorithm allowing the search to be conducted over the domain of job permutations.