Affordable Access

Publisher Website

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

Authors
Publisher
Elsevier B.V.
Publication Date
Volume
11
Issue
6
Identifiers
DOI: 10.1016/j.asoc.2011.03.007
Keywords
  • Multi-Objectivization
  • Helper-Objective
  • Job Shop Scheduling Problem (Jssp)
  • Epistasis
Disciplines
  • Computer Science

Abstract

Abstract 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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

A multi-objective PSO for job-shop scheduling prob...

on Expert Systems with Applicatio... Jan 01, 2010

A Pareto approach to multi-objective flexible job-...

on International Journal of Produ... Jan 01, 2011

An improved particle swarm optimization with decli...

on Computers & Operations Researc...

An effective hybrid particle swarm optimization al...

on Computers & Industrial Enginee... Jan 01, 2009
More articles like this..