跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/08/04 01:23
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:張偉立
論文名稱:利用分支界限法求解多資源零工式生產排程
論文名稱(外文):Solving multiple-resource job shop scheduling by branch-and-bound technique
指導教授:洪一峰洪一峰引用關係
學位類別:碩士
校院名稱:國立清華大學
系所名稱:工業工程與工程管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:61
中文關鍵詞:多資源離散圖形分支界限法零工式生產排程
外文關鍵詞:multiple-resourcedisjunctive graphbranch-and-bound techniquejob shop scheduling
相關次數:
  • 被引用被引用:8
  • 點閱點閱:451
  • 評分評分:
  • 下載下載:143
  • 收藏至我的研究室書目清單書目收藏:0
零工式生產排程(job shop scheduling)在生產排程上佔了很重要的角色,很多產業的排程問題是屬於零工式生產型態。近年來,關於零工式生產問題的研究很多,這些研究大多只考慮單一資源(single-resource)。在製造業中,機台常是唯一被考慮的資源,我們需要決定各種工件在有限機台上的加工順序,例如半導體產業,機器通常是非常昂貴的,所以數量是有限的。
現實的生產環境中,單一資源的零工式生產模型簡化了實際的狀況,當工件在某台機器上作業時,常需要輔以夾具或特殊的技術人員同時對工件做加工,夾具和特殊技術人員也可視為資源的一種,當一個作業同時需要兩個或兩個以上的資源,我們將這樣的生產環境稱為多資源(multiple-resource)的生產環境。我們希望求解多資源的零工式生產排程問題,若能將所有的資源妥善的規劃,有效率地運用有限的資源,定能減少不必要的損失。本論文主要研究的方向為如何產生一個合理且最佳的排程,其目標為得到最短的完工時間(makespan)。Giffler and Thompson【1960】以離散圖形表示零工式生產排程問題,運用分支界限法(branch-and-bound technique)求解目標為最小化完工時間的單一資源零工式生產排程問題。在本論文中,我們修改離散圖形表示多資源零工式生產排程問題,並且發展新的分支界限技巧求解這類問題。我們針對問題做多因子的實驗設計,並且分析這些因子是否顯著影響解題的時間,分析結果顯示資源數、工件數、作業數和資源使用頻率這四個因子對於解題時間是影響是顯著的。
Job shop scheduling plays an important role in production scheduling. Many manufacturing scheduling problems can be modeled as a job shop scheduling problem. In recently years, there are many research works related to job shop scheduling, but most of theses works consider only single-resource on an operation. In high tech industries, such as semiconductor manufacturing, only machines are considered as limited resource.
But, in many cases, an operation requires more than one resource. We call this kind of problem as multiple-resource scheduling. This research intends to solve multiple-resource job shop scheduling problem with the objective of minimizing makespan. Giffler and Thompson【1960】 introduced the disjunctive graph technique to represent job shop scheduling and used branch-and-bound technique to solve single-resource job shop scheduling problem. In this study, we modify disjunctive graph to represent multiple-resource job shop scheduling and develop a branch-and-bound technique to solve this problem. Experimental designs and statistical methods are used to evaluate and analyze the performance of the method. The results show that the number of resources, the number of jobs, the number of operations and the utilizations of resources affect the solution time used by branch-and bound method.
目錄
第一章 序論 ……………………….…………………………………………...1
1.1研究背景 ……………………………………………………………...1
1.2研究動機 ……………………………………………………………...1
1.3研究方法 ……………………………………………………………...2
1.4研究目的 …………………………………………………………….. 3
1.5論文架構 ……………………………………………………………...5
第二章 文獻探討 …………………………………………………...…………7
2.1零工式生產問題…………………………………………...……………7
2.1.1 零工式生產問題簡介……….……………………………………7
2.2求解零工式生產問題的方法………………………………………...…8
2.2.1數學模式方法(mathematical formulation)………..………...…8
2.2.2 分支界限法(branch-and-bound technique)………..………...…10
2.2.3 優先順序派工法則(priority dispatch rules)…………………….12
2.2.4 人工智慧方法(artificial intelligence)……..………..………...…14
2.2.5 區域搜尋法(local search)…………………………..………...…15
2.3 多資源(multiple resource)排程問題…………………………..……..15
第三章 方法建構…………………………………………………………16
3.1問題的定義和描述 ………………………………..………….………16
3.2離散圖形建構…………………………………....……………….……19
3.3分支界限法建構………………………………………………….……21
3.4 舉例說明……………………. ……………………..…………………32
第四章 實驗設計與分析 …………………...……………………………….43
4.1 舉例說明…………………………………….………………………...43
4.2實驗問題假設與參數設定……………………..……………….……48
4.3 實驗因子設定…... …………………………..…………………….……49
4.4 實驗分析……... …………………………..……....……………….……50
4.4.1實驗因子之變異數分析………………..…………………….……50
4.4.2 反應變數之統計值………………..………………………………51
第五章 結論與未來展望 …………………………………………..…..54
參考文獻 ………………………………………………………………..……….55









