A note on the preemptive scheduling to minimize total completion time with release time and deadline constraints.

In this paper, we consider two problems about the preemptive scheduling of a set of jobs with release times on a single machine. In the first problem, each job has a deadline. The objective is to find a feasible schedule which minimizes the total completion time of the jobs. In the second problem (called two-agent scheduling problem), the set of jobs is partitioned into two subsets $$\mathcal{J}^{(1)}$$ and $$\mathcal{J}^{(2)}$$ . Each job in $$\mathcal{J}^{(2)}$$ has a deadline. The objective is to find a feasible schedule which minimizes the total completion time of the jobs in $$\mathcal{J}^{(1)}$$ . For the first problem, Du and Leung (Journal of Algorithms 14:45-68, ) showed that the problem is NP-hard. We show in this paper that there is a flaw in their NP-hardness proof. For the second problem, Leung et al. (Operations Research 58:458-469, ) showed that the problem can be solved in polynomial time. Yuan et al. (Private Communication) showed that their polynomial-time algorithm is invalid so the complexity of the second problem is still open. In this paper, by a modification of Du and Leung's NP-hardness proof, we show that the first problem is NP-hard even when the jobs have only two distinct deadlines. Using the same reduction, we also show that the second problem is NP-hard even when the jobs in $$\mathcal{J}^{(2)}$$ has a common deadline $$D>0$$ and a common release time 0. [ABSTRACT FROM AUTHOR]