具機器可用時間與機器合適度限制下之平行機台最佳化排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：23

、訪客IP：3.144.125.201

姓名

廖祿文(Lu-Wen Liao) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

具機器可用時間與機器合適度限制下之平行機台最佳化排程問題
(Optimal Parallel Machine Scheduling with Machine Availability and Eligibility Constraints)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

本論文主要在探討有限規劃時間幅度下，具機器可用時間與機器合適度限制下之平行機台最佳化排程問題。機器可用時間限制(Machine availability constraint)，意指每一機台具有服務時間之限制；而機器合適度限制(Machine eligibility constraint)，意指每一工件被限定在特定機台服務之限制。目前尚無研究同時考慮上述二限制，然而實務上如電視台廣告、半導體製程等等之排程問題，皆須同時納入此二限制。本研究首先將理論研究，延伸至含此二限制之問題，分別探討:一、極小化最大完工時間(Makespan, Cmax)之排程問題；二、極小化最大延遲時間(Maximum lateness, Lmax)之排程問題。本論文最後將上述研究成果，推廣應用至工件的操作時間具不可分割特性下(Job preemption is not allowed)之平行機台排程問題，此為本論文第三個所探討的排程問題。
針對極小化最大完工時間之排程問題，我們利用網路流量分析方法(Network flow approach)，將排程問題轉換成多個最大流量網路問題(Maximum network flow problem)，並建構相對應之網路流量模型。每一個網路流量模型，描述了工件與機台可操作時間，在給定不同的「最大完工時間」下之相互關係。本研究利用二元搜尋方法與最大流量網路問題演算法，建構一多項式演算法(Polynomial time algorithm)。此一多項式演算法依序求解問題中之最大流量網路問題，以得到最小之「最大完工時間」。針對極小化最大延遲時間之排程問題，本研究利用臨界值(Critical values)之概念，與運用相類似上述極小化最大完工時間之排程問題之網路流量分析方法，提出兩階段之二元搜尋演算法來求解此一排程問題。本論文最後，將以極小化最大延遲時間之排程問題的結果，進一步應用到第三類排程問題上，以求解問題之下界值(Lower bound)。並依據工件與機台間之相互特性，整理出相關命題(Propositions)，發展分支定界法(Branch and bound algorithm)，以求取問題之最佳解。

摘要(英)

In this dissertation we consider the parallel machine scheduling problem with machine availability and eligibility constraints under a given planning horizon. Machine availability constraint indicates that each machine is not continuously available at all times throughout the planning horizon; machine eligibility constraint means that each job can only be processed on specified machines. We observe that there is a little published works in machine scheduling considered machine availability and eligibility constraints simultaneously. But this type of scheduling problem can be found in some practical environments, such as TV advertising scheduling and the testing of fabricated wafers in semiconductor manufacturing. In this dissertation, therefore, we extend the existing works to consider the following three types of scheduling problems with machine availability and eligibility constraint simultaneously. We first consider the first type of the scheduling problem where the objective is to minimizing the maximum makespan (Cmax). Then, we consider the second type of scheduling problem where the objective is to minimizing the minimum lateness (Lmax). Finally, we extend the result of the second type of scheduling problem to deal with the more general scheduling problem where the job preemption is not allowed.
For the minimization of Cmax, we utilize a network flow approach to formulate the scheduling problem into a series of maximum flow problem, and propose a polynomial time algorithm to solve the scheduling problem optimally. For the minimization of Lmax, we first introduce the concept of the critical values, and then apply the network flow approach for developing a two-phase binary search algorithm to solve the problem optimally. Finally, we extend the result of the second type of scheduling problem to derive a lower bound of the scheduling problem in which job preemption is not allowed; and then we investigate the characteristics of jobs and machines to find related propositions for developing a branch and bound algorithm to solve the scheduling problem optimally.

關鍵字(中)

★ 機器合適度限制
★ 排程
★ 平行機台
★ 網路流量
★ 分支定界演算法
★ 機器可用時間限制

關鍵字(英)

★ Scheduling
★ Parallel machines
★ Network flows
★ Branch and bound algorithm
★ Machine availability constraint
★ Machine eligibility constraint

論文目次

摘要 i
Abstract iii
Table of Content v
List of Figures vii
List of Tables viii
Chapter 1 Introduction 1
1.1 Background and motivation 1
1.2 Problem definition 2
1.3 Research objectives 3
1.4 Research methodology and framework 4
1.4.1 Research methodology 4
1.4.2 Research framework 4
Chapter 2 Literature review 7
2.1 Machine availability constraint 7
2.2 Machine eligibility constraint 8
Chapter 3 Network flow model for preemptive scheduling problem 11
3.1 Minimizing maximum makespan 12
3.1.1 Obtaining the time epoch set and determining the time interval 13
3.1.2 Constructing network for the based problem with 14
3.1.3 Developing binary search algorithm 23
3.1.3.1 Verifying the feasibility of the problem and determining a lower bound and an upper bound of the optimal Cmax 24
3.1.3.2 Binary search algorithm 26
3.2 Minimizing maximum lateness: 28
3.2.1 Constructing network for the based problem with 29
3.2.2 Developing two-phase binary search algorithm 34
3.2.2.1 Defining the critical values and obtaining the critical value set 34
3.2,2.2 Verifying the feasibility of the problem and determining a lower bound and an upper bound of the optimal Cmax 36
3.2.2.3 Phase I: finding two adjacent critical values 37
3.2.2.4 Phase II: searching the optimal Lmax within the range specified by two adjacent critical values found at Phase I 38
3.2.2.5 The proposed two-phase binary search algorithm 39
Chapter 4 Applicability of the network flow model 44
4.1 Branching scheme 44
4.2 Propositions 46
4.3 Bounding scheme 49
4.4 Branch and bound algorithm 50
4.5 An illustrative example 52
4.6 Computational results 55
Chapter 5 Conclusion 60
References 62

