An Efficient Algorithm for Finding Ideal Schedules
In this talk we address the problem of scheduling UET jobs with release dates and precedence constraints on two identical processors.
We say that a schedule is ideal if it minimises both maximum and total completion time simultaneously. We give an instance of the problem showing that ideal schedules do not exist in general when preemptions are allowed. If preemptions are not allowed, then ideal schedules do exist for general precedence constraints, and we describe an algorithm for finding ideal schedules in O(n^3) time, where n is the number of jobs. (joint work with Ed Coffman and Darek Dereniowski)