臺灣博碩士論文加值系統

在現實環境下，依生產型態的不同工廠可區分為：流程型工廠、零工式工廠以及開放式工廠等。其中，流程型工廠是產業最常見的生產型態之一，而多工廠之流程型工廠排程問題稱為分派式流程型工廠排程問題，近年來由於許多企業採用全球化製造，使分派式流程型工廠排程問題成為排程研究討論的新焦點。然而，過去對於分派式流程型工廠排程問題之研究均僅探討排列式生產排程，故引發本研究使用混合禁忌搜尋法後的模擬退火演算法評估排列與非排列分派式流程型工廠在不同績效準則下之排程績效之研究動機，研究考慮的績效準則包括：如最大完工時間、最大延遲時間、總完工時間以及總延遲時間等，實驗結果證實在不同的績效準則下對於分派式流程型工廠排程問題，採用非排列式生產排程之績效均顯著優於排列式生產排程。

In reality, the patterns produced by different plants can be divided into: Flow shop, job shop and open shop. Among them, flowshop is the most common type of the industry, and multi-factories flowshop scheduling problem is called distributed flowshop scheduling problem, in recent years the distribution flowshop scheduling problems become a new focus of discussion. However, over the distribution flowshop scheduling problems studies were discussed only permuted production schehuling, therefore, this paper triggered mixed tabu search and simulated annealing algorithm evaluation of permutation and non-permutation distributed flowshop scheduling problem under the different scheduling performance criteria, this study considers performance six criteria, the results confirm in the different performance criterion non-permutation production performance were significantly better than permutation production schedule.

摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
表目錄 v
圖目錄 vi
第一章 緒論 1
1.1問題背景與動機 1
1.2研究目的 2
1.3研究假設與限制 2
1.4 研究流程 3
第二章 文獻探討 5
2.1分派式流程型工廠排程問題 5
2.2 Permutation與Non-permutation 排程問題文獻探討 6
2.3模擬退火演算法之相關文獻 8
2.4禁忌搜尋演算法之相關文獻 14
第三章 研究方法 16
3.1 數學符號之定義 16
3.2 DFSP問題之混合整數規劃模式 16
3.3 TS-SA演算法之設計 18
第四章 實驗結果及分析 22
4.1實驗設計 22
4.2迭代數分析 23
4.3 NPS與PS績效之IR表 26
4.4機台數對績效影響之分析 39
4.5工廠數對績效影響之分析 40
4.6到期日對績效影響之分析 43
第五章 結論與建議 45
5.1結論 45
5.2研究貢獻與建議 45
參考文獻 46

