Solution approaches for multi objective parallel machine scheduling problems

This study considers the multi-objective parallel machine scheduling. A novel algorithm with name Sequence Job Minimum Completion Time (SJMCT) is proposed for unrelated parallel machines and non-identical jobs to minimize the two objectives. These objectives are minimization of maximum job completion time and total tardiness when each job is assigned only to one machine at time. The proposed algorithm's performance is compared with some common dispatching rules based on a small size problem (four machines and nine jobs). Because of the complexity in multi-objective parallel machine scheduling problems, for large size problems, two novel metaheuristic algorithms SJMCT-NSGA-II based on Non-dominated sorting genetic algorithm (NSGA-II) and SJMCT-SPEA-II based on Strength Pareto evolutionary algorithm (SPEA-II) are proposed to obtain Pareto optimal solutions. The simulation results for 272 tests are reported to show the efficiency of these two algorithms. Two test problems of simulation experiences are done to study effects of the different parameters. In the simulations, the effects of generation numbers and job numbers are investigated. The results demonstrate that the proposed SJMCT-SPEA-II has better performed than the SJMCT-NSGA-II. Besides choosing the appropriate performance measures, Spacing and Spread Diversity Metrics are also ensured this result. Finally, the conclusions and some directions for future research are reported.