考量機台維修與機器何適度限制之平行機台排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：73

、訪客IP：18.117.102.80

姓名

洪崇賓(Chung-pin Hung) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

考量機台維修與機器何適度限制之平行機台排程問題
(Scheduling the Jobs and Maintenance Activity on Parallel Machines with Eligibility Constraints)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

在此研究中，我們考慮當極小化最大延遲時間時，在機器合適度限制與變動機器維修時間下，n個不可分割的工作和m台平行機台的排程問題。每台機器累積一段工作時間後必須進行維修以確保作業正確性，每個工作也只能被安排在某些特定的機器上‧進行機器維修的時間點並未固定，在給定機台最大連續工作時間下，決定何時進行維修‧
在極小化最大延遲時間的目標式下，首先我們將允許工作切割的排程問題，利用網路流技術轉變成最大流量問題；接著我們提出一個演算法其結合網路流技術與二元搜尋法尋找其問題的最佳解；最後，將結果作為分支界限法的下界，求取不允許工作切割排程問題的最佳解‧
實驗的分析顯示，分支界限法所產生的節點數比例非常小，顯示提出的淘汰法則強而有力‧我們的演算法能用於12個工作和5台機器問題下而得到一個最佳解。

摘要(英)

In this paper we consider the problem of scheduling n independent and non-preemptive jobs into m parallel machines with eligibility constraints and variable machine maintenance intervals while minimizing the maximum lateness. Each machine is not always available for processing and should be shut down for maintenance to prevent malfunction. Each job is only allowed to be processed on a specific machine set. The maintenance of machine is not a fixed time interval known in advance, and the length of each interval is restricted to the given maximum continuously processing time.
To minimizing the Lmax firstly, we utilize a network flow technique to formulate the scheduling problem of the preemptive jobs into a series of maximum flow problems. Then, we propose an algorithm which combines a network flow technique and a binary search procedure to solve the problem optimally. Finally, we use the result of the preemptive scheduling problem as the lower bound of the proposed branch and bound algorithm to get the optimal solution of the study problem.
Computational analysis shows that the effectiveness of eliminating rules proposed is powerful and very low percentage of nodes is generated by the branch and bound algorithm. Our algorithm can get the optimal solution for the problem with up to 12 jobs and 5 machines.

關鍵字(中)

★ 機器可用時間限制
★ 平行機台
★ 網路流
★ 分枝界限法
★ 機器維修工作
★ 機器合適度限制

關鍵字(英)

★ parallel machine
★ Network flow
★ branch and bound

論文目次

Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem Description 3
1.3 Research Objectives 4
1.4 Research methodology and frame work 5
1.4.1 Research methodology 5
1.4.2 Research Framework 5
Chapter 2 Literature Review 7
2.1 Machine Availability 7
2.2 Machine Eligibility Constraint 9
2.3 Network Flow Approach 10
2.4 Machine Availability and Eligibility Constraint 11
Chapter 3 Branch and Bound Algorithm 13
3.1 Notation 13
3.2 Bounding Scheme 16
3.2.1 Obtaining the time epoch set and determining the time interval 18
3.2.2 Constructing network for the based problem with 20
3.2.3 Upper bound UB and Lower bound LB of the base problem 22
3.2.4 Binary search algorithm 23
3.3 Branching Scheme 27
3.3.1 Dominance Rules 29
3.4 Branch and bound algorithm 32
Chapter 4 Computational Analysis 36
4.1 Test Problem Generation 36
4.2 Validation of the Branch and Bound Algorithm 37
4.3 Performance of the Branch and Bound Algorithm 40
Chapter 5 Conclusion 46
5.1 Research contribution 46
5.2 Research limitations 47
5.3 Further Research 47
References 48
Appendix A Proposed Theorem (Sheen and Liao (2007)) 51
Appendix B Proposed Proposition (Sheen and Liao (2007)) 53
Appendix C Data Table C1 – C13 54

參考文獻

1. Adiri, I., J. Bruno, E. Frostig, A. H. G. Rinnooykan. 1989. Single machine flow-time scheduling with a single breakdown. ACTA Information 26 679-696.
2. 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.
3. 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.
4. Centeno, G., R. L. Armacost. 1997. Parallel machine scheduling with release time and machine eligibility restrictions. Computers & Industrial Engineering 33 273-276.
5. Centeno, G., R. L. Armacost. 2004. Minimizing the makespan on parallel machines with release time and machine eligibility restricitions. International Journal of Production Research 42 1243-1256.
6. Horn, W. A. 1974. Some simple scheduling algorithms, Naval Research Logistics Quarterly 21 177-185.
7. Hwang, H. C., S. Y. Chang, K. Lee. 2004. Parallel machine scheduling under a grade of service provision. Computers & Operation Research 31 2055-2061.
8. Ji, M., Y. He, T. C. E. Cheng. 2007. Single-machine scheduling with periodic maintenance to minimize makespan. Computer & Operations Research 34 1764-1770.
9. Kellerer H. 1998. Algorithm for multiprocessor scheduling with machine release time. IIE Transactions, 30, 991-999.
10. Labetoulle J., E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooykan. 1984. Preemptive scheduling of uniform machines subject to release dates. In: Pulleyblank WR (Eds.). Progress in Combinatorial Optimization, New York: Academic Press 245-261.
11. Lee, C. Y. 1996. Machine scheduling with an availability constraint, Journal of Global Optimization, 9, 395-416.
12. Lee, C. Y., Z. L. Chen. 2000. Scheduling jobs and maintenance activities on parallel machines. Naval Research Logistics 47 145-165.
13. Lee, C. Y., C. S. Lin. 2001. Single machine scheduling with maintenance and repair rate-modifying activities. European Journal of Operation Research 135 493-513.
14. Liao, C. J., W. J. Chen. 2003. Single machine scheduling with periodic maintenance and nonresumable jobs. Computers & Operation Research 30 1335-1347.
15. Liao, W., G. J. Sheen. 2007. Parallel machine scheduling with machine availability and eligibility constraints. European Journal of Operational Research Article in press.
16. Lin, C. F. 2006. Branch and bound algorithm for parallel machine scheduling with availability and eligibility constraints. Unpublished Master Thesis, Institute of Industrial Management, National Central University
17. Lin, Y., W. Li. 2004. Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research 156 261-266.
18. Lu, B. H. 2005. Parallel machine scheduling with machine availability and
eligibility constraints. Unpublished Master Thesis, Institute of Industrial
Management, National Central University.
19. Pinedo, M. 2002. Scheduling: theory, algorithm and system 2nd ed. Englewood Cliffs, NJ: Prentice-Hall.
20. Qi, X., T. Chen, F. Tu. 1999. Scheduling the maintenance on a single machine. The Journal of the Operation Research Society 50 1071-1078.
21. Sanlaville, E. 1995. Nearly online scheduling of preemptive independent tasks. Discrete Applied Mathematics 57 229-241.
22. Schmidt, G. 2000. Scheduling with limited machine availability. European Journal of Operational Research 121 1-15.
23. Sheen, G. J., L.W. Liao. 2007. Scheduling machine-dependent jobs to minimize lateness on identical machines with availability constraints. Computers & Operations Research 34 2266-2278.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2007-7-21

推文