臺灣博碩士論文加值系統

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

摘要………………………………………………………………………………Ⅰ
英文摘要…………………………………………………………………………Ⅱ
致謝………………………………………………………………………………Ⅲ
目錄………………………………………………………………………………Ⅳ
表目錄……………………………………………………………………………Ⅵ
圖目錄……………………………………………………………………………Ⅶ
符號說明…………………………………………………………………………Ⅷ
第一章 緒論………………………………………………………………………1
1.1 研究背景與目的……………………………………………………………1
1.2研究範圍與內容………………………………………………………………2
1.3研究方法………………………………………………………………………2
第二章 文獻探討…………………………………………………………………4
2.1單階段流程型生產之相關文獻….…………………………………………4
2.2單階段開放型生產之相關文獻.……………………………………………5
2.3多階段生產之相關文獻………………………………………………………6
第三章 模式建構…………………………………………………………………8
3.1第二階段開放型生產機台數為雙機之排程研究……………………………8
3.1.1研究假設條件………………………………………………………………9
3.1.2數學規劃之建立……………………………………………………………10
3.1.3啟發式排程演算法之建立…………………………………………………12
3.1.4啟發式排程演算法之範例說明……………………………………………15
3.1.5啟發式排程演算法之Worst Case…………………………………………17
3.1.5.1一般情形…………………………………………………………………17
3.1.5.2特例………………………………………………………………………20
3.1.6分支界線演算法之建立……………………………………………………21
3.2第二階段開放型生產機台數為多機之排程研究……………………………23
3.2.1研究假設條件………………………………………………………………23
3.2.2數學規劃之建立……………………………………………………………24
3.2.3啟發式排程演算法之建立…………………………………………………25
3.2.4啟發式排程演算法之範例說明……………………………………………28
3.2.5啟發式排程演算法之Worst Case…………………………………………31
3.2.5.1多機開放型生產排程之Worst Case…………………………………32
3.2.5.2 第二階段為多機之啟發式排程演算法之Worst Case求解…………33
第四章 結果分析…………………………………………………………………33
4.1第二階段開放型生產機台數為雙機之排程研究……………………………33
4.2第二階段開放型生產機台數為多機之排程研究……………………………41
第五章結論與未來發展…………………………………………………………42
5.1 結論…………………………………………………………………………42
5.2 建議與未來發展……………………………………………………………43
參考文獻…………………………………………………………………………44

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.3.Barany, I., and Fiala, T., Nearly optimum solution of multimachine scheduling problems, Szigma Mathematika Kozgazdasagi Folyoirat, 19 (1982) 177-191(in Hungarian).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.7.Dannenbring, D.G., An evaluation of flowshop sequencing heuristics, Management Science, 23(11) (1977) 1174-1182.8.George, J. and Kyparisis, Koulamas, C., Open shop scheduling with makespan and total completion time criteria, Computers and Operational Research, 27 (2000) 15-27.9.George, J. and Kyparisis, Koulamas, C., Flow shop and open shop scheduling with a critical machine and two operations per job, European Journal of Operational Research, 127 (2000) 120-125.10.Glassey, C. R., and Weng, W. W., Dynamic batching heuristics for simultaneous processing, IEEE Transactions on Semiconductor Manufacturing, 4 (1991) 77-82.11.Gonzalez, T., and Sahni, S., Open shop scheduling to minimize finish time, Journal of the Association for Computing Machinery, 23 (1976) 665-79.12.Gonzalez, T. and Sahni, S., Flowshop and Jobshop Schedules: Complexity and Approximation, Operations Res., 26 (1978) 36-52.13.Graham, R.L., Lawler, E.L., Lenstra, J.K., and Rinnooy, K. A., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5 (1979) 287-326.14.Graves, S. C., A review of production scheduling, Operations Research, 29(4) (1981) 646-675.15.Gupta, J.N.D., A functional heuristic algorithm for the flow shop scheduling problem, Operations Research Quarterly, 22 (1971) 39-47.16.Johnson, S. M., Optimal two and three stage production schedules with set-up time included, Naval Research Quarterly, 1 (1954) 61-68.17.Lee, C. Y., Cheng, T. C. E., and Lin, B. M. T., Minimizing the Makespan in the 3-Machine Assembly-type Flowshop Scheduling Problem, Management Science, 39(5) (1993) 616-625. 18.Nawaz, M., Enscore, R. J. T, and Ham, I., A heuristic algorithm for the m machine, n job flow shop sequence problem, Omega, 11(1) (1983) 91-95.19.Schuurman, Petra, and Woeginger, Gerhard J., Approximation algorithms for the multiprocessor open shop scheduling problem, Operations Research Letters, 24 (1999) 157-163. 20.Pinedo, M., Scheduling: Theory, Algorithms, and Systems, Prentice Hall, Englewood Cliffs, NJ, (1995).21.Sevastianov, SV, and Woeginger, GJ, Makespan minimization in open shops: a polynomial time approximation scheme, Mathematical Programming, 82 (1998) 191-8.22.Su, L. H., and Chou, F. D., Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated, Production Planning and Control, 11(8) (2000) 806-819.23.Tautenhahn, T., Open-Shop-Problem mit Einheitsbear-beitungszeiten, Dissertation, Otto-Von-Guericke-Univer-sitat Mgdeburg, (1993).24.Webster, S.T., A General Lower Bound for the Makespan Problem, Europ. J. Ops Res., Vol., 89 (1996) 516-524.25.Yoshida, T, and Hitomi, K., Optimal two-stage production scheduling with setup times separated, IIE Transaction, 11 (1979) 261-263.