臺灣博碩士論文加值系統

開放工廠(Open shop)之排程問題可簡單地描述如下：假設有n項獨立工件及m部不同的機器，工件必須至所有的機器進行處理，而且工件經過機器的順序及機器處理工件的順序皆無固定。開放工廠之排程問題發生於健康檢查和汽車保養維修作業等等。
生產排程受到產品的特性或生產技術的限制，所以產生不同的加工狀況，例如：連續性(No-wait)為化學、石油工業或金屬熔融業的特色；阻斷性(Blocking)為暫存區產能受到限制或沒有暫存區的情形，最常見的是利用機器手臂進行夾取的作業。針對二機開放工廠而言，阻斷性限制與連續性限制具有相同的特性。
本研究針對二機開放工廠受連續性加工之限制，以總時程(Makespan)最小化為研究目標，發展一啟發式演算法(Heuristics)與分枝界限演算法(Branch and bound)。發展啟發式演算法以期能迅速且有效地解決大規模之問題，將啟發式演算法之結果於分枝界限演算法之上限值，並且設計分枝界限演算法之分枝策略和淘汰法則，透過撰寫C++的程式，測試大量的問題以進行啟發式演算法與分枝界限演算法之求解時間與品質的績效評估。

The openshop scheduling problem can be stated as follows. There are n independent jobs and m different machines. There is no restriction on the order in which the operations of a job are to be performed. Each machine can process at most one job at a time and each job can be processed on one machine at a time. Examples of openshop problem include teacher-class timetabling problem, health examination and the operate of car maintenance.
Scheduling problems with no-wait constraints occur in many industries. For instance, in hot metal rolling industries , where the heated metal has to undergo a series of operations at continuously high temperatures before it is cooled in order to prevent defects.Similarly , in the plastic molding and silverware production industries, a series of operations must be performed to immediately follow one another to prevent degradation.
We consider the problem of minimizing makespan in a two-machine no-wait openshop environment. In our research, we present a heuristic solution method for solving large-scaled problems. We also develop a branch and bound algorithm. We use an upper bound based on a heuristic algorithm, and discuss new dominance rules to help pruning unpromising nodes in the branch-and-bound search tree. Finally, computational experiments are conducted to evaluate the performances of the heuristic algorithm , upper bound, lower bounds, and branch-and-bround algorithm.

中 文 摘 要 i
Abstract ii
致 謝 iii
目 錄 iv
圖 目 錄 vii
表 目 錄 ix
第一章 緒 論 1
1.1 研究背景與動機 1
1.1.1 排程問題的分類 1
1.1.2 排程問題的評估準則 2
1.1.3 排程問題的求解方法 3
1.2 研究問題描述 4
1.2.1 研究範圍與限制 5
1.3 研究架構 5
第二章 文獻探討 7
2.1 流程工廠之文獻探討 7
2.1.1 連續性限制 8
2.1.2 考慮整備時間 8
2.1.3 有限暫存區 9
2.1.4 具平行機器特性之流程工廠 9
2.2 零工工廠之文獻探討 10
2.2.1 連續性限制 10
2.2.2 單位加工時間 11
2.3 開放工廠之文獻探討 11
2.3.1 連續性加工的複雜度證明 12
2.3.2 考慮搬運時間 12
2.4文獻彙整 12
第三章 研究方法 16
3.1 符號定義 16
3.2 建立數學模式 18
3.3 啟發式演算法 19
3.3.1 啟發式演算法之設計 19
3.3.3 啟發式演算法之實例說明 25
3.4 分枝界限演算法 28
3.4.1 分枝策略 29
3.4.2 上限值 42
3.4.3 下限值 42
3.4.4 淘汰法則 44
第四章 實例驗證 50
4.1 啟發式演算法之測試說明 51
4.1.1 啟發式演算法之績效評估 52
4.2分枝界線演算法之績效評估 54
4.2.1 上限值及下限值之績效評估 54
4.2.2 淘汰法則之裁減分枝績效 56
4.2.3 分枝界限演算法之求解績效 57
4.3具有瓶頸機台之績效評估 59
第五章 結論與建議 62
5.1 結論 62
5.2 未來研究方向 64
參 考 文 獻 65
附 錄 72