參考文獻

1. Ahuja, R.K., T.L. Magnanti and J.B.Orlin (1993), Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, New Jersey).
2. Ahuja, R.K., and J.B. Orlin (1989), A fast and simple algorithm for the maximum flow problem, Operations Research 37 (5), 748-759.
3. Blazewicz, J., M. Drozdowski, P. Formanowicz, W. Kubiak, and G. Schmidt (2000), Scheduling preemptable tasks on parallel processors with limited availability, Parallel Computing 26, 1195-1211.
4. Blazewicz, J., K. Ecker, E. Pesch, G. Schmidt, and J. Weglarz (2001), Scheduling Computer and Manufacturing Processes (Springer, Berlin).
5. Blazewicz, J., K. Ecker, G. Schmidt, and J. Weglarz (1993), Scheduling in Computer and Manufacturing Systems (Springer, Berlin).
6. Centeno, G., and R.L Armacost (1997), Parallel machine scheduling with release time and machine eligibility restrictions, Computers & Industrial Engineering 33(1-2), 273-276.
7. 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.
8. Dantzig, G. B., and D. R. Fulkerson (1956), On the max-flow min-cut theorem of networks, in: H. W. Kuhn, A. W. Tucker (eds.), Liner Inequalities and Related Systems, Annals of Mathematics Study 38 (Princeton University Press, Princeton, New York) 215-221.
9. Ford, L.R., and D.R. Fulkerson (1956), Maximal flow through a network, Canadian Journal of Mathematics 8, 399-404.
10. Fulkerson, D.R., and G.B. Dantzig (1955), Computations of maximum flow in networks, Naval Research Logistics Quarterly Quart 2, 277-283.
11. Gharbi, A., and M. Haouari (2005), Optimal parallel machines scheduling with availability constraints, Discrete Applied Mathematics 148, 63-87
12. Graham, R.L., E.L. Lawer, J.K. Lenstra, and A.H.G. Rinnooy Ken (1979), Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics 5, 287-326.
13. Horn, W.A. (1974), Some simple scheduling algorithms, Naval Research Logistics Quarterly 21, 177-185.
14. Hwang, H.C., and S.Y. Chang (1998), Parallel machines scheduling with machine shutdowns, Computers & Mathematics with Applications 36(3), 21-31.
15. Hwang, H.C., S.Y. Chang, and K. Lee (2004), Parallel machine scheduling under a grade of service provision, Computer & Operations Research 31, 2055-2061.
16. Hwang, H.C., K. Lee, and S.Y. Chang (2005), The effect of machine availability on the worst-case performance of LPT, Discrete Applied Mathematics 148, 49-61.
17. Kellerer, H. (1998), Algorithm for multiprocessor scheduling with machine release time, IIE Transactions 30, 991-999.
18. Lawer, E.L. (1976), Combinational Optimization: Networks and Matroids (Holt, Rinehart & Winston, New York).
19. Labetoulle, J., E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnoy Kan (1984), Preemptive scheduling of uniform machines subject to release dates, in: W.R. Pulleyblank (eds.), Progress in Combinatorial Optimization (Academic Press, New York) 245-261.
20. Lee, C.Y. (1991), Parallel machines scheduling with nonsimultaneous machine available time, Discrete Applied Mathematics 30, 53-61.
21. Lee, C.Y. (1996), Machine scheduling with an availability constraint, Journal of Global Optimization 9, 395-416.
22. Lee, C.Y., L. Lei, and M. Pinedo (1997), Current trends in deterministic scheduling, Annals of Operations Research 70, 1-41.
23. Lee, C.Y., Y. He, and G. Tang (2000), A note on “parallel machine scheduling with non-simultaneous machine available time”, Discrete Applied Mathematics 100, 133-135.
24. Liao, C.J., D.L. Shyur, and C.H. Lin (2005), Makespan minimization for two parallel machines with an availability constraint, European Journal of Operational Research 160, 445-456.
25. Lin, G..H., E.Y. Yao, and Y. He (1998), Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times, Operations Research Letters 22, 75-81.
26. Liu, Z., and E. Sanlaville (1995), Profile scheduling of list algorithm, in: P. Chretienne et al. (eds.), Scheduling Theory and its Applications (Wiley, New York) 91-110.
27. Lin, Y., and W. Li (2004), Parallel machine scheduling of machine-dependent jobs with unit-length, European Journal of Operational Research 156, 261-266.
28. Pinedo, M. (2002), Scheduling: Theory, Algorithm and System (New Jersey, Prentice Hall).
29. Sanlaville, E. (1995), Nearly on line scheduling of preemptive independent tasks, Discrete Applied Mathematics 57, 229-241.
30. Sanlaville, E., and G. Schmidt (1998), Machine scheduling with availability constraints, Acta Informatica 35, 795-811.
31. Schmidt, G. (1984), Scheduling on semi-identical processors, Zeitschrift für Operations Research A28, 153-162.
32. Schmidt, G. (1988), Scheduling independent tasks with deadlines on semi-identical processors, Journal of the Operational Research Society 39, 271-277.
33. Schmidt, G. (2000), Scheduling with limited machine availability, European Journal of Operational Research 121, 1-15.
34. Takao, A., and A. Yasuhito (2000), Recent developments in maximum flow algorithms, Journal of the Operations Research Society of Japan 43(1), 2-31.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2006-9-27

推文