Minimizing maximum cost on a single machine with two competing agents and job rejection

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.