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$$ A 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}\}$$ J A = { J 1 a , ? , J n a a } and J B = { J 1 b , ? , J n b b } , respectively. Each job $$J_j\in \mathcal{J}_A\cup \mathcal{J}_B$$ J j ? J A ? J B has a release date $$r_j$$ r j and the $$n=n_a+n_b$$ 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$$ 1 | r j , pmtn | L max a : f max b ≤ Q can be solved in $$O(n_a\log n_a+ n_b\log n_b)$$ O ( n a log n a + n b log n b ) time. They use the strategy that schedules the jobs of agent $$B$$ B without preemption as late as possible under the restriction $$f^b_{\max }\le Q$$ f max b ≤ Q . We show that the strategy fails to work even when $$n_a=n_b=1$$ 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$$ 1 | r j , pmtn | L max a : f max b ≤ Q and the Pareto optimization problem $$1|r_j,\; \text{ pmtn }| (L^a_{\max }: L^b_{\max })$$ 1 | r j , pmtn | ( L max a : L max b ) . We show that the two problems can be solved in $$O(n_an \log n)\hbox { and }O(n_an_bn \log n)$$ O ( n a n log n ) and O ( n a n b n log n ) time, respectively.