粒子群最佳化演算法於排程問題之應用｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	曾兆堂 Chao-Tang Tseng
論文名稱：	粒子群最佳化演算法於排程問題之應用 Particle Swarm Optimization for Solving Scheduling Problems
指導教授：	廖慶榮 Ching-Jong Liao 欒斌 Pin, Luarn
口試委員:	潘昭賢 nono 張保隆 Pao-Long Chang 彭文理 nono 陳茂生 Maw-Sheng Chen 江行全 nono
學位類別：	博士 Doctor
系所名稱：	管理學院 - 企業管理系 Department of Business Administration
論文出版年：	2006
畢業學年度：	94
語文別：	英文
論文頁數：	84
中文關鍵詞：	共通啟發式演算法、排程、流程型工廠、粒子群最佳化演算法
外文關鍵詞：	Metaheuristic, Scheduling, Flowshop, Particle swarm optimization
相關次數：	點閱：500 下載：29
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

上一筆

粒子群最佳化演算法（Particle Swarm Optimization；PSO）是一個啟發自鳥之群體行為的新興共通啟發式演算法。近年來，PSO已發展出連續型與間斷型兩種版本，以求解連續最佳化問題，但其在排程問題上的應用相當罕見。因此，本論文將應用連續型或間斷型版本，發展出求解排程問題的有效PSO演算法。為了探索PSO應用的潛能，我們考慮了不同難度的排程問題，包括流程型工廠、批量流之流程型工廠以及多工處理之多階混合流程型工廠等三類排程問題。

首先，我們發展出一個間斷型粒子群最佳化演算法（Discrete Particle Swarm Optimization；DPSO），以求解流程型工廠排程問題。該演算法主要延伸自間斷型版本的PSO演算法。在演算法中，我們重新定義粒子及速度，並發展一個有效的方法，使粒子移動至新的順序。為了證實演算法的績效，本論文比較過去曾經應用在流程型工廠的一個連續型PSO演算法及兩個基因演算法。實驗結果證明，我們提出的DPSO演算法非常具有競爭力。再者，我們將鄰域搜尋法結合DPSO演算法，實驗結果亦證明DPSO演算法可以確實引導鄰域搜尋法至較佳的區域進行搜尋，在流程型工廠且準則為總完工時間下展現很好的求解效果，但需花較多的計算時間。

接著，我們考慮一個在n件工件及m部機器下，批量流在流程型工廠之排程問題，其目標是最小化總加權提早及延遲時間。對此問題，首先我們提出一個NBM演算法，求得一個已知順序下的最佳子批量配置。該演算法的效率優於目前文獻中曾提出的線性規劃模式。其次，我們改善上述的DPSO演算法以搜尋最佳的順序。此演算法引入基因演算法中的繼承機制，改善粒子的建構方式。為了驗證該演算法，本論文比較上述的DPSO演算法及一個混合基因演算法。實驗結果顯示，利用兩點繼承機制的改善後DPSO演算法，在此排程問題上呈現最好的績效。

最後，我們發展出一個PSO演算法，以求解多工處理之多階混合流程型工廠排程問題。該演算法主要延伸自連續版本的PSO演算法，並引入一個新的粒子編碼方式以及兩個有用的更新粒子速度機制，同時粒子的建構亦應用了前述的繼承機制。實驗結果證明，我們所提出的PSO演算法優於DPSO演算法，且對於50個工件以內的問題有很好的求解效果。

Particle Swarm Optimization (PSO) is a novel metaheuristic inspired by the flocking behavior of birds. In resent years, the continuous and discrete versions of PSO have been developed to solve continuous optimization problems. The applications of PSO to scheduling problems are extremely few. In this dissertation, we focus on developing the efficient PSO algorithms based on the continuous or discrete versions of PSO to solve the scheduling problems. To explore the potential applications of PSO, we consider three scheduling problems with different complexities which include the flowshop, lot streaming flowshop, and multistage hybrid flowshop with multiprocessor task scheduling problems.