[1] M. R. Garey, D. S. Johnson and R. Sethi, "The complexity of flowshop and jobshop scheduling, " Mathematics of Operations Research, vol. 2, 1976, pp. 117-129.
[2] C. N. Potts, D. B. Shmoys and D. P. Williamson, "Permutation vs. non-permutation flow shop schedules, " Operations Research Letters, vol. 10, no. 5, 1991, pp. 282-284.
[3] B. Naderi and R. Ruiz, "The distributed permutation flowshop scheduling problem," Computers & Operations Research, vol. 37, 2010, pp. 754-768.
[4] S. M. Johnson, "Optimal two- and three-stage production schedules with setup times included," Naval Research Logistics Quarterly , vol. 1, no. 1, 1954, pp. 61-68.
[5] D. S. Palmer, "Sequencing jobs through a multi-stage process in the minimum total time: a quick method of obtaining a near optimum," Operational Research Quarterly , vol.16, no. 1, 1965, pp. 101-107.
[6] H. G. Campbell, R. A. Dudek and M. L. Smith, "A heuristic algorithm for N-job, M-machine sequencing problem," Management Science Series B—Application, vol. 16, no. 10, 1970, pp. 630-637.
[7] M . Nawaz, E. E. E. Jr and I. Ham, "A heuristic algorithm for the m machine, n job flowshop sequencing problem," Omega-International Journal of Management Science, vol. 11, no. 1, 1983, pp. 91-95.
[8] J. M. Framinan, R. Leisten and C. Rajendran, "Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem," International Journal of Production Research, vol. 41, no.1, 2003, pp. 121-148.
[9] X. Dong, H. Huang and P. Chen, "An improved NEH-based heuristic for the permutation flowshop problem," Computers & Operations Research, vol 35, no. 12, 2008, pp. 3962-3968.
[10] S. F. Rad, R. Ruiz and N. Boroojerdian, "New high performing heuristics for minimizing makespan in permutation flowshops," Omega-International Journal of Management Sciencevol, vol. 37, no. 2, 2009, pp. 331-345.
[11] P. J. Kalczynski, J. Kamburowski, "An empirical analysis of the optimality rate of flow shop heuristics," European Journal of Operational Research,vol. 198, no. 1, 2009, pp.93-101.
[12] J. Grabowski, M. Wodecki, "A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion," Computers & Operations Research, vol. 31, no. 11, 2004, pp. 1891-1909.
[13] I. H. Osman, C. N. Potts, "Simulated annealing for permutation flowshop scheduling," Omega—International Journal of Management Science , vol. 17, no. 6, 1989, pp. 551-557.
[14] R. Ruiz, C. Maroto and J. Alcaraz, "Two new robust genetic algorithms for the flowshop scheduling problem," Omega—International Journal of Management Science, vol. 34, no. 5, 2006, pp. 461-476.
[15] C. Rajendran, H. Ziegler, "Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs," European Journal of Operational Research, vol. 155, no. 2, 2004, pp.426-438.
[16] G. Onwubolu, D. Davendra, "Scheduling flow shops using differential evolution algorithm," European Journal of Operational Research, vol. 171, no. 2, 2006, pp. 674-692.
[17] M. F. Tasgetiren, Y. C. Liang, M. Sevkli and G. Gencyilmaz, "A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem," European Journal of Operational Research, vol. 177, no. 3, 2007, pp. 1930-1947.
[18] R. Ruiz, T. A. Stutzle, “simple an defective iterated greedy algorithm for the permutation flowshop scheduling problem,” European Journal of Operational Research, vol. 177, no. 3, 2007, pp. 2033-2049.
[19] E. Vallada, R. Ruiz, "Cooperative metaheuristics for the permutation flowshop scheduling problem," European Journal of Operational Research , vol. 193, no. 2, 2009, pp. 365-376.
[20] E. Vallada, R. Ruiz and G. Minella, "Minimising to taltardiness in the m-machine flowshop problem: a review and evaluation of heuristics and metaheuristics," Computers & Operations Research , vol. 35, no. 4, 2008, pp. 1350-1373.
[21] G. Minella, R. Ruiz and M. Ciavotta, "A review and evaluation of multiobjective algorithms for the flowshop scheduling problem," INFORMS Journal on Computing , vol. 20, no. 3,2008, pp. 451-471
[22] H. Z. Jia, A. Y. C. Nee, J. Y. H. Fuh and Y. F. Zhang, "A modified genetic algorithm for distributed scheduling problems," Journal of Intelligent Manufacturing, vol. 14, no. 3-4, 2003, pp. 351-362.
[23] H. Z. Jia, J. Y. H. Fuh, A. Y. C. Nee and Y. F. Zhang, "Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems," Computers & Industrial Engineering, vol. 53, no. 2, 2007, pp. 313-320.
[24] F. T. S. Chan, S. H. Chung and P. L. Y. Chan "An adaptive genetic algorithm with dominated genes for distributed scheduling problems," Expert Systems with Applications, vol. 29, no. 2, 2005, pp.364-371.
[25] F. T. S. Chan, S. H. Chung, L. Y. Chan, G. Finke and M. K. Tiwari, "Solving distributed FMS scheduling problems subject to maintenance: genetic algorithms approach," Robotics and Computer-Integrated Manufacturing, vol. 22, no. 5-6, 2006, pp. 493-504.
[26] C. J. Liao, L. M. Liao and C. T. Tseng, "A performance evaluation of permutation vs. non-permutation schedules in a flowshop," International Journal of Production Research, vol. 44 , no. 20, 2006, pp.4297-4309.
[27] S. Lazano, B. A. Diaz, I. Eguia and L. Onieva , "A one-step tabu search algorithm for manufacturing cell design," Journal of the Operational Research Society, vol. 50, no. 5, 1999, pp. 509-516.
[28] W. H. Yang, "Group scheduling in a two-stage flowshop," Journal of the Operational Research Society, vol. 53, no. 12, 2002, pp. 1367–1373.
[29] A. Allahverdi, J. N. D. Gupta and T. Aldowaisan, "A survey of scheduling research involving setup considerations," OMEGA, International Journal of Management Science, vol. 27, no. 2, 1999, pp. 219-239.
[30] A. Allahverdi, C. T. Ng, T. C. E. Cheng and M. Y. Kovalyov, "A survey of scheduling problems with setup times or costs," European Journal of Operational Research, vol. 187, no. 3, 2008, pp. 985-1032.
[31] T. C. E. Cheng, J. N. D. Gupta and G. Wang, "A review of flowshop scheduling research with setup times," Production and Operations Management, vol. 9, no. 2, 2000, pp. 262-282.
[32] K. C. Ying, J. N. D. Gupta, S. W. Lin and Z. J. Lee, "Permutation and non-permutation schedules for the flowline manufacturing cell with sequence dependent family setups," International Journal of Production Research , Vol. 48, no. 8, 2010, pp. 2169-2184
[33] M. Tandon, P. T. Cummings, and M. D. LeVan, "Flowshop sequencing with non-permutation schedules," Computers and Industrial Engineering, vol. 15, no. 8, 1991, pp. 601-607.
[34] S. Pugazhendhi, S. Thiagarajan, C. Rajendran and N. Anantharaman, "Performance enhancement by using non-permutation schedules in flowline-based manufacturing systems," Computers and Industrial Engineering, vol. 44, no. 1, 2002, pp. 133-157.
[35] S. Pugazhendhi, S. Thiagarajan, C. Rajendran and N. Anantharaman, "Performance enhancement by using non-permutation schedules in flowline-based manufacturing systems," Computers and Industrial Engineering, vol. 44, no. 1, 2002, pp. 133-157.
[36] S. Pugazhendhi, S. Thiagarajan, C. Rajendran and N. Anantharaman, "Relative performance evaluation of permutation and non-permutation schedules in flowline-based manufacturing systems," International Journal of Advanced Manufacturing Technology, vol. 23, no. 11-12, 2004b, pp. 820-830.
[37] K. C. Ying and S. W. Lin, "Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems," International Journal of Advanced Manufacturing Technology, vol. 33, no. 7-8,2007, pp. 793–802.
[38] S. W. Lin and K. C. Ying, "Applying hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems," International Journal of Production Research, vol. 47, no. 5, 2009, pp. 1411–1424.
[39] C. N. Potts, D. B. Shmoys and D. P. Williamson, "Permutation vs. non-permutation flow shop schedules," Operations Research Letters, vol. 10, no. 5, 1991,pp. 282-284.
[40] D. Rebaine, "Flow shop vs. permutation shop with time delay," Computers and Industrial Engineering, vol. 48, no. 2, 2005, pp. 357-362.
[41] S. H. Hendizadeh, H. Faramarzi, S. A. Mansouri, J. N. D. Gupta and T. Y. ElMekkawy, "Meta-heuristics for scheduling a flowline manufacturing cell with sequence dependent family setup times," International Journal of Production Economics, vol. 111, no. 2, 2008, pp. 593-605.
[42] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, "Optimization by simulated annealing," American Association for the Advancement of Science, vol. 220, no. 4598, 1983, pp. 671-680.
[43] V. Cerny, "Thermodynamical approach to the traveling salesman problem: An efficient simulaton algorithm," Journal of Optimization Theory and Applications , vol. 45, no.1, 1985, pp. 41-51.
[44] P. J. M. V. Laarhoven and E. H. L. Aarts, "Simulated Annealing: Theory and Applications," ESO: Kluwer Academic Publishers, Dordrecht, 1987.
[45] E. H. L. Aarts and J. Korst, "Simulated Annealing and Boltzmann Machines," New York: John Wiley and Sons Inc, 1989.
[46] I. H. Osman and C. N. Potts, "Simulated annealing for permutation flow-shop scheduling," OMEGA , vol. 17, no. 6, 1989, pp. 551-557.
[47] F. A. Ogbu and D. K. Smith, "The application of the simulated annraling algorithm to the solution of the n/m/Cmax flowshop problem," Computers & Operations Research , vol. 17, no. 3, 1990, pp. 243-253.
[48] F. A. Ogbu and D. K. Smith, "Simulated annealing for permutation flowshop scheduling," OMEGA, vol. 19, no. 1, 1990, pp. 64-67.
[49] H. Ishibuchi, S. Misaki and H. Tanaka. "Modified simulated annealing algorithms for the flow shop sequencing problem," European Journal of Operational Research, vol. 81, no.2 , 1995, pp. 388-398.
[50] M. Widmer and A. Hertz, "A new heuristic methods for the flow shop sequencing problem," European Journal of Operational Research, vol. 41, no. 2, 1989, pp. 186-193.
[51] E. Taillard, "Some efficient heuristic methods for the flow shop sequencing problem," European Journal of Operational Research, vol. 47, no. 1 , 1990, pp. 65-74.
[52] J. Gao and R. Chens, "An NEH-based heuristic algorithm for distributed permutation flowshop scheduling problems," Scientific Research and Essays , vol. 6, no. 14, 2011, pp. 3094-3100.