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

Abstract

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.