Abstract
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, 1993) 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, 2010) 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.
This is a preview of subscription content, log in via an institution to check access.
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52, 229–242.
Baker, K. R., & Smith, J. C. (2003). A multiple-criterion model for machine scheduling. Journal of Scheduling, 6, 7–16.
Du, J. Z., & Leung, J. Y.-T. (1993). Minimizing mean flow time with release time and deadline constraints. Journal of Algorithms, 14, 45–68.
Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A guide to the theory of NP-completeness. San Francisco: Freeman.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.
Horn, W. A. (1974). Some simple scheduling algorithms. Navel Research Logistics Quartely, 21, 177–185.
Lawler, E. L. (1982). Recent results in the theory of machine scheduling. In A. Bachem, M. Groschel, & B. Korte (Eds.), Mathematical programming: The state of the art. New York: Springer.
Leung, J. Y.-T., Pinedo, M., & Wan, G. H. (2010). Competitive two agent scheduling and its applications. Operations Research, 58, 458–469.
Smith, W. E. (1956). Various optimizers for single state production. Naval Research Logistics Quarterly, 3, 59–66.
Yuan, J. J., Ng, C. T., Cheng, & T. C. E. (2013) Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness, In Submissiom.
Acknowledgments
Research supported by NSFC (11271338), NSFC (11171313), and NSF Henan (132300410392).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wan, L., Yuan, J. & Geng, Z. A note on the preemptive scheduling to minimize total completion time with release time and deadline constraints. J Sched 18, 315–323 (2015). https://doi.org/10.1007/s10951-014-0368-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-014-0368-y