具機器可用時間與機器合適度限制且工作具互斥性之平行機台排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：45

、訪客IP：3.12.41.106

姓名

徐豪駿(Hao-chun Hsu) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

具機器可用時間與機器合適度限制且工作具互斥性之平行機台排程問題
(Parallel Machine Scheduling with Machine Availability,Eligibility and Job Incompatible Constraints)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

在此研究中，我們考慮當極小化最大完工時間時，在具機器可用時間與機器合適度且工作具互斥性限制下，n個不可分割的工作和m台平行機台的排程問題。每台機器只有某些時間區段可以被安排處理工作，每個工作也只能被安排在某些特定的機器上，某些工作會屬於某個群組，且只有工作屬於不同群組能被放置於同一可用的時間區段中進行工作。
首先，我們使用網路流技術用來闡述可分割工作的排程問題並將其轉變成最大流量問題。其次，我們提出一演算法基於最多剩餘工作處理時間之群組優先/最早發放時間優先(FRPF/ERD)法則來得到上限。然後，我們利用分枝界限法來處理問題中的工作互斥限制，其中我們提出六個支配的法則來提升分枝界限法的效率。最後，我們參考廖祿文(2008)提出一演算法，其結合網路流技術和二元搜尋法去找到該問題的最佳解。
實驗的分析顯示，所提出的淘汰法則是有效率的並且在分枝界限法中只有非常小的比例的節點被產生。在所有淘汰法則中，我們發現利用第五個支配法則刪除的節點比例會隨著有工作數量增加或機台的數目增加而增加。

摘要(英)

In this paper we consider the problem of scheduling n preemptive jobs on m identical machines with machine availability, eligibility and incompatible job constraints when minimizing the maximum makespan. Each machine is not continuously available for processing at all time and each job is only allowed to be processed on specific machines. In the same availability interval, each job belongs to a family and only jobs from different family can be processed.
Firstly, we use a network flow technique to model the scheduling problem with the job preemption into a series of maximum flow problems. Secondly, we propose an algorithm which bases on the Family With Most Job Remaining Processing Time First /Earliest Release Date First (FRPF/ERD) rule to find an upper bound. Thirdly, we use a branch and bound algorithm to deal with incompatible constraint of our problem and use six dominance rules to increase the efficiency of the branch and bound algorithm. Finally, we modify an algorithm proposed by Liao and Sheen (2008). This algorithm includes a network flow technique and a binary search procedure to find an optimal solution for the scheduling problem.
Computational analysis shows that eliminating rules are effective. The percentage of nodes generated by the branch and bound algorithm is low. More than half of nodes eliminated are attributed to Proposition 5, which will become more effective when n and m increase.

關鍵字(中)

★ 排程
★ 分枝界限法
★ 網路流
★ 平行機台
★ 可用時間限制
★ 工作互斥
★ 合適度限制

關鍵字(英)

★ Scheduling
★ machine availability
★ branch and bound algorithm
★ network flow technique
★ machine eligibility
★ incompatible jobs
★ parallel machine

論文目次

摘要 I
Abstract II
Table of Content III
List of Tables V
List of Figures VI
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem Description 3
1.3 Research Objectives 4
1.4 Research Methodology and Framework 4
1.4.1 Research Methodology 4
1.4.2 Research Framework 5
Chapter 2 Literature Review 7
2.1 Machine Availability Constraint 7
2.2 Machine Eligibility Constraint 8
2.3 Job Incompatible Constraint 9
2.4 Network Flow Approach 10
2.5 Machine Availability and Eligibility Constraints 11
Chapter 3 Branch and Bound Algorithm 13
3.1 Notations 13
3.2 Network flow model for problem 15
3.2.1 The Base Problem for 16
3.2.2 Obtain the Time Epoch Set E and Determine Time Interval 16
3.2.3 Construct Network 16
3.2.4 Network Flow Algorithm 21
3.3 Branching scheme 23
3.3.1 Upper bound 23
3.3.2 Dominance Rules 26
3.4 Branch And Bound Algorithm 30
Chapter 4 Computational Analysis 35
4.1 Generating Test Problems 35
4.2 Validation of the Branch and Bound Algorithm 36
4.3 Performance of the Branch and Bound Algorithm 38
Chapter 5 Conclusion 48
5.1 Research Contribution 48
5.2 Research Limitation 49
5.3 Further Research 49
References 50

參考文獻

