具多次彈性維護限制之單一機台求極小化總完工時間排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：13

、訪客IP：3.141.32.217

姓名

李明倫(Min-Lun Lee) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

具多次彈性維護限制之單一機台求極小化總完工時間排程問題
(Single Machine Scheduling with Flexible Maintenance Periods for Minimizing Total Completion Time)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

考量機台的維護保養工作在排程規畫上具有其重要性，若安排得宜，將可以避免因為故障造成不可預期的損失，故我以機台維護保養的排程做為研究主題。本研究探討在單一機台環境下，機台須進行多次維護保養工作，每次維護具有不同的維護時間，並且必須在前一維護工作完成後的特定時間區間內開始下一次的維護，其目的在極小化總完工時間的排程問題。
本研究首先提出了一個混整數規劃模型，考慮工作與工作，工作與維護，兩兩之間的順序關係，依此關係對其開始、結束時間的限制建構模型。接著，本研究提出了一分枝界限法，考量每個可用區間的時間長度，對可能排入的工作從數量、加工時間上進行篩選。但由於最佳解演算法可處理問題規模較小，為了因應問題規模較大的狀況，我們也嘗試在這個問題上採用short processing time first(SPT)法則，並分析其績效。
由實驗的結果可以發現，本研究所提出之分枝定界法可以有效的的求得最佳解，也能刪去不必要的節點達99.9%以上。此外，應用本研究提出的分支定界法與SPT法則來求解此問題互有利弊，且對於SPT法則的績效較差的情況，本研究的分支定界法通常有較優的表現。

摘要(英)

In this research, we consider the scheduling problem of processing n jobs on a single machine along with several maintenance activities. Each maintenance have different duration, and has to be perform within a period between it minimum time lag and maximum time lag. The objective is to minimize the total completion time.
We proposed a math programming and a branch and bound algorithm to solve the problem optimally. The math programming model is base on the sequential order of jobs and maintenances, use it to restrict the starting time and ending time of each job and maintenance. The branch and bound algorithm consider the capacity and flexibility of available intervals between maintenances and branch the every possible job set to an interval. However, optimal approaches may not solve a problem with large problem size. So the performance of applying SPT rule to this problem is also tested and analysis in this research.
Computation analysis shows that our proposed methods can solve the problem optimally and the branch and bound algorithm is can eliminate more than 99.9% unnecessary nodes. Besides, applying our algorithm or SPT rule to this problem both have goodness and shortcoming. For those instances that SPT rule has large error, our algorithm usually performs better.

關鍵字(中)

★ 機器排程
★ SPT法則
★ 彈性維修
★ 分枝定界法

關鍵字(英)

論文目次

摘要 i
Abstract ii
Table of Contents iii
List of Figures v
List of Tables vii
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 Frameworks 5
1.4.1 Research Methodology 5
1.4.2 Research Framework 5
Chapter 2 Literature Review 7
2.1 Flexible maintenance and its restriction rule 7
2.2 Scheduling Problems with Available constraints for minimizing total completion time 9
Chapter 3 Methodology 12
3.1 Notation 12
3.2 Mixed binary integer programming 13
3.3 Branch and Bound Algorithm 14
3.3.1 Basic Propositions 15
3.3.2 Branching scheme 15
3.3.3 Bounding Scheme 20
3.3.4 Branch and Bound Algorithm 23
3.4 SPT-maxTL heuristic 26
Chapter 4 Computational Analysis 27
4.1 Generating Test Problems 27
4.2 Validation Test 28
4.2.1 Enumeration Branching 29
4.2.2 Result of validation test 30
4.3 Performance of the branch and bound algorithm 32
4.4. Performance of SPT-maxTL heuristic 44
Chapter 5 Conclusion 50
5.1 Research Contribution 50
5.2 Research Limitation 50
5.3 Further Research 51
References 52
Appendix 1. Algorithm to find job combination 54

參考文獻

Chen, J. S. (2006). Optimization models for the machine scheduling problem with a single flexible maintenance activity. Engineering Optimization, 38(1),53-71
Kacem, I., Sadfi, C. & El-Kamel, A. (2005). Branch and bound and dynamic programming to minimize the total completion times on a single machine with availability constraints. Proceedings of 2005 IEEE International Conference on Systems, Man, Cybernetics, 2, 1657-1662.
Lee, C. Y. & Liman, S. D. (1992). Single machine flow-time scheduling with scheduled maintenance. Acta Informatica, 29, 375-382.
Lee, C. Y. & Chen, Z. L. (2000). Scheduling of jobs and maintenance activities on parallel machine. Naval Research Logistics, 47(2), 145-165.
Lee, C. Y. (1996). Machine Scheduling with an availability constraint. Journal of Global Optimization, 9, 395-416.
Mellouli, R., Sadfi, C., Chu, C., & Kacem, I. (2008). Identical parallel machine scheduling under availability constraints to minimize the sum of completion times. European Journal of Operational Research, 197, 1150-1165.
Mellouli, R., Sadfi, C., Chu, C., & Kacem, I. (2006). MSPT2 heuristic and dynamic programming method for the parallel machine scheduling problem with scheduled preventive maintenance. Proceedings of 2005 IEEE International Conference on Service System and Service Management, 2, 1264-1270.
Chen, J. S. (2006). Single-machine scheduling with flexible and periodic maintenance. The Journal of the Operational Research Society, 57(6), 703-710.
Pinedo, M. (2008), Scheduling: Theory, Algorithm and System (3th ed), New York: Prentice-Hall.
Ma, Y., Chu, C., & Zuo, C. (2009). A survey of scheduling with deterministic availability constraints. Computers and Industrial Engineering, 58, 199-211.
Sadfi, C., Penz, B., Rapine, C., Blazewicz, J., & Formanowicz, P. (2003). An improved approximation algorithm for the single machine total completion time scheduling problem with available constraints. European Journal of Operational Research, 161, 3-10.
Schmidt, G. (2000). Scheduling with limited machine availability. European Journal of Operational Research, 121, 1-15.
Sun, K. & Li, H. (2009). Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines. Int. J. Production Economics, 124, 151-158.
Xu, D. & Yin, Y. (2011). On single-machine scheduling with flexible maintenance activities. Int. J. Adv. Maunf. Techol, 56, 1139-1145.
Xu, D., Sun, K., & Li, H. (2006). Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan. Computers & Operations Research, 35, 1134-1349.
Yang, S. L., Ma, Y., Xu, D. L., & Yang J., B. (2011). Minimizing total completion time on a single machine with a flexible maintenance activity. Computers & Operations Research, 38, 755-770.

指導教授

沈國基

審核日期

2013-7-19

推文