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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：9

、訪客IP：3.131.13.194

姓名

陳昱全(Yu-Cyuan Chen) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

機台可用區間及合適度限制求最小化總完工時間之平行機台排程問題
(Identical Parallel Machine Scheduling with Machine Availability and Eligibility Constraints to Minimize Total Completion Time)

相關論文

★ 應用失效模式效應分析於產品研發時程之改善	★ 服務品質因子與客戶滿意度關係研究-以汽車保修廠服務為例
★ 家庭購車決策與行銷策略之研究	★ 計程車車隊派遣作業之研究
★ 電業服務品質與服務失誤之探討-以台電桃園區營業處為例	★ 應用資料探勘探討筆記型電腦異常零件-以A公司為例
★ 車用配件開發及車主購買意願探討(以C公司汽車配件業務為實例)	★ 應用田口式實驗法於先進高強度鋼板阻抗熔接條件最佳化研究
★ 以層級分析法探討評選第三方物流服務要素之研究-以日系在台廠商為例	★ 變動良率下的最佳化批量研究
★ 供應商庫存管理架構下運用層級分析法探討供應商評選之研究-以某電子代工廠為例	★ 台灣地區快速流通消費產品銷售預測模型分析研究–以聯華食品可樂果為例
★ 競爭優勢與顧客滿意度分析以中華汽車為例	★ 綠色採購導入對電子代工廠的影響-以A公司為例
★ 以德菲法及層級分析法探討軌道運輸業之供應商評選研究–以T公司為例	★ 應用模擬系統改善存貨管理制度與服務水準之研究-以電線電纜製造業為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

在此研究中，我們考慮最小化總完工時間時，在機器可用區間與機器和適度限制下， n 個具有不同發放時間且無法被分割的工作與 m 台工作效率相同的平行機台之排程問題。每台機器並非一直處於可使用狀態，也就是我們也考慮會有例行停機維修的狀況；而每個工作可開始執行的時間通常是不盡相同，工作也會因工作本身的特性而對應出其合適加工的機台。
我們提出一個分支界限的演算法去尋找此問題的最佳解。在演算法中，我們探討了兩種分支的方式：一種為採用Melloui et al. (2009)所提出的分支方法；另一種則是自己提出的分支方法，兩者最大不同在於後者方式具有順序排程的概念，根據自己提出的分支方式再提出減少分支的規則。接著在未排的時間區間下將原問題釋放機器和適度限制並允許工作可以被切割，藉此可採用Yalaoui and Chu (2006)提出之特性來解轉換後問題並求得下界。

摘要(英)

In most scheduling problem, machines are always continuously available to process jobs all the time. However, it usually exist unavailable time intervals for routine maintenance in practice. Besides, some job is suitable for specific machines to process based on the property of job. In this study, we consider the problem of scheduling n non-preemptive jobs with distinct release time on m identical parallel machines under machine availability and eligibility constraints to minimize total completion time.
For the scheduling problem, we use branch and bound method to find the optimal solution. In the branch and bound algorithm, we discuss two way of branching. First one is, we adopted the branching scheme from Mellouli et al. (2009) which concept is through assigning an additional job on each available interval. We also propose the other approach of branching which contained the concept of forward scheduling. Based on the branching scheme we proposed, we also propose a dominance rule to eliminate redundant nodes. We adopted the property in Yalaoui and Chu (2006) which could solve the reduced problem by relaxing the restriction of machine eligibility constraint and allow jobs split, and let the optimal solution to be our lower bound.

關鍵字(中)

★ Parallel machine
★ Available interval
★ Eligibility constraint
★ Release time
★ Total completion time

關鍵字(英)

★ 平行機台
★ 可用區間限制
★ 機台合適度
★ 工作釋放時間
★ 總完工時間

論文目次

Abstract i
摘要 ii
Table of Contents iii
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Background and motivation 1
1.2 Problem definition 2
1.3 Research objectives 4
1.4 Research methodology 4
1.5 Research framework 5
Chapter 2 Literature review 7
2.1 Parallel machine with release time constraint 7
2.2 Scheduling problem with availability constraint 8
2.3 Scheduling problem with eligibility constraint 9
2.4 Parallel machine with both availability and eligibility constraints 9
Chapter 3 Methodology 11
3.1 Notations 11
3.2 Obtain the time point sequence, E(α). 12
3.3 Introduction of Branch and Bound 14
3.3.1 Branching schemes 14
3.3.2 Dominance rules 21
3.3.3 Bounding scheme – upper bound 24
3.3.4 Bounding scheme – lower bound 24
3.4 Branch and Bound algorithm 27
Chapter 4 Computational Analysis 39
4.1 Problem Generation 39
4.1.1 Instance Generation 39
4.1.2 Sensitivity Analysis 40
4.2 Performance of the branch and bound algorithm 44
4.2.1 Validation of the branch I and branch II 44
4.2.2 Efficiency of the propositions and lower bound 47
4.2.3 Maximum size of the branch and bound algorithm 48
4.3 Performance of the branch and bound algorithm in preemptive case 49
4.3.1 Validation of the branch I and branch II in preemptive case 50
4.3.2 Maximum size of the branch and bound algorithm 51
Chapter 5 Conclusion 53
5.1 Research Contribution 53
5.2 Research Limitation 54
5.3 Future Research 54
Reference 55
Appendix 57

參考文獻

Reference
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.

指導教授

葉英傑

審核日期

2016-7-20

推文