平行機台排程問題下考量工單釋放時間與機台適合度之最小化總完工時間

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：37

、訪客IP：3.17.150.89

姓名

蔡承益(Cheng-I Tsai) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

平行機台排程問題下考量工單釋放時間與機台適合度之最小化總完工時間
(Identical Parallel Machine Scheduling Problem with Release Dates and Machine Eligibility Restriction to Minimize Total Completion Time)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

在現實環境中，每個作業在開始作業前，皆有所謂的備料時間，造成作業能開始執行的時間有所不同。除此之外，作業和機台(服務人員)被賦予不同的等級或條件，針對不同作業將會有不同機台負責執行但有著相同的服務速率。在此研究中，我們考慮當極小化總作業之完工時間時，在具有工單釋放時間與機台適合度的限制條件下有n個不可分割的工作和m台相同工作效率的平行機台排程問題。
求解此排成問題，我們使用分支界限法求得最佳解。在提出的基本作業排序規則下，首先提出了下限值的計算方式，計算方式是運用允許作業切割及使用最短剩餘工作時間者先排的規則來產生，計算所得的下限值將用來比較現有可行解並判斷該節點是否繼續分支，接著由Chu和Yalaoui (2006)所提出的減少分支規則做衍伸，改成屬於本篇文章能使用的規則，來減少不必要的節點產生進而提升求解效率。根據上述方法，我們將在此篇論文中將求解方式條列成演算法，並根據演算法的邏輯以java來協助我們求得題目之最佳解。
實驗分析結果，我們提出的分支界線演算法能正確的求解出Pm |rj,Mj |∑Cj 排程問題最佳解。節點也能有效率的產生，在2台機台15個工作的環境下相較於窮舉法，減少99.99%以上的節點數。我們的演算法在2機台環境下能求解到15個工作數，在有適合度條件下3機台環境能求解15個工作數而4機台環境能求解10個工作數。

摘要(英)

In practice, there is a waiting time which is generated by preparing materials before job is scheduled, then jobs will be scheduled with different starting time. In addition, jobs and machines(servers) are classified into different level or with different conditions, then jobs will be assigned to own machines but still have same speed when they are processed. In this research, we consider the problem of scheduling n non-preemptive jobs on m identical parallel machines with release dates and machine eligibility restriction to minimize total completion time.
For the scheduling problem, we use branch and bound to find the optimal solution. Following basic proposition, we propose a lower bound first. With splitting job is allowed and using extended shortest remaining processing time rule to calculate the value of bound and compare with feasible solutions to determine the node is branched or not. We also propose dominance rules which are modified from Chu and Yalaoui (2006) to discard redundant nodes and improve efficiency of searching process. According above methods, we will present the branch and bound algorithm step by step and code the logistic to java programming and solve the scheduling problem.
In computational result, we validate our branch and bound can find the optimal solution for Pm |rj,Mj |∑C_j scheduling problem. Compare complete branching method with our branch and bound algorithm we can eliminate 99.99% created nodes efficiently. The solvable size of problem is up to 15 jobs with condition of 2 machines, 15 jobs with condition of 3 machines machine eligibility restriction and 10 jobs with condition of 4 machines.

關鍵字(中)

★ 排程
★ 平行機台
★ 機台適合度限制
★ 工單釋放時間
★ 分支定界演算法

關鍵字(英)

論文目次

目錄
摘要 i
Abstract ii
Table of Content iii
List of Figures iv
List of Tables v
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem description 2
1.3 Research objectives 3
1.4 Research Methodology and Frameworks 3
Chapter 2 Literature Review 5
2.1 Identical parallel machine with release dates 5
2.2 Identical parallel machine with machine eligibility restriction 8
Chapter 3 Methodology for the scheduling problem 10
3.1 Notation 10
3.2 Basic Proposition 11
3.3 Bounding Scheme 14
3.3.1 Lower bound 14
3.4 Branching Scheme 14
3.5 Dominance Rules 18
3.6 Branch and bound algorithm 21
Chapter 4 Computational Analysis 26
4.1 Test Problem Generation 26
4.2 Validation of the Branch and Bound Algorithm 27
4.3 Performance of the Branch and Bound Algorithm 28
4.3.1 Efficiency of Branch and Bound Algorithm 28
4.3.2 Efficiency of propositions 33
Chapter 5 Conclusion 38
5.1 Research contribution 38
5.2 Research limitation 38
5.3 Further Research 39
References 40

參考文獻

Belouadah, H., Posner M.E., Potts, C.N. (1992), Scheduling with release dates on a single machine to minimize total weighted completion time, Discrete Applied Mathematics, 36, 213-231.
Baptiste, P. (2000), Scheduling equal-length jobs on identical parallel machines, Discrete Applied Mathematics, 103, 31-32.
Brucker, P., Kravchenko, S.A. (2008), Scheduling jobs with equal processing times and time windows on identical parallel machines, Journal of Scheduling, 11, 229-237.
Centeno, G., Armacost, R.L. (1997), Parallel machine scheduling with release time and machine eligibility restrictions, Computers & Industrial Engineering, 33(1-2), 273-276.
Centeno, G., Armacost, R.L. (2004), Minimizing makespan on parallel machines with release time and machine eligibility restrictions, International Journal of Production Research, 42, 1243-1256.
Du, J., Leung, J.Y.-T., Young, G.H. (1991), Scheduling chain structured tasks to minimize makspan and mean flow time, Information and Computation, 92, 219-236.
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. (1979), Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287-326.
Kim, S.-I., Choi, H.-S., Lee, D.-H. (2006), Tabu search heuristics for parallel machine scheduling with sequence dependent setup and ready times, In proceedings ICCSA 2006, LNCS 3982, 728-737.
Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P., (1977), Complexity of machine scheduling problems, Annals of Discrete Applied Mathematics, 1, 343-362.
Lin, C.-H., Liao, C.-J. (2008), Minimizing makespan on parallel machines with machine eligibility restrictions, The Open Operational Research Journal, 2, 18-24.
Nessah, R., Chu, C., Yalaoui, F. (2007), An exact method for P_m |sds,r_i |∑_(i=1)^n▒C_i problem, Computers & Operations Research, 34, 2840-2848.
Nessah, R., Yalaoui, F., Chu, C. (2008), A branch and bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates, Computers & Operations Research, 35, 1176-1190.
Pinedo, M. (2008), Scheduling: theory, algorithm, and systems, 3^rded., New Jersey: Prentice-Hall.
Shim, S.-O., Kim, Y.-D. (2008), A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property, Computers & Operations Research, 35, 863-875.
Yang, D.-L., Hung, C.-L., Hsu, C.-J. (2002), Minimizing the makespan in a single machine scheduling problem with a flexible maintenance, Journal of the Chinese Institute of Industrial Engineers, 19, 63-66
Yalaoui, F., Chu, C. (2002), Parallel machine scheduling to minimize total tardiness, International Journal of Production Economics, 76, 265-279.
Yalaoui, F., Chu, C. (2006), New exact method to solve the P_m |r_j |∑▒C_j schedule problem, International Journal of Production Economics, 100, 168-179.

指導教授

葉英傑

審核日期

2014-7-28

推文