Abstract
Extensive research has been devoted to preemptive scheduling. However, little attention has been paid to problems where a certain time penalty must be incurred if preemption is allowed. In this paper, we consider the single-machine scheduling problem of minimizing the total completion time subject to job release dates and preemption penalties, where each time a job is started, whether initially or after being preempted, a job-independent setup must take place. The problem is proved to be strongly NP-hard even if the setup time is one unit. We also study a natural extension of a greedy algorithm, which is optimal in the absence of preemption penalty. It is proved that the algorithm has a worst-case performance bound of 25/16, even when the maximum completion time, i.e., makespan, criterion is considered simultaneously.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.REFERENCES
Potts, C. N. and L. N. Van Wassenhove, “Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity,” J. Oper. Res. Soc. 43, 395–406 (1992).
Monma, C. L. and C. N. Potts, “Analysis of heuristics for preemptive parallel machine scheduling with batch setup times,” Oper. Res. 41, 981–993 (1993).
Chen, B., “A better heuristic for preemptive parallel machine scheduling with batch setup times,” SIAM J. Comput. 22, 1303–1318 (1993).
Zdrzalka, S., “Preemptive scheduling with release dates, delivery times and sequence independent setup times,” Eur. J. Oper. Res. 76, 60–71 (1994).
Schuurman P. and G.J. Woeginger, “Preemptive scheduling with job-dependent setup times,” Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms 1999 pp. 759–767.
Liu, Z. and T. C. E. Cheng, “Scheduling with job release dates, delivery times and preemption penalties,” Information Process. Lett., 82, 107–111 (2002).
Julien, F. M., M. J. Magazine, and N. G. Hall, “Generalized preemption models for single-machine dynamic scheduling problems,” IIE Trans. 29, 359–372 (1997).
Garey, M. R. and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, 1979.
Phillips, C., C. Stein, and J. Wein, “Minimizing average completion time in the presence of release dates,” Math. Prog., 82, 199–223 (1998).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Liu, Z., Cheng, T.E. Minimizing Total Completion Time Subject to Job Release Dates and Preemption Penalties. Journal of Scheduling 7, 313–327 (2004). https://doi.org/10.1023/B:JOSH.0000031424.35504.c4
Issue Date:
DOI: https://doi.org/10.1023/B:JOSH.0000031424.35504.c4