Backtrack Beam Search for Multiobjective Scheduling Problem

摘要

This paper proposes a new approximation method for the multi-objective optimization problem. Proposal method is based on the beam search using the tree structure which is one of the approximate algorithms for combinatorial optimization. In this algorithm, not only finding a solution by search, but backtracking is also executed further, and quality of the solution is improved by using analyzed result of tentative solution. We apply this method to the multi-objective flow-shop problem in which it minimizes maximum completion time, total setup cost and etc. in order to demonstrate the effectiveness of this method by a numerical experiment.