雙階段流程型與開放型生產型態之排程研究

Study on the Two-Stage of Flowshop and Openshop Scheduling Problems

丁威清(Wei-Ching Ting)

指導教授 ： 蘇玲慧

中原大學/工學院/工業工程研究所/碩士(2002年)

https://doi.org/10.6840/cycu200200365

摘要

本研究將針對雙階段流程型與開放型生產型態之排程問題加以探討，其中衡量指標為考量總完成時間最小化，而問題之複雜度早已被證實為NP-hand，因此發展一啟發式排成演算法，以縮短求解時間並使其求解品質達到一定的水準。
本研究分為兩部分來探討，第一部份探討第一階段為任意機台數而第二階段為雙機生產之排程問題；第二部份探討第一階段與第二段皆為任意機台數之排程問題，而兩部分的目標皆為總完成時間最小化。
本研究之啟發式演算法是先將整個生產作業視為一個較大的流程型生產，利用CDS(The Campbell, Dudek, and Smith)法則的觀念來安排工件進入整個系統的先後順序，之後採用凍結事件程序(Frozen-Event Procedure)將第二階段開放型生產排程問題由動態問題轉換成靜態的問題，之後再利用LAPT(Longest Alternate Processing Time)法則的觀念來安排已在第一階段完成加工的工件至第二階段進行加工。針對此兩部分的問題分別建立數學規劃模式以及分支界線演算法，以驗證啟發是排程演算法之正確性，以及評估啟發式排程演算法求解品質之基準，並提出此啟發式排程演算法之Worst Case。
本研究的啟發式演算法提供了雙階段流程型與開放型兩不同加工型態之間排程問題的解決方法，使此相關方面的管理者能夠以迅速且有效方式來解決此相關方面的排程問題。

關鍵字

雙階段生產排程 ； 流程型生產 ； 分支界線演算法 ； 開放型生產 ； Worst Case

並列摘要

In this paper we consider two-stage of flowshop and openshop scheduling problems. The performance considered is the minimization makespan. Since the complexity of the problem proved to be NP-hard, a heuristic algorithm is provided to shorten require time and solve this NP-hard problem.
Two cases are considered in this study. In the first case, the number of processor in the first stage is arbitrary and numbers of processor in the second stage are two. In the second case, the number of processor in the any stage is arbitrary. Both objectives of the two cases are minimization makespan.
First, the heuristic algorithm treats all operations as a flowshop scheduling problems. A CDS (The Campbell, Dudek, and Smith) is proposed to arrange the sequence of which all operations entered the system. A frozen-event procedure is proposed to transform dynamic scheduling problem in the second stage into static ones, moreover, a LAPT (Longest Alternate Processing Time) is proposed to arrange that the operation which has been executed in the first stage. For each case, the mathematical programming models and the branch and bound algorithm are formulated to validate the performance of those heuristic scheduling algorithms, and we also propose the worst case of those heuristic scheduling algorithms.

並列關鍵字

Worst Case ； flowshop ； openshop ； two stages scheduling ； Branch and Bound

參考文獻

1. Achugbue, J.O., and Chin, F.Y., Scheduling the Openshop to Minimize Mean Flow Time, SIAM Journal on Computing, 11 (1982) 709-20.

2. Ahmadi, J.H., Ahmadi, R.H., Dasu, S. and Tang, C.S., Batching and scheduling jobs on batch and discrete processors, Operations Research, 39(4) (1992) 750-763.

4. Chen, B., and Strusevich, V.A., Worst-case analysis of heuristics for open shops with parallel machines, Eur. J. Oper. Res., 70 (1993) 379-390.

5. Chang, S. Suang, Young, H. K., and Sang, H. Y., A problem reduction and decomposition approach for scheduling for a flowshop of batch processing machines, European Journal of Operational Research, 121 (2000) 179-192.

6. Compbell, H.G., Dudek, R.A., and Smith, M.L., A heuristic algorithm for the ’N’ job ’M’ machine sequence problem, Management Science, 16 (1970) 630-637.