機器具可用區間限制與工件迴流特性之零工式生產排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：25

、訪客IP：18.118.20.134

姓名

黃偉婷(Wei-ting Huang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

機器具可用區間限制與工件迴流特性之零工式生產排程問題
(Job Shop Scheduling with Machine Availability Constraint and Recirculation Jobs)

相關論文

★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立	★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究	★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用	★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究	★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討－以平面式觸控面板產業為例	★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例	★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例	★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例	★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

本研究主旨將探討機器具可用區間限制以及工件迴流特性下之零工式生產排程(Job Shop Scheduling)問題。在機器具可用區間限制下，在傳統零工式生產排程中，一般假設機台作業時間為連續性不中斷的情形，但在實際的生產排程環境中，機器設備會執行一段時間後，機台會做維修保養，在生產過程中發生故障造成工廠成本的損失；而工件迴流(Recirculation Jobs)現象係指工件重複拜訪機器兩次以上之情形。因此，本論文將主要研究方向為如何生產一個合理且最佳的排程，並極小化最短完工時間(makespan)。
本研究先將機器具可用區間限制轉成虛擬作業，並利用離散圖形(Disjunctive Graph)呈現。為了提供最佳解，本文採用分支定界法(Branch and Bound Algorithm)來求解此類問題。首先，安排最少虛擬作業於各機台中並加入no-wait特性，並修正虛擬作業和其他作業間排定情形；後來將利用分支法則，決定分枝的作業節點並計算下界值。在過程中，分支過程可能為不可解，透過Propositions發展新增虛擬作業方式來變成可行解。反覆持續更新分支節點的完工時間以及下界值，如此便可順利的使用刪除法則剔除毋須的分支，以求得最佳配置與最佳順序。
實驗結果透過窮舉法和分支定界法相比較，可知道14題測試題中兩者方法計算最佳解的結果為相同。而評估分支定界法的效率，分為2組實驗測試，每組均有6題測試題，透過評估本文在刪除節點數有比窮舉法來的有效率。

摘要(英)

In the thesis we consider the job shop scheduling with machine availability restrictions and recirculation jobs while minimizing the makespan. Each machine is not continuously available at all time. On the other hand, each machine is not always available for processing. Besides, each job may visit a machine more than once and has to be processed at an available interval.
We propose the branch and bound algorithms to solve the scheduling problem optimally. First, we decide that the minimum number of each machine unavailable interval. Then, we modify disjunctive graph technique to model the scheduling problem with the dummy jobs that is denoted by each machine unavailable interval. Also, each dummy job is no-wait attribute. Second, we develop the branching scheme to generate the entire tree and use propositions to transfer infeasible solutions to feasible. Then, determine the lower bound of the makespan as the length of the longest path. Finally, we use algorithm to recalculate the scheduling problem until find an optimal solution.
Experimental designs are used to evaluate and analyze the performance of the algorithm. Computational analysis shows that the lower bound proposed is effective and can eliminate more than 60% node when the total operation numbers. The results show that the lower bound affect the solution time used by branch and bound algorithm.

關鍵字(中)

★ 零工式生產
★ 分支定界法
★ 機器可用區間限制
★ 迴流

關鍵字(英)

★ Machine available interval constraint
★ Reentrant
★ Job shop scheduling
★ Branch and bound algorithm

論文目次

中文摘要 i
Abstract ii
目錄 iii
圖目錄 v
表目錄 vii
第一章緒論 1
1.1 研究背景與動機 1
1.2 問題描述 2
1.3 問題假設 3
1.4 研究目的 3
1.5 研究方法與流程 3
1.5.1 研究方法 3
1.5.2 研究流程 4
第二章文獻探討 6
2.1 零工式生產排程 6
2.1.1 零工式生產排程簡介及分離圖模式介紹 6
2.1.2 零工式生產排程相關文獻 8
2.2 機器可用時間限制 10
2.3 工件具迴流特性 12
第三章演算法流程 13
3.1 問題定義與名詞解釋 13
3.1.1 問題描述 13
3.1.2 名詞解釋 14
3.1.3 符號定義 17
3.2 分離圖模型 19
3.3 Proposition彙整 20
3.4 分支定界法建構 28
3.4.1 分支法則 28
3.4.2 下界值界限法 31
3.5 演算法流程圖 33
第四章實驗設計與分析 36
4.1 實驗環境 36
4.2 實驗參數設定 36
4.3 實驗測試題 39
4.4 實驗數據分析 39
4.5 評估分支定界法 40
第五章結論 43
5.1 研究結論與貢獻 43
5.2 研究限制 43
5.3 未來研究方向 44
References 45
附錄一 47

參考文獻

1. Bartusch, M., R.H. Mohring, and F.J. Radermacher. 1988. Scheduling project networks with resource constraints and time windows. Annals of Operation Research 16 201-240.
2. Birger, F., K. Neumann, and C. Schwindt. 2001. Project scheduling with calendars. OR Spektrum 23 325–334.
3. Blazewicz, J., M. Drozdowski, P. Formanowicz, W. Kubiak, and G.. Schmidt. 2000. Scheduling preemptable tasks on parallel processors with limited availability. Parallel Computing 26 1195-1211.
4. Blazewicz, J., P. Dell’Olmo, M. Drozdowski, and P. Maczka. 2003. Scheduling multiprocessor tasks on parallel processors with limited availability. European Journal of Operational Research 149 377-389.
5. Brucker, P., A. Drexl, R. Mohring, K. Neumann and E. Pesch. 1999. Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research 112 3–41.
6. Carlier, J., and E. Pinson. 1989. An algorithm for solving the job shop problem. Management Science 35 164–176.
7. Carlier, J., and E. Pinson. 1990. A practical use of Jackson’s preemptive schedule for solving the job-shop problem. Annals of Operations Research 26 269–287.
8. Carlier, J., and E. Pinson. 1994. Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research 78 146–161.
9. Centeno, G., and R.L. Armacost. 1997. Parallel machine scheduling with release time and machine eligibility restrictions. Computers & Industrial Engineering 33 273-276.
10. Centeno, G., and R.L. Armacost. 2004. Minimizing makespan on parallel machines with release time and machine eligibility restrictions. International Journal of Production Research 42 1243-1256.
11. He, R.J. 2005. Parallel machine scheduling problem with time windows: a constraint programming and tabu search hybrid approach. Proceedings of the Fourth International Conference on Machine Learning and Cybernetics 18-21 August.
12. Heilmann, R. 2003. A branch and bound procedure for the multi-mode resource constrained project scheduling problem. European Journal of Operational Research 144 348-365.
13. Hwang, H.C., and S.Y. Chang. 1998. Parallel machines scheduling with machine shutdowns. Computers & Mathematics with Applications 36 21-31.
14. Hwang, H.C., S.Y. Chang, and K. Lee. 2004. Parallel machine scheduling under a grade of service provision. Computers & Operation Research 31 2055-2061.
15. Kellerer, H. 1998. Algorithm for multiprocessor scheduling with machine release time. IIE Transactions 30 991-999.
16. Lee, C.Y. 1996. Machine scheduling with an availability constraint. Journal of Global Optimization 9 395-416.
17. Lee, C.Y., Y. He, and G. Tang. 2000. A note on parallel machine scheduling with non-simultaneous machine available time. Discrete Applied Mathematics 100 133-135.
18. Lin, Y., and W. Li. 2004. Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research 156 261-266.
19. Liu, Z., and E. Sanlaville. 1995. Preemptive scheduling with variable profile. precedence constraints and due dates. Discrete Applied Mathematics 58 253-280.
20. Mason, S. J., and K. Oey. 2003. Scheduling complex job shops using disjunctive graphs: a cycle elimination procedure. Int. J. Prod. Res. 41 981–994.
21. Neumann, K., and C. Schwindt. 1997. Activity-on-node networks with minimal and maximal time lags. OR Spektrum 19 205-217.
22. Neumann, K., C. Schwindt, and J. Zimmermann. 2003. Order-based neighborhoods for project scheduling with nonregular objective functions. European Journal of Operational Research 149 325-343.
23. Pinedo, M. 2002. Scheduling: theory, algorithm and system 2nd ed. Englewood Cliffs, NJ: Prentice-Hall.
24. Rojanasoonthon, S., and J. Bard. 2005. A GRASP for parallel machine scheduling with time windows. INFORMS Journal on Computing 17 32-51.
25. Sanlaville, E. 1995. Nearly online scheduling of preemptive independent tasks. Discrete Applied Mathematics 57 229-241.
26. Schmidt, G. 1988. Scheduling independent tasks with deadlines on semi-identical processors. Journal of the Operational Research Society 39 271-277.
27. Schmidt, G. 2000. Scheduling with limited machine availability. European Journal of Operational Research 121 1-15.
28. Sheen, G..J., and L.W. Liao. 2007. A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags. European Journal of Operational Research 181 102-116.
29. Ullman, J.D. 1975. NP-complete scheduling problems. Journal of Computer and System Sciences. 10 384-393.
30. Wang, M. Y., S. P. Sethi, and S. L. van de Velde. 1997. Minimizing makespan in a class of reentrant shops. Operations Research 45 702–712.
31. Yu, Y. D. 1999. Parallel machine scheduling with eligibility constraints for reentrant job. Unpublished Master Thesis, Institute of Industrial Management, National Central University
32. Zoghby, J., J. W. Barnes, and J. J. Hasenbein. 2005. Modeling the reentrant job shop scheduling problem with setups for metaheuristic searches. European Journal of Operational Research 167 336-348.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2011-7-19

推文