First, we present a PSO algorithm extended from the discrete version of PSO for the flowshop scheduling problem. In the proposed discrete PSO (DPSO) algorithm, the particle and the velocity are redefined, and an efficient approach is developed to move a particle to the new sequence. To verify the proposed DPSO algorithm, comparisons with a continuous PSO algorithm and two genetic algorithms are made. Computational results show that the proposed DPSO algorithm is very competitive. Furthermore, we incorporate a local search scheme into the proposed algorithm, called DPSO-LS. Computational results show that the local search can be really guided by DPSO in our approach. Also, DPSO-LS performs well in flowshop scheduling with total flow time criterion, but it requires more computation times.

Then, we consider an n-job, m-machine lot streaming problem in a flowshop with equal-size sublots where the objective is to minimize the total weighted earliness and tardiness. To solve the problem, we first propose an NBM algorithm, which is much more efficient than the existing LP model for obtaining the optimal sublot starting and completion times for a given job sequence. Then, we develop an improved DPSO algorithm to search for the best sequence. The improved DPSO algorithm introduces an inheritance scheme, inspired by genetic algorithm, into the construction of particles. To verify the improved DPSO algorithm, comparisons with the existing DPSO algorithm and a hybrid genetic algorithm (HGA) are made. Computational results show that the proposed DPSO algorithm with the two-point inheritance scheme is very competitive for the lot streaming flowshop scheduling problem.

Finally, we develop a PSO algorithm, extended from the continuous version of PSO, for the multiprocessor task scheduling in a multistage hybrid flowshop. In the proposed PSO algorithm, a new encoding scheme for the particle and two useful mechanisms for updating the particle’s velocity are introduced. The construction of particles also employs the inheritance scheme. Computational results show that the PSO algorithm is superior to the DPSO algorithm and is a useful method for solving the problem with 50 or less jobs.

CHINESE ABSTRACT i
ENGLISH ABSTRACT iii
ACKNOWLEDGEMENTS v
CONTENTS vi
LIST OF FIGURES ix
LIST OF TABLES x
Chapter 1. INTRODUCTION.............................................1
   1.1. Motivation	..................................................1
   1.2. Research objectives	.........................................2
   1.3. Organization of dissertation	................................3
Chapter 2. LITERATURE REVIEW.........................................5
   2.1. Particle swarm optimization..................................5
       2.1.1. Background of PSO......................................5
       2.1.2. Continuous PSO.........................................5
       2.1.3. Discrete PSO...........................................7
   2.2. Flowshop scheduling problem.................................10
   2.3. Lot streaming flowshop scheduling problem...................12
   2.4. Multistage hybrid flowshop scheduling problem
        with multiprocessor task....................................15
Chapter 3. DEVELOPMENT OF DPSO ALGORITHM FOR
           FLOWSHOP SCHEDULING PROBLEM..............................17
   3.1. Development of DPSO algorithm...............................17
       3.1.1. Definition of discrete particle.......................17
       3.1.2. Velocity trail........................................18
       3.1.3. Construction of a particle sequence...................20
       3.1.4. Variant of gbest model................................22
       3.1.5. Proposed DPSO algorithm...............................22
       3.1.6. Local search scheme...................................23
   3.2. Computation results.........................................24
       3.2.1. Comparison with continuous PSO........................24
       3.2.2. Comparison with GA for single-objective flowshop......29
       3.2.3. Comparison with GA for multi-objective flowshop.......30
       3.2.4. Performance of DPSO with local search.................33
   3.3. Summary.....................................................36
Chapter 4. DPSO ALGORITHM FOR LOT STREAMING
           FLOWSHOP SCHEDULING PROBLEM..............................38
   4.1. Problem definition..........................................38
   4.2. Optimal sublot allocation for a given sequence..............40
       4.2.1. NBM algorithm.........................................40
       4.2.2. Numerical example.....................................43
   4.3. Improvement of DPSO.........................................46
   4.4. Computational results of lot streaming flowshop scheduling..48
       4.4.1. Parameters setting....................................48
       4.4.2. Comparison among five inheritance schemes.............46
       4.4.3. Comparison with other algorithms......................52
   4.5. Summary.....................................................56
