博碩士論文 994206006 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:26 、訪客IP:3.235.30.155
姓名 林于鉉(Yu-hsuan Lin)  查詢紙本館藏   畢業系所 工業管理研究所
論文名稱 具最小與最大時間延遲限制之零工式排程問題
(Job-Shop Scheduling Problem withMinimum and Maximum Time Lags)
相關論文
★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討-以平面式觸控面板產業為例★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   至系統瀏覽論文 ( 永不開放)
摘要(中) 本論文主要在探討具有最大時間區間與最小時間區間限制特性的零工式生產( job-shop)排程問題,此限制類型的問題常見於工業環境中,例如:半導體產業的蝕刻製程,化學產業的鍍鎳製程等等,當一工件從前一工作站完工後,需要等待一段時間才能進入至下一工作站進行加工,該工件都至少必須等待一定的最小時間,同時等待不能超過一定的最大時間,因此最小與最大等候時間區制須要考慮每個工件能開始加工的時間。針對此問題我們將發展一結合 Carlier and Pinson (1989),Sheen and Liao (2007) and Pinedo (2008)提出的演算法,利用開始時間與最大最小完工時間的限制減少需要展開的時間與節點數量,並求得最佳解。
摘要(英) We consider the job shop scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem is common in a manufacturing environment where the next job has to be carried out within a specific time range after the completion of the immediately preceding job. Each operation in job shop system must be waiting for the lower bound of waiting time but do not exceed the upper bound of waiting time to perform the next operation. Besides, minimum and maximum time lags constraints on the starting time of each operation are also considered.
We describe a branch and bound algorithm, based on the input and output of a clique and relevant propositions, for finding the optimal waiting times. There are n jobs have to be processed on m machines in order to minimize makespan. We incorporate the concept of head and tail which proposed from Carlier and Pinson (1989) and the branch and bound algorithm proposed by Sheen and Liao (2007) to solve the job-shop scheduling with minimum and maximum time lags problem. With the proposed branch and bound algorithm, we can either find an optimal schedule or establish the infeasibility within an acceptable run time.
關鍵字(中) ★ 零工式生產環境。
★ 等候時間窗口
★ 枝界法
關鍵字(英) ★ job shop problem
★ minimum and maximum time lags
論文目次 摘要 ............................................................................................................................................ I
Abstract ...................................................................................................................................... II
Outline ...................................................................................................................................... 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 .................................................................. 5
1.4.1 Research methodology ............................................................................... 5
1.4.2 Research framework ................................................................................... 5
Chapter 2 Literature Review ...................................................................................................... 8
2.1 Disjunctive Graph ......................................................................................................... 8
2.2 Job Shop Problem ......................................................................................................... 9
2.3 Minimum and Maximum Time Lags .......................................................................... 11
2.4 Job-shop Problem With Time Lags ............................................................................ 13
Chapter 3 Branch and Bound Algorithm .................................................................................. 15
3.1 Notations ..................................................................................................................... 15
3.2 Problem Statement ...................................................................................................... 17
3.3 Propositions ................................................................................................................ 20
3.4 Branching scheme ...................................................................................................... 23
3.5 Adjustment of Starting Time Intervals, Release Times and Tail Values ..................... 27
IV
3.6 Bounding Scheme ....................................................................................................... 28
3.7 Algorithms .................................................................................................................. 29
Chapter 4 Computational Analysis ........................................................................................... 34
4.1 Test Problem Generation ............................................................................................ 34
4.2 Validation of the Branch and Bound Algorithm ......................................................... 35
4.3 Evaluation of the Branch and Bound Algorithm ........................................................ 36
Chapter 5 Conclusion ............................................................................................................... 39
5.1 Research Conclusion and Contribution ...................................................................... 39
5.2 Research Limitation .................................................................................................... 40
5.3 Further Research ......................................................................................................... 40
References ............................................................................................................................... 42
Appendix ................................................................................................................................. 45
參考文獻 1. Adams, J., E. Balas., and D. Zawack. (1988), The shifting bottleneck procedure for job-shop scheduling. Management Science 34 (3), 391±401.
2. Balas, E.(1969), Machine Sequencing via Disjunctive Graphs: An Implicit Enumeration Algorithm, Operations Research, Vol. 17, No. 6. (Nov. - Dec.), pp. 941-957.
3. Baker KR.(1974), Introduction to Sequencing and Scheduling. Wiley: New York.
4. Brucker, P., B. Jurisch., and A. Kramer (1994a), The job-shop problem and immediate selection. Annals of Operations Research ;50; 73-114.
5. Brucker, P., B. Jurisch., and B. Sievers. (1994b), A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics;49; 107-127
6. Brucker, P., T. Hilbig., and J. Hurink. (1999a), A branch and bound algorithm for a single-machine scheduling problem with positive and negative time lags. Discrete applied mathematics; vol:94 iss:1-3 pg:77
7. Brucker, P., S. Knust., T.C.E. Cheng., and N.V. Shakhlevich. (2004), Complexity results for flow-shop and open-shop scheduling problems with transportation delays. Annals of Operations Research; vol:129 iss:1 pg:81
8. Carlier J.(1982), The one-machine sequencing problem. European Journal of Operational Research ;11; 42-47.
9. Carlier, J., and E. Pinson. (1989), An algorithm for solving the job shop problem. Management Science 35 164–176
10. 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.
11. Carlier, J., and E. Pinson. (1994), Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research 78 146–161.
12. Chu C, Proth J-M.(1996), Single machine scheduling with chain structured precedence constraints and separation time windows. IEEE Transactions on Robotics and Automation ;12(6):835–43.
13. Deo, N.(1974), Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, NJ.
14. Dauzere-Peres S., and J.B. Lasserre. (1993), A modified shifting bottleneck procedure for job-shop scheduling. International Journal of Production Research 31(4); 923-932.
15. Dell’Amico M. (1996), Shop problems with two machines and time lags. Operations Research ;44(5):777–87.
16. Fondrevelle, J., A Oulamara and M.C. Portmann (2006), Permutation flowshop scheduling problems with maximal and minimal time lags. Computers & operations research ; vol:33 iss:6 pg:1540
17. Garey, M.R., and D.S. Johnson. (1979), Computers and Intertractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA.
18. Hurink, J., and J. Keuchel. (2001), Local search algorithm for a single-machine scheduling problem with positive and negative time-lags. Discrete Applied Mathematics ;112; 179-197.
19. Jain, A.S., and S. Meeran. (1999), Deterministic job-shop scheduling: Past, present and future. European journal of operational research ; vol:113 iss:2 pg:390
20. Muth, J.F., and G.L. Thompson. (eds.) (1963), Industrial Scheduling, Prentice-Hall, Englewood Cliffs, NJ.
21. Neumann, K., Schwindt, C., 1997. Activity-on-node networks with minimal and maximal time lags and their application to make-to-order production. OR Spektrum 19, 205–217.
22. Neumann, K., Zhan, J., 1995. Heuristics for the minimum project-duration problem with minimal and maximal time-lags under fixed resource constraints. Journal of Intelligent Manufacturing 6, 145–154.
23. Neumann, K., Schwindt, C., Zimmermann, J., 2002. Recent results on resource-constrained project scheduling with time windows: Model, solution methods, and applications. Central European Journal of Operations Research 10, 113–148.
24. Neumann, K., Schwindt, C., Zimmermann, J., 2003. Order-based neighborhoods for project scheduling with nonregular objective functions. European Journal of Operational Research 149, 325–343.
25. Roy, B., and B. Sussman. (1964), Les problemes d’ordonnancement avec constraintes disjonctives, SEMA, Note D.S., No. 9, Paris.
26. Rinnooy Kan, A.H.G. (1976), Machine scheduling problems: Classification, complexity and computations. In: Stenfert Kroese, H.E., Leiden, B.V. (Eds.), Martinus Nijhoff, The Hague, The Netherlands.
27. 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.
28. White, K.P., and R.V. Rogers. (1990), Job-shop scheduling: Limits of the binary disjunctive formulation. International Journal of Production Research 28 (12), 2187±2200.
29. Wikum, E.D., D.C. Llewllyn., and G..L. Nemhauser. (1994), One-machine generalized precedence constrained scheduling problems. Operations Research Letters 16; 87-99.
30. Yang, D.L., and M.S. Chern. (1995),A two-machine flow-shop sequencing problem with limited waiting time constraint. Computers & Industrial Engineering ;28; 63-70.
指導教授 沈國基(Gwo-ji Sheen) 審核日期 2012-7-19
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明