Erratum to “Competitive Two-Agent Scheduling and Its Applications”

Leung et al. (2010) [Leung JY-T, Pinedo M, Wan G (2010) Competitive two-agent scheduling and its applications. Oper. Res. 58:458–469] considered a two-agent nonpreemptive single-machine scheduling problem. Agent A is responsible for n₁ jobs with due dates $d_1,\dots ,d_n$ and has as the objective the minimization of the total tardiness of the n₁ jobs. Agent B is responsible for n₂ jobs and has as the objective the minimization of the total completion time of the n₂ jobs. The problem is to find a schedule for the $n_1+n_2$ jobs that minimizes the objective of agent A (with regard to his n₁ jobs) while keeping the objective of agent B (with regard to his n₂ jobs) below or at a fixed level Q. Leung et al. (2010) [Leung JY-T, Pinedo M, Wan G (2010) Competitive two-agent scheduling and its applications. Oper. Res. 58:458–469], in their theorem 3, showed that this problem can be solved through dynamic programming in pseudopolynomial time. However, in the proof of their theorem and in their dynamic programming formulation, there is an error that requires some changes in their proof.