Solving multi-objective job shop problem using nature-based algorithms: new Pareto approximation features

Abstract

In this paper the job shop scheduling problem (JSP) with minimizing two criteria simultaneously is considered. JSP is frequently used model in real world applications of combinatorialoptimization. Multi-objective job shop problems (MOJSP) were rarely studied. We implement andcompare two multi-agent nature-based methods, namely ant colony optimization (ACO) and geneticalgorithm (GA) for MOJSP. Both of those methods employ certain technique, taken from the multicriteria decision analysis in order to establish ranking of solutions. ACO and GA differ in a methodof keeping information about previously found solutions and their quality, which affects the course ofthe search. In result, new features of Pareto approximations provided by said algorithms are observed:aside from the slight superiority of the ACO method the Pareto frontier approximations provided byboth methods are disjoint sets. Thus, both methods can be used to search mutually exclusive areas ofthe Pareto frontier.