One-processor scheduling with symmetric earliness and tardiness penalties. (English) Zbl 0671.90033

Garey, Michael R.; Tarjan, Robert E.; Wilfong, Gordon T.

Math. Oper. Res. 13, No. 2, 330-348 (1988).

The problem of nonpreemptive scheduling tasks on one processor is considered. Every task is characterized by its length and the preferred starting (or completion) time. Two objectives are considered: total earliness and maximum earliness, where earliness for every task is defined as the absolute discrepancy between real and preferred starting times. Minimization of the first criterion is shown to be NP-hard but a polynomial time algorithm that produces optimal schedules whenever all tasks have the same lengths or are to be assigned in a predefined order, is given. On the other hand, optimal schedules with respect to the second criterion can, in the general case, be found in polynomial time.

Reviewer: J.Blazewicz

MSC:

90B35	Deterministic scheduling theory in operations research
68Q25	Analysis of algorithms and problem complexity

Keywords:

nonpreemptive scheduling; Two objectives; total earliness; maximum earliness; NP-hard; polynomial time algorithm