臺灣博碩士論文加值系統

在生產管理中，排程(scheduling)是一個非常重要的領域，為了能提高產能，並減少生產時間，平行機流程式工廠(flow shop with multiprocessors, FSMP)廣泛運用於實務當中，在玻璃業、鋼鐵業最為常見，甚至出現於半導體製程中。而機器劣化(deterioration)之FSMP於生產系統中，是一種普遍的生產型態，機器在生產過程中，會不斷降低其生產效率，使得生產時間越來越長。為了使劣化機器回復原始效能，考慮維護(maintenance)之要求。
粒子群演算法(particle swarm optimization, PSO)於許多工程領域(如財務預測、影像處理、資料分群)中，被證實是一種有效能且具效率的工具，但相較於基因、蟻群等演算法，粒子群演算法在排程上的運用較為少見。本研究利用粒子群演算法的概念，改良出分簇粒子群演算法(cluster particle swarm optimization, CPSO)，並將其運算結果與蟻群演算法，及粒子群演算法進行比較。實驗結果顯示，在小規模問題下，分簇粒子群演算法相較於蟻群與粒子群演算法，有效性改善率分別達到33.67%及41.37%，健全度改善率分別達到48.03%及53.31%，在大規模問題下，由於整數規劃無法在合理時間內求出最佳解，故無法算出有效性改善率，而健全度改善率分別達到43.20%及50.98%，證實分簇粒子群演算法具突破傳統演算法之求解能力與品質。

Scheduling is one of essential dimensions of production management. In order to increase capacity and reduce processing time effectively, flow shop with multiprocessors, FSMP, is often applied to practice industry, such as glass making, iron and steel industry, even in semiconductor manufacturing process. FSMP with deterioration is a common mode of production, machine will constantly reduce its efficiency, and processing time of tasks will increase. In order to restore efficiency of machines, we have to consider requirement of maintenance.
Particle swarm optimization (PSO) is proved to be an effective and efficient tool in other engineering fields. Compared to other algorithm, PSO is rarely applied in scheduling. We present a proposed PSO algorithm, extended from discrete PSO, applying in a two-stage multiprocessor flow shop scheduling with deteriorating maintenance, and compare the results of computational experiments with PSO and ACO. Experiments confirmed that the cluster particle swarm optimization has better efficiency.

目錄
第 壹 章 緒論......................................................................................................1
第 一 節 問題背景與研究動機..................................................................1
第 二 節 研究範圍與限制..........................................................................3
第 三 節 研究目的......................................................................................4
第 四 節 研究流程......................................................................................4
第 貳 章 文獻探討..............................................................................................6
第 一 節 平行機流程式排程問題..............................................................6
第 二 節 具有機器劣化與維護之作業排程問題......................................8
第 三 節 蟻群演算法..................................................................................9
第 四 節 粒子群演算法............................................................................12
第 參 章 研究方法............................................................................................16
第 一 節 數學模型之建構........................................................................16
第 二 節 分簇粒子群演算法....................................................................18
第 三 節 釋例............................................................................................19
第 肆 章 資料測試與分析................................................................................23
第 一 節 模擬資料與測試環境................................................................23
第 二 節 有效性與健全度........................................................................24
第 三 節 小規模問題模擬測試................................................................25
第 四 節 大規模問題模擬測試................................................................32
第 五 節 測試結果分析與彙整................................................................41
第 伍 章 結論與建議........................................................................................42
第 一 節 結論............................................................................................42
第 二 節 建議............................................................................................43
參 考 文 獻........................................................................................................44

