One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties 2: For a Fixed Task Order, the Block-Shifting Algorithm Minimizes the Total DiscrepancyResearch Paper
A task may have a preferred execution time because a material delivery, external event, or downstream operation is timed to it. Starting early can be as costly as starting late. Garey, Tarjan, and Wilfong study this situation on one processor, where tasks cannot overlap but idle time between tasks is permitted. Their total-discrepancy problem is hard when…