A Branch-and-Bound Based Heuristic Algorithm for Minimizing Makespan in Machining-Assembly Flowshop Scheduling

作     者：Kazuko Morizawa 

作者机构：Graduate School of Engineering Osaka Prefecture University Osaka Japan 

出 版 物：《Engineering（科研）》 (工程（英文）（1947-3931）)

年 卷 期：2014年第6卷第13期

页      面：877-885页

学科分类：1002[医学-临床医学] 100214[医学-肿瘤学] 10[医学] 

主　　题：Scheduling Heuristic Branch and Bound Algorithm Machining-Assembly Flowshop Makespan 

摘      要：This paper proposes a heuristic algorithm, called list-based squeezing branch and bound algorithm, for solving a machine-fixed, machining-assembly flowshop scheduling problem to minimize makespan. The machine-fixed, machining-assembly flowshop consists of some parallel two-machine flow lines at a machining stage and one robot at an assembly stage. Since an optimal schedule for this problem is not always a permutation schedule, the proposed algorithm first finds a promising permutation schedule, and then searches better non-permutation schedules near the promising permutation schedule in an enumerative manner by elaborating a branching procedure in a branch and bound algorithm. The results of numerical experiments show that the proposed algorithm can efficiently provide an optimal or a near-optimal schedule with high accuracy such as mean relative error being less than 0.2% and the maximum relative error being at most 3%.