1.Chang, P. C., Chen, S. H., & Mani, V (2009). A note on due-date assignment and single machine scheduling with a learning/aging effect. International Journal of Production Economics, 117(1), 142-149.
2.Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1, 53-66.
3.Dorigo, M., Maniezzo, V., & Colorni, A. (1996). The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26, 29-41.
4.Gagné, C., Gravel, M., & Price, W. L. (2006). Solving real car sequencing problems with ant colony optimization. European Journal of Operational Research, 174(3), 1427-1448.
5.Hani, Y., Amodeo, L., Yalaoui, F., & Chen, H. (2007). Ant colony optimization for solving an industrial layout problem. European Journal of Operational Research, 183(2), 633-642.
6.Haouari, M., Hidri, L., & Gharbi, A. (2006). Optimal scheduling of a two-stage hybrid flow shop. Mathematical Methods of Operations Research, 64, 107-124.
7.Huang, R. H. (2010). Multi-objective job-shop scheduling with lot-splitting production. International Journal of Production Economics, 124(1), 206-213.
8.Huang, K. L., & Liao, C. J. (2008). Ant colony optimization combined with taboo search for the job shop scheduling problem. Computers & Operations Research, 35(4), 1030-1046.
9.Huang, R. H., Yang, C. L., & Huang, Y. C. (2009). No-wait two-stage multiprocessor flow shop scheduling with unit setup. International Journal of Advanced Manufacturing Technology, 44(9-10), 921-927.
10.Huang, R. H., & Yang, C. L. (2009). Solving a multi-objective overlapping flow-shop scheduling. International Journal of Advanced Manufacturing Technology, 42(9-10), 955-962.
11.Huang, R. H., Yang, C. L., & Huang, H. T. (2010). Parallel machine scheduling with common due windows. Journal of the Operational Research Society, 61(4), 640-646.
12.Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks, 4, 1942-1948.
13.Kennedy J., & Eberhurt, R. (1997). A discrete binary version of the particle swarm algorithm. IEEE International Conference on Systems, 5, 4104-4108.
14.Liao, C. Y., Tseng, C. T., & Luarn, P. (2007). A discrete version of particle swarm optimization for flowshop scheduling problems. Computer Operation Research, 34(10), 3099-3111.
15.McMullen, P. R. (2001). An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives. Artificial Intelligence in Engineering, 15(3), 309-317.
16.Mosheiov, G. (2001). Parallel machine scheduling with a learning effect. Journal of the Operational Research Society, 52, 1165-1169.
17.Negenman, E. G. (2001). Local search algorithms for the multiprocessor flow shop scheduling problem. European Journal of Operation Research, 128(1), 147-158.
18.Oguz, C., & Ercan, M. F. (2005). A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Journal of Scheduling, 8(4), 323-351.
19.Oguz, C., Zinder, Y., Do, V. H., Janiak, A., & Lichtenstein, M. (2004). Hybrid flow-shop scheduling problems with multiprocessor task systems. European Journal of Operation Research, 152(1), 115-131.
20.Ratnaweera, A., Halgamuge, S. K. & Waston, H. C. (2004). Self-Organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Transactions on Evolutionary Computation, 8(3), 240-255.
21.Shi, Y. H., & Eberhart, R. C. (1998a). A modified particle swarm optimizer. IEEE World Congress on Computational Intelligence, 5, 69-73.
22.Shi, Y. H., & Eberhart, R. C. (1998b). Parameter selection in particle swarm optimization. Evolutionary Programming, 1447, 591-600.
23.Sivrikaya-Serifoglu, F., & Ulusoy, G. (2004). Multiprocessor task scheduling in multistage hybrid flow-shops: A genetic algorithm approach. Journal of the Operational Research Society, 55, 504-512.
24.Taillard E. (1993). Benchmarks for basic scheduling problems. European Journal of Operation Research, 64(2), 278-285.
25.Tseng, C. T., & Liao C. J. (2008). A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks. International Journal of Production Research, 46(17), 4655-4670.
26.Wang, J. B., & Cheng, T. C. E (2007). Scheduling problems with the effects of deterioration and learning. Asia-Pacific Journal of Operational Research, 24(2), 245-261.
27.Yang, S. J. (2010). Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration. Applied Mathematics and Computation, 217(7), 3321-3329.
28.Yang, Y., Kreipl, S., & Pinedo, M. (2000). Heuristics for minimizing total weighted tardiness in flexible flow shops. Journal of Scheduling, 3(2), 89-108.
29.Yang, S. J., & Yang, D. L. (2010a). Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities. Computers & Mathematics with Applications, 60(7), 2461-2169.
30.Yang, S. J., & Yang, D. L. (2010b). Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities. Omega, 38(6), 528-533.
31.Yang, S. J., Yang, D. L., & Cheng, T. C. E (2010). Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance. Computers & Operations Research, 37(8), 1510-1514.
32.Ying, K. C., & Lin, S. H. (2006). Multiprocessor task scheduling in multistage hybrid flow-shops: An ant colony system approach. International Journal of Production Research, 44(16), 3161-3177.
33.Zhao, C. L., & Tang, H. Y. (2010). Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan. Applied Mathematical Modelling, 34(3), 837-841.