(3.238.7.202) 您好!臺灣時間:2021/03/04 02:36
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:唐澤生
研究生(外文):CHE-SHENG TANG
論文名稱:使用模擬退火演算法求解Just-in-time工作權重個數最大化之排程問題
論文名稱(外文):Scheduling of maximizing the weighted number of just-in-time jobs using simulated annealing heuristic
指導教授:蘇玲慧蘇玲慧引用關係
指導教授(外文):Ling-Huey Su
學位類別:碩士
校院名稱:中原大學
系所名稱:工業與系統工程研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:中文
論文頁數:55
中文關鍵詞:模擬退火排程無相關平行機台Just-in-time
外文關鍵詞:Unrelated parallel machineSimulated AnnealingJust-in-time
相關次數:
  • 被引用被引用:0
  • 點閱點閱:180
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本研究主旨在探討無相關平行機台(unrelated parallel machines)上工作不允許佔先(preemption)之排程問題研究,而研究目標為完成時間剛好為該工作交期之工作權重數量最大化。每個工作具有不同的抵達時間,每個工作還須考量機台限制的條件,也就是工作必須由指定的機台集合中的任一機台上進行加工,機台具有可利用時間限制的條件,以及工作具有順序相依性的整備時間(sequence-dependent set-up time),每個工作會因為排入機台上的前一個工作不同,而需要不同的整備時間。本研究目的為針對此問題擬提出啟發式演算法H1,並將所得啟發解作為模擬退火法(simulated annealing)之起始解,近而求得滿意的近似最佳解,並將此結果與陳科甫(2009)使用網路流量(network flow)進行求解之最佳解進行比較,並透過模擬實驗來分析此啟發解之求解品質。模擬退火法在工作數為20時,經實驗設計分析測試,參數因子具有顯著效果,但當工作數為40時,經實驗設計分析測試,參數因子皆無顯著效果,因此本研究中直接使用啟發式演算法H1與數學規劃模式比較求解誤差,經由實驗結果得知,平均求解誤差為3.39 %,求解效率實驗結果得知啟發式演算法H1的平均求解時間約8.99秒,陳科甫(2009)之平均求解時間為662.611秒。

We consider the unrelated parallel machines with sequence-dependent setup times problem. The objective is using Simulated Annealing to maximize the weighted number of jobs that are completed exactly at their due date. Each job has different arrival time and can only be processed on specified machines. Each machine is not continuously available at all times. Setup magnitude of a job depends on its immediately preceding job on the same machine. And we compared with Chen (2009) to find the deviation . And the computation result will be report.

目 錄
摘要 I
Abstract II
誌 謝 III
目 錄 IV
表目錄 VII
第一章 緒論 1
1.1 研究之背景及目的 1
1.2 研究範圍與內容 1
1.3 研究方法 2
第二章 文獻探討 4
2.1 Just-in-time相關文獻 4
2.2 模擬退火演算法 5
2.3 機台限制、機台可利用區間、順序相依性整備時間之相關文獻 6
第三章 模式建構 9
3.1 本研究之基本假設 9
3.2 符號說明 10
3.3 Rm,NCwin│rj,setup,Mj│ΣwjUj問題定義 11
3.4 模擬退火法之起始解 12
3.4.1 啟發式演算法H1 13
3.4.2 解讀編碼之演算法 17
3.4.3 模擬退火演算法 28
第四章 結果分析 32
4.1 實驗參數設定 32
4.2 模擬退火演算法之實驗參數設計 34
4.3 實驗結果分析 37
第五章 結論與未來展望 43
5.1 結論 43
5.2 建議與未來展望 43
參考文獻 45

圖目錄
圖1.1研究流程圖 3
圖3.1排程S,且工作k排在工作j之後 12
圖3.2 Step 1示意圖 16
圖3.3 Step 3- i之示意圖 16
圖3.4啟發解之甘特圖 17
圖3.5編碼示意圖 18
圖3.6解空間之示意甘特圖 18
圖3.7擾動機制示意圖 19
圖3.8遇機台限制之特殊情況 19
圖3.9工作k排入機台的最早開始時間,且工作k排在工作j之後 21
圖3.10遇機台空間不足夠排入編碼中所有工作之特殊情況 24
圖3.11P1,5排入Just-in-time後機台空間不足讓剩餘工作與整備時間排入 27
圖3.12模擬退火演算法流程圖 31
圖4.1實驗參數因子對演算法H1求解誤差之關係圖 38
圖4.2實驗參數因子對演算法H1求解時間之關係圖 39


