Multiobjective Optimization of a Pre-emptive Flexible Job-shop Problem with Machine Transportation Delay

Abstract: The job scheduling problem is a type of scheduling problem where a list of jobs and machines are given. A solution consists of a schedule where each job is assigned to one or multiple machines at a certain time. In this study, a multiobjective evolutionary algorithm called NSGA-II was applied to optimize schedules for a particular scheduling problem given by a board game made by the Swedish educative company INSU. The scheduling problem features novel restrictions on the schedules, such as transportation delay between the jobs, skill requirements for the machines to fulfill. The board game also allows pre-emption, i.e., that the jobs can be paused and resumed by the same or other machines. These restrictions impose a challenge for creating a genetic representation for the evolutionary algorithm and a decoder which decodes the representation into a schedule. This problem was solved by proposing a new genetic representation based on previous work and testing it with a few crossover and mutation methods in two experiments. The experiments found that the new representation is effective in creating high-quality schedules, but it is inconclusive as to which crossover and mutation method is the most effective. The decoder’s execution time was also measured, which showed that the decoder scales rapidly with an increasing number of jobs. Despite this, the new representation and decoder are useful for optimizing other scheduling problems with pre-emption and other restrictions.