迴流工作具最小與最大時間延滯限制之平行機台排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：30

、訪客IP：3.21.244.95

姓名

詹珮芸(Pei-Yun Chan) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

迴流工作具最小與最大時間延滯限制之平行機台排程問題
(Parallel Machine Scheduling with Minimal and Maximal Time Lags for Reentrant Job)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

本研究主旨為探討一平行機台排程問題，其作業具迴流特性，且迴流時間需滿足最大與最小時間延滯之限制;其機台具可用時間與合適度限制，目標為使總完工時間最小化。每個作業可重複於同一機台加工多次，但兩次重複加工之間隔時間受到時間延滯(Time Lags)的限制。每個機台只有某些時間區段可以被安排處理工作，每個工作也只能被安排在某些特定的機器上。
我們設置虛擬工作取代各機台不可被使用的時間，並將問題分成兩個階段：
(1)提出一個分枝界限演算法搜尋可行的作業與機台指派組合，利用機台合適度限制進行分枝，發展定界法則提昇演算效率，並將指派結果以分離圖(Disjunctive Graph)表示；(2)利用先前研究提出的分枝定界法(沈國基與廖祿文，2007)求解(1)所得結果之排程解，即分別求解m個單機台排程問題，並以最後完工的作業作為總完工時間。
實驗的分析顯示，在總作業數大於五且機器合適度比率為八十的情境下，定界法則可刪去百分之八十以上的節點，顯著地提昇演算法的效率。我們提出的演算法可用於求解10個作業與3台機器的排程問題，並可獲得最佳解。

摘要(英)

In this paper we study the problem of scheduling recirculation jobs on identical parallel machines with eligibility and availability restrictions when minimizing the makespan. Namely, each job may visit a machine more than once and is only allowed to be processed on specific machines; each machine is not always available for processing. Besides, minimal and maximal time lag constraints on the starting time of each reentrant job are also considered.
We develop two branch and bound algorithms to solve the scheduling problem optimally. One is to deal with the jobs allocation problem with machine eligibility, and the other is to schedule the sequence on each allocated machine with minimal and maximal time lags constraints. We introduce a dummy job to denote each machine unavailable interval, and propose the first branch and bound algorithm which uses the
depth first strategy to allocate jobs. We transform the scheduling problem corresponding to each leaf node into m single machine problems, which can be represented by a disjunctive graph. Finally, we use the second branch and bound algorithm adopted from Sheen and Lao (2007) for obtaining the optimal solution for each single machine problem to find the maximum makespan.
Computational analysis shows that the eliminating rules proposed is effective and can eliminate more than 80% node when the total operation number is larger than 5 with eighty percent in generating machine availability by the branch and bound algorithm. Our algorithm can get the optimal solution for the problem with up to 10 operations and 3 machines.

關鍵字(中)

★ 平行機台
★ 分枝界限法
★ 排程
★ 合適度限制
★ 迴流
★ 時間延滯限制
★ 可用時間限制

關鍵字(英)

★ Parallel machine
★ Branch and bound
★ Reentrant
★ Scheduling
★ Minimal and maximal time lags
★ Availability constraint
★ Eligibility constraint

論文目次

摘要................................................................................................................................i
Abstract........................................................................................................................ii
致謝.............................................................................................................................. iii
Table of Content ..........................................................................................................iv
List of Figures..............................................................................................................vi
List of Tables...............................................................................................................vii
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 Frame Work.........................................................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 Minimum and Maximum Time Lags ...............................................................9
2.4 Re-entrant Scheduling....................................................................................10
Chapter 3 Branch and Bound Algorithm ................................................................12
3.1 Notations ........................................................................................................12
3.2 Transform ansform P , NC M , recrcCmax m win j into max P M , recrcC m j ...................14
3.3 Branching and Bound Algorithm for the Problem max P M , recrcC m j .........16
3.3.1 Branching Scheme ..............................................................................16
3.3.2 Disjunctive Graph ...............................................................................18
3.3.3 Bounding Scheme ...............................................................................21
3.4 Branching and Bound Algorithm for the Problem max 1recrcC with Minimal
and Maximal Time Lags Constraints ...........................................................24
3.4.1 Propositions ........................................................................................25
3.4.2 Adjustment of Starting Time Intervals, Release Times and Tail Values
......................................................................................................................27
3.4.3 Bounding Scheme ...............................................................................29
3.4.4 Branching............................................................................................29
3.4.5 Feasible Schedule................................................................................31
3.5 Branch and Bound Algorithm for the Problem max P M , recrcC m j with
Minimum and Maximum Time Lags ...........................................................31
Chapter 4 Computational Analysis ..........................................................................35
4.1 Test Problem Generation................................................................................35
4.2 Validation of the Branch and Bound Algorithm ............................................36
4.3 Evaluation of the Branch and Bound Algorithm............................................37
Chapter 5 Conclusion .............................................................................................43
5.1 Research Conclusion and Contribution .........................................................43
5.2 Research Limitation.......................................................................................44
5.3 Further Research ............................................................................................44
References...................................................................................................................46
Appendix. Branch and bound algorithm for the one-machine scheduling problem
with minimum and maximum time lags ..................................................................49