表目錄
表3.1 演算法範例資料表(一) 15
表3.2 演算法範例資料表(二) 15
表4.1 實驗參數設定表 34
表4.2 實驗參數設定表 35
表4.3 模擬退火實驗設計結果 36
表4.4  n=20,m=3實驗設計之ANOVA分析 36
表4.5 啟發式演算法與數學規劃模式求解誤差表(λ=0.2) 40
表4.6 啟發式演算法與數學規劃模式求解誤差表(λ=0.5) 41
表4.7 啟發式演算法與數學規劃模式求解誤差表(λ=1) 42


陳科甫 (2009), “平行機台下Just-in-time工作權重個數最大化之排程問題”.
汪定偉、王俊偉、王洪峰、張瑞友、郭哲 (2008), “智能優化方法”.
Andresen M., Brasel H., Morig M., Tusch J., Werner F., Willenius P., (2008), “Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop,” Mathematical and Computer Modelling, 48, 1279–1293.
Baker K.R., (1974), “Introduction to Sequencing and Scheduling,” Wiley, New York.
Breit J., Schmidt G., Strusevich V. A., (2001), “Two-machine open shop scheduling with an availability constraint,” Operations Research Letters 29, 65–77.
Centeno G., Armacost R.L., (1997), “Parallel machine scheduling with release time and machine eligibility restrictions.” Computers & Industrial Engineering, 33(1-2),273-276.
Behnamian J., Zandieh M., Ghomi S.M.T. F, (2009), ” Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm,” Expert Systems with Applications , 36, 9637 – 9644.
Centeno G., Armacost R.L., (2004), “Minimizing makespan on parallel machines with release time and machine eligibility restrictions,” International Journal of Production Research, 42(6) 1243-1256.
Cepek O., Sung S. C. , (2005), “A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines,” Computers & Operations Research, 32, 3265–3271.
Daya M. Ben , Fawzan M. A1, (1996), “A simulated annealing approach for the one-machine mean tardiness scheduling problem,” European Journal of Operational Research, 93, 61-67.
Huegler , Vasko, (1997), “A performance comparison of heuristics for the total weighted tardiness problem,” Computers & Industrial Engineering, 32(4), 753 - 767.
Hiraishi K., Levner E., Vlach M., (2002), “Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs,” Computers & Operations Research, 29(7), 841–848.
Hendel Y., Runge N. and Sourd F. , (2009), “The one-machine just-in-time scheduling problem with preemption,” Discrete Optimization, 6, 10 - 22.
Jin F., Song S., Wu C., (2009), “A simulated annealing algorithm for single machine scheduling problems with family setups,” Computers & Operations Research, 36, 2133–2138.
Jabbarizadeh F., Zandieh M., Talebi D., (2009), “Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints.” Computers & Industrial Engineering.vol.56 Issue.4 1452-1463.
Kirkpatrick S., Gelatt C. D., Vecchi M. P., (1983), “Optimization by Simulated Annealing,” Science, New Series, 220, 671-680.
Kim D. W., Kim K. H., Jang W., Chen F. F., (2002), “Unrelated parallel machine scheduling with setup times using simulated annealing,” Robotics and Computer Integrated Manufacturing, 18, 223–231.
Krajewski L.J., King B.E., Ritzman L.P., Wong D.S., (1987), “Kaban, MRP and shaping the manufacturing environment,” Management Science, 33, 39–57.
Kubzin M. A., Potts C. N., Strusevich V. A., (2009), ” Approximation results for flow shop scheduling problems with machine availability constraints,” Computers & Operations Research , 36, 379 – 390.
Lann A., Mosheiov G, (1996), “Single machine scheduling to minimize the number of early and tardy jobs,” Computers & Operations Research 23, 765–781.
Low C., (2005), “Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines,” Computers & Operations Research, 32, 2013–2025.
Liao L.W., Sheen G.J. , (2008), ”Parallel machine scheduling with machine availability and eligibility constraints.” European Journal of Operations Research,184,458-467.
Liu C. Y., Chang S. C., (2000), “Scheduling flexible flow shops with sequence-dependent setup effects,” IEEE Transactions on Robotics and Automation, 16 (4), 408–419.
Lebacque V., Jost V., Brauner N., (2007), ” Simultaneous optimization of classical objectives in JIT scheduling,” European Journal of Operational Research, 182, 29–39.
Lee K., Leung J. Y.-T., Pinedo M. L., (2009), ” Online scheduling on two uniform machines subject to eligibility constraints,” Theoretical Computer Science, 410, 3975–3981.
Mellouli R., Sadfi C., Chu C., Kacem I., (2007), “Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times,” European Journal of Operational Research, 197, 1150–1165.
Mati Y., (2010), ” Minimizing the makespan in the non-preemptive job-shop scheduling with limited machine availability,” Computers & Industrial Engineering, 19, 89–97.
Metropolis N., Rosenbluth A., Rosenbluth M., Teller A., (1953), “Equation of state calculations by fast computing machines,” Journal of Chemical Physics, 21, 1087-1092.
Naderi B., Ghomi S.M.T. F., Aminnayeri M., (2010), “A high performing metaheuristic for job shop scheduling with sequence-dependent setup times,” Applied Soft Computing, 10, 703–710.
Naderi, Zandieh M., Ghomi Fatemi (2008), “Scheduling job shop problems with sequence dependent setup times.” International Journal of Production Research, 10 1366-5881.
Paula M.R.D., Mateus G. R., Ravetti M.G., (2009), ” A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times,” Computers & Operations Research , 37, 938 – 949.
Roshanaei V., Esfehani M. M. S., Zandieh M., (2010), “Integrating non-preemptive open shops scheduling with sequence-dependent setup times using advanced metaheuristics,” Expert Systems with Applications, 37, 259–266.
Rabadi G., Georgios C., Anagnostopoulos, Mollaghasemi M., (2007), “A heuristic algorithm for the just-in-time single machine scheduling problem with setups: a comparison with simulated annealing,” The International Journal of Advanced Manufacturing Technology, 32, 326–335.
Schmidt G.., (1984), “Scheduling on semi-identical processors.” Zeitschrift f fur Operations Research, A28153-162.
Schmidt G.., (1984), “Scheduling independent tasks with deadlines on semi-identical processors.” Journal of the Operational Research Society, 39, 271-277.
Sung S. C., Vlach M. , (2005), “Maximizing weighted number of just-in-time jobs on unrelated parallel machines,” Journal of Scheduling,8 453-460.
Tuong N. H., Sounhal A. , (2010), “Due dates assignment and JIT scheduling with equal-size jobs,” European Journal of Operational Research, 205, 280–289.
Tuong N. H., Sounhal A. , (2008), “Some New Polynomial Cases In Just-In-Time
Scheduling Problems with Multiple Due Dates,” Proceeding of the Sixth International
conference on Research, Innovation and Vision for the Future in Computing and Communications Technologies, pp. ISBN 978-1-4244-2379-8, 36–41.
Wan G., Yen B. P.-C., (2009), ” Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs,” European Journal of Operational Research, 195, 89–97.
Zandieh M., Ghomi S. M. T. Fatemi , Hosseini S. M. Moattar, (2006), ”An immune algorithm approach to hybrid flowshops scheduling with sequence-dependent setup times,” Applied Mathematics and Computation, 180, 111–127.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 吳文星,〈日據時期臺灣總督府推廣日語運動初探(上)〉,《臺灣風物》第37卷第1期,1987年,頁1-31。
2. 朱傳譽,〈臺灣革命報人林呈祿和他所辦的革命報刊〉,《報學》第3卷第5期,1965年,頁129-138。
3. 王順隆,〈日治時期臺灣人「漢文教育」的時代意義〉,《臺灣風物》49卷4期,1999年12月,頁107-127。
4. 吳文星,〈日據時期臺灣總督府推廣日語運動初探(下)〉,《臺灣風物》第37卷第4期,1987年,頁53-86。
5. 吳文星,〈日據時代臺灣書房之再檢討〉,《思與言》第26卷1期,1988年5月,頁101-108。
6. 吳文星,〈日據時期臺灣教育史料及其研究之評介〉,《臺灣史田野研究通訊》26
7. 吳文星,〈近十年來關於日治時期臺灣教育史研究之動向(1991-2000)〉,《臺灣師大歷史學報》29期,2001年6月,頁 221-238。
8. 吳叡人,〈福爾摩沙意識型態-試論日本殖民統治下臺灣民族運動「民族文化」論述的形成(1919-1937)〉,《新史學》17卷2期,2006年6月,頁143-146。
9. 周婉窈,〈實學教育、鄉土愛與國家認同─日治時期臺灣公學校第三期「國語」教科書的分析〉,《臺灣史研究》第4卷第2期,1999年6月,頁7-55。
10. 周婉窈,〈失落的道德世界-日本殖民統治時期臺灣公學校修身教育之研究〉,《臺灣史研究》8 卷2期,2001年12月,頁1-63。
11. 張圍東,〈日據時代臺灣報紙小史〉,《國立中央圖書館臺灣分館館刊》5卷第3期,1999年3月,頁49-58。
12. 許佩賢,〈日治初期近代學校的創設與地方社會─以公學校經費問題為中心─〉,《新竹師院學報》第18期,2004年6月,頁295-322。
13. 陳培豐,〈殖民地臺灣國語教育的誕生-伊澤修二關於教化、文明與國體的思考〉,《新史學》12卷1期,2001年3月,頁148-149。
14. 陳培豐,〈重新解析殖民地臺灣的國語「同化」教育政策-以日本的近代思想史為座標〉,《臺灣史研究》第7卷2期,2001年6月,頁 1-49。
 
系統版面圖檔 系統版面圖檔