Minimizing maximum cost on a single machine with two competing agents and job rejection
将经典Lawler算法扩展到允许拒绝工作以及两竞争代理共享处理器的场景，并证明这两个扩展问题可在多项式时间内求解。
The classical Lawler’s Algorithm provides an optimal solution to the single-machine scheduling problem, where the objective is minimizing maximum cost, given general non-decreasing, job-dependent cost functions, and general precedence constraints. First, we extend this algorithm to allow job rejection, where the scheduler may decide to process only a subset of the jobs. Then, we further extend the model to a setting of two competing agents, sharing the same processor. Both extensions are shown to be solved in polynomial time.