圖目錄
圖1.1 離散圖形(disjunctive graph)……….……………………...………..3
圖1.2 流程圖架構..………………………………………………………..6圖3.1 各種資源…………………………..………………………………16
圖3.2 回流現象…………………………………………………………..18
圖3.3 非主動的排程(non-active schedule)………………………………19
圖3.4 主動的排程(active schedule)……...………………………………19
圖3.5 以離散圖形表示多資源零工式生產問題………………………..20
圖3.6 離散弧線(disjunctive arc)以節點(3,1,2)為例……………………..21
圖3.7離散圖形………………………...…………………………………24
圖3.8完整分支樹狀圖...……………………………..……….………….24
圖3.9分支樹狀圖...…………………..……………….………………….26
圖3.10分支節點圖形,決定使用資源一之作業派序….…………..…..28
圖3.11作業排序的分支樹狀圖…..………..….…………………………29
圖3.12 ………………..……………………....…...………………………30
圖3.13 ………….…………………………………………………………31
圖3.14初始圖形……………………...………………….………….……32
圖3.15分支樹狀圖…………….…………………………………………33
圖3.16作業(1,1,3)離散弧線已被決定..…………………………………34
圖3.17決定作業後的圖形.………………………………………………35
圖3.18 …………………….………………………………………………35
圖3.19作業(3,1,4),(2,1,3)的離散弧線……………………………………36
圖3.20資源1作業排序分支樹狀圖……………………….……………37
圖3.21資源2作業排序分支樹狀圖……………………….……………38
圖3.22 資源4作業排序的分支樹狀圖………………………....………40
圖3.23每個分支節點的上界和下界值………………………...………..41
圖3.24分支界限法流程圖……………………………………...………..42
圖4.1小問題甘特圖………………….………………………..…………44
圖4.2中問題甘特圖………………….……………………..……………46
圖4.3大問題甘特圖…………………………………...…………………48












