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

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


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