考量平行機台之彈性維護週期求極小化總完工時間排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：36

、訪客IP：3.14.133.127

姓名

李彥漢(Yen-han Li) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

考量平行機台之彈性維護週期求極小化總完工時間排程問題
(Parallel Machine Scheduling with Flexible Maintenance Activity 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 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

本研究主旨在考慮機台具有彈性維護限制下，n個不可分割的工作和m台平行機台的排程問題求解最小化總完工時間。大部分的排程問題大多假設機台為連續可用，但此假設並不適用於實際工業環境，而近年來有越來越多研究考慮機台有可用區間的限制。彈性維護限制為機台無法一直處於可加工的工作狀態，每台機台在連續工作一段時間後必須進行維護以防止機台的故障發生和維護工作的良率。本研究給定機台最大連續工作時間和機台最小連續工作時間在連續的兩個維護中間，意旨機台維護的開始時間為不固定，限制在機台最大連續工作時間和機台最小連續工作時間內決定何時執行維護作業，此限制為機台具有彈性維護周期限制(Machine with flexible maintenance period)。
我們提出一個分枝界限演算法去尋找這個問題的最佳解。我們根據四個proposition來尋找最佳解。首先，這個問題上沿用區間內shortest processing time first(SPT)法則會找到最佳解。然後，考量每個可用區間的時間長度，決定多少工作可以排入和決定維護開始的時間。最後，lower bound、upper bound和dominance proposition用來消除無法成為最佳解不必要的節點。
實驗的分析顯示，分枝界限法配合提出的支配法則後，節點的產生率非常小，都在1.0E-4%以下，我們發現節點的產生率會隨著工作數目得增加而減少。

摘要(英)

In this paper we consider the problem of scheduling n nonresumable jobs on m identical parallel machines with flexible maintenance activities, and the objective is to minimize total completion time of jobs. In this past, the majority of scheduling study assumed that machines are continuously available at all time. In recent year, there are more and more studies consider that each machine is not continuously available. The flexible maintenance activity constraint means that each machine must be maintained after it continuously working for a period of time to prevent breakdown of machine and keep the quality of process jobs. This study given the minimum working time and maximum working time within any two consecutive maintenance activities, which means the starting time of unavailability period are decision variable together with jobs to be scheduled.
We propose a branch and bound algorithm to find the optimal solution for our problem. Four propositions of an optimal solution are identified. First, we adopt that interval shortest processing time (SPT) algorithm will find optimal solution. Then, consider the capacity of available intervals and decide how many jobs processing in each available interval and when the maintenance activities starting. Finally, a lower bound, upper bound and dominance proposition are proposed to eliminate unnecessary node.
Computational analysis shows that the rate of nodes generated by using branch and bound algorithm with proposed propositions and properties is very low. It generated ratio is less than 1.0E-4%, we observe that the rate of generated nodes is decreasing with the number of jobs increase.

關鍵字(中)

★ 排程
★ 平行機台
★ 機台彈性維護周期
★ 分枝界限法

關鍵字(英)

★ Scheduling
★ Parallel machines
★ Flexibility and period maintenance activity
★ Branch and bound algorithm

論文目次

摘要 i
Abstract ii
致謝 iv
Table of Content v
List of Figures vi
List of Tables vii
Chapter 1 Introduction 1
1.1 Background and motivation 1
1.3 Research objectives 4
1.4.1 Research methodology 4
1.4.2 Research framework 5
Chapter 2 Literature review 7
2.1 Machine with flexible maintenance activity and its restriction rule 7
2.2 Machine availability constraints for total completion time 12
Chapter 3 Methodology for the scheduling problem 16
3.1 Notations 16
3.2 Branch and bound algorithm 17
3.2.1 Basic propositions 17
3.2.2 Branching scheme 23
3.2.3 Dominance proposition 26
3.2.4 Bounding scheme 27
3.2.5 Algorithm 31
Chapter 4 Computational analysis 35
4.1 Generating test problem 35
4.2 Validation of the branch and bound algorithm 36
4.3 Performance of the branch and bound algorithm 37
4.4 Compare with similar problem 46
Chapter 5 Conclusion 48
5.1 Research contribution 48
5.2 Research limitation 49
5.3 Further research 49
References 51
Appendix 54

參考文獻

Arts, R. H. P. M., Knapp, G. M., Lawrence, M. Jr. (1998), Some aspects of measuring maintenance performance in the process industry, Journal of Quality in Maintenance Engineering, 4, 6-11.
Brucker, P., Kravchenko, S. (1999), Preemption can make parallel machine scheduling problems hard. Technical Report, Osnabrucker Schiften zur Mathematik, Reihe P, 211.
Chen, J. S. (2006), Optimization models for the machine scheduling problem with a single flexible maintenance activity, Engineering Optimization, 38, 53-71.
Chen, J. S. (2008), Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, European Journal of Operational Research, 190, 90-102.
Hsu, W. J., (2013), Parallel machine scheduling with flexible maintenance activities for minimizing total completion time, National Central University, 碩士論文.
Lee, C. Y., Liman, S. D. (1993), Capacitated two-parallel machine scheduling to minimize sum of job completion times, Discrete Applied Mathematics, 41, 211–222.
Lee, C. Y. (1996), Machine scheduling with an availability constraint. Journal of Global Optimization, 9, 395–416.
Lee, C. Y., Chen Z. L. (1998), Scheduling of Jobs and Maintenance Activities on Parallel Machines, Naval Research Logistics, 47, 61-67.
Levin, A., Mosheiov, G., Sarig, A. (2009), Scheduling a maintenance activity on parallel identical machines, Naval Research Logistics, 56, 33–41.
Liao, C. J., Chao, C. W., Lin, C. H. (2009), Minimizing the sum of job completion times on capacitated two-parallel machines. European Journal of Operational Research, 197, 475-781.
Mellouli, R., Sadfi, C., Chu, C., Kacem, I. (2009), Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times. European Journal of Operational Research, 197, 1150-1165.
Pinedo, M. (2008), Scheduling: theory, algorithm, and systems. 3rd ed., New Jersey: Prentice-Hall.
Sanlaville, E., Schmidt, G. (1998), Machine scheduling with availability constraints, Acta Informatica, 35, 795-811.
Schmidt, G. (2000), Scheduling with limited machine a availability, European Journal of Operational Research, 4, 6-11.
Sun, K., Li, H. (2010), Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines, International Journal of Production Economics, 124, 151-158.
Su, L. H., Tsai, H. L. (2010), Flexible preventive maintenance planning for two parallel machines problem to minimize makespan, Journal of Quality in Maintenance Engineering, 16, 288-302.
Sbihi, M., Varnier, C. (2008), Single-machine scheduling with periodic and flexible periodic maintenance to minimize maximum tardiness, Computers & Operations Research, 55, 830-840.
Tan, Z., Chen, Y., Zhang, A. (2013), On the exact bounds of SPT for scheduling on parallel machines with availability constraints, International Journal of Production Economics, 146, 293-299.
Xu, D., Sun, K., Li, H. (2008), Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan, Computers & Operations Research, 35, 1344-1349.
Yang, D. L., Hung, C. L., Hsu, C. J., Chen, M. S. (2002), Minimizing the makespan in a single machine scheduling problem with a flexible maintenance, Journal of the Chinese Institute of Industrial Engineers, 19, 63-66.
Yalaoui, F., Chu, C. (2006), New exact method to solve the P_m |r_j |∑▒C_j schedule problem, International Journal of Production Economics, 100, 168-179.
Yang, D. L., Hsub, C. J., Kuo, W. H. (2008), A two-machine flow shop scheduling problem with a separated maintenance constraint, Computers & Operations Research, 35, 876–83.
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.

指導教授

沈國基(Gwo-ji Sheen)

審核日期

2014-7-28

推文