算法设计与分析第二章带有到达时间的单机排序问题，目标是最小化最大延迟时间

The Design of Approximation Algorithms

2.1 Scheduling jobs with deadlines on a single machine

首先要了解延迟Lj=Cj-dj和最大延迟Lmax.

对于有到达时间rj的排序问题，设计近似比时，一般会放到最大的（接受）工件，从r_max开始排序无间断加工。

而对于带有交货期（due date）的排序问题，设计近似比时，比较常用的就是EDD规则（最早交货期规则，the earliest due date rule）。

本节2-近似算法的核心是，从最大的到期日期开始加工工件，因此之后机器无空闲，再减去最小的交货期。即假设将第一个加工工件到期日期放缩到最大，此后机器一直加工到最后一个工件，再将最后一个加工工件交货期放缩到最小。

该章节翻译如下，如有错误或其他问题，麻烦大家指出，🐟的个人分享，以后会持续更新，欢迎大家积极讨论。