Minimizing total completion time for preemptive scheduling with release dates and deadline constraints

• Autorzy: He C. , Lin H. , Lin Y. , Dou J.
• Języki publikacji: EN

Abstrakty

EN

It is known that the single machine preemptive scheduling problem of minimizing total completion time with release date and deadline constraints is NP-hard. Du and Leung solved some special cases by the generalized Baker's algorithm and the generalized Smith's algorithm in O(n2) time. In this paper we give an O(n2) algorithm for the special case where the processing times and deadlines are agreeable. Moreover, for the case where the processing times and deadlines are disagreeable, we present two properties which could enable us to reduce the range of the enumeration algorithm.

Słowa kluczowe

EN

Preemptive Scheduling; Release date; Deadline; Total completion time

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2014
• Tom: Vol. 39, No. 1
• Strony: 17--26
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

He C.

• School of Science, Henan University of Technology, Zhengzhou, Henan 450052, China

autor

Lin H.

• School of Science, Henan University of Technology, Zhengzhou, Henan 450052, China

autor

Lin Y.

• Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, China

autor

Dou J.

• School of Science, Henan University of Technology, Zhengzhou, Henan 450052, China

Bibliografia

• [1] Baker, K.R. Introduction to Sequencing and Scheduling. Wiley, New York, 1974.
• [2] Baker, K.R., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints. Operations Research, 26: 111-120 (1983).
• [3] Brucker, P. Scheduling Algorithms (third edition). Springer, Berlin, 2001.
• [4] Blazewicz, J., Dror, M. Mathematical programming formulations for machine scheduling: A survey. European Journal of Operational Research, 51: 283-300 (1991).
• [5] Du, J., Leung, J.Y.T. Minimizing mean ow time with release time and deadline constraints. Journal of Algorithms, 14: 45-68 (1993).
• [6] Du, J., Leung, J.Y.T., Young, G.H. Minimizing mean ow time with release time constraints. Theoretical Computer Science, 75: 347-355 (1990).
• [7] Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5: 287-326 (1979).
• [8] Horn, W.A. Some simple scheduling algorithms. Naval Research Logistics Quarterly, 21: 177-18 (1974).
• [9] Smith, W.E. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3: 59-66 (1956).
• [10] Sourd, F. Preemptive scheduling with two minimax criteria. Annals of Operations Research, 107: 303-319 (2001).