An efficient algorithm for finding ideal schedules |
| |
Authors: | Edward G Coffman Jr Dariusz Dereniowski Wies?aw Kubiak |
| |
Affiliation: | 1. Department of Electrical Engineering, Columbia University, New York, NY, USA 2. Department of Algorithms and System Modeling, Gda??sk University of Technology, Gda??sk, Poland 3. Faculty of Business Administration, Memorial University, St. John??s, Canada
|
| |
Abstract: | We study the problem of scheduling unit execution time jobs with release dates and precedence constraints on two identical
processors. We say that a schedule is ideal if it minimizes both maximum and total completion time simultaneously. We give
an instance of the problem where the min-max completion time is exceeded in every preemptive schedule that minimizes total
completion time for that instance, even if the precedence constraints form an intree. This proves that ideal schedules do
not exist in general when preemptions are allowed. On the other hand, we prove that, when preemptions are not allowed, then
ideal schedules do exist for general precedence constraints, and we provide an algorithm for finding ideal schedules in O(n
3) time, where n is the number of jobs. In finding such ideal schedules we resolve a conjecture of Baptiste and Timkovsky (Math. Methods Oper.
Res. 60(1):145–153, 2004) Further, our algorithm for finding min-max completion-time schedules requires only O(n
3) time, while the most efficient solution to date has required O(n
9) time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|