Minimizing total completion time for preemptive scheduling with release dates and deadline constraints
2014
scientific article
english
- preemptive scheduling
- release date
- deadline
- total completion time
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.
17 - 26
CC BY-NC-ND (attribution - noncommercial - no derivatives)
public
15