A new algorithm for solving the parallel machine scheduling problem to maximize benefit and the number of jobs processed

This paper provides a mathematical model and a bi-phase heuristic algorithm for the uniform parallel machines scheduling problem to maximize benefits and the number of jobs processed before their due dates as the weighted objective function. In the first phase of this heuristic, named “the neighborhood combined dispatching rules algorithm” (NCDRA), an initial sequence by the segmentation of the dispatching rules (DRs) is generated. Then, the output sequence is segmented, and required efforts are made to derive a sequence combined with these rules to improve the objective. The second phase involves a local search in which operators such as swapping, insertion, and reversion are concurrently implemented there on. The proposed algorithm is examined on four classes of problems with 50, 100, and 1000 jobs on 5, 10, and 50 machines, respectively. Results obtained by NCDRA and a Simulated Annealing (SA) algorithm developed on problem instances indicate that the NCDRA provides high-quality results on objective function for solving problems in different scales.