Two machine scheduling subject to arbitrary machine availability constraint

We study two machine scheduling subject to arbitrary machine availability constraint. Each machine can have multiple unavailable intervals, and both machines can be unavailable at the same time. The jobs can be resumed after being preempted by another job or interrupted by the unavailable intervals. We consider both the single criterion and the bi-criteria problems concerning two most common criteria: makespan and the total completion time. If makespan is the single criterion to optimize, Liu and Sanlaville (1995) have shown that the optimal schedule can be found in polynomial time. If total completion time is the single criterion, the existing algorithm can only find the optimal schedules for some special cases; however, the complexity of the problem with arbitrary machine availability constraint remains open. For two bi-criteria problems, i.e., the problem of minimizing the total completion time subject to the constraint that the makespan is minimum, and the problem of minimizing makespan subject to the constraint that total completion time is minimum, their computational complexity are also open. In this paper, we show all these three open problems are in P by giving optimal algorithms that run in polynomial time. An interesting finding in this research is that these three problems are closely related to each other and thus the algorithms also rely on one another.