在具機器可用時間與機器合適度限制之平行機台排程問題下運用分枝界限法尋求最佳解

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：15

、訪客IP：18.117.111.1

姓名

林正峰(Cheng-Feng Lin) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

在具機器可用時間與機器合適度限制之平行機台排程問題下運用分枝界限法尋求最佳解
(Branch and Bound Algorithm for Parallel Machine Scheduling with Availability and Eligibility Constraints)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

在此研究中，我們考慮當極小化最大延遲時間時，在具機器可用時間與機器合適度限制下，n個不可分割的工作和m台平行機台的排程問題。每台機器只有某些時間區段可以被安排處理工作，每個工作也只能被安排在某些特定的機器上，每個工作和機器上的每個可用的時間區段都有特定的服務水準，而只有當這個時間區段的服務水準高於或等於工作的服務水準時，此工作才能被安排在這個時間區段內。
我們提出一個分枝界限法去尋找這個問題的最佳解。首先，網路流技術用來闡述可分割工作的排程問題並將其轉變成最大流量問題。然後，我們提出一個演算法其結合網路流技術和二元搜尋法去找到其問題的最佳解，並將其結果作為我們的下限。最後，我們提出五個支配的法則來提升分枝界限法的效率。
實驗的分析顯示，所提出的淘汰法則是非常強而有力的並且在分枝界限法中只有非常小的比例的節點被產生。我們的演算法能用於20個工作和7台機器問題下而得到一個最佳解。

摘要(英)

In this paper we consider the problem of scheduling n non-preemptive jobs on m identical machines with machine availability and eligibility constraints when minimizing the maximum lateness. Each machine is not always available for processing and each job is only allowed to be processed on specific machines. Each job and availability interval of machines has a specific service level. Each job has to be processed at availability interval with the service level specified or higher one.
We propose a branch and bound algorithm to find out the optimal solution of this problem. Firstly, network flow technique is used to formulate the scheduling problem of the preemptive jobs into a series of maximum flow problems. Then, we propose an algorithm which combines a network flow technique and a binary search procedure to find an optimal solution for the problem and use this result as our lower bound. Finally, we propose five dominance rules to increase the efficiency of the branch and bound algorithm.
Computational analysis shows that the effectiveness of eliminating rules proposed is powerful and very low percentage of nodes is generated by the branch and bound algorithm. Our algorithm can get the optimal solution for the problem with up to 20 jobs and 7 machines.

關鍵字(中)

★ 排程
★ 網路流
★ 平行機台
★ 分枝界限法
★ 服務水準限制
★ 合適度限制
★ 可用時間限制

關鍵字(英)

★ Scheduling
★ network flow
★ branch and bound
★ parallel machine
★ availability constraint
★ service level constraint
★ eligibility constraint

論文目次

中文摘要 i
Abstract ii
致謝 iii
Table of Content iv
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 Framework 3
1.4.1 Research Methodology 3
1.4.2 Research Framework 4
Chapter 2 Literature Review 6
2.1 Machine Availability Constraint 6
2.2 Machine Eligibility Constraint 7
2.3 Network Flow Approach 8
2.4 Machine Availability and Eligibility Constraints 8
Chapter 3 Branch and Bound Algorithm 10
3.1 Notations 10
3.2 Bounding Scheme 12
3.2.1 The Base Problem for 12
3.2.2 Obtain the Time Epoch Set E and Determine Time Interval 13
3.2.3 Construct Network 14
3.3 Proposed Algorithm for Solving the Problem 18
3.3.1 Define the Critical Values and Obtain the Set L 18
3.3.2 Propositions 20
3.3.3 Phase I: Find Two Adjacent Critical Values 22
3.3.4 Phase II: Search the Optimal within the Range Specified by Two Adjacent Critical Values Found at Phase I. 22
3.3.5 Two-Phase Binary Search Algorithm 24
3.4 Branching Scheme 27
3.4.1 Dominance Rules 29
3.4.2 Branch and Bound Algorithm for the Problem 33
Chapter 4 Computational Analysis 36
4.1 Test Problem Generation 36
4.2 Validation of the Branch and Bound Algorithm 37
4.3 Performance of the Branch and Bound Algorithm 39
Chapter 5 Conclusion 51
5.1 Research Contribution 51
5.2 Further Research 51
References 53

參考文獻

[1] 樊志育 (1986), “廣告學,” 三民書局, 台北市
[2] 盧寶后 (2005), “具機器可用時間與機器合適度限制之平行機台排程問題,” 國立中央大學工業管理研究所碩士論文
[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., P. Dell’Olmo, M. Drozdowski, and P. Maczka (2003), “Scheduling multiprocessor tasks on parallel processors with limited availability,” European Journal of Operational Research, 149, 377-389.
[5] Bollapragada, S., H. Cheng, M. Phillips, M. Garbiras, M. Scholes, T. Gibbs, and M. Humphreville (2002), “NBC’s Optimization System Increase Revenues and Productivity,” Interfaces, 32(1), 47-60.
[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] De Reyck, B, and 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.
[9] Gharbi, A. and M. Haouari, (2005) “Optimal parallel machines scheduling with availability constraints,” Discrete Applied Mathematics, 148, 63-87.
[10] Horn, W.A, (1974), “Some simple scheduling algorithms,” Naval Research Logistics Quarterly, 21, 177-185.
[11] Hwang, H.C., and S.Y. Chang (1998), “Parallel machines scheduling with machine shutdowns,” Computers & Mathematics with Applications, 36(3), 21-31.
[12] Hwang, H.C., S.Y. Chang, and K. Lee (2004), “Parallel machine scheduling under a grade of service provision,” Computers & Operation Research, 31, 2055-2061.
[13] Kellerer H. (1998), “Algorithm for multiprocessor scheduling with machine release time,” IIE Transactions, 30, 991-999.
[14] 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.
[15] Lee, C.Y. (1991), “Parallel machines scheduling with nonsimultaneous machine available time,” Discrete Applied Mathematics, 30, 53-61.
[16] Lee, C.Y. (1996), “Machine scheduling with an availability constraint,” Journal of Global Optimization, 9, 395-416.
[17] 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.
[18] Liao, L.W., and G.J. Sheen, “Parallel machine scheduling with machine availability and eligibility constraints” Working Paper, National Central University, Chung-Li, Taiwan, ROC
[19] Lin, Y., and W. Li (2004), “Parallel machine scheduling of machine-dependent jobs with unit-length,” European Journal of Operational Research, 156, 261-266.
[20] Liu, Z., and E. Sanlaville (1995), “Preemptive scheduling with variable profile, precedence constraints and due dates,” Discrete Applied Mathematics, 58, 253-280.
[21] Pinedo, M. (2002), Scheduling: Theory, Algorithm and System (2th ed.), Prentice Hall, Englewood Cliffs, NJ.
[22] Sanlaville, E. (1995), “Nearly online scheduling of preemptive independent tasks,” Discrete Applied Mathematics, 57, 229-241.
[23] Schmidt, G. (1988), “Scheduling independent tasks with deadlines on semi-identical processors,” Journal of the Operational Research Society, 39, 271-277.
[24] Schmidt, G. (2000), “Scheduling with limited machine availability,” European Journal of Operational Research, 121, 1-15.
[25] Sheen, G..J., and L.W. Liao (2005), “Scheduling machine-dependent jobs to minimize lateness on identical machines with availability constraints,” Computers & Operations Research. (Accepted)(SCI)
[26] Ullman, J.D. (1975), “NP-complete scheduling problems,” Journal of Computer and System Sciences, 10, 384-393.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2006-7-16

推文