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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：22

、訪客IP：3.22.61.73

姓名

鄒永瑜(Yung-Yu Tsou) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

機台可用區間限制求最小化總完工時間之平行機台排程問題
(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 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

在此研究中，我們討論n個不可被分割的工作和m台平行機台的排程問題，針對每台機台具有不同的可用區間限制狀況，考慮最小化總完工時間。在大多數的排程問題研究中都不考慮機台有可用區間的限制，然而在實務上這種條件限制的情況是很常見的。例如在製造業中，機台不可能一直處於運轉的狀態，會針對機台進行例行停機維護，以提升機台在生產時的良率以及壽命。
為了找出此問題的最佳解，我們提出了一個分支定界演算法。在此演算法中，我們採用Chen (2016)所提出的分支方式作為我們的分支方法，此分支方是利用到順序排程的概念。接著提出兩個命題，比較兩個排滿工作的可用區間的開始時間以及所被安排工作數的關係，判斷此部分排程是否不可能為最佳解，藉以在展枝時減少展出不必要的節點。我們調整Chen (2006)所提出的下界方式，利用工作可以被搶斷以及可以同時在不同機台工作之特性求得下界。最後我們也與Chen (2006)所提出的演算法進行比較，不管是在比較演算法可以求解的問題大小，或者是在總共展出的節點數與CPU處理時間上，我們的演算法都表現得比較好。

摘要(英)

In this research, we consider the scheduling problem with n non-preemptive jobs and m identical parallel machines under availability constraint. Cause of the availability constraint, each machine has its own available processing time. And the objective of our scheduling problem is to minimize the total completion time. Most research in scheduling area assumes machines can work continuously but that is not possible in reality. For example in industrial manufacturing, workers will stop the machines in a period for preventive maintenance. It can keep the machines status stable and have good production quantity.
To find out the optimal solution for our problem, we propose a branch and bound algorithm. We adopt the branching scheme Chen. (2016) proposed which is based on the idea of forward scheduling. Then, we propose two propositions to eliminate the nodes which cannot lead to optimal. The propositions are developed by comparing the starting time and the number of jobs assigned in the available intervals which are filled up with jobs. The lower bound calculation is modified from Chen (2016). We add job splitting constraint into the original problem and solve by SPT rule. Finally, we compare our algorithm with the algorithm proposed from Chen (2016) which can solve our problem. No matter comparing the maximum size of instance the algorithm can solve or the performance of number of nodes and CPU run time, our branch and bound algorithm has better performance.

關鍵字(中)

★ 平行機台
★ 可用區間限制
★ 總完工時間

關鍵字(英)

★ Parallel machine
★ Availability constraint
★ Total completion time

論文目次

Table of Content
Abstract i
摘要 iii
Table of Content iv
List of Figures vi
List of Tables vii
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 8
2.1 One unavailable interval in a machine 8
2.2 Arbitrary number of unavailable interval in a machine 9
Chapter 3 Methodology 11
3.1 Notation 11
3.2 Obtaining the time epoch set 12
3.3 Branching scheme 13
3.4 Propositions 17
3.5 Bounding scheme 21
3.5.1 Lower bound 21
3.5.2 Upper bound 23
3.6 Branch and Bound Algorithm 23
Chapter 4 Computational Analysis 28
4.1 Instance Generation 28
4.2 Validation of the branch and bound algorithm 29
4.3 Performance of the branch and bound algorithm 31
4.3.1 Percentage of nodes eliminated 31
4.3.2 Percentage of nodes eliminated by a specific proposition 32
4.3.3 Maximum size of instance 33
4.4 Compare with the algorithm proposed from Chen (2016) 35
Chapter 5 Conclusion 38
5.1 Research Contribution 38
5.2 Research Limitation 39
5.3 Further Research 39
References 41
Appendix 44
List of Figures
Figure 1 Demonstration of machine environment 3
Figure 2 Research framework 7
Figure 3 An example of distinct time point epochs 13
Figure 4 Searching tree of branching scheme 16
Figure 5 Td=2 and Td′=1. Td>Td′, we don’t branch out node d′ 17
Figure 6 The position of job j in the available interval ai,k 18
Figure 7 Illustrate for proposition 3 20
Figure 8 Percentage of nodes eliminated by branch and bound algorithm 31
Figure 9 Percentage of nodes eliminated by a specific proposition 32
Figure 10 The relation between number of nodes generated and number of jobs 34
Figure 11 The relation between CPU run time and number of jobs 35
Figure 12 Comparison of number of nodes (n=10) 36
Figure 13 Comparison of CPU rum time (n=10) 36
Figure 14 Comparison of number of nodes (n=11) 37
Figure 15 Comparison of CPU rum time (n=11) 37
List of Tables
Table 1 Validation results of branch and bound algorithm 30
Table 2 Instance that can solve by our branch and bond algorithm 33

參考文獻

Hmid S.D.R. and T.T. Mohammad (2008). “Study of Scheduling Problems with Machine Availability Constraint”, Journal of Industrial and Systems Engineering, 1(4), 360-383.
Sanlaville E. and G. Schmidt (1998). “Machine scheduling with availability constraints”, Acta Informatica, 35, 795-811.
Schmidt G. (2000). “Scheduling with limited machine availability”, European Journal of Operational Research, 121, 1-15.
Centeno G. and R.L. Armacost (1997). “Parallel machine scheduling with release time and machine eligibility restrictions”, Computers & industrial engineering, 33 (1), 273-276.
Yalaoui F. and C. Chu (2006). “New exact method to solve the P_m |r_j |∑▒C_j schedule problem”, Int. J. Production Economics, 100, 168-179.
Brucker P. and S.A. Kravchenco (2008). “Scheduling jobs with equal processing times and time windows on identical parallel machines”, Journal of Scheduling, 11, 229-237.
Horn W.A. (1973). “Technical note-minimizing average flow time with parallel machines”, Operations Research, 21(3), 846-847.
Adiri I., J. Bruno, E. Frostig and A.H.G. Rinnooykan (1989). “Single machine flow-time scheduling with a single breakdown”, ACTA Information, 26,679-696.
Kacem I., C. Chu and A. Souissi (2006). “Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times”, Computers and Operations Research, 180, 396-405.
Mellouli R., C. Sadfi, C. Chu and I. Kacem (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 System (3th ed)”, New York: Prentice-Hall.
Centeno G. and R.L. Armacost (2004). “Minimizing makespan on parallel machines with release time and machine eligibility restrictions”, International Journal of Production Research, 42(6), 1243-1256.
Liao L.W. and G.J Sheen (2008). “Parallel machine scheduling with machine availability and eligibility constraints”, European Journal of Operational Research, 184, 458–467.
Lee C.Y. and Z.L. Chen (2000). “Scheduling jobs and maintenance activities on parallel machines”, Naval Research Logistics, 47, 145-165.
Nessah N., C. Chu and F. Yalaoui (2007). “An exact method for P_m |sds,r_i |∑_(i=1)^n▒C_i problem”, Computers and Operations Research, 34, 2840-2848.
Qi X., T. Chen and F. Tu (1999). “Scheduling the maintenance on a single machine”, The Journal of the Operation Research Society, 50, 1071-1078.
Shim S.O. and Y.D. Kim (2008). “A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property”, Computers and Operations Research, 35, 863-875.
李彥漢，「考量平行機台之彈性維護週期求極小化總完工時間排程問題」，國立中央大學，碩士論文，民國103年。
鮑可軒，「具工作可切割特性與機台可用區間及合適度限制求最小化總完工時間之平行機台排程問題」，國立中央大學，碩士論文，民國104年。
陳昱全，「機台可用區間及合適度限制求最小化總完工時間之平行機台排程問題」，國立中央大學，碩士論文，民國105年。

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2017-7-24

推文