臺灣博碩士論文加值系統

摘要
流程工廠(Flowshop)之排程問題可簡單地描述如下：有n項獨立工件及m部不同的機器，每項工件所須經過機器的順序均相同，同一時間內，每部機器最多只能針對一項工件進行處理且每項工件僅能在一部機器上加工，流程工廠之排程問題常見於相同或類似產品之大量生產系統。
連續性(No-wait)限制是指工件進入生產系統中，一旦開始加工就必須持續地進行，直到完工，不允許工件有閒置或等待的狀況發生。具有此限制之排程問題常見於許多產業，例如，在金屬熔融業中，已加熱之金屬為了防止產生缺陷，在冷卻之前必須持續地在高溫時進行一連串的作業。同樣地，在塑膠成型及銀製品產業，其一連串作業必須接連立即地進行，以防止溫度下降。
本研究針對雙機流程工廠受連續性加工之限制，以總延遲時間(Total tardiness)最小化為績效目標，發展一啟發式演算法(Heuristic)與分枝界限演算法(Branch and bound)。啟發式演算法能迅速且有效地求解大規模之問題，且啟發式演算法亦可應用於求取分枝界限演算法之上限值。本研究設計分枝界限演算法之分枝策略、下限值和淘汰法則，以期能有效地求得最佳解。
最後，本研究大量地產生隨機測試問題，以評估所發展之啟發式演算法與分枝界限演算法之求解績效。由測試結果得知分枝界限演算法在有限時間內僅能求解小規模問題之最佳解，當工件數為25時，啟發式演算法與分枝界限演算法的平均誤差只有6％，且平均誤差會隨著工件數的減少而降低。下限值與最佳解的平均誤差為11％，工件數的多寡並不影響此平均誤差的增減，而加入淘汰法則對分枝界限演算法的整體效率則可提升約16％∼20％。另外，本研究也探討兩種瓶頸機台的特例，由測試結果得知，當有瓶頸機器時，啟發式演算法與下限值均可求得大部分問題的最佳解，且求解時間極短，所以，具有瓶頸機器的問題較易求解。

Abstract
The flowshop scheduling problem can be stated as follows. There are n independent jobs and m different machines. There is a common 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. Flowshop scheduling is often encountered in mass production systems.
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 performance measure of total tardinesss in a two-machine no-wait flow shop 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 the heuristic algorithm developed, and propose some 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 proposed algorithms. As the result, branch-and-bound algorithm can only solve to the optimum solution small-scaled problems. When the number of jobs equals to 25, the average error of heuristic solution is 6%. The average error of lower bound is about 11%. The developed dominance rules help reducing 16%~20% nodes in the branch-and-bound search tree. Besides, our research examines two special cases of bottleneck-machine. It is showed that both heuristic solution and lower bound coincide with the optimum solution in great majority problems with bottleneck-machine. Therefore, problems with bottleneck-machine become easier to solve.

目錄
摘要 I
Abstract III
目錄 VI
表目錄 IX
圖目錄 X
第一章 緒 論 1
1.1 研究背景與動機 1
1.1.1 排程問題的分類 1
1.1.2 排程問題的評估準則 3
1.1.3 排程問題的求解方法 3
1.2 研究問題描述 5
1.2.1 研究範圍與限制 5
1.3 研究架構 6
第二章 文獻探討 8
2.1 連續性限制 9
2.1.1評估指標 Cmax 10
2.1.2評估指標 ∑Cj 10
2.2 考慮整備時間 11
2.2.1評估指標 Cmax 11
2.2.2評估指標 ∑Ci 12
2.2.3其他評估指標 12
2.3 有限暫存區 13
2.4文獻探討與整理 14
第三章 研究方法 21
3.1 符號定義 21
3.1.1探討連續性的限制 22
3.2 建立數學模式 23
3.3 啟發式演算法 24
3.3.1 啟發式演算法之設計 24
3.3.2啟發式演算法之實例說明 27
3.4 分枝界限演算法 30
3.4.1 分枝策略 30
3.4.2 上限值 35
3.4.3 下限值 35
3.4.4 淘汰法則 38
第四章 實例驗證 53
4.1分枝界限演算法之績效評估 54
4.1.1 上限值及下限值之績效評估 54
4.1.2 分枝界限演算法之求解績效 57
4.1.3淘汰法則之績效評估 60
4.2具有瓶頸機台之績效評估 61
第五章 結論與建議 65
5.1 結論 65
5.2 未來研究方向 67
參考文獻 68

