跳到主要內容

臺灣博碩士論文加值系統

(44.211.117.197) 您好!臺灣時間:2024/05/21 02:23
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林珮瑜
研究生(外文):Pei-Yu Lin
論文名稱:具維修作業之雙平行機台排程問題
論文名稱(外文):Two Parallel Machines Scheduling Problem With Maintenance Activities
指導教授:楊達立楊達立引用關係
指導教授(外文):Dar-Li Yang
學位類別:碩士
校院名稱:國立虎尾科技大學
系所名稱:資訊管理研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:60
中文關鍵詞:排程平行機台維修作業啟發式演算法最大完工時間
外文關鍵詞:SchedulingParallel machinespreventive maintenanceGenetic algorithmMakespan
相關次數:
  • 被引用被引用:1
  • 點閱點閱:429
  • 評分評分:
  • 下載下載:21
  • 收藏至我的研究室書目清單書目收藏:0
時代的進步帶動著工商業的發達,各行各業的工廠機器均逐步走向自動化,以取代傳統的人工技術,藉著多台機器以及順暢的製造流程,產品製造的速度比起以往的人工可以快上幾十、甚至百倍,產品品質的穩定度也大大提升。
製造過程中各個工作流程的排序方式以及派工,都會影響到產品最後完工的時間,然而製造者無不希望以最快的速度來完成工作的完工時間。機器在不斷的運作中難免會發生故障需要進行維修,以維持工作流程的順暢並順利完工。
本研究即是針對維修時間固定(rate-modifying maintenance activities)之維修模式,考慮相同平行機台(identical parallel machine)之生產排程問題,先前的研究已經解決全部完工時間總和(total completion time)及全部機台負荷時間總和(total machine load)的問題,本研究將針對機台之最大完工時間(makespan)目標最小化下,設計啟發式演算法,並提出電腦模擬分析結果。


As the development of industrial and commercial progress led the contemporary life, plant machinery of all walks of life are gradually moving towards automation, replacing the traditional manual techniques by multiple machines and smooth manufacturing process. Nowadays, manufacturing speed is faster than previous artificial can dozens, even hundreds of times, and the stability of the product quality is greatly enhanced.
Sort of workflow as well as dispatching, will influence the product manufacturing process and the final completion time. however, the manufacturer wish to finish the manufacturing process as soon as possible. Machine in continuous operation will inevitably malfunction so it need to be repaired in order to maintain the work flow smoothly and successfully.
In this study, we foucus on two repair models : “the rate-modifying activities” and “deteriorating maintenance activities”. Then we consider the two models above respectively with two different production schedules: “identical parallel machine” and “unrelated parallel-machine”. As the previous studies have been resolved the problem of total completion time and total machine load, this study tends to present our argument not only with theoretical analysis but also with all the machine makespan done by computer simulation.


中文摘要 ........i
英文摘要 ........ii
誌謝 ........iii
表目錄 ........vii
圖目錄 ........viii
符號說明 ........ix
第一章 緒論 ........1
1.1 研究動機與背景 ........1
1.2 研究動機與目的 ........2
1.3 研究流程與架構 ........3
第二章 文獻探討 ........4
2.1 排程的定義與介紹 ........4
2.2平行機台 ........6
2.3 LS排程演算法 ........7
2.4 LPT排程演算法 ........7
2.5維修作業 ........7
2.6基因演算法 ........8
2.6.1基因演算法之構成要素 ........8
2.6.2基因演算法應用於排程之相關文獻 ........12
第三章 研究方法 ........13
3.1 問題描述 ........13
3.2 符號定義及假設 ........13
3.3 雙平行機台之維修及派工 ........13
3.3.1 LS法則用於雙平行機台之問題 ........14
3.3.2 LPT於雙平行機台之問題 ........25
第四章 基因演算法 ........38
4.1基因演算法 ........38
4.1.1編碼 ........39
4.1.2初始母體 ........39
4.1.3適合度函數 ........39
4.1.4複製 ........40
4.1.5交配 ........40
4.1.6突變 ........41
4.1.7停止條件 ........41
4.2 執行步驟 ........42
第五章 實驗結果與分析 ........43
5.1參數設定 ........43
5.1.1 LS法則下之排程問題 ........43
5.1.2 LPT法則下之排程問題 ........44
5.1.3 LS法則結合基因演算法 ........44
5.2模擬結果與分析 ........45
第六章 結論與未來研究 ........49
6.1 結論 ........49
6.2 未來研究 ........49
參考文獻 ........51
Extended Abstract ........54
簡歷(CV) ........60