[1] Azizoglu, M., S. Webster. 2001. Scheduling a batch processing machine with incompatible job families. Computers &Industrial Engineering39 325-335.
[2] Blazewicz, J., M. Drozdowski, P. Formanowicz, W. Kubiak, G. Schmidt. 2000. Scheduling preemptable tasks on parallel processors with limited availability. Parallel Computing26 1195-1211.
[3] Blazewicz, J., P. Dell’Olmo, M. Drozdowski, P. Maczka. 2003. Scheduling multiprocessor tasks on parallel processors with limited availability. European Journal of Operational Research 149 377-389.
[4] Bodlaender, H.L., K. Jansen, and G.J. Woeginger. 1994. Scheduling with incompatible jobs. Discrete Applied Mathematics 55 219-232.
[5] Centeno, G., R.L. Armacost. 1997. Parallel machine scheduling with release time and machine eligibility restrictions. Computers & Industrial Engineering33(1-2) 273-276.
[6] Centeno, G., R.L. Armacost. 2004. Minimizing makespan on parallel machines with release time and machine eligibility restrictions. International Journal of Production Research42(6) 1243-1256.
[7] De Reyck, B., W. Herroelen. 1998. A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations. European Journal of Operational Research 111 152-174.
[8] Horn, W.A. 1974. Some simple scheduling algorithms. Naval Research Logistics Quarterly 21 177-185.
[9] Hwang, H.C., S.Y. Chang. 1998. Parallel machines scheduling with machine shutdowns. Computers & Mathematics with Applications36(3) 21-31.
[10] Hwang, H.C., S.Y. Chang, K. Lee. 2004. Parallel machine scheduling under a grade of service provision. Computers & Operation Research31 2055-2061.
[11] Hwang, H.C., S.Y. Chang, Y. Hong. 2004. A posterior competitiveness for list scheduling algorithm on machines with eligibility constraints. Asia - Pacific Journal of Operational Research 21(1) 117-125.
[12] Jansen, K. 2003. Approximate strong separation with application in fractional graph coloring and preemptive scheduling. Theoretical Computer Science302 239-256.
[13] Labetoulle J, Lawler EL, Lenstra JK, Rinnoy Kan AHG. Preemptive scheduling of uniform machines subject to release dates. In: Pulleyblank WR (Eds.). Progress in Combinatorial Optimization, New York: Academic Press, 1984. p.245-261.
[14] Lee, C.Y. 1991. Parallel machines scheduling with nonsimultaneous machine available time. Discrete Applied Mathematics30 53-61.
[15] Lee, C.Y. 1996. Machine scheduling with an availability constraint. Journal of Global Optimization9 395-416.
[16] Lee, C.Y., Y. He, G. Tang. 2000. A note on parallel machine scheduling with non-simultaneous machine available time. Discrete Applied Mathematics100 133-135.
[17] Liao, L.W., G.J. Sheen. 2007. Parallel machine scheduling with machine availability and eligibility constraints. European Journal Operation Research. Article in press.
[18] Lin, C. F. 2006. Branch and bound algorithm for parallel machine scheduling with availability and eligibility constraints. Unpublished Master Thesis, Institute of Industrial Management, National Central University.
[19] Lin, Y., W. Li. 2004. Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research156 261-266.
[20] Lu, B. H. 2005. Parallel machine scheduling with machine availability and eligibility constraints. Unpublished Master Thesis, Institute of Industrial Management, National Central University.
[21] Lai, Y. S. 2007. Parallel machine scheduling with machine availability , eligibility and job incompatible constraints. Unpublished Master Thesis, Institute of Industrial Management, National Central University.
[22] Pinedo, M. 2002. Scheduling: Theory, Algorithm and System (2th ed.). Englewood Cliffs, NJ: Prentice-Hall.
[23] Schmidt, G. 1988. Scheduling independent tasks with deadlines on semi-identical processors. Journal of the Operational Research Society39 271-277.
[24] Schmidt, G. 2000. Scheduling with limited machine availability. European Journal of Operational Research121 1-15.
[25] Sanlaville, E. 1995. Nearly online scheduling of preemptive independent tasks. Discrete Applied Mathematics57 229-241.
[26] Sheen, G.J., L.W. Liao. 2007. Scheduling machine-dependent jobs to minimize lateness on identical machines with availability constraints. Computers & Operations Research 34 2266-2278.
[27] Ullman, J.D. 1975. NP-complete scheduling problems. Journal of Computer and System Sciences10 384-393.
[28] Wang, C.S., R. Uzsoy. 2002. A genetic algorithm to minimize maximum lateness on a batch processing machine. Computers &Operations Research29 1621-1640.
[29] Webster, S., K.R. Baker. 1995. Scheduling groups of jobs on a single machine. Operation Research43 692-703.

指導教授

沈國基(Gwo-ji Sheen)

審核日期

2012-7-19

推文