(3.231.29.122) 您好!臺灣時間:2021/02/25 15:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:丁威清
研究生(外文):Wei-Ching Ting
論文名稱:雙階段流程型與開放型生產型態之排程研究
論文名稱(外文):Study on the Two-Stage of Flowshop and Openshop Scheduling Problems
指導教授:蘇玲慧蘇玲慧引用關係
指導教授(外文):ling-Huey Su
學位類別:碩士
校院名稱:中原大學
系所名稱:工業工程研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:46
中文關鍵詞:雙階段生產排程流程型生產分支界線演算法開放型生產Worst Case
外文關鍵詞:Worst Caseflowshopopenshoptwo stages schedulingBranch and Bound
相關次數:
  • 被引用被引用:1
  • 點閱點閱:92
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1

本研究將針對雙階段流程型與開放型生產型態之排程問題加以探討,其中衡量指標為考量總完成時間最小化,而問題之複雜度早已被證實為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.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