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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：107

、訪客IP：3.133.140.2

姓名

許文志(Wen-Chih Hsu) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

考量機台彈性維護限制之平行機台求極小化總完工時間排程問題
(Parallel machine scheduling with flexible maintenance activities 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 activities)。
我們提出一個分枝界限演算法去尋找這個問題的最佳解。首先，我們提出一個啟發式演算法基於剩餘工作具有最小處理時間之優先處理(SPT)法則去找到問題的可行解，並將該可行解作為分枝界限法之上限。接著我們提出兩個支配法則來提升分枝界限法的效率。
實驗的分析顯示，分枝界限法配合使用提出的支配法則後，節點的產生率非常小，在4個工作2台機台的問題下，節點產生率達0.066%以下，我們發現節點的產生率會隨著工作數目的增加而減少。我們的演算法能用於8個工作8台機台的問題下求得最佳解。

摘要(英)

In this paper we consider the problem of scheduling n non-preemptive jobs on m identical machines with flexible maintenance activities, and the objective is to minimize total completion time of jobs. In the past, the majority of scheduling studies assumes that machines are continuously available at all time, in the recent, 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 maximum continuously working time for each machine, which means the start time of each maintenance is unfixed, and perform the maintenance activity cannot exceed the given time. This constraint is called as machine with flexible maintenance activities.
We propose a branch and bound algorithm to find out the optimal solution for our problem. First, we propose a heuristic algorithm which based on the Shortest Processing Time First (SPT) rule to find out a feasible solution for our problem, its result as an upper bound of branch and bound algorithm. Then we propose two related propositions to increase the efficiency of branch and bound algorithm.
Computational analysis shows that the rate of nodes generated by using branch and bound algorithm with propose propositions is very low. For the problem with 4 jobs and 2 machines, its rate of generated nodes is less than 0.006%, we observe that the rate of generated nodes is decreasing with the number of job n increase. Our algorithm can get the optimal solution for the problem with up to 8 jobs and 8 machines.

關鍵字(中)

★ 排程
★ 平行機台
★ 機器彈性維護限制
★ 分支界限法

關鍵字(英)

★ Scheduling
★ parallel machine
★ machine with flexible maintenance activity
★ branch and bound algorithm

論文目次

摘要 i
Abstract ii
Table of Content iv
List of Figures vi
List of Table vii
Chapter 1 Introduction 1
1.1 Background and motivation 1
1.2 Problem definition 2
1.3 Research objectives 4
1.4 Research methodology and framework 4
1.4.1 Research methodology 5
1.4.2 Research framework 5
Chapter 2 Literature review 7
2.1 Machine with flexible maintenance activity 7
2.2 Machine availability constraints for total completion time 11
Chapter 3 Methodology for the scheduling problem 14
3.1 Notations 14
3.2 Branch and bound algorithm 15
3.2.1 Branching scheme 15
3.2.2 Propositions 23
3.2.3 Bounding scheme 24
3.2.4 Branch and bound algorithm 28
Chapter 4 Computational Analysis 32
4.1 Test Problem Generation 32
4.2 Validation of the Branch and Bound Algorithm 33
4.3 Performance of the Branch and Bound Algorithm 36
Chapter 5 Conclusion 43
5.1 Research Contribution 43
5.2 Research limitation 44
5.3 Further Research 44
Reference 45

參考文獻

[1] Arts R.H.P.M., Gerald M. Knapp, Lawrence Mann Jr. (1998), Some aspects of measuring maintenance performance in the process industry, Journal of Quality in Maintenance Engineering, 4 6 -11.
[2] Schmidt G. (2000), Scheduling with limited machine availability, European Journal of Operational Research, 121 1-15.
[3] Sanlaville E., Schmidt G. (1998), Machine scheduling with availability constraints, Acta Informatica, 35 795–811.
[4] Lee C.Y., Chen Z.L. (2000), Scheduling of Jobs and Maintenance Activities on Parallel Machines, Naval Research Logistics, 47 145-165.
[5] Qi X., Chen T., Tu F. (1999), Scheduling the maintenance on a single machine, The Journal of the Operation Research Society, 50 1071-1078.
[6] Sbihi M., Varnier C. (2008), single machine scheduling with periodic and flexible periodic maintenance to minimize maximum tardiness, 55 830–840
[7] Mosheiov G., Sarig A. (2009), Scheduling a maintenance activity to minimize total weighted completion-time, 57 619-623
[8] Chen J.S. (2006), Optimization models for the machine scheduling problem with a single flexible maintenance activity, Engineering Optimization, 38 53-71

[9] 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
[10] 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.
[11] Adiri I, Bruno J, Frostig E, Rinnooy Kan AHG. (1989), Single machine flow-time scheduling with a single breakdown, Acta Informatica 26 679–96
[12] Lee C.Y., Liman SD. (1992),Single machine flow-time scheduling with scheduled maintenance, Acta Informatica, 29 375–82.
[13] 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
[14] Sadfi C., Penz B., Rapine C., Blazewicz J., Formanowicz P. (2005), An improved approximation algorithm of the single machine total completion time scheduling problem with availability constraints, European Journal of Operational Research, 161 3– 30
[15] Levin A., Mosheiov G., Sarig A. (2009), Scheduling a maintenance activity on parallel identical machines, Naval Research Logistics, 56 33–41
[16] Sun K., and Li H. (2010), Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines, Production Economics, 124 151–158

[17] 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
[18] Xu D., Yin Y. (2011), On single-machine scheduling with flexible maintenance activities, Int J Adv Manuf Technol, 56 1139–1145
[19] Graham, R.L., Lawler E.L., Lenstra J.K., and Ronnooy Kan A.H.G (1979), Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5 287-326
[20] 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
[21] Graves G.H., Lee C.Y. (1999), Scheduling maintenance and semiresumable jobs on a single machine, Naval Research Logistics, 46 845–863
[22] Pan E., Liao W., Xi L. (2010), Single-machine-based production scheduling model integrated preventive maintenance planning, Int J Adv Manuf Technol, 50 365–375
[24] Kacem I., Chu C., Souissi A. (2008), Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times, Computer & Operation Research, 35 827–844
[25] Kaabi J., Varnier., Zerhouni N. (2002), Heuristics for scheduling maintenance and production on a single machine, IEEE SMC, 5
[26] Rebai M., Kacem I., Adjallah K.H. (2010), Scheduling Jobs and Preventive Maintenance Activities on Parallel Machine, APPLIED COMPUTER SCIENCE, 406-411
[27] Rebai M., Kacem I., Adjallah K.H. (2012), Earliness–tardiness minimization on a single machine to schedule, J Intell Manuf, 23 1207–1224
[28] Chen Z.L. (2004), Simultaneous Job Scheduling and Resource Allocation on Parallel Machines, Annals of Operations Research, 129, 135–153
[29] Wang S., Yu J. (2008), An effective heuristic for flexible job-shop scheduling problem with maintenance activities, Computers & Industrial Engineering, 59 436–447

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2013-7-19

推文