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