Find in Library
Search millions of books, articles, and more
Indexed Open Access Databases
Minimizing Total Completion Time For Preemptive Scheduling With Release Dates And Deadline Constraints
oleh: He Cheng, Lin Hao, Lin Yixun, Dou Junmei
Format: | Article |
---|---|
Diterbitkan: | Sciendo 2014-02-01 |
Deskripsi
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