Multiobjective evolutionary algorithms for job shop scheduling

Abstract

A job shop can be seen as a multi-operation model where jobs follows fixed routes, but not necessarily the same for each job. Job Shop Scheduling (JSS) attempts to provide optimal schedules according to some criterion. Common variables to optimize are makespan, machine idleness, lateness and total weighted completion time. According to this variables different objectives can be devised. Multiobjective optimization, also known as vector-valued criteria or multicriteria optimization, have long been used in many application areas where a problem involves multiple objectives, often conflicting, to be met or optimized. Multistage evolution and cooperative population search (CPS), as extended evolutive models, can be applied to solve multicriteria optimization, either using a plain aggregative approach or seeking the Pareto Front. Multirecombination and Local Search were introduced in the CPS method in order to speed up and to improve the evolution.