ON A DOMINANCE TEST FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH RELEASE DATES TO MINIMIZE TOTAL FLOW TIME

スポンサーリンク

概要

• 論文の詳細を見る

• The dominance test is a bounding operation in branch-and-bound algorithms, where each subproblem is examined whether it can be terminated or not by comparing, implicitly or explicitly, with another subproblem. For a single machine scheduling problem with release dates to minimize total flow time, Chu [5] proposed a branch-and-bound algorithm with a dominance test based on already known and new dominance properties and reported that the dominance test works successfully to solve problem instances exactly with up to 100 jobs. On the other hand, a naive combination of these dominance properties may delete all of the optimal solutions. The purpose of this paper is to point out such a pitfall and then propose a way to avoid it. Furthermore, new dominance properties based on the property developed by Chu [5] are proposed. Computational experiments are performed to see how often the branch-and-bound algorithm with a naive dominance test fails and to show an effectiveness of our branch-and-bound algorithm.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Fujie Tetsuya

  Kobe University of Commerce

• Yanai Shuzo

  Kobe University of Commerce

関連論文

• ON GROTSCHEL-LOVASZ-SCHRIJVER'S RELAXATION OF STABLE SET POLYTOPES
• ON A DOMINANCE TEST FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH RELEASE DATES TO MINIMIZE TOTAL FLOW TIME

スポンサーリンク