Partial Solutions and MultiFit Algorithm for Multiprocessor Scheduling

A new polynomial algorithm is developed for the classical multiprocessor scheduling problem in which independent jobs are nonpreemptively scheduled on identical parallel machines with the objective of minimizing the makespan, i.e. the latest job finishing time. The algorithm at first generates and merges a set of partial solutions in order to obtain a feasible solution for the multiprocessor scheduling problem. Then a set of bin packing problems are solved in order to improve the solution, by iteratively using a M u l t i F i t type procedure on different job sets. The effectiveness of this approach is evaluated by solving a large number of benchmark instances. The results indicate that the proposed algorithm, called PSMF, is very competitive with well known constructive algorithms for a wide range of instances. Furthermore, PSMF is competitive with respect to some of the best heuristics for parallel machine scheduling problems only when it uses a 2‐exchange procedure.