AN EFFICIENT ALGORITHM FOR SCHEDULING INDEPENDENT TASKS.
AUBURN UNIV ALA
Pagination or Media Count:
An algorithm is developed for sequencing an independent task set, characterized by deterministic processing times and due dates, on a single processor so that total tardiness is minimized. The tasks are assumed to have a loss function of the form max O, c sub i - d sub i where c sub i is the calender completion time of task i and d sub i is its due date. The method is in general suboptimal, but conditions are given for which an optimal schedule is always obtained. In addition, a technique is presented for improving suboptimal solutions by interchanging certain non-adjacent pairs of tasks. Finally, this scheduling technique is applied to the multiple processor case. Author
- Computer Programming and Software
- Computer Hardware