近似求解機台可用區間限制求最小化總完工時間之平行機台排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：10

、訪客IP：3.15.197.123

姓名

林志佳(Chih-Chia Lin) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

近似求解機台可用區間限制求最小化總完工時間之平行機台排程問題
(Approximation of Identical Parallel Machine Scheduling with Machine Availability Constraint to Minimize Total Completion Time)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

在此研究中，我們探討ｎ個不可被分割的工作以及ｍ個平行機台的排程問題，針對每個機台具有不同數量的可用時間間隔限制的狀況，考慮最小化總完工時間。在多數的排程問題都沒有考慮可用時間間隔的限制，然而在實際情形上這種情形十分地常見，例如在製造業中，機台不可能一直處於運轉的狀態，會針對機台進行例行停機維護，以提升機台在生產時的良率及壽命。
為了求解此問題的近似解，我們參考了Woeginger(2000)中的trimmed動態規劃演算法，利用定義ε的值，刪減一些相似的state，進而求出近似解，在此演算法中我們加入了Chen(2016)和Tsou(2017)中所提到的三個propositions，此方法是利用到順序排程的概念，其他的則是比較兩個排滿工作時可用區間的開始時間及所被安排工作數量的關係，判斷這部分的排程是否可能為最佳解，藉以減少需要被儲存的state。我們提出了一個方程式估算每次iteration大約會產生多少states，以方便我們計算記憶體量是否足夠進行運算。最後我們與Tsou(2017)所提出的分支定界演算法進行比較，比較處理時間及與最佳解的相似程度。

摘要(英)

In this research, we discuss a scheduling problem including n non-preemptive jobs and m identical parallel machines with availability constraints. Our objective is minimizing the total completion time. . Most scheduling problems assume machines will work continuously, but in fact the situation is not always possible. So we consider the situation that each machine has its own available intervals For example, in the manufacturing industry, machines cannot always be in an operating state. Workers will stop the machines for a preventive maintenance period. It can keep the machines status stable and increase the yield of productions and the service life of the machines.
To find out the approximation solution for our problem, we first develop a dynamic programming algorithm. We adopt the proposed schemes of Tsou.(2017) and Chen.(2016) which is/are based on the idea of scheduling. We used three propositions to eliminate the possibility which cannot lead to the optimal solutions. These propositions are compared by the starting time and the number of jobs which are assigned in the available intervals filled up with jobs. Finally, we compare our dynamic programming with the branch and bound algorithm proposed from Tsou(2017).

關鍵字(中)

★ 平行機台
★ 可用時間限制
★ 總完工時間
★ 近似解
★ 動態規劃

關鍵字(英)

★ Parallel Machine
★ Availability Constraint
★ Total Completion Time
★ Approximate Solution
★ Dynamic Programming

論文目次

Abstract i
摘要 ii
Table of Content iii
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Background and motivation 1
1.2 Problem definition 3
1.3 Research objectives 4
1.4 Research methodology 4
1.5 Research framework 6
Chapter 2 Literature Review 7
2.1 One unavailable interval in a machine 7
2.2 Arbitrary number of unavailable interval in a machine 8
2.3 Approximation of Identical Parallel Machine Scheduling 9
Chapter 3 Methodology 10
3.1 Notation 10
3.2 Trimming the state in the dynamic programming 11
3.3 Degree Vector 14
3.4 Relation between state and ?-box 16
3.5 Propositions 18
3.6 Bounding scheme 20
3.6.1 Lower bound 21
3.7 Dynamic programming algorithm 22
3.8 Time Complexity 25
Chapter 4 Computational Analysis 26
4.1 Instance Generation 26
4.2 Validation of the dynamic programming algorithm 27
4.3 Performance of the trimming dynamic programming algorithm 29
4.3.1 Percentage of states eliminated between different error bounds 29
4.3.2 The percentage and number of trimming states with and without proposition and bounding 30
4.3.3 Maximum size of jobs and machines 33
4.4 Compare with the result by Tsou (2017) 39
Chapter 5 Conclusion 40
5.1 Research contribution 40
5.2 Research limitation 41
5.3 Future Research 41
Reference 42

參考文獻

Reference
[1] Adiri, I., J.Bruno, E.Frostig, & A. R.Kan,. Single machine flow-time scheduling with a single breakdown. Acta Informatica, 26(7), 679-696, 1989.
[2] Gawiejnowicz, S., W.Kurc , & L.Pankowska,. Solving a permutation problem by a fully polynomial-time approximation scheme. Discussiones Mathematicae, Differential Inclusions, Control and Optimization, 30(2), 191-203, 2010.
[3] Kacem, I., & A. R.Mahjoub, Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval. Computers & Industrial Engineering, 56(4), 1708-1712,2009.
[4] Mellouli, R., C.Sadfi, C.Chu, & I.Kacem,. Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times. European Journal of Operational Research, 197(3), 1150-1165, 2009.
[5] Pinedo, M. L., Scheduling: theory, algorithms, and systems. Springer, 2008.
[6] Schmidt, G., Scheduling with limited machine availability1. European Journal of Operational Research, 121(1), 1-15, 2000.
[7] Schuurman, P., & G. J. Woeginger,. Approximation schemes-a tutorial. Lectures on scheduling, 2006.
[8] Woeginger, G. J. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?. INFORMS Journal on Computing, 12(1), 57-74, 2000.
[9] 陳昱全，「機台可用區間及合適度限制求最小化總完工時間之平行機台排程問題」，國立中央大學，碩士論文，民國105年。
[10] 鄒永瑜，「機台可用區間限制求最小化總完工時間之平行機台排程問題」，國立中央大學，碩士論文，民國106年。

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2018-8-10

推文