A LISTFIT heuristic for minimizing makespan on identical parallel machines

This paper presents a new heuristic for minimizing makespan on identical parallel machines. The new heuristic, called LISTFIT, is based on bin-packing and list scheduling, two methods commonly used to solve this problem. Its worst case performance bound is no worse than that of the commonly used MULTIFIT heuristic. However, the average performance of the proposed listfit heuristic is considerably better than that of the multifit heuristic. The proposed heuristic may be of particular relevance to practitioners who are interested in solving this or related problems with real world constraints of computational time and effectiveness.