Partial Solutions and MultiFit Algorithm for Multiprocessor Scheduling

A new polynomial algorithm is developed for the classical multiprocessor scheduling problem in which independent jobs arenonpreemptively 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 partialsolutions in order to obtain a feasible solution for themultiprocessor scheduling problem. Then a set of bin packing problems are solved in order to improve the solution, by iterativelyusing a MultiFit 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 theproposed 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 bestheuristics for parallel machine scheduling problems only when it uses a 2-exchange procedure.