7102 List-based Squeezing Branch and Bound法におけるノード選択方法の改良(OS7 学生研究課題発表)

概要

論文の詳細を見る
The "list-based squeezing branch and bound (LSQ) algorithm" is a kind of local search algorithms, which searches neighborhood of an initial schedule in an enumerative manner by using a branching procedure in a branch and bound algorithm (B & B) in parallel. In the LSQ, some initial schedules are found first by using promising heuristic methods, and then a B & B-based parallel local search is implemented for obtaining an optimal (or a near-optimal) schedule. In this paper, the LSQ is applied to n-job, m-machine flowshop scheduling problems to minimize makespan. A new procedure for selecting promising nodes to be branched is proposed and incorporated into the searching process of the LSQ to improve the efficiency and accuracy. Numerical experiments are implemented through benchmark problems to demonstrate that the proposed method can efficiently obtain a near optimal schedule with high accuracy.
社団法人日本機械学会の論文
2006-06-23