Helper-objective optimization strategies for the Job-Shop Scheduling Problem

Multiple Objective Evolutionary Algorithms (MOEAs) applied to the Job-Shop Scheduling Problem have been shown to perform better than single objective Genetic Algorithms (GAs). Helper-objectives, representing portions of the main objective, help guide MOEAs in their search process. This paper provides additional understanding of helper-objective methods. The sequence in which helper-objectives are used is examined and we show that problem-specific knowledge can be incorporated to determine a good helper-objective sequence. Computational results demonstrate how carefully sequenced helper-objectives can improve search quality. This dismisses the established practice of picking helper sequence based upon a random order due to lack of knowledge about optimal sequencing. Explanations are provided for how helpers accelerate the search process by distinguishing between otherwise similar solutions and by partial removal of epistasis in one or more dimensions of the solution space. Helper-objective size was also explored to determine if maximal helper divisions are best for the set of problems studied. Helper-objective size appears to be important to the optimization and larger helpers are not necessarily better which implies that methods such as Multi-Objectivization via Segmentation (MOS) may benefit from smaller problem divisions. Lastly, an examination of the non-dominated front size was performed to determine if tuning front size makes sense for this type of algorithm since previous works have established tuning front size as important. No evidence was found to support tuning and the correlation between small front size and effectiveness appears to be a natural part of how helper-objective algorithms work rather than a reason for reducing front size. Published by Elsevier B.V.