Multi-objective job shop scheduling using i-NSGA-III

摘要

The complexity of job shop scheduling problems is related to many factors, such as a large number of jobs, the number of objectives and constraints. Evolutionary algorithms are a natural fit to search for the optimum schedules in complex job shop scheduling problems with multiple objectives. This paper extends the authors' i-NSGA-In algorithm to tackle a manufacturing job shop scheduling problem with multiple objectives. One of the complex objectives is to pair jobs with similar properties to increase the overall cost savings. The genetic operators in i-NSGA-III are replaced with novel problem-specific crossover and mutation operators. The proposed approach is validated by comparing against the enumeration technique for problems with 5 to 10 jobs. Unlike the enumeration technique, the proposed methodology shows competence in terms of computation time and ability to schedule a large number of jobs with a high number of objectives. Further comparisons with NSGA-III demonstrate the superiority of i-NSGA-III for problems with 30, 40, and 50 jobs.