臺灣博碩士論文加值系統

本次研究是首次對於具有順序相依整備時間之流程型製造單元重工排程進行研究。單元式製造排程在原始條件下已為一NP-hard問題，加入重工條件使我們的問題能更符合在現實的生產環境，但也使問題求解的複雜度增加。近年來有研究學者觀察人類歷史中帝國與殖民地之資源競爭現象，進而提出了帝國主義競爭演算法(Imperialist Competitive Algorithm, ICA)，其求解的表現也相當優越，但ICA的主要問題在於常陷於區域最佳解。本研究將對ICA的移動方式進行修改，並運用修改型帝國主義演算法求解允許重工之流程型製造單元排程問題，經由實驗比較本修改型帝國主義演算法與原始帝國主義演算法之間的優劣。

This thesis examined the flowshop manufacturing cell reworking scheduling problem (FMCRSP) with sequence-dependent family setup times. The present study is among the first to investigate flowshop manufacturing cell scheduling problem with reworking consideration, though it is a necessary production constraint in many real-world applications. In view of the strongly NP-hard nature of this problem, a new nature-inspired optimization method, called Imperialist Competition Algorithm (ICA), was proposed to solve it. In this paper, we compared the revised ICA with basic ICA for the FMCRSP with makespan criterion.

摘　要 i
ABSTRACT ii
誌 謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與限制 2
1.4 研究流程 3
第二章 文獻探討 5
2.1 流程型製造單元排程問題 5
2.2 重工排程之相關文獻 8
2.3 帝國主義競爭演算法 9
2.3.1帝國主義演算法步驟與流程 9
2.3.2帝國主義競爭演算法之相關文獻 18
第三章 研究方法 20
3.1 數學符號之定義 20
3.2流程型製造單元重工排程問題之數學模式 22
3.3改良式帝國主義競爭演算法 24
3.3.1改良式帝國主義競爭演算法之編碼及應用 26
第四章 實驗結果及分析 29
4.1 設計實驗部分 29
4.2演算法之收斂情形 30
4.3 小型問題實驗結果分析 31
4.4 大型問題實驗結果分析 35
4.5 統計檢定分析 41
第五章 結論與建議 43
5.1 結論 43
5.2 研究貢獻 43
5.3 未來研究與建議 44
參考文獻 45