Chapter 5. PSO ALGORITHM FOR MULTISTAGE HYBRID
           FLOWSHOP WITH MULTIPROCESSOR TASK........................58
   5.1. Problem statement...........................................58
   5.2. Proposed PSO algorithm......................................59
       5.2.1. Encoding of particle..................................60
       5.2.2. Updating velocity.....................................62
       5.2.3. Construction of particle..............................63
   5.3. Computational results.......................................64
       5.3.1. Parameters setting....................................65
       5.3.2. Performance evaluation of different schemes...........66
       5.3.3. Comparison with other algorithms......................68
   5.4. Summary.....................................................72
Chapter 6. CONCLUSIONS AND FUTURE STUDIES...........................74
   6.1. Conclusions.................................................74
   6.2. Future studies..............................................76
REFERENCES..........................................................78

                                

[1] Pinedo, M. (2002). Scheduling: Theory, Algorithm, and System. Second Ed., Englewood Cliffs, NJ: Prentice-Hall.
[2] Varadharajan, T. K., & Rajendran, C. (2005). “A multi-objective simulated- annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs,” European Journal of Operational Research, 167, 772-795.
[3] Xia, W., & Wu, Z. (2005). “An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems,” Computers and Industrial Engineering, 48, 409-425.
[4] Nowicki, E., & Smutnicki, C. (1996). “A fast tabu search algorithm for the job shop problem,” Management Science, 42, 797-831.
[5] Grabowski, J., & Wodecki, M. (2004). “A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion,” Computers and Operations Research, 31, 1891-1909.
[6] Sridhar, J., & Rajendran, C. (1996). “Scheduling in flowshop and cellular manufacturing systems with multiple objectives--a genetic algorithmic approach,” Production Planning and Control, 7, 374-382.
[7] Etiler, O., Toklu, B., Atak, M., & Wilson, J. (2004). “A genetic algorithm for flow shop scheduling problems,” Journal of the Operational Research Society, 55, 830-835.
[8] Gagné, C., Price, W. L., & Gravel, M. (2002). “Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times,” Journal of the Operational Research Society, 53, 895-906.
[9] Ying, G. C., & Liao, C. J. (2004). “Ant colony system for permutation flow-shop sequencing,” Computers and Operations Research, 31, 791-801.
[10] Rajendran, C., & Ziegler, H. (2004). “Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs,” European Journal of Operational Research, 155, 426-438.
[11] Kennedy, J., & Eberhart, R. C. (1995). “Particle swarm optimization,” Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, 1942-1948.
[12] Hu, X., Shi, Y., & Eberhart, R. C. (2004). “Recent advances in particle swarm,” Proceedings of the IEEE Congress on Evolutionary Computation, Portland, Oregon, 90-97.
[13] Kennedy, J., & Eberhart, R. C. (1997). “A discrete binary version of the particle swarm algorithm,” Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics, Piscatawary, NJ, 4104-4109.
[14] Van den Bergh, F., & Engelbrecht, A. P. (2000). “Cooperative learning in neural network using particle swarm optimizers,” South African Computer Journal, 26, 84-90.
[15] El-Galland, A. I., El-Hawary, M. E., & Sallam, A. A. (2001). “Swarming of intelligent particles for solving the nonlinear constrained optimization problem,” Engineering Intelligent Systems for Electrical Engineering and Communications, 9, 155-63.
[16] Tasgetiren, M. F., Sevkli, M., Liang, Y. C., & Gencyilmaz, G. (2004). “Particle swarm optimization algorithm for single machine total weighted tardiness problem,” Proceeding of the IEEE congress on Evolutionary Computation, Portland, Oregon, 1412-1419.
[17] Tasgetiren, M. F., Liang, Y. C., Sevkli, M., & Gencyilmaz, G. (2004). “Particle swarm optimization algorithm for makespan and maximum lateness minimization in permutation flowshop sequencing problem,” Proceeding of the Fourth International Symposium on Intelligent Manufacturing Systems, Sakarya, Turkey, 431-441.
[18] Kennedy, J., Eberhart, R. C., & Shi, Y. (2001). Swarm Intelligence. San Francisco, CA: Morgan Kaufmann.
[19] Shi, Y., & Eberhart, R. C. (1998). “A modified particle swarm optimizer,” Proceedings of the IEEE congress on Evolutionary Computation, Piscataway, NJ, 69-73.
[20] Kennedy, R. C., & Shi, Y. (2000). “Comparing inertia weights and constriction factors in particle swarm optimization,” Proceedings of CEC, San Diego, CA, 84-88.
[21] Ho, S. L., Yang, S., Ni, G., Lo, E. W. C., & Wong, H. C. (2005). “A particle swarm optimization-based method for multiobjective design optimizations,” IEEE Transactions on Magnetics, 41, 1756-1759.
[22] Eberhart, R. C., & Kennedy, J. (1995). “A new optimizer using particle swarm theory,” Proceedings of the Sixth International Symposium on Micromachine and Human Science, Nagoya, Japan, 39-43.
[23] Garey, M. R., Johnson, D. S., & Sethi, R. (1976). “The complexity of flowshop and jobshop scheduling,” Mathematics of Operations Research, 1, 117-129.
[24] Allahverdi, A., & Al-Anzi, F. S. (2006). “A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application,” Computers and Operations Research, 33, 1056-1080.
[25] Demirkol, E., Mehta, S., & Uzsoy, R. (1998). “Benchmarks for shop scheduling problems,” European Journal of Operational Research, 109, 137-141.
[26] Gangaharan, R., & Rajendran, C. (1994). “A simulated annealing heuristic for scheduling in a flowshop with bicriteria,” Computers and Industrial Engineering, 27, 473-476.
[27] Murata, T., Ishibuchi, H., & Tanaka, H. (1996). “Multi-Objective Genetic algorithm and its applications to flowshop scheduling,” Computers and Industrial Engineering, 30, 957-968.
[28] Nawaz, M., Enscore, E. E., & Ham, I. (1983). “A heuristic algorithm for the m-machine, n-job flowshop sequencing problem,” OMEGA, 11, 91-95.
[29] Rajendran, C., & Chaudhuri, D. (1992). “An efficient heuristic approach to the scheduling of jobs in a flowshop,” European Journal of Operational Research, 61, 318-325.
[30] Reiter, S. (1966). “A system for managing job shop production,” The Journal of Business, 34, 371-393.
[31] Potts, C. N., & Baker, K. R. (1989). “Flow shop scheduling with lot streaming,” Operations Research Letters, 8, 297-303.
[32] Baker, K. R., & Pyke, D. F. (1990). “Solution procedures for the lot-streaming problem,” Decision Sciences, 21, 475-491.
[33] Chang, J. H., & Chiu, H. N. (2005). “A comprehensive review of lot streaming,” International Journal of Production Research, 43, 1515-1536.
[34] Trietsch, D., & Baker, K. R. (1993). “Basic techniques for lot streaming,” Operations Research, 41, 1065-1076.
[35] Vickson, R. G., & Alfredsson, B. E. (1992). “Two- and three-machine flow shop scheduling problems with equal sized transfer batches,” International Journal of Production Research, 30, 1551-1574.
[36] Kalir, A. A., & Sarin, S. C. (2001). “A near-optimal heuristic for the sequencing problem in multiple-batch flow-shops with small equal sublots,” Omega, 29, 577-584.
[37] Yoon, S. H., & Ventura, J. A. (2002). “Minimizing the mean weighted absolute deviation from due dates in lot-streaming flow shop scheduling,” Computers and Operations Research, 29, 1301-1315.
[38] Yoon, S. H., & Ventura, J. A. (2002). “An application of genetic algorithms to lot-streaming flow shop scheduling,” IIE Transactions, 34, 779-787.
[39] Gupta, J. N. D., & Tunc, E. A. (1991). “Schedules for a two-stage hybrid flowshop with parallel machines at the second stage,” International Journal of Production Research, 29, 1489-1502.
[40] Gupta, J. N. D. (1988). “Two stage, hybrid flowshop scheduling problem,” Journal of the Operational Research Society, 39, 359-364.
[41] Guinet, A., Solomon, M. M., Kedia, P. K., & Dussauchoy, A. (1996). “A computational study of heuristics for two-stage flexible flowshop,” International Journal of Production Research, 34, 1399-1415.
[42] Linn, R., & Zhang, W. (1999). “Hybrid flow shop scheduling: A survey,” Computers and Industrial Engineering, 37, 57-61.
[43] Haouari, H., & M’Hallah, R. (1997). “Heuristic algorithms for the two-stage hybrid flowshop problem,” Operations Research Letters, 21, 43-53.
[44] Lin, H. T., & Liao, C. J. (2003). “A case study in a two-stage hybrid flow shop with setup time and dedicated machines,” Journal of Production Economics, 86, 133-143.
[45] Riane, F., Artiba, A., & Elmaghraby, S. E. (1998). “A hybrid three-stage flowshop problem: Efficient heuristics to minimize makespan,” European Journal of Operational Research, 109, 321-329.
[46] Lee, C. Y., Lei, L., & Pinedo, M. (1997). “Current trends in deterministic scheduling,” Annals of Operations Research, 70, 1-41.
[47] Krawczyk, H., & Kubale, M. (1985). “An approximation algorithm for diagnostic test scheduling in multicomputer systems,” IEEE Transaction on Computers, 34, 869-872.
[48] Chen, J., & Lee, C. Y. (1999). “General multiprocessor task scheduling,” Naval Research Logistics, 46, 57-74.
[49] Guan, Y., Xiao, W. Q., Cheung, R. K., & Li, C. L. (2002). “A multiprocessor task scheduling model for berth allocation: heuristic and worst-case analysis,” Operations Research Letters, 30, 343-350.
[50] Oğuz, C., & Ercan, M. F. (2005). “A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks,” Journal of Scheduling, 8, 323-351.
[51] Drozdowski, M. (1996). “Scheduling multiprocessor tasks- an overview,” European Journal of Operational Research, 94, 215-230.
[52] Oğuz, C., Zinder, Y., Do, V. H., Janiak, A., & Lichtensten, M. (2004). “Hybrid flow-shop scheduling problems with multiprocessor task systems,” European Journal of Operational Research, 152, 115-131.
[53] Şerifoğlu, F. S., & Ulusoy, G. (2004). “Multiprocessor task scheduling in multistage hybrid flow-shops: a genetic algorithm approach,” Journal of the Operational Research Society, 55, 504-512.
[54] Taillard, E. (1993). “Benchmarks for basic scheduling problems,” European Journal of Operational Research, 64, 278-285.
[55] Onwubolu, G. C. (2002). Emerging Optimization Techniques in Production Planning and Control. London: Imperial College Press.
[56] Den Besten, M., Stützle, T., & Dorigo, M. (2000). “Ant colony optimization for the total weighted tardiness problem,” Proceeding of Sixth International Conference Parallel Problem Solving from Nature, Springer, Berlin, 611-620.
[57] Campbell, H. G., Dudek, R. A., & Smith, M.L. (1970). “A heuristic algorithm for the n job, m machine sequencing problem,” Management Science, 16, 630-637.
[58] Dannenbring, D. (1977). “An evaluation of flow shop sequencing heuristics,” Management Science, 23, 1174-1182.
[59] Framinan, J. M., Leisten, R., & Ruiz-Usano, R. (2002). “Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimization,” European Journal of Operational Research, 141, 559-569.
[60] Liu, J., & Reeves, C. R. (2001). “Constructive and composite heuristic solutions to the scheduling problem,” European Journal of Operational Research, 132, 439-452.
[61] Błażewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., & Weglarz, J. (2001). Scheduling Computer and Manufacturing Processes, Second Ed., Berlin: Springer-Verlag.
[62] Bean, J. C. (1994). “Genetics and random keys for sequencing and optimization,” ORSA Journal on Computing, 6, 154-160.

簡易檢索 / 詳目顯示

相關論文