參考文獻

1. Bartusch, M., R.H. Mohring, and F.J. Radermacher. 1988. Scheduling project networks with resource constraints and time windows. Annals of Operation Research 16 201-240.
2. Birger, F., K. Neumann, and C. Schwindt. 2001. Project scheduling with calendars. OR Spektrum 23 325–334.
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. Brucker, P., A. Drexl, R. Mohring, K. Neumann and E. Pesch. 1999. Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research 112 3–41.
6. Carlier, J., and E. Pinson. 1989. An algorithm for solving the job shop problem. Management Science 35 164–176.
7. Carlier, J., and E. Pinson. 1990. A practical use of Jackson’s preemptive schedule for solving the job-shop problem. Annals of Operations Research 26 269–287.
8. Carlier, J., and E. Pinson. 1994. Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research 78 146–161.
9. Centeno, G., and R.L. Armacost. 1997. Parallel machine scheduling with release time and machine eligibility restrictions. Computers & Industrial Engineering 33 273-276.
10. 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 1243-1256.
11. He, R.J. 2005. Parallel machine scheduling problem with time windows: a constraint programming and tabu search hybrid approach. Proceedings of the Fourth International Conference on Machine Learning and Cybernetics 18-21 August.
12. Heilmann, R. 2003. A branch and bound procedure for the multi-mode resource constrained project scheduling problem. European Journal of Operational Research 144 348-365.
13. Hwang, H.C., and S.Y. Chang. 1998. Parallel machines scheduling with machine shutdowns. Computers & Mathematics with Applications 36 21-31.
14. 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.
15. Kellerer, H. 1998. Algorithm for multiprocessor scheduling with machine release time. IIE Transactions 30 991-999.
16. Lee, C.Y. 1996. Machine scheduling with an vailability 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. Lin, Y., and W. Li. 2004. Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research 156 261-266.
19. Liu, Z., and E. Sanlaville. 1995. Preemptive scheduling with variable profile. precedence constraints and due dates. Discrete Applied Mathematics 58 253-280.
20. Mason, S. J., and K. Oey. 2003. Scheduling complex job shops using disjunctive graphs: a cycle elimination procedure. Int. J. Prod. Res. 41 981–994.
21. Neumann, K., and C. Schwindt. 1997. Activity-on-node networks with minimal and maximal time lags. OR Spektrum 19 205-217.
22. Neumann, K., C. Schwindt, and J. Zimmermann. 2003. Order-based neighborhoods for project scheduling with nonregular objective functions. European Journal of Operational Research 149 325-343.
23. Pinedo, M. 2002. Scheduling: theory, algorithm and system 2nd ed. Englewood Cliffs, NJ: Prentice-Hall.
24. Rojanasoonthon, S., and J. Bard. 2005. A GRASP for parallel machine scheduling with time windows. INFORMS Journal on Computing 17 32-51.
25. Sanlaville, E. 1995. Nearly online scheduling of preemptive independent tasks. Discrete Applied Mathematics 57 229-241.
26. Schmidt, G. 1988. Scheduling independent tasks with deadlines on semi-identical processors. Journal of the Operational Research Society 39 271-277.
27. Schmidt, G. 2000. Scheduling with limited machine availability. European Journal of Operational Research 121 1-15.
28. Sheen, G..J., and L.W. Liao. 2007. A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags.European Journal of Operational Research 181 102-116.
29. Ullman, J.D. 1975. NP-complete scheduling problems. Journal of Computer and System Sciences. 10 384-393.
30. Wang, M. Y., S. P. Sethi, and S. L. van de Velde. 1997. Minimizing makespan in a class of reentrant shops. Operations Research 45 702–712.
31. Yu, Y. D. 1999. Parallel machine scheduling with eligibility constraints for reentrant job. Unpublished Master Thesis, Institute of Industrial Management,
National Central University
32. Zoghby, J., J. W. Barnes, and J. J. Hasenbein. 2005. Modeling the reentrant job shop scheduling problem with setups for metaheuristic searches. European Journal of Operational Research 167 336-348.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2007-7-23

推文