<abstract xmlns="http://www.w3.org/1999/xhtml"><p> 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</p></abstract>

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

Minimizing Total Completion Time For Preemptive Scheduling With Release Dates And Deadline Constraints

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

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

Foundations of Computing and Decision Sciences

It is known that the single machine preemptive scheduling problem of minimizing total completion time with release date and deadline constraints is NP- hard....

Minimizing Total Completion Time For Preemptive Scheduling With Release Dates And Deadline Constraints

Publié en ligne: 11 mars 2014

Pages: 17 - 26

DOI: https://doi.org/10.2478/fcds-2014-0002

Mots clés
Preemptive Scheduling, Release date, Deadline, Total completion time

This content is open access.

Minimizing Total Completion Time For Preemptive Scheduling With Release Dates And Deadline Constraints

Publié en ligne: 11 mars 2014

Pages: 17 - 26

DOI: https://doi.org/10.2478/fcds-2014-0002

Mots clésPreemptive Scheduling, Release date, Deadline, Total completion time

This content is open access.

Mots clés
Preemptive Scheduling, Release date, Deadline, Total completion time