A Branch-and-Bound Algorithm for Minimizing Makespan in a Machine-fixed, Machining-Assembly Flowshop with Parallel Flowshop Lines

DOI Web Site 1 Citations 5 References

Bibliographic Information

Other Title
  • 並列加工フローショップをもつ機械指定型・加工 : 組立スケジューリング問題の最適解法
  • ヘイレツ カコウ フローショップ オ モツ キカイ シテイガタ カコウ クミタテ スケジューリング モンダイ ノ サイテキ カイホウ

Search this article

Description

This paper proposes a branch-and-bound algorithm for minimizing makespan in a machine-fixed, machining-assembly flowshop with two-machine, two-parallel flowshop lines at the machining stage and one robot at the assembly stage. Two parts of each job are machined on prespecified two-machine flowshop lines at the machining stage and these parts are assembled at the assembly stage after all component parts of each job have been machined at the machining stage. Since the optimal schedule is not always a permutation schedule in this problem, it is neccesary to search for an optimal schedule from among (n!)^2 schedules including non-permutation schedules. Therefore, the proposed algorithm consists of two phases, namely first finding an optimal (or nearoptimal) "permutation" schedule and then searching for an optimal schedule in the whole set of schedules including non-permutation schedules starting from a current best permutation schedule obtained in the first phase. A branching rule for searching non-permutation schedules and a lower bound for minimizing makespan in this model are also presented. To evaluate the effectiveness of the proposed method, one hundred instances are generated for each problem with n=10, 15, 20, 30, 50 and are solved by the proposed B&B algorithms. The results of numerical experiments show that the proposed B&B algorithms can solve about 30% of the large sized problems with 50 jobs within one hour.

Journal

Citations (1)*help

See more

References(5)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top