表目錄
表3.1 工件的加工時間與交期日 27
表3.2 工件的時間與交期日 36
表3.3 工件的加工時間與交期日 37
表4.1 上限值與交期日之績效評估： Pi,j ~U(1,25) 55
表4.2 下限值與交期日之績效評估：Pi,j ~U(1,25) 56
表4.3 上限值與下限值之績效評估：Pi,j ~U(1,25) 56
表4.4 不同加工時間分佈的上限值與下限值之績效 57
表4.5 分枝界限演算法之求解時間(秒) 58
表4.6 分枝界限法節點數與時間之關係：Pi,j ~U(1,25) 59
表4.7 分枝界限演算法之平均節點數 59
表4.8 淘汰法則對節點數的績效：Pi,j ~U(1,25) 61
表4.9 淘汰法則對求解時間的績效：Pi,j ~U(1,25) 61
表4.10 啟發式演算法之績效(M1>M2) 62
表4.11 啟發式演算法之績效(M1<M2 ) 63
表4.12 有無瓶頸機器求解時間之比較 64

圖目錄
圖1.1 研究流程圖 7
圖3.1 工件連續性限制之示意圖 22
圖3.2 啟發式演算法執行流程 26
圖3.3 第二個位置排入剩餘未排入工件的情況 28
圖3.4 MDD法最佳排程 29
圖3.5 第一與第二工件互換排程 29
圖3.6 第二個與第三個工件互換排程 30
圖3.7 分枝界限演算法之分枝策略 32
圖3.8 相鄰工件Idle的四種類型 34
圖3.9 重新組合工件的排列順序及下限值 37
圖3.10 部分排程時間點t與 t'' 38
圖3.11 部分排程S與S''之機器一完工時間比較 39
圖3.12 部分排程S與S''之機器二完工時間比較 39
圖3.13 部分排程S與S''之延遲時間比較 40
圖3.14 交期日dj≦Cj(S)與dk＜Ck(S'')對應於S與S''之比較 42
圖3.15 交期日dj≦Cj(S)與dk≧Ck(S)對應於S與S''之比較 42
圖3.16 交期日Cj(S)≦dj≦Cj(S'')與dk≧Ck(S)對應於S與S''之比較 43
圖3.17 淘汰法則2之S與S''比較 43
圖3.18 交期日dj≦Cj(S)與dk＜Ck(S'')對應於S與S''之比較 45
圖3.19 交期日dj≦Cj(S)與dk≧Ck(S)對應於S與S''之比較 45
圖3.20 交期日Cj(S)≦dj≦Cj(S'')與dk≧Ck(S)對應於S與S''之比較 46
圖3.21 交期日dj≦Cj(S)與dk＜Ck(S'')對應於S與S''之比較 47
圖3.22 交期日dj≦Cj(S)與dk≧Ck(S)對應於S與S''之比較 48
圖3.23 交期日Cj(S)≦dj≦Cj(S'')與dk≧Ck(S)對應於S與S''之比較 48
圖3.24 交期日dj≦Cj(S)與dk＜Ck(S'')對應於S與S''之比較 50
圖3.25 交期日dj≦Cj(S)與dk≧Ck(S)對應於S與S''之比較 50
圖3.26 交期日Cj(S)≦dj≦Cj(S'')與dk≧Ck(S)對應於S與S''之比較 51
圖3.27 淘汰法則6之S與S''比較 52
圖3.28 淘汰法則彙整 52

