近似求解平行機台具機器預防性維修、機器合適度及與工作相關之設置時間限制求最小化總完工時間的排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：99

、訪客IP：18.191.135.237

姓名

黃覺慧(Chueh-Hui Huang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

近似求解平行機台具機器預防性維修、機器合適度及與工作相關之設置時間限制求最小化總完工時間的排程問題
(Approximation of a Parallel Machine Scheduling Problem with the Consideration of Preventive Maintenance, Machine Eligibility and Sequence-Dependent Setup Times to Minimize the Total Completion Time)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

在此研究中，我們考慮在機器可用區間、機器合適度及與工作順序相關之設置時間限制下求取最小總完工時間之近似解的排程問題。我們有n個具不同發放時間及與工作順序相關之設置時間的工作，以及m台平行機台。每台機器並非可以一直使用，我們考慮在每部機台中皆會有一例行維修的情況；每個工作可以加工的機台與可以開始加工的時間也不同；並且還有工作順序相關之設置時間，也就是設置時間會根據目前將要加工的工作以及前一個在此機台上加工的工作來決定。為了減少求解問題的時間與記憶體，我們求取其近似解。
在本研究中，我們提出一個近似演算法去尋找這個排程問題的近似解。在演算法中，我們採Woeginger(2000)與Kacem and Mahjoub (2009)提出的方法。首先，用動態規劃來求取每一輪的子結果，再把每一輪中有近似關係的子結果刪除到僅剩一個，並用剩下的子結果再去進行下一輪計算直到動態規劃結束，並取最後一輪的子結果中最小的總完工時間作為此排程問題的答案。

摘要(英)

In this research, we find the minimizing total completion time of a scheduling problem on parallel machines with consideration of machine eligibility, preventive maintenance and sequence-dependent setup times. In our problem, we have n non-preemptive jobs with their release times and sequence-dependent setup times on m parallel machines. Each machine cannot serve jobs at every time point, that is, we consider a preventive maintenance on each machine. Each job has its release time and a set of eligible machines, and also a sequence-dependent setup time which determined by current job and the previous job. In order to reduce CPU run time and memory while solving a scheduling problem by finding an optimal solution, we try to find out a near-optimal solution for the problem.
We propose an approximation algorithm to solve our scheduling problem approximately. In the algorithm, we use methods which proposed by Woeginger (2000) and Kacem and Mahjoub (2009). At first, a dynamic program is presented to calculate output of partial schedule in each iteration. After mapping at the end of each iteration, we use trimming-the-state-space technique to trim outputs which are close to each other and left only one of these states in state space. Finally, at the end of the final iteration, we find the minimum objective value which is stored in the left states.

關鍵字(中)

★ 近似解
★ 機器合適度
★ 可用區間
★ 平行機台

關鍵字(英)

論文目次

目錄
摘要 i
Abstract ii
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem Description 2
1.3 Research Objectives 4
1.4 Research Methodology 4
1.5 Research Framework 5
Chapter 2 Literature review 6
2.1 Approximation schemes 6
2.2 Scheduling problem with machine availability constraint 7
2.3 Scheduling problem with machine eligibility constraint 8
2.4 Scheduling problem with sequence-dependent setup times 8
Chapter 3 Algorithm for Pm,hi1│rj,Mj,sab│Cj 10
3.1 Notations 10
3.2 Dynamic programing scheme 11
3.2.1 Input vector and state space 12
3.2.2 Mapping function and corresponding function 14
3.2.3 Objective function 18
3.3 Bounding scheme 19
3.3.1 Bounding scheme – upper bound 19
3.3.2 Bounding scheme – lower bound 20
3.4 Trimming-the-state-space scheme 22
3.4.1 Trimming parameters 23
3.4.2 Relation between states and ?-Box 27
3.5 Approximation algorithm 29
3.6 Time Complexity 31
Chapter 4 Computational Analysis 33
4.1. Instance generation 33
4.2 Validation of the approximation algorithm 34
4.3 Efficiency of algorithm 35
4.3.1 Percentage of state eliminated for trimming-the-state-space technique 36
4.3.2 Percentage of state eliminated for bounding scheme 39
4.3.3 The maximum size of instances for approximation algorithm 41
Chapter 5 Conclusion 48
5.1 Research Contribution 48
5.2 Research Limitation 49
5.3 Future Research 50
Reference 51

參考文獻

[1] Alon N., Y. Azar, G. J. Woeginger, T. Yadid, “Approximation Schemes for Scheduling on Parallel Machines”, Journal of Scheduling, 1, 55–66, 1998.
[2] Mellouli R., C. Sadfi, C. Chu and I. Kacem, “Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times”, European Journal of Operational Research, 197, 1150-1165, 2009.
[3] Pinedo M., Scheduling: Theory, Algorithm and System (3th ed.), New York: Prentice-Hall, 2008.
[4] Ruiz R., T. Stutzle, “An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives”, European Journal of Operational Research, 187, 1143-1159 , 2008.
[5] Kacem, I., Mahjoub, A. R., “Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval”, Computers & Industrial Engineering, 1708-1712, 2009.
[6] Schuurman, P., Woeginger G. J.,.“Approximation schemes - a tutorial”, Manuscript, to appear in Lectures on Scheduling, edited by R.H. Mohring, C.N. Potts, A.S. Schulz, G.J. Woeginger and L.A. Wolsey, 2006.
[7] Vallada E., R. Ruiz, “A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times”, European Journal of Operational Research, 211, 612–622, 2011.
[8] Woeginger, G. J., “When does a dynamic programming formulation guarantee the existence of a fully poly nomial time approximation scheme (FPTAS)?”, INFORMS J. Comput., 12, 57-74, 2000.
[9] Belouadah, H., Potts, C. N., “Scheduling identical parallel machine to minimize total weighted completion time”, Discrete Applied Mathematics, 201–218, 1994.
[10] 江曜君，『具機器可用時間與機器合適度限制和相依整備作業之平行機台排程問題』，中央大學工業管理研究所碩士論文，2011。
[11] 陳昱全，『機台可用區間及合適度限制求最小化總完工時間之平行機台排程問題』，中央大學工業管理研究所碩士論文，2016。

指導教授

沈國基

審核日期

2018-8-10

推文