Minimizing the Makespan in Nonpreemptive Parallel Machine Scheduling Problem

A new n log n algorithm for the scheduling problem of n independent jobs on m identical parallel machines with minimum makespan objective is proposed and its worst-case performance ratio is estimated. The algorithm iteratively combines partial solutions that are obtained by partitioning the set of jobs into suitable families of subsets. The computational behavior on three families of instances taken from the literature provided interesting results.