Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness

We consider two-agent scheduling on a single machine with release dates and preemption to minimize the maximum lateness. In this scheduling model, there are two agents \(A\hbox { and }B\) each having his own job set \(\mathcal{J}_A= \{ J^a_1, \ldots , J^a_{n_a}\}\hbox { and }\mathcal{J}_B= \{ J^b_1, \ldots , J^b_{n_b}\}\), respectively. Each job \(J_j\in \mathcal{J}_A\cup \mathcal{J}_B\) has a release date \(r_j\) and the \(n=n_a+n_b\) jobs need to be preemptively scheduled on a single machine. Leung et al. (Oper Res 58:458–469, 2010) present a comprehensive study of two-agent scheduling in various machine environments. They show that problem \(1|r_j,\; \text{ pmtn }| L^a_{\max }: f^b_{\max }\le Q\) can be solved in \(O(n_a\log n_a+ n_b\log n_b)\) time. They use the strategy that schedules the jobs of agent \(B\) without preemption as late as possible under the restriction \(f^b_{\max }\le Q\). We show that the strategy fails to work even when \(n_a=n_b=1\), invalidating their result. We then study the minimization problem \(1|r_j,\; \text{ pmtn }| L^a_{\max }: f^b_{\max }\le Q\) and the Pareto optimization problem \(1|r_j,\; \text{ pmtn }| (L^a_{\max }: L^b_{\max })\). We show that the two problems can be solved in \(O(n_an \log n)\hbox { and }O(n_an_bn \log n)\) time, respectively.