A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times



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)n2) which improves substantially over the best known algorithm with complexity O(mn2).

Bibtex Entry