An heuristic of changes for the scheduling problems of jobs in uniform processors

This paper examines the nonpreemptive assignment of independent jobs to a system of uniform processors with the objective of reducing makespan, or the time required from the start of execution until all jobs are completed. We consider a set of n jobs, each having an execution time and a set of m ≥ 2 processors which are assumed to have different speeds (say σ1 = 1 ≤ σ2 ≤ ... ≤ σm). Since the problem of finding a minimal makespan has been shown to be NP-hard, we develop a powerful interchange heuristic. The heuristic proposed is composed by three phases: initial assignment, job reassignment and job interchange. The main feature of this method is not to perform a pre-classification of the tasks. Some comparisons are made with other heuristic schemes and a lower bound that validates the results obtained. The heuristic achieves optimal solutions for several instances in a short computational time.