1.Achugbue, J.O. and Chin, F.Y., “Scheduling the openshop to minimize mean flow time,” SIAM Journal of computing , Vol.11, pp709-720 (1982).
2.Adams, J., E. Balas, and D. Zawack., “ The shifting bottleneck procedure for job shop scheduling ,” Mgmt. Sci, 34, pp.391-401 (1988).
3.Adiri, I., and N. Amit.,“ Openshop and flowshop scheduling to minimize sum of completion times,” Comput. and Opns. Res, Vol.11, pp.275-284 (1984).
4.Applegate, D., and Cook, W., “A computational study of the job shop scheduling problem,” ORSA Journal on Computers Industrial Engineering, Vol. 29, pp.723-727 (1991).
5.Brucker P.,“ Minimizing maximum lateness in a two-machine unit-time jobshop,” Computing, 27, pp.367-370 (1981).
6.Brucker P., “A linear time algorithm to minimize maximum lateness for the two-machine unit-time jobshop, scheduling problem,” Lecture Notes in Control and Inform . Sci.38, pp.566-571 (1982).
7.Della-Croce, F., Tadei, R., and Volta, G. ” A genetic algorithm for job shop problem,” Comput. and Opns. Res , Vol.22, pp.15-24 (1994).
8.Dutta, S.K., and A. A. Cunningham. “ Sequencing two-machine flow shops with finite intermediate storage,” Mgmt.Sci, Vol. 21,pp.989-996 (1975).
9.Garey, M. R., and D. S. Johnson. “ Computers and intractability：A guideto the theory of NP-completeness,” Freeman,San Francisco (1979).
10.Gilmore, P. C., and R. E. Gomory. “ Sequencing a one state-variable machine：A solvable case of the traveling salesman problem ,” Opns. Res., Vol.12, pp.655-679 (1964).
11.Gonzalez, T. “ Unit execution time shop problems, ” Math.O.R., Vol.7, pp.57-66 (1982).
12.Gonzalez, T., and S. Sahni.“ Openshop scheduling to minimize finish time,” J. Assoc. Comput. Machinery, Vol. 23, pp.665-679 (1976).
13.Graham, R. L., E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. “Optimization and approximation in deterministic sequencing and scheduling：A survey,” Annals of Discrete Math , Vol.5, pp.287-326 (1979).
14.Gupta, J. N. D.“Optimal flow shop schedules with no intermediate storage space,” Naval Res. Logistics Quarterly, Vol.23, pp.235-243 (1976).
15.Hall, N.G., H. Kamoun,and C. Sriskandrajah.“ Scheduling in robotic cells：classification, two and three machine cells,”Opns.Res., to appear (1996).
16.Hefetz, N., and I. Adiri.“A note on the influence of missing operations on scheduling problems,” Naval Res. Logistics Quarterly , Vol.29, No.3, pp.535-539 (1982).
17.Jackson, J.R. “ An extension of Johnson’s results on job lot scheduling,” Naval Res. Logistics Quarterly , No.3, pp.201-203 (1956).
18.Jain,A.,and Meeran, S. “ Job shop scheduling using Neural networks, ” Intemaional Journal of Production Res., Vol.36, pp.1249-1272 (1998).
19.Jeffrey B. Sidney, Chris N. Potts, Chelliah Sriskandarajah “ A heuristic for scheduling two-machine No-wait flow shops with anticipatory setups, ” Operations Research Letters,26, pp.165-173 (2000).
20.Johnson,S. M.“ Optimal two-and three-stage production schedules with setup times included,”Naval Res.Logistics Quarterly,No.1, pp.61-68 (1954).
21.Kamoun, H., N. G. Hall, and C. Sriskandrajah. “ Scheduling in robotic cells：Heuristics and cell design ,” Working Paper 93-08, Department of Industrial Engineering, University of Toronto (1993).
22.Kubiak, W. “A pseudo-polynomial algorithm for a two-machine No-wait job shop scheduling problem,” European J. Opnl. Res., Vol.43, pp.267-270 (1989).
23.Kubiak, W.,C. Sriskandarajah, and Zaras ,“ A note on the complexity of openshop scheduling problems,” INFOR, 29, 4, pp.284-294 (1991).
24.Kubiak W., Sethi S., Sriskandarajah C.“An efficient algorithm for a job
shop problem,” Mathematical Industrial System, No.1, pp.203-216 (1995).
25.Kuriyan, K. Scheduling of batch processes. Ph.D. Thesis, School of Chemical Engineering, Purdue University, West Lafayette,Indiana (1987).
26.Lawler, E. L. , J. K. Lenstra , A. H. G. Rinnooy Kan , and D. B. Shmoys. “ The traveling salesman problem,” Wiley, New York, (1985).
27.Lawler, E. L. , J. K. Lenstra , A. H. G. Rinnooy Kan , and D. B. Shmoys. “Sequencing and scheduling：algorithms and complexity, in：S.C. Graves, A.H.G. Rinnooy Kan, P. Zipkin (Eds.), Handbooks in Operations Rearch and Mangement Science, Vol.4：Logistic of Production and Inventory, North-Holland,Amsterdam, pp.445-522 (1993).
28.Lee, C., Piramuthu. S., and Tsai. Y.” Job shop scheduling with a genetic algorithm and machine learning, ” International J. Production Res., Vol.37, pp.2725-2753 (1997).
29.Leisten,R.“ Flow shop sequencing problems with limited buffer storage,” International J. Production Res., Vol.28, No.11, pp.2085-2100 (1990).
30.Lenstra, J. K., and A. H. G. Rinnooy Kan. “ Computational complexity of discrete optimization problems, ” Annals of Discrete Math., No.4, pp.121-140 (1979).
31.Levner, E. V. “Optimal planning of parts machining on a number of machines,” Automatic Remote Control., Vol.12, pp.1972-1978 (1969).
32.Logendran, R., C. Sriskandrajah.“ Two-machine group scheduling problem with Blocking and anticipatory setups ,” European J. Opnl. Res., Vol.69, No.3, pp.467-481 (1993).
33.M. Dell’ Amico, R. J. M. Vaessens.“ Flow-and opean-shop scheduling on two machines with transportation times and machine-independent processing times is NP-hard ,” Materiali di discussion 141,Dipartimento di Economia Politica, Universita di Modena, Italy (1995).
34.Natalia, V. Shakhlevich, Yuri, N., and Frank Werner. “ Complexity of mixed shop scheduling problems：A survey ,” European J. Opnl. Res., Vol.120, pp.343-351 (2000).
35.Nawaz, M., E. E. Enscore, and I. Ham. “ A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, ” Omega., No.11, pp.91-95 (1983).
36.Nowocki, E., and Smutnicki, C.“ Fast taboo search algorithm for job shop problem ,” Management Science, Vol.42, pp.797-813 (1996).
37.Papadimitriou, C., and P. Kanellakis. “ Flow shop scheduling with limited temporary storage,”J. Assoc. Comput. Machinery.,Vol.27,pp.533-549 (1980).
38.Piehler, J. Ein Beitrag zum Reinhenfolge Problem. Unternehmensfor- schung., No.4, pp.138-142 (1960).
39.Pinedo, M. and Schrage, L. ” Stochastic Scheduling：A Survey, in：Deterministic and Stochastic Scheduling, (ed),”M.A.H. Dempster et al. Dordrecht (1982).
40.Pinedo, M. “Scheduling：Theory, Algorithm, and System ,” Prentice Hall, Englewood Cliffs, New Jersey (1995)
41.Rajendran, C., and D. Chaudhuri.“ Heuristic algorithm for continuous flow-shop problem ,” Naval Res. Logistics, No.37, pp.695-705 (1990).
42.Rayward－Smith V. J., Rebaine. D. “Open-shop scheduling with delays,” Theoret. Inform. Appl , pp.439-448 (1992).
43.Reddi,S. S.,and C. V. Ramamoorthy. Reply to Dr. Goyal’s Comments, Opnl. Res. Quarterly , Vol.24, pp.133-134 (1973).
44.Rock, H.“The three machine No-wait flow shop problem is NP-complete ,” J. Assoc. Comput. Machinery, 31, 336-345 (1984a).
45.Rock, H.“ Some new results in No-wait flow shop scheduling ,” Zeitschrift fur Opns. Res., Vol.28, pp.1-16 (1984b).
46.Sergey V. Sevastianov, Gerhard J. Woeginger. “ Makespan minimization in open shops: A polynomial time approximation scheme ,” Math. Programming, Vol.82 , pp.191-198 (1998).
47.Sriskandarajah, C.,and P. Ladet. “ Some No-wait shops scheduling problems：complexity aspects,”European J. Opnl. Res.,Vol.24, No.3, pp.424-438 (1986).
48.Sriskandarajah, C., and S. P. Sethi.“Scheduling algorithms for flexible flowshops：Worst and average case performance ,” European J. Opnl. Res., Vol.43, No.2, pp.143-160 (1989).
49.Sriskandarajah, C. “ Performance of scheduling algorithm for No-wait flowshops with parallel machines,” European J. Opnl. Res., Vol.70, No.3, pp.365-378 (1993).
50.Strusevich, V. A.“ Two machine flowshop No-wait scheduling problem with setup, processing and removal times separated,” Report 9094/A, Econometric Institute, Erasmus University, Rotterdam (1990).
51.Strusevich. V. A. “A heuristic for the two-machine open-shop scheduling problem with transportation times,” Discrete Applied Math., Vol.93, pp.287-304 (1999).
52.Svetlana, A. Kravchenko. “A polynomial algorithm for a two-machine No-wait job-shop scheduling problem ,”European J. Opnl.Res., Vol.106, pp.101-107 (1998).
53.Svetlana, A. Kravchenko.“ Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem ,”Discrete Applied Mathematics, Vol.98, pp.209-217 (2000).
54.Szwarc, W. “ A note on the flow-shop problem without interruptions in job processing,”Naval Res.Logistics Quarterly,Vol.28,No.4, pp.665-669 (1981).
55.Taillard , E. “ Parallel taboo search techniques for the job shop scheduling problem ,”ORSA Journal on Computing, Vol.16, pp.108-117 (1994).
56.Timkovsky. V. G. “ On the complexity of scheduling an arbitrary system,” Soviet Journal of Comput. and System Sciences, No.5, pp.46-52 (1985).
57.Van Deman, J. M.,and K. R. Baker. “ Minimizing mean flow time in the flowshop with no intermediate queues,” AIIE Trans., No.6, pp.28-34 (1974).
58.Van Laar Hoven, P., Aartts, E.,and Lenstra, J. “ Jobshop scheduling by simulated annealing ,” Opns. Res., Vol.40, pp.113-125 (1992).
59.Yao, M. J., Hanijanto S., and Elmaghraby S. E., “ Simple Heuristics for The Two Machine Openshop Problem with Blocking ,” Journal of the Chinese Institute of Industrial Engineers, Vol.17, No.5, pp.537-547 (2000).
60.林暘桂，「不相關平行機總加權延遲最小化之排程問題」，碩士論文，朝陽科技大學工業工程與管理研究所，台中(2001).
61.盧慶緯，「不可中斷開放工廠總完工時間最小化之排程問題」，碩士論文，朝陽科技大學工業工程與管理研究所，台中(2002).