A pairwise interchange algorithm for parallel machine scheduling

This paper considers the problem of non-preemptive scheduling n tasks on m identical parallel processors to minimize makespan for simultaneous arrivals. Based on a pairwise interchange method, an effcient algorithm is presented which is able to give a near-optimal schedule in a short time through suitable pairwise interchange between tasks, after an initial solution is constructed. The behaviour of the algorithm is discussed. Testing results prove its high performance in comparison with available simple heuristic procedures. Finally, the algorithm is generalized for the problems of non-identical processors and non-simultaneous arrivals.