中文部分：
[1] 李朝源，改良式帝國主義競爭演算法，碩士論文，元智大學資訊管理學系，桃園，2011。
英文部分：
[2] R. L. Graham, 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 Mathematics, 1979, pp. 287–325.
[3] A. Allahverdi and J. N. D. Gupta and T. Aldowaisan, "A review of scheduling research involving setup considerations," OMEGA, International Journal of Management Science, Vol. 27, No. 2, 1999, pp. 219–239.
[4] S. H. Hendizadeh, T. Y. ElMekkawy and G.G. Wang, "Bi-criteria scheduling of a flowshop manufacturing cell with sequence dependent setup times," European Journal of Industrial Engineering, Vol. 1, No. 4, 2007, pp. 391–413.
[5] J. N. D. Gupta and W. P. Darrow, "The two-machine sequence dependent flowshop scheduling problem," European Journal of Operational Research, Vol. 24, No. 3, 1986, pp. 439–446.
[6] S. W. Lin, J. N. D. Gupta, K. C. Ying and Z. J. Lee, "Using simulated annealing to schedule a flowshop manufacturing cell with sequence dependent family setup times," International Journal of Production Research, Vol. 47(12), 2008, pp. 3205–3217.
[7] J. E. Schaller, J. N. D. Gupta and A. J. Vakharia, "Scheduling a flowline manufacturing cell with sequence dependent family setup times," European Journal of Operational Research, Vol. 125, No. 2, 2000, pp. 324–33
[8] H. G. Campbell, R. A. Dudek and M. L. Smith, "A Heuristic Algorithm for the n Job, m Machine Sequencing Problem," Management Science, Vol. 16, No. 10, 1970, pp. B630–B637.
[9] M. Nawaz, E. E. Enscore Jr and I. Ham, "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem," Omega, Vol. 11, Issue 1, 1983, pp. 91–95.
[10] J. E. Schaller, J. N. D. Gupta and A. J. Vakharia, "Scheduling a flowline manufacturing cell with sequence dependent family setup times," European Journal of Operational Research, Vol. 125, No. 2, 2000, pp. 324–339.
[11] W. H. Yang, "Group scheduling in a two-stage flowshop," The Journal of the Operational Research Society, Vol. 53, No. 12 , 2002, pp. 1367–1373.
[12] M. Solimanpur, P. Vrat and R. Shankar, "A heuristic to minimize makespan of cell scheduling problem," International Journal of Production Economics, Vol. 88, Issue 3, 2004, pp. 231–241.
[13] J. Schaller, "Scheduling on a single machine with family setups to minimize total tardiness," International Journal of Production Economics, Vol. 105, Issue 2, 2007, pp. 329–344.
[14] R. Logendran, S. Carson and E. Hanson, "Group scheduling in flexible flow Shops," International Journal of Production Economics, Vol. 96, Issue 2, 2005, pp. 143–155.
[15] P. M. Franca, J. N. D. Gupta, A. S. Mendes, P. Moscato and K. Veltink, "Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups," Computers and Industrial Engineering, Vol. 48, No. 3, 2005, pp. 491–506.
[16] R. Logendran, P. de Szoeke and F. Barnard, "Sequence-dependent group scheduling problems in flexible flow shops," International Journal of Production Economics, Vol. 102, No. 1, 2006, pp. 66–86.
[17] R. Logendran, N. Salmasi and C. Sriskandarajah, "Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups," Computers & Operations Research, Vol. 33, No. 1, 2006, pp. 158–180.
[18] S. W. Lin, J. N. D. Gupta, K. C. Ying and Z. J. Lee, "Using simulated annealing to schedule a flowshop manufacturing cell with sequence dependent family setup times," International Journal of Production Research, Vol. 47(12), 2008, pp. 3205–3217.
[19] N. Salmasi, R. Logendran and M. R. Skandari, "Total flow time minimization in a flowshop sequence-dependent group scheduling problem," Computers & Operations Research, Vol. 37, No. 1, 2010, pp. 199–212.
[20] H. M. Cheng and K. C. Ying, "Minimizing makespan in a flow-line manufacturing cell with sequence dependent family setup times," Expert Systems with Applications, Vol. 38, Issue 12, 2011, pp. 15517–15522 .
[21] S. H. Hendizadeh, T. Y. ElMekkawy and G.G. Wang, "Bi-criteria scheduling of a flowshop manufacturing cell with sequence dependent setup times," European Journal of Industrial Engineering, Vol. 1, No. 4, 2007, pp. 391–413.
[22] S. W. Lin and K.C. Ying, "Scheduling a bi-criteria flowshop manufacturing cell with sequence-dependent family setup times, "European Journal of Industrial Engineering , Vol. X, no. Y, 20xx (in press)
[23] K. Inderfurth, M. Y. Kovalyov, C. T. Ng and F. Werner, "Cost minimizing scheduling of work and rework processes on a single facility under deterioration of reworkables," International Journal of Production Economics, Vol. 105, Issue 2, 2007, pp. 345–356.
[24] E. A. Gargari and C. Lucas, "Imperialist Competitive Algorithm: An Algorithm for Optimization Inspired by Imperialistic," IEEE Congress on Evolutionary Computation, Tehran, 2007, pp. 4661–4667.
[25] S. Nazari-Shirkouhi, H. Eivazy, R. Ghodsi, K. Rezaie and E. Atashpaz-Gargari ,"Solving the integrated product mix-outsourcing problem using the Imperialist Competitive Algorithm, "Expert Systems with Applications, Vol. 37, Issue 12, 2010, pp. 7615–7626.
[26] N. Javadian, J. Rezaeian, H. Khorshidian and K. Rahmani, "Single Machine Preemptive Scheduling by Hybridized Meta-Heuristic Approach," Communication Software and Networks (ICCSN), 2011 IEEE 3rd International Conference on, 2011, pp. 750 – 753.
[27] G. J. Wang, Y. B. Zhang and J. W. Chen, "A Novel Algorithm to Solve the Vehicle Routing Problem with Time Windows: Imperialist Competitive Algorithm," Advanced in Information Sciences and Service Sciences, Vol. 3, 2011, pp. 108–116.
[28] R. Shafaei, N. Moradinasab and M. Rabiee, "Efficient meta heuristic algorithms to minimize mean flow time in no-wait two stage flow shops with parallel and identical machines," International Journal of Management Science and Engineering Management, 2011, pp. 421–430.
[29] F. Jolai, M. Rabiee and H. Assefi, "A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependent setup times," International Journal of Production Research, 2011.
[30] S. F. Attar, M. Mohammadi and R. Tavakkoli-Moghaddam, "A Novel Imperialist Competitive Algorithm to Solve Flexible Flow Shop Scheduling Problem in Order to Minimize Maximum Completion Time," International Journal of Computer Applications, Vol. 28, No.10, 2011, pp. 27–32.
[31] K. Lian, C. Zhang, L. Gao and X. Li, "Integrated process planning and scheduling using an imperialist competitive algorithm," International Journal of Production Research, 2011, pp. 1–18.
[32] M. Abdechiri, K. Faez and H. Bahrami, "Adaptive Imperialist Competitive Algorithm (AICA)," Cognitive Informatics (ICCI), 2010 9th IEEE International Conference on, Beijing, 2010, pp. 940–945.