Treffer: Scheduling with assignable due dates, two competing agents and late work related criteria

This paper investigates several scheduling problems on a single machine that exhibit three key features: (i) assignable due dates are considered, meaning that a predefined set of due dates is provided, and these due dates can be assigned to the jobs independently and arbitrarily; (ii) two competing agents are involved, with jobs divided into two disjoint sets, each owned by one agent; and (iii) each agent's objective is to minimize a specific late work-related criterion. Specifically, the goal is to determine a due date assignment and a feasible schedule that minimizes the weighted sum of the selected scheduling criteria for both agents. For the first time, we integrate two-agent scheduling, assignable due dates, and late work-related criteria. We develop pseudo-polynomial-time dynamic programming algorithms to address problems where one agent's criterion is the total late work, while the other agent's criterion is either the total late work, total tardiness, or weighted number of tardy jobs. Moreover, we propose polynomial-time algorithms to tackle various special cases of these related problems. © 2025 Elsevier Ltd