A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times
[.pdf]
Abstract
Consider the problem of scheduling a set of tasks of length p without
preemption on m identical machines with given release and deadline
times. We present a new algorithm for computing the schedule with
minimal completion times and makespan. The algorithm has time
complexity O(min(1, p/m)n
2) which improves substantially
over the best known algorithm with complexity O(mn
2).
Bibtex Entry