1. Johnson, S. M.“ Optimal two-and three-stage production schedules with setup times included,”Naval Res.Logistics Quarterly,No.1, pp.61-68 (1954).
2. Piehler, J. Ein Beitrag zum Reinhenfolge Problem. Unternehmensfor- schung., No.4, pp.138-142 (1960).
3. Gilmore, P. C. and Gomory, R. E. “ Sequencing a one state-variable machine：A solvable case of the traveling salesman problem ,” Opns. Res., Vol.12, pp.655-679 (1964).
4. Reddi, S. S. and Ramamoorthy, C. V. “On the Flow-shop Sequencing Problem with No Wait in Process” Operational Research Quarterly, Vol.113, pp. 323-331(1972).
5. Van Deman, J. M. and Baker, K. R. “ Minimizing mean flow time in the flowshop with no intermediate queues,” AIIE Trans., No.6, pp.28-34 (1974).
6. Dutta, S. K. , and Cunningham, A. A. “ Sequencing two-machine flow shops with finite intermediate storage,” Mgmt.Sci, Vol. 21,pp.989-996 (1975).
7. Gupta, J. N. D.“Optimal flow shop schedules with no intermediate storage space,” Naval Res. Logistics Quarterly, Vol.23, pp.235-243 (1976).
8. Coffman, E. G. “ Computer and Job Shop Scheduling ” Wiley, New York(1976).
9. Garey, M. R. and Johnson, D. S. “ A guide to the theory of NP -completeness. ” Computers and intractability, Freeman ,San Francisco (1979).
10. Panwalkar, S. S. and Woollam, C. R. “Ordered Flow Shop Problems with no In-process Waiting : Further Results ” J. Operations Research Soc. Vol.31,pp.1039-1043(1980)
11. Papadimitriou, C. , and Kanellakis, P. “ Flow shop scheduling with limited temporary storage,”J. Assoc. Comput.Machinery.,Vol.27,pp.533-549(1980).
12. Szearc, W. “ A note on the flow-shop problem without interuptions in job processing ” Naval Res.Logistics Quarterly, Vol.28,No.4, pp.665-669 (1981).
13. 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).
14. Gonzalez, T. “ Unit execution time shop problems, ” Math.O.R., Vol.7, pp.57-66 (1982).
15. Adiri, I. and Pohoryles, D. “Flowshop/No-idle or No-wait scheduling to minimize the sum of completion times” Naval Res. Logistics Quarterly, Vol.29, No.3, pp.495-504(1982).
16. Nawaz, M. , Enscore, E. E. and Ham, I. “A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, ” Omega., No.11, pp.91-95 (1983).
17. Rock, H.“ Some new results in No-wait flow shop scheduling ,” Zeitschrift fur Opns. Res., Vol.28, pp.1-16 (1984b).
18. Lawler, E. L. , Lenstra, J. K. , Rinnooy Kan, A. H. G. , and Shmoys, D. B. “ The traveling salesman problem,” Wiley, New York, (1985).
19. Sriskandarajah, C. and Ladet, P. “ Some No-wait shops scheduling problems：complexity aspects,”European J. Opnl. Res.,Vol.24, No.3, pp.424-438 (1986).
20. Rajendran, C. and Chaudhuri, D. “ Heuristic algorithms for Continuous Flow-Shop Problem ” Naval Research. Logistics, Vol.37, pp.695-705 (1990).
21. Rajendran, C. and Chaudhuri, D. “Heuristic algorithms for continuous flow-shop problem,” Naval Research Logistics, Vol.37, pp.695–705(1990).
22. 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).
23. Leisten, R. “ Flow shop sequencing problems with limited buffer storage,” International J. Production Res., Vol.28, No.11, pp.2085-2100 (1990).
24. Jack, A. A. , Veen, V. D. and Dal, R.V. “Solvable Case of the No-wait Flow-shop Scheduling Problem”Journal of the Operational Research Society, Vol.42,No11.pp.971-980(1991).
25. Kamoun, H. , Hall, N. G. and Sriskandrajah, C. “ Scheduling in robotic cells：Heuristics and cell design ,” Working Paper 93-08, Department of Industrial Engineering, University of Toronto (1993).
26. Logendran, R. and Sriskandrajah, C. “ Two-machine group scheduling problem with Blocking and anticipatory setups,” European J. Opnl. Res., Vol.69, No.3, pp.467-481 (1993).
27. Sriskandarajah, C. “Performance of scheduling algorithms for no-wait flowshops with parallel machines ”European Journal of Operational Research, Vol.70, pp.365–378(1993).
28. Hall, N. G. , Kamoun, H. and Sriskandrajah, C. “ Scheduling in robotic cells：classification, two and three machine cells,”Opns.Res., to appear (1996).
29. Hall, N. G. , Kamoun, H. and Sriskandrajah, C.“ Scheduling in robotic cells：classification, two and three machine cells,”Opns.Res., to appear (1996).
30. Dorigo, M. , Maniezzo, V. , and Colorni, A. “Ant system: optimization by a colony of cooperating agents.” IEEE Transactions on Systems, Man and Cybernetics: B, Vol.26, pp.29–41(1996).
31. Aldowaisan,T. and Allahverdi, A. “Total flowtime in no-wait flowshop with separated setup times ” Computers & Operations Research, Vol.25, No.9, pp. 757-765(1998).
32. Dorigo, M. , Di Caro, G. , and Gambardella, L. M. “Ant algorithms for discrete optimization,” Artificial Life, Vol.5, pp.137–172(1999).
33. Allahverdi, A. “Stochastically minimizing total flowtime in flowshops with no waiting space” European Journal of Operational Research, Vol.113, pp.101-112(1999).
34. Panwalkar, S. S. and Woollam, C. R. “Flow Shop Scheduling Problems with No In-process Waiting: A Special Case” Journal of Operational Research Society, Vol.113, pp.101-112(1999).
35. Sidney, J. B. and Potts, C. N. Chelliah Sriskandarajah “ A heuristic for scheduling two-machine No-wait flow shops with anticipatory setups, ” Operations Research Letters,26, pp.165-173 (2000).
36. Bertolissi, E. “Heuristic algorithm for scheduling in the no-wait flow- shop” Journal of Materials Processing Technology, Vol.107, pp.459-465 (2000).
37. Aldowaisan,T. “ A new heuristic and dominance relations for no-wait Flowshops with setups, ” Computers & Operations Research, Vol.28, pp. 563-584(2001).
38. Wang , G. and Edwin Cheng, T. C. “Heuristics for two-machine no-wait flowshop scheduling with an availability constraint” Information Processing Letters,Vol.80, pp.305–309(2001).
39. Lin, B. M. T. and Cheng, T. C. E. “Batch scheduling in the no-wait two machine flowshop to minimize the makespan” Computers & Operations Research, Vol.28, pp.613-624(2001).
40. Espinouse, M. L. , Formanowicz, P. and Penz, B. “Minimizing the Makespan in the Two-Machine No-Wait Flow-Shop with Limited Machine Availability” Computers & Industrial Engineering, Vol.37, pp.497-500(2001).
41. Aldowaisan,T. and Allahverdi, A. “No-wait flowshops with bicriteria of makespan and total completion time,” Journal of the Operational Research Society, Vol.53, pp.1004-1015(2002).
42. Pan, J. C. , Chen, J. and Chao, C. “Minimizing tardiness in a two-machine flow-shop.” Computers & Operations Research (2002) ;29 :869–885.
43. Aldowaisan,T. and Allahverdi, A. “New heuristics for no-wait flowshops to minimize makespan” Computers & Operations Research, Vol.30, pp.1219-1231(2003).
44. Edwin Chenga, T. C. and Liu, Z.“Approximability of two-machine no- wait flowshop scheduling with availability constraints” Operations Research Letters, Vol.31, pp.319 - 322(2003).
45. Saadani, N. E. H. , Guinet, A. and Moalla, M. “Three stage no- idle flow-shops” Computers & Industrial Engineering, Vol.44, pp.425-434 (2003).
46. Akkan, C. and Karabati S. “ The two-machine flowshop total completion time problem: Improved lower bounds and a branch-and-bound algorithm ” European Journal of Operational Research Vol.159 pp.420–429(2004).
47. Aldowaisan,T. and Allahverdi, A. “New heuristics for m-machine no-wait flowshop to minimize total completion time,” Omega, Vol.32, pp.345-352(2004).
48. Shyu, S. J. , Lin, B. M. T. and Yin, P. Y. “Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time”Computers & Industrial Engineering, Vol.15, pp.1–13 (2004).
49. Kamburowski, J. “More on three-machine no-idle flow shops” Computers & Industrial Engineering, Vol.46, pp.461-466(2004).
50. Dileepan, P. “A note on minimizing maximum lateness in a two-machine no-wait flowshop” Computers & Operations Research, Vol.31, pp.2111–2115(2004).
51. Akkan, C. , Karabati, S. “The two-machine flowshop total completion time problem：Improved lower bound and a branch-and-bound algorithm ” European Journal of Operational Research, Vol.159, pp.420-429(2004).
52. Aldowaisan,T. and Allahverdi, A. “No-wait flowshops with bicriteria of makespan and maximum lateness” European Journal of Operational Research, Vol.152, pp.132-147(2004).
53. Schaller, J. “Note on minimizing total tardiness in a two-machine flowshop”, Computers & Operations Research (2005) ;32 :3273–3281.
54. 施大維，「開放工廠總加權完工時間最小化問題之研究」，碩士論文，朝陽科技大學工業工程與管理研究所，台中(2000).
55. 陳柏秀，「二機連續性開放工廠總時程最小化排程問題之研究」，碩士論文，朝陽科技大學工業工程與管理研究所，台中(2003).
56. 詹詠翔，「二機連續性零工工廠總時程最小化排程問題之研究」，碩士論文，朝陽科技大學工業工程與管理研究所，台中(2004).