Effective Lower Bounds for Scheduling Problems in Two-stage Hybrid Flowshops

二階段式混合流線型機組排程問題之高效下界函數

林妙聰(Bertrand Miao-Tsong Lin) ； 吳家銘(Jia-Ming Wu)

《管理學報》 21卷3期 (2004/06) Pp. 363-374

https://doi.org/10.6504/JOM.2004.21.03.05

摘要

流線型機組經常在產業中被用以描述組織內部活動或者上下游業者間之關係，在此研究中，我們針對兩項二階段式混合流線型機組的排程問題提出新的下界函數。此兩項問題之前已經被證明為需要龐大計算量的困難問題，為規劃較高效率之分支界定法，我們運用資料重組技術分別設計新的下界函數。本研究中，我們設計並進行一系列的電腦實驗以分析所提出的下界函數的效能，數據結果明確顯示出在分支界定法中使用我們的下界函數可以簡單又有效地排出最佳組合。

關鍵字

混合流線型機組 ； 最小完工時間 ； 下界函數 ； 分支界定法

並列摘要

In the past decades, flowshops have been widely adopted to represent intra-organizational activities as well as inter-organizational relationships in the industrial networks. In this study, we provide lower bounds for two scheduling problems in two-stage hybrid flowshops. The problems under study are already known to be computationally challenging. To facilitate the development of branch-and-bound algorithms, we design lower bounds for the two problems. The lower bounds are derived based upon data rearrangement techniques. Computational experiments are designed and conducted to study the performances of the proposed bounds. Numerical results clearly evince the distinguished capability of the proposed bounds in curtailing unnecessary computation efforts for coping with the two problems under study.

並列關鍵字

Hybrid flowshop ； makespan ； NP-hardness ； lower bound ； branch-and-bound algorithm

參考文獻

Cheng, T. C. E.,B. M. T. Lin,A. Toker(2000).Flowshop batching and scheduling to minimize the makespan.Naval Research Logistics.47,128-144.

Fisher, M. L.(1981).The Lagrangian relaxation method for solving integer programming problems.Management Science.27,1-18.

Fisher, M. L.(1985).An applications-oriented guide to Lagrangian relaxation.Interfaces.15,10-21.

Garey, M. R.,D. S. Johnson(1979).Computers and Intractability: A Guide to the Theory of NP-Completeness.San Francisco, CA:Freedman.

Graham, R. L.,E. L. Lawler,J. K. Lenstra,A. H. G Rinnoy Kan(1979).Optimization and approximation in deterministic sequencing and scheduling: A survey.Annals of Discrete Mathematics.5,287-326.