表目錄
表3.1 資源表單…………………………………..………………………17
表3.2 資源表單……………..……………………………………………17
表3.3 資源表單………………..…………………………………………20
表3.4 資源表單…………………………………………………………..30
表3.5 資源表單……………..……………………………………………32
表3.6………………………………………………………………………36
表3.7………………………………………………………………………38
表3.8………………………………………………………………………39
表3.9………………………………………………………………………35
表4.1 小問題……………………………………………………………..44
表4.2 中問題……………………….………...…………………………..45
表4.3 大問題……………………………………………………………..47
表4.4解題時間與各因子的變異數分析……….………………………..51
表4.5資源數在不同水準之下解題時間的統計值…….………………..52
表4.6工件數不同水準之下解題時間的統計值….……………………..52
表4.7作業數不同水準之下解題時間的統計值….……………………..52
表4.8資源使用率不同水準之下時間的統計值.………………………..53
參考文獻
Applegate, D. and Cook, W. (1991), “A Computational Study of the Job-Shop Scheduling Problem”, ORSA Journal on Computing, Vol. 3, No. 2, pp. 149-156.
Ashour, S. (1967), “A Decomposition Approach for the Machine Scheduling Problem”, International Journal of Production Research, Vol. 6, No. 2, pp. 109-122.
Balas, E. (1965), “Machine scheduling via disjunctive graphs: An implicit enumeration algorithm”, Operations Research, Vol. 17, pp. 941-957.
Balas, E. (1969), “Machine Scheduling via Disjunctive Graphs: An Implicit Enumeration Algorithm”, Operation Research, Vol. 17, pp. 941-957.
Baker, K. R. (1977), “Computational Experience With a Sequencing Algorithm Adapted to the Tardiness Problem”, American Institute of Industrial Engineers. , Vol. 9, pp. 32-35.
Baker, K. R. and Bertrand, J. W. M. (1982), “A Dynamic Priority Rule for Scheduling Against Due-Date”, Journal of Operations Management, Vol. 3, pp. 37-42.
Baker, K. R. and Schrage, L. E. (1978), “Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence-Related Tasks”, Operation Research, Vol. 26, pp. 111-120.
Barker, J. R. and McMahon, G. B. (1985), “Scheduling the General Job-Shop”, Management Science, Vol. 31, No. 5, pp.594-598.
Blazewicz, J., Dror, M. and Weglarz, J. (1991), “Mathematical Programming Formulations foe Machine Scheduling: A Survey”, European Journal of Operation Research, Vol. 51, No. 3, pp. 283-300.
Barnes, J. W. and Brennan, J. J. (1977), “An Improved Algorithm for Scheduling Jobs on Identical Machines”, American Institute of Industrial Engineers, Vol. 9, pp.25-31.
Brooks, G. H. and White, C. R. (1965), “An Algorithm for Finding Optimal or Near Optimal Solutions to the Production Scheduling Problem”, Journal of Industrial Engineering, Vol. 16, No. 1, pp. 34-40.
Brucker, P. , Garey, M. R. and Johnson, D. S. (1977), “Scheduling Equal-length Tasks under Treelike Precedence Constraints to Minimize Maximum Lateness”, Mathematics of Operations Research, Vol. 2, pp.275-284.
Carlier, J. and Pinson, E. (1989), “An algorithm for solving the job shop problem”, Management Science, Vol. 35, pp. 164-176.
Chao, X. and Pinedo, M. (1999), Operations Scheduling with Applications in Manufacturing and Services, Irwin, McGRAW-Hill, U.S.A..
Chen, T.-R. and Hisa T. C. (1994), Job Shop Scheduling with Multiple Resources and an Application to a Semiconductor Testing Facility, 1994 Proceedings of the 33rd IEEE Conference on Decision and Control, LakeBuenaVista, FL , U.S.A., pp. 1564-1570.
Chu, C., Portmann, M. C. and Proth, J. M. (1992), “A Splitting-Up Approach to Simplify Job-Shop Scheduling Problems”, International Journal of Production Research, Vol. 30, No. 4, pp. 859-870.
Coffman, Jr., E. G. and Graham, R. L. (1972), “Optimal Scheduling for Two-Processors Systems”, Acta Informatica, Vol. 1, pp.200-213.
Colorni, A., Dorigo, M., Maniezzo, V. and Trubian, M. (1994). “Ant system for Job-shop Scheduling”, JORBEL - Belgian Journal of Operations Research, Statistics and Computer Science, Vol. 34, No. 1, pp.39-53.
Czerwinski C. S. and Luh, P. B. (1992), An Improved Lagrangian Relexation Approach for Solving Job Shop Scheduling Problems, 1992 Proceedings of the 31rd IEEE Conference on Decision and Control, Tucson, AZ.
Della Croce, F., Menga, G., Tadei, R., Cavalotto, M. and Petri, L. (1993), “Cellular Control of Manufacturing Systems”, European Journal of Operation Research, Vol. 69, pp. 498-509.
Dobson, G. and Karmarker, U. S. (1989), “Simultaneous Resource Scheduling to Minimize Weighted Flow Times”, Operations research, Vol. 37, No. 4., pp. 592-560.
Dogramaci, A. and Surkis, J. (1979), “Evaluation of a Heuristic for Scheduling Independent Jobs on Parallel Identical Processors”, Management Science, Vol. 25, pp.1208-1216.
Elmaghraby, S. E. and Park, S. H. (1974), “Scheduling Jobs on a Number of Identical Machines”, American Institute of Industrial Engineers. , Vol. 6, pp. 1-13.
Emmons, H. (1969), “One-Machine Sequencing to Minimize Certain Functions of Job Tardiness”, Operations research, Vol. 17, pp. 701-715.
Fisher, M. L. (1973a), “Optimal Solution of Scheduling Problems using Lagrange Multipliers: Part I”, Operations Research, Vol. 21, pp. 1114-1127.
Fisher, M. L. (1973b), “Optimal Solution of Scheduling Problems using Lagrange Multipliers: Part II”, Symposium on the Theory of Scheduling and its Applications, Springer, Berlin.
Fisher, M. L. (1976), “A Dual Algorithm for the One-Machine Scheduling Problem”, Mathematical Programming, Vol. 11, pp.229-251.
Fry. T. D., Vicens, L., Macleod, K. and Fernandez, S. (1989), “A Heuristic Solution Procedure to Minimize on a Single Machine”, Journal of the Operational Research Society, Vol. 40, pp.293-297.
Gere, W. S. Jr. (1966), “Heuristics in Job-Shop Scheduling”, Management Science, Vol. 13, pp. 167-190.
Giffler, B. and Thompson, G. L. (1960), “Algorithms for Solving Production Scheduling Problems”, Operations Research, Vol.8, No. 4, pp.487-503.
Glover, F. (1977), “Heuristics for integer programming using surrogate constraints”, Decision Sciences, Vol. 8, No. 1, pp. 156-166.
Graham, R. L. (1966), “Bounds on Certain Multiprocessing Anomalies”, Bell System Technical Journal, Vol. 45, pp. 1563-1581.
Graham, R. L. (1969), “Bounds on Multiprocessing Timing Anomalies”, SIAM Journal of Applied Mathematics, Vol. 17, pp. 416-429.
Gupta, J. N. D. and Maykut, A. R., (1973), “Scheduling Jobs on Parallel Processors With Dynamic Programming”, Decision Sciences, Vol. 4, pp.447-457.
Hoitomt, D. J., Luh, P. B. and Pattipati, K. R. (1993), “Practical Approach to Job Shop Scheduling Problems”, IEEE Transaction on Robotics and Automation, Vol. 9, No. 1, pp. 1-13.
Holland, J. H. (1975), Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor.
Hu, T. C. (1961), “Parallel Sequencing and Assembly Line Problems”, Operation Research, Vol. 9, pp.841-848.
Ignall, E. and Schrage, L. (1965), “Application of the Branch and Bound Technique to some Flow-Shop Scheduling Problems”, Operation Research, Vol.13, pp.400-412.
Jackson, J. R. (1955), Scheduling a Production Line to Minimise Maximum Tardiness, Research Report 43, Management Science Research Projects, University of California, Los Angeles, U.S.A..
Jackson, J. R. (1956), “An Extension of Johnson’s Result on Job Lot Scheduling”, Naval Research Logistics Quarterly, Vol. 3, No. 3, pp.201-203.
Jain, A. S. and Meeran, S. (1999), “Deterministic Job Shop Scheduling: Past, Present, Future”, European Journal of Operation Research, Vol. 113, pp. 390-434.
Kim, Y. D. (1993a), “A New Branch and Bound Algorithm for Minimizing Mean Tardiness in Two-Machine Flowshops”, Computers and Operation Research, Vol. 20, pp.391-401.
Kim, Y. D. (1993b), “Heuristics for Flowshop Scheduling Problems Minimizing Mean Tardiness”, Journal of Operation Research Society, Vol. 44, pp.19-28.
Kirkpatrick, S., Gelatt, C. D. Jr. and Vecchi, M. P. (1983), “Optimization by Simulated Annealing”, Science, Vol. 220, No. 4598, pp.671-680.
Lageweg, B. J., Lenstra, K. and Rinnooy Kan, A. H. G. (1997), “Job-Shop Scheduling by Implicit Enumeration”, Management Science, Vol. 24, No. 4, pp. 441-450.
Lawler, E. L. (1964), “On Scheduling Problems with Deferral Costs”, Management Science, Vol. 11, pp.280-288.
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G.. and Shmoys, D. B. (1993), “Sequencing and Scheduling: Algorithms and Complexity”, in Graves, S. C., Rinnooy Kan, A. H. G., Zipkin, P. H. (eds), Handbook in Operations Research and Management Science, Volume 4: Logistics of Production and Inventory, North Holland, Amsterdam.
Lomnicki, Z. A. (1965), “A Branch and Bound Algorithm for the Exact Solution of the Three-Machine Scheduling Problem”, Operational Research Quarterly, Vol. 16, No. 1, pp. 89-100.
Manne, A. S. (1960), “On the Job-Shop Scheduling Problem”, Operations Research, Vol. 8, pp. 219-223.
McHugh, J. A. M. (1984), “Hu’s precedence tree scheduling algorithm: A Simple Proof”, Naval Research Logistics Quarterly, Vol. 31, pp.409-411.
McNaughton, R. (1959), “Scheduling with deadlines and loss functions”, Management Science, Vol. 6, pp.1-12.
Nakano, R. and Yamada, T. (1991), Conventional Genetic Algorithm for Job-Shop Problems, in Kenneth, M. K. and Booker, L. B. (eds), 1991 Proceedings of the 4th International Conference on Genetic Algorithms and their Applications, San Diego, U.S.A., pp. 474-479.
Nemhauser, G. L. and Wolsey, L. A. (1988), Integer and Combinatorial Optimisation, John Wiley and Sons, New York.
Ow, P. S. (1985), “Focused Scheduling in Proportionate Flow Shops”, Management Science, Vol. 31, pp.852-869.
Panwalkar, S. S. and Iskander, W. (1977), “A Survey of Scheduling Rules”, Operations Research, Vol. 25, No. 1, pp.45-61.
Picard, J. and Queyranne, M. (1978), “The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling”, Operation Research, Vol. 26, pp.86-100.
Pinedo, M. and Singer, M. (1999), “A Shifting Bottleneck Heuristic for Minimizing the Total Weighted Tardiness in a Job Shop”, Naval Research Logistics, Vol 46, pp. 1-17.
Potts, C. N. and Van Wassenhove, L. N. (1982), “A Decomposition Algorithm for the Single Machine Total Tardiness Problem”, Operation Research Letters, Vol. 1, pp.177-181.
Potts, C. N. and Van Wassenhove, L. N. (1991), “Single Machine Tardiness Sequencing Heuristics”, IIE Transaction, Vol. 23, pp.346-354.
Rajaraman, M. K. (1975), “An Algorithm for Scheduling Parallel Processors”, International Journal of Production Research, Vol. 13, pp.479-486.
Rajaraman, M. K. (1977), “A Parallel Scheduling Algorithm for Minimizing Total Cost”, Naval Research Logistics Quarterly, Vol. 24, pp.473-481.
Root, J. G. (1965), “Scheduling With Deadlines and Loss Functions on k Parallel Machines”, Management Science, Vol. 11, pp. 460-475.
Roy, B. and Sussmann, B., (1964), Les problemes d’ordonnancement avec constraint disjonctives, Note D.S. No. 9 bis, SEMA, Paris, France.
Rowe, A. J. and Jackson, J. R. (1956), “Research Problems in Production Routing and Scheduling”, Journal of Industrial Engineering, Vol. 7, pp.116-121.
Sarin, S. C., Ahn, S., and Bishop, A. B. (1988), “An Improved Branching Scheme for the Branch and Bound Procedure of Scheduling n Jobs On m Parallel Machines to Minimize Total Weighted Flowtime”, International Journal of Production Research, Vol. 27, pp.925-934.
Sen, T. P., Dileepan, P. and Gupta, J. N. D. (1989), “The Two-Machine Flowshop Scheduling Problem With Total Tardiness”, Computers and Operations Research, Vol. 16, pp. 333-340.
Singer, M. and Pinedo, M. (1998), “A computational study of branch and bound techniques for minimizing the total tardiness in job shops”, IIE Scheduling Logistics, Vol 29, pp. 109-119.
Smith, W. E. (1956), “Various Optimizers for Single Stage Production”, Naval Research Logistics Quarterly, Vol. 3, No. 3, pp.59-66.
Srinivasan, V. (1971), “A Hybrid Algorithm for the One Machine Sequencing Problem to Minimize Total Tardiness”, Naval Research Logistics, Vol. 18, pp. 317-327.
Van De Velde, S. (1991), Machine Scheduling and Lagrangian Relaxation, Ph. D. Thesis, CWI Amsterdam,The Netherlands.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top