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 (Formula presented.) each having his own job set (Formula presented.), respectively. Each job (Formula presented.) has a release date (Formula presented.) 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 (Formula presented.) can be solved in (Formula presented.) time. They use the strategy that schedules the jobs of agent (Formula presented.) without preemption as late as possible under the restriction (Formula presented.). We show that the strategy fails to work even when (Formula presented.), invalidating their result. We then study the minimization problem (Formula presented.) and the Pareto optimization problem (Formula presented.). We show that the two problems can be solved in (Formula presented.) time, respectively.