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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：22

、訪客IP：3.140.198.43

姓名

盧寶后(Baw-Ho Lu) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

具機器可用時間與機器合適度限制之平行機台排程問題
(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 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(英)

In this paper we consider the problem of scheduling n non-preemptive jobs on m identical machines with availability and eligibility constraints for minimizing the maximum lateness. That is, each machine is not continuously available at all time and each job is only allows to be processed on specified machines. Each availability interval of machines has a specific service level, and each job has to be processed at availability intervals with the service level specified or higher one.
We develop a branch-and-bound algorithm to solve this scheduling problem optimally. Firstly, we propose an algorithm based on the Least Flexible Job First/ Earliest Due Date First (LFJ/EDD) rule to find the upper bound. Network flow technique is used to model the scheduling problem of the preemptive jobs into a series of base problem that is equivalent to a maximum flow problem. Then, we propose a polynomial time algorithm that combines a maximum flow algorithm and binary search procedure to solve this scheduling problem optimally and use this result as our lower bound.
Computational experiments are proposed to compare the validity with complete branching method and to test the efficiency of proposed branch and bound algorithm. According to the result of computational experiment, we find that the run time of our algorithm is acceptable.

關鍵字(中)

關鍵字(英)

★ Scheduling
★ branch and bound
★ network flows
★ par

論文目次

Table of Content
Abstract i
Table of Content ii
List of Tables iv
List of Figures v
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem Description 4
1.3 Research Objectives 5
1.4 Research Methodology and Framework 5
1.4.1 Research Methodology 5
1.4.2 Research Framework 6
Chapter 2 Literature Review 8
2.1 Machine Availability Constraint 8
2.2 Machine Eligibility Constraint 12
Chapter 3 Branch and Bound Algorithm 15
3.1 Notation 15
3.2 Bounding Scheme 17
3.2.1 Upper Bound 18
3.2.2 Lower Bound 22
3.3 Branching Scheme 42
3.3.1 Node Representation 42
3.3.2 The branching process 42
3.3.3 The Proposed Branch and Bound Algorithm for the Problem 45
Chapter 4 Computational Analysis 48
4.1 Test Generation 48
4.2 Validation of the Branch and Bound Algorithm 49
4.3 Evaluation of the Branch and Bound Algorithm 50
4.3.1 Comparing with complete branching method 51
4.3.2 The Performance of the Branch and Bound Algorithm 53
Chapter 5 Conclusion 57
5.1 Research Contribution 57
5.2 Limitation Research 58
5.3 Further Research 58
References 59

參考文獻

[1] 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.
[2] 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.
[3] 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.
[4] 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.
[5] Ecker, K., G. Schmidt, J. Weglarz, and J. Blazewicz (1994), Scheduling in Computer and Manufacturing Systems (2th ed.), Springer-Verlag, Berlin.
[6] Federgruen, A., and H. Groenevelt (1986), “Preemptive scheduling of uniform machined by ordinary network flow techniques,” Management Science, 32(3), 341-349.
[7] Hwang, H.C., and S.Y. Chang (1998), “Parallel machines scheduling with machine shutdowns,” Computers & Mathematics with Applications, 36(3), 21-31.
[8] 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.
[9] Kellerer, H. (1998), “Algorithm for multiprocessor scheduling with machine release time,” IIE Transactions, 30, 991-999.
[10] Lee, C.Y. (1991), “Parallel machines scheduling with nonsimultaneous machine available time,” Discrete Applied Mathematics, 30, 53-61.
[11] Lee, C.Y. (1996), “Machine scheduling with an availability constraint,” Journal of Global Optimization, 9, 395-416.
[12] 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.
[13] Lin, Y., and W. Li (2004), “Parallel machine scheduling of machine-dependent jobs with unit-length,” European Journal of Operational Research, 156, 261-266.
[14] Liu, Z., and E. Sanlaville (1995), “Preemptive scheduling with variable profile, precedence constraints and due dates,” Discrete Applied Mathematics, 58, 253-280.
[15] Liu, Z., and E. Sanlaville (1994), Profile scheduling of list algorithm, In: Chretienne, P. et al. (Eds.), Scheduling Theory and its Applications, NY: Wiley, p.91-110.
[16] Pinedo, M. (2002), Scheduling: Theory, Algorithm and System (2th ed.), Prentice Hall, Englewood Cliffs, NJ.
[17] Sanlaville, E. (1995), “Nearly online scheduling of preemptive independent tasks,” Discrete Applied Mathematics, 57, 229-241.
[18] Schmidt, G. (1988), “Scheduling independent tasks with deadlines on semi-identical processors,” Journal of the Operational Research Society, 39, 271-277.
[19] Schmidt, G. (2000), “Scheduling with limited machine availability,” European Journal of Operational Research, 121, 1-15.
[20] Ullman, J.D. (1975), “NP-complete scheduling problems,” Journal of Computer and System Sciences, 10, 384-393.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2005-7-3

推文