平行機台具有彈性維護週期與接續完工限制 求極小化總完工時間排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：17

、訪客IP：18.191.165.88

姓名

蔡尚澄(Shang-Cheng Tsai) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

平行機台具有彈性維護週期與接續完工限制求極小化總完工時間排程問題
(Parallel Machine Scheduling with Flexible Maintenance and Resumable Jobs for Minimizing Total Completion Time)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

本文中，我們考慮在m台相同平行機台n個可接續的工作在有彈性維護並考慮同一工作接續必須額外有整備時間的情況下，並求最小總完工時間的排程問題. 在過去的排程研究中都假設機台是可連續工作在無限延伸時間中。假設一個工作在處理階段被中斷然後再接續工作我們稱這個情形為可接續的案子，反之不可中斷且接續在同一台機器的工作我們稱為不可接續的案子。近年來，越來越多研究考慮到機台並非一直都可使用。所以彈性維護限制為要預防機台的損壞影響時間成本和產品不必要的損壞並確保製程品質水準。本研究中考慮在兩個維護的時間間隔中有最大可工作區間和最小可工作區間限制。我們會提出一個分支界限演算法去尋找這個問題的最佳解，並用貪婪演算法去找近似最佳解。

摘要(英)

In this article, we consider the problem of scheduling n resumable jobs on the m identical parallel machine with flexible maintenance activities and sequence independent setup time, and the objective is to minimize total completion of jobs. In this past, the majority of scheduling studies assumes that machines are continuously at all time. If a job is disrupted during processing by a disrupted machine and it does not need (need) to restart after the machine becomes available again, it is called the resumable (nonresumable) case. In recent year, more and more studies consider that each machine is not continuously available. Flexible maintenance activity constraints mean that each machine must be maintained after a continuous period of time to prevent machine failure and maintain the quality of the process. This study considers the minimum working time and maximum working time within any two consecutive maintenance activities. We develop a branch and bound algorithm and a greedy algorithm and try to find the optimal solution in our problem.

Keywords: Scheduling, identical parallel machine, flexible maintenance, resumable job, independent setup time, branch and bound, iterated greedy algorithm, total completion time.

關鍵字(中)

★ 排程
★ 相同的平行機台
★ 彈性維護
★ 可接續工作
★ 獨立整備時間
★ 分支界線
★ 迭代貪婪演算法
★ 總完工時間

關鍵字(英)

★ Scheduling
★ identical parallel machine
★ flexible maintenance
★ resumable job
★ independent setup time
★ branch and bound
★ iterated greedy algorithm
★ total completion time

論文目次

Chapter 1 Introduction 1
1.1 Background and motivation 1
1.2 Problem definition 4
1.2.1 Research methodology and framework 6
1.2.2Research methodology 6
1.2.3Research framework 7
Chapter 2 Literature review 9
2.1 Machine with flexible maintenance activity 9
2.2 Parallel machine with setup times 11
2.3 Machine availability constraints for total completion time 12
2.4 Greedy algorithm for parallel machines 13
Chapter 3 Methodology for the scheduling problem 14
3.1 Notation 14
3.2 Branching scheme 22
3.1.1 Dominance proposition 25
3.2 Bounding scheme 26
3.2.1 Lower bound 27
3.2.2 Upper bound 29
3.3 Algorithm 30
3.3.1 Branch and Bound Algorithm 30
3.3.2 Greedy Algorithm 32
Chapter 4 Examples analysis 34
4.1 Generating test example 34
Chapter 5 Conclusion 41
5.1 Research constrain 41
5.2 Research limitation 42
References 43

參考文獻

References
[1] Ali, A., Jatinder, N.D.G., and Tariq, A. (1999), “A review of scheduling research involving setup considerations”, Omega, 27( 2), 219–239.
[2] Ahmed, G. A. (2015), “Parallel-machine scheduling with maintenance: Praising the assignment problem”, European Journal of Operational Research, 252(1), 90-97.
[3] Chung, Y. L., and Zhi, L. C. (1998), “Scheduling of jobs and maintenance activities on parallel machines”, Naval Research Logistics (NRL), 47(2), 145–165.
[4] Chen, J.S. (2006), “Optimization models for the machine scheduling problem with a single flexible maintenance activity”, Engineering Optimization, 38(1), 53-71.
[5] 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 (1) 90–102.
[6] Chenjie, W., Changchun, L., Zhi, H. Z., and Li, Z. (2016), “Minimizing the total completion time for parallel machine scheduling with job splitting and learning”, Computers & Industrial Engineering, 97, 170-182.
[7] Ik, S. L., and Jaewook, Y. (2013), “Parallel Machine Scheduling with Maintenance Activities”, Computers & Industrial Engineering, 101, 361-371.
[8] Maher, R., Imed, K., and Kondo, H. A. (2013), “Scheduling jobs and maintenance activities on parallel machines”, Operational Research, 13(3), 363–383.
[9] Mellouli, R., Sadfi, C., Chu, C., and Kacem, I. (2009), “Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times”. European Journal of Operational Research, 197 (3) 1150–1165.
[10] M. F. T. (2016), “Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion”, Computers & Operations Research, 77, 111-126.
[11] Pei, C. C., and Shih, H. C.(2011), “Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times”, Applied Soft Computing, 11(1), 1263–1274.
[12] R.H.P.M., Gerald, M. K. and Lawrence, M. Jr. (1998), “Some aspects of measuring maintenance performance in the process industry”, Journal of Quality in Maintenance Engineering, 4(1), 6 – 11.
[13] Shan, L. Y., Ying M., Dong, L. X. and Jian, B. Y. (2011), “Minimizing total completion time on a single machine with a flexible maintenance activity”. Computers & Operations Research, 38(4), 755–770.
[14] Sang, O. S., and Yeong, D. K. (2008), “A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property”, Computers & Operations Research, 35(3), 863–875.
[15] Qi, X., Chen, T. and Tu, F (1999), “Scheduling the maintenance on a single machine”. Journal of the Operational Research Society, 50(10), 1071-1078.
[16] Zhiyi, T., Yong, C., and An, Z. T. (2013), “On the exact bounds of SPT for scheduling on parallel machines with availability constraints”, International Journal of Production Economics, 146(1), 293–299.

指導教授

沈國基(Gow-Ji Sheen)

審核日期

2017-7-28

推文