博碩士論文 102426013 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:17 、訪客IP:3.230.173.249
姓名 鮑可軒(Ko-hsuan Pao)  查詢紙本館藏   畢業系所 工業管理研究所
論文名稱 具工作可切割特性與機台可用區間及合適度限制求最小化總完工時間之平行機台排程問題
(Preemptive Parallel Machine Scheduling with Machine Availability and Eligibility Constraints to Minimize Total Completion Time)
相關論文
★ 應用失效模式效應分析於產品研發時程之改善★ 服務品質因子與客戶滿意度關係研究-以汽車保修廠服務為例
★ 家庭購車決策與行銷策略之研究★ 計程車車隊派遣作業之研究
★ 電業服務品質與服務失誤之探討-以台電桃園區營業處為例★ 應用資料探勘探討筆記型電腦異常零件-以A公司為例
★ 車用配件開發及車主購買意願探討(以C公司汽車配件業務為實例)★ 應用田口式實驗法於先進高強度鋼板阻抗熔接條件最佳化研究
★ 以層級分析法探討評選第三方物流服務要素之研究-以日系在台廠商為例★ 變動良率下的最佳化批量研究
★ 供應商庫存管理架構下運用層級分析法探討供應商評選之研究-以某電子代工廠為例★ 台灣地區快速流通消費產品銷售預測模型分析研究–以聯華食品可樂果為例
★ 競爭優勢與顧客滿意度分析以中華汽車為例★ 綠色採購導入對電子代工廠的影響-以A公司為例
★ 以德菲法及層級分析法探討軌道運輸業之供應商評選研究–以T公司為例★ 應用模擬系統改善存貨管理制度與服務水準之研究-以電線電纜製造業為例
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   至系統瀏覽論文 ( 永不開放)
摘要(中) 在此研究中,我們討論 n 個可以分割且具有工作釋放時間的工作和 m 台平行機台的排程問題,針對機台合適度與可用區間限制的狀況,亦即工作有自己適合加工的機台且機台並非一開機就可以重頭做到尾,會有停機維修的狀況加入其中,考慮最小化總完工時間。為了找到此問題的最佳解,我們提出一個分枝界限的演算法,在此演算法中首先利用Liao and Sheen (2008)提出的時間切點的概念,將可用區間對應到時間軸上會發生狀態改變的時間點做切割,根據這樣調整後的區間做分枝,之後,利用二分配對圖發展此分之界限演算法的上界,此上界為一個反覆性的啟發示演算法,得以在演算法一開始便有一初始上界,用以提升演算效率,在最後的實驗分析中可得知此上界演算法不僅是一個複雜度極小的演算法,還是一個效果很好的界限。接著釋放掉機台合適度的限制法展一個複雜度亦極小的下界。實驗結果顯示此分枝界限演算法可以砍掉99%以上非必要的節點,說明此演算法的效率很好,且確實可以找到原問題的最佳解。
摘要(英) In this research, we consider the problem of scheduling n preemptive jobs with distinct release time on m identical parallel machines under machine availability and eligibility constraints to minimize total completion time. To find the optimal solution, we propose a branch and bound algorithm. First, using the idea of time epochs which was proposed from Liao and Sheen (2008) to separate machine available intervals. Then adopt the branching scheme from Mellouli et al. (2009) to branch out a node by assigning an additional job on each available interval specified by two adjacent time epochs. Second, according to our bounding scheme, we develop an iterated heuristic upper bound based on bipartite matching algorithm to find an initial feasible upper bound. By relaxing the restriction of machine eligibility constraint, we used extended shortest remaining processing time (SRPT) which proposed from Yalaoui and Chu (2006) to solve the reduced problem optimally, and set the optimal solution of it to be our lower bound. Computational analysis shows that the efficiency of our branch and bound algorithm can eliminate unnecessary nodes up to 99%. Due to the result of the average percentage gap of our upper bound, it can show that this upper bound is not only a polynomial time bound but also a tight bound.
關鍵字(中) ★ 平行機台
★ 可用區間限制
★ 機台合適度
★ 工作釋放時間
★ 先佔
★ 總完工時間
關鍵字(英) ★ parallel machine
★ available interval
★ eligibility constriant
★ release time
★ preemption
★ total completion time
論文目次 摘要 ii
Abstract iii
Table of Contents iv
List of Figures vi
List of Tables vii
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 6
Chapter 2 Literature review 8
2.1 Scheduling problem with availability and eligibility constraints 8
2.2 Parallel machine scheduling for total completion time 10
Chapter 3 Branch and bound algorithm 11
3.1 Notations 11
3.2 Obtaining the time epoch set and determining the time intervals 12
3.3 Branching scheme 13
3.4 Propositions 15
3.5 Bounding scheme 19
3.5.1 Upper bound 20
3.5.2 Lower bound 27
3.6 Branch and bound algorithm 30
Chapter 4 Computational Analysis 34
4.1 Data Generation 34
4.2 Validation of the branch and bound algorithm 35
4.3 Performance of the branch and bound algorithm 37
4.3.1 Maximum size of the branch and bound algorithm 37
4.3.2 Contribution of propositions and bounding scheme 38
4.3.3 Performance of upper bound 40
Chapter 5 Conclusion 42
5.1 Research Contribution 42
5.2 Research Limitation 43
5.3 Future Research 43
References 44
參考文獻 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.
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.
Horn W.A. (1973) “Technical note-minimizing average flow time with parallel machines”, Operations Research, 21(3), 846-847.
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.
Lee C.Y. and C.Y. Chen (2000) “Scheduling jobs and maintenance activities on parallel machines”, Naval Research Logistics, 47, 145-165.
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.
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.
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.
Pinedo M. (2008) “Scheduling: Theory, Algorithm and System (3th ed)”, New York: Prentice-Hall.
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.
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.
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.
Wu L.E. (2013) “A Branch and Bound Algorithm for Parallel Machine Scheduling Problem with Machine Availability and Job Preemption Constraint”, 中央大學碩士論文.
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.
指導教授 葉英傑(Ying-chieh Yeh) 審核日期 2015-7-7
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明