[1] 田國興,2000,“有設置時間之流程型工廠多階段平行機台總排程時間
最小化問題”,中原大學,碩士論文。
[2] 沈育安,2005,“以模擬為基礎之啟發是演算法求解平行機台排程問
題”,國立成功大學,碩士論文。
[3] 陳奕帆,2009,“運用基因演算法解決流程式人力分配排程問題”,國
立虎尾科技大學,碩士論文。
[4] 熊詩敏,2007,“結合優勢性質與基因遺傳演算法於具有整備時間之單
機與非等校平行機台之研究”,元智大學,碩士論文。
[5] Aleksei V. Fishkin , Klaus Jansen , and Monaldo Mastrolilli , 2001,
"Grouping techniques for scheduling problems: simpler and faster",
Proceedings 9th Annual European Symposium on Algorithms, LNCS 2161,
Springer Verlag, pp. 206-217.
[6] Back Thomas and Schwefel Hans Paul, 1993, " An overview of evolutionary
algorithms for parameter optimization". Evolutionary Computation,1, pp.
1-24.
[7] Chen, W. J., 2006, "Minimizing total flow time in the single-machine
scheduling problem with periodic maintenance ", Journal of the Operational
Research Society, vol. 57, pp. 410-415.
[8] Davis.L, 1985, " Applying Adaptive Algorithms to Epistactic Domains",
Proceedings of the International Joint Conference on Artificial Intelligence,
IJCAI85, pp. 162-164.
[9] Graham,R.L., Ruleler,E.L., Lenstra,J.K., Rinnooy Kan,A.H.G., 1979,
"Optimization and approximation in deterministic sequencing and
scheduling: a survey ", Annals of Discrete Mathematics, 5,pp.287-326 .
[10] Grefenstette,J.J., 1986, "Optimization of control parameters for genetic
algorithms", IEEE Transactions on systems,16, pp. 122-128.
[11] Horowitz, E. and Sahni, S., 1976, "Exact and approximate algorithm for
scheduling nonidentical processors", Journal of the Association for
Computing Machinery, 23, pp. 317-327.
[12] Jeffrey Herrmann, Jean-Marie Proth, Nathalie Sauer., 1997, " Heuristics for
unrelated machine scheduling with precedence constraints". European
Journal of Operational Research, 102, pp. 528-537.
[13] John, H. ,1975, "Adaptation in Natural and Artificial System " 83 pp,Univ
Mich Press, Ann Arbor.
[14] Kim Dong Won, Kim Kyong Hee, Jang Wooseung, Chen F Frank, 2002,
"Unrelated parallel machine scheduling with setup times using simulated
annealing". Robotics and Computer Integrated Manufacturing, 18, pp.
223–231.
[15] Kubzin, M.A., Strusevich, V.A., 2005, "Two-machine flow shop no-wait
scheduling with machine maintenance",A Quarterly Journal of Operations
research ,3, pp. 303-313.
[16] Lee, C.Y. and Leon,V.J. , 2001,"Machine scheduling with a rate-modifying
activity", European Journal of Operational Research, 129, pp. 119-128.
[17] Lee, C.Y., Chen, Z.L., 2000, "Scheduling jobs and maintenance activities
on parallel machines", Naval Research Logistics, vol. 47, pp. 145-165.
[18] Lian Yu, Heloisa M. Shih, Michele Pfund, W. Matthew Carlyle and John W.
Fowler, 2002, "Scheduling of unrelated parallel machines: an application to
PWB manufacturing", IIE Transactions, 34, pp. 921-931.
[19] Liao, C. J. and Chen, W. J. , 2003, "Single-machine scheduling with
periodic maintenance and nonresumable jobs ",Computers and Operations
Research, vol. 30, pp. 1335-1347.
[20] M’Hallah Rym and Bulfin R.L., 2005, "Minimizing the weighted number
of tardy jobs on parallel processors", European Journal of Operational
Research,160, pp. 471-484.
[21] Manderick, B. and Spiessens, P., 1994, " How to Select Genetic Operators
for Combinatorial Optimization Problems by Analyzing their Fitness
Land-scape".J.M. Zurada, R. J. Marks II, and Robinson (eds.),IEEE Press,
New York.
[22] Racem Mellouli, Cherif Sadfi, Chengbin Chu, Imed Kacem, 2009,
"Identical parallel-machine scheduling under availability constraints to
minimize the sum of completion times", European Journal of Operational
Research ,Vol.197 , pp. 1150-1165.
[23] Ramiro Varela, Camino R. Vela, Jorge Puente, Alberto Gomez, 2003, "A
knowledge-based evolutionary strategy for scheduling problems with
bottlenecks", Eurpean Journal of Operational Research, vol. 145, pp. 57-71.
[24] Srinivas, M. Srinivas and M. P. Lalit , 1994,"Genetic Algorithms: A
Survey ", IEEE Computer, vol.27, pp. 18-20.
[25] Sun, H., Wang, G., 2003, "Parallel machine earliness and tardiness
scheduling with proportional weights", Computers&Operations
Reserarch,30 , pp. 801-808.
[26] Tadahiko Murata, Hisao Ishibuchi, Hideo Tanaka, 1996, "Multi-objective
genetic algorithm and its applications to flowshop scheduling", Computers
and Industrial Engineering, Vol. 30, No. 4, pp. 957-968.
[27] Tamaki, H., Nishino, E. and Abe, S. ,1999“A Genetic Algorithm Approach
to Multi-Objective Scheduling Problems with Earliness and Tardiness
Penalties,” in Proceedings of the IEEE International Conference on
Evolutionary Computation(ICEC’99), pp. 46-52 [28] Tian Gui Yun, Yin Guofu,Taylor David, 2002, "Internet-based
manufacturing:A review and a new infrastructure for distributed intelligent
manufacturing", Journal of Intelligent Manufacturing, Vol.13, pp. 323-338.
[29] Van der Velde, S.L., 1993, "Duality based algorithm for scheduling
unrelated parallel machines ", ORSA Journal on Computing, 5, pp.
192-205.
[30] Yang, J. and Soh, C. K., 1997, "Structural optimization by genetic
algorithms with tournament selection", ASCE Journal of Computing in
Civil Engineering, 11(3), pp. 195–200.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