Mehmet ŞEVKLİ, M. Mutlu YENİSEY

Atölye tipi çizelgeleme problemleri için parçacık sürü optimizasyonu yöntemi

Popülasyon temelli sezgisel yöntemlerden biri olan Parçacık Sürü Optimizasyonu (PSO), kuş ve balık sürülerinin sosyal davranışlarından etkilenerek geliştirilen yeni bir eniyileme yöntemidir. Bu makalede, zor çizelgeleme problemleri arasında yer alan Atölye Tipi Çizelgeleme problemlerinin çözümü için, bir PSO modeli, Değişken Komşuluk Arama yöntemi ile birlikte geliştirilmiştir. Oluşturulan bu model, tamamlanma zamanı performans ölçütüne göre literatürde yer alan bazı zor test problemleri üzerindeki sonuçları incelenmiş ve iyi sonuçlar veren diğer sezgisel yöntemlerin sonuçlarıyla karşılaştırılmıştır. Sonuçta genel olarak önerilen modelin diğer yöntemlere göre daha iyi veya eşdeğer seviyede olduğu görülmüştür.

A particle swarm optimization for the job shop scheduling problems

Particle Swarm Optimization (PSO) is one of the population based optimization technique inspired by social behavior of bird flocking and fish schooling. PSO inventers were inspired of such natural process based sce¬narios to solve the optimization problems. In PSO, each single solution, called a particle, is considered as a bird, the group becomes a swarm (population) and the search space is the area to explore. Each particle has a fitness value calculated by a fitness function, and a velocity of flying towards the optimum, food. All particles fly across the problem space following the particle nearest to the optimum. PSO starts with initial popu¬lation of solutions, which is updated iteration-by-iteration. Therefore, PSO can be counted as an evolutionary algorithm besides being a metaheuristics method, which allows exploiting the searching experience of a single particle as well as the best of the whole swarm. In this paper, A PSO model for the job shop scheduling problem is proposed. In addition, a simple but efficient local search method called Variable Neighborhood Search (VNS) is embedded to the PSO model and applied to several hardest benchmark suites. The results for the PSO algorithm with VNS are also presented and compared with many efficient meta-heuristic algorithms in literature. As a final result, PSO with VNS results are generally found to be better than other results.

PDF

___

Abido, M. A., (2002). Optimal power flow using particle swarm optimization, Electrical Power and Energy Systems, 24, 563-571.
Adams, J., Balas., E. ,Zawack, D., (1988). The shifting bottleneck procedure for the job shop scheduling. Management Science, 34, 391-401.
Aydin, M. E., Fogarty, T. C., (2004). A distributed evolutionary simulated annealing algorithm for combinatorial optimisation problems, Journal of Heuristics, 10, 269-29
Balas, E., Vazacopoulos, A., (1998). Guided local search with shifting bottleneck for job shop scheduling problem, Management Science, 44(2), 262-275.
Bean, J. C., (1994). Genetic algorithm and random keys for sequencing and optimization, ORSA Journal on Computing, 6, 2, 154-160.
Beasley, J. E., (2004). OR Library. http://www.brunel.ac.uk/depts/ma/research/jeb/in fo.html
Besten, M., Stutzle, T., Dorigo, M., (2001). Design of iterated local search algorithms, Proceedings, Evolutionary Workshops, LNCS, Berlin.
Bierwirth, C., Mattfeld, D., Kopher, H., (1996). A generalized permutation approach to job shop scheduling with genetic algorithms, ORSpektrum, 17, 87-92.
Blum, C., Sampels, M., (2004). An ant colony optimization algorithm for shop scheduling problems, Journal of Mathematical Modeling and Algorithms, 3, 285-308.
Cheng, R., Gen M., Tsujimura, Y., (1996). A tutorial survey of job-shop scheduling problems using genetic algorithms-I. Representation, Computers and Industrial Engineering, 30, 4, 983-997.
Dell'Amico, M., Trubian,M., (1993). Applying tabu search to the job shop scheduling problem, Annals of Operations Research, 41, 231-252.
Dondorf, U., Pesch, E., (1995). Evolution based learning in a job shop scheduling environment, Computers and Operations Research, 22, 25-40.
Eberhard, R. C., Kennedy, J., (1995). A new optimizer using particle swarm theory. Proceedings, 6th International Symposium on Micro Machine and Human Science, Nagoya, Japan.
Jones, D. F., Mirrazavi, S.K., Tamiz M., (2002). Multi-objective meta-heuristics:An overview of the current state-of-the-art, Europen Journal of Operational Research, 137, 1-9.
Kennedy, J., Eberhard, R.C., Shi,Y., (2001). Swarm Intelligence. San Mateo, Morgan Kaufmann.
Kolonko, M., (1999). Some new results on simulated annealing applied to the job shop scheduling problem. European Journal of Operational Research, 113, 123-136.
Kumar, N. S. H., Srinivasan G., (1996). A Genetic Algorithm for Job Shop Scheduling-A case Study. Computers in Industry, 31, 155-160.
Laarhoven, P. J., Aarts, M. V., Lenstra, J. K., (1992). Job shop scheduling by simulated annealing, Operational Research, 401, 113-125.
Matsuo, H., Suh, C. J., Sullivan, R. S., (1988). A controlled search simulated annealing method for the general job-shop scheduling problem. PhD Thesis, Graduate School of Business, University of Texas at Austin
Mladenovic, N., Hansen, P., (1997). Variable Neighborhood Search. Computers and Operations Research, 24, 1097-1100.
Murovec, B., Suhel, P., (2004). A repearing technique for the local search of the jop-shop problem. European Journal of Operational Research, 153, 220-238.
Nowicki, E., Smutnicki, C., (1996). A fast taboo search algorithm for the job shop problem, Management Science, 42, 797-813.
Pezzella, P., Merelli, E., (2000). A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operational Research, 120, 297-310.
Pinedo, M., (1995). Scheduling: Theory, algorithms and systems, Prentice-Hall, New Jersey.
Ponnambalam, S. G., Aravindan, P., Rao, P. S., (2001). Comparative evaluation of genetic algorithms for job-shop scheduling. Production Planning and Control, 126, 560-574.
Rinnooy, K., (1976). Machine Scheduling Problems: Classification Complexity and Computations. Martinus Nijhoff, The Hague.
Salman, A., Ahmad, I., Al-Madani, S., (2003). Particle swarm optimization for task assignment problem, Microprocessors and Microsystems, 26, 363-371.
Satake, T., Morikawa, K., Takahashi, K., Nakamura, N., (1999). Simulated annealing approach for minimizing the makespan of the general jobshop. International Journal of Production Economics, 60, 515-522.
Steinhöfel, K., Albrecht, A.,Wong, C.K., (2002). Fast parallel heuristic for the job shop scheduling problem, Computers and Industrial Engineering, 29, 151-169.
Stützle, T., (1998). Applying iterated local search to the permutation flowshop problem. Technical Report, Darmstad, Germany, Darmstad University of Technology, Computer Science Department.
Tailard, E., (1994). Parallel taboo search techniques for the job shop scheduling. ORSA Journal on Computing, 16, 2, 108-117.
Tasgetiren, M. F. Liang, Y. C., (2003). A binary particle swarm optimization algorithm for lot sizing problem, Journal of Economic and Social Research, 5, 2, 1-20.
Tasgetiren, M. F., Liang, Y. C., Sevkli, M., Gencyilmaz. G., (2004a). Particle swarm optimization algorithm for makespan and maximum lateness minimization in permutation flowshop sequencing problem, Proceedings, 4th Interna-tional Symposium on Intelligent Manufacturing Systems (IMS2004), Sakarya, Turkey, 431-441.
Tasgetiren, M. F., Sevkli, M., Liang, Y. C., Gencyilmaz. G., (2004b). Particle swarm optimization algorithm for permutation flowshop sequencing problem, Proceedings, 4th International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS2004), LNSC 3172, Brussels, 382-390, Belgium.
Tasgetiren, M. F., Sevkli, M., Liang, Y. C., Gencyilmaz. G., (2004c). Particle swarm optimization algorithm for single machine total weighted tardiness problem, Proceedings, 2004 Congress on Evolutionary Computation (CEC'04), 1412-1419, Portland, Oregon.
Van den Bergh, F., Engelbecht, A. P., (2000). Cooperative learning in neural networks using particle swarm optimizers, South African Computer Journal, 26, 84-90.
Wang, L., Zheng, D., (2001). An effective hybrid optimization strategy for job-shop scheduling problems. Computers and Industrial Engineering 28, 585-596.
Yeh, L. W., (2003). Optimal procurement policies for multi-product multi-supplier with capacity constraint and price discount, Master Thesis, Department of Industrial Engineering and Management, Yuan Ze University, Taiwan.
Yoshida, H., Kawata, K., Fukuyama, Y., Nakanishi, Y., (2000). A particle swarm optimization for reactive power and voltage control considering voltage security assessment, IEEE Transactions on Power Systems, 15, 1232-1239.
Zhou, H., Feng, Y., Han, L., (2001). The hybrid heuristic genetic algorithm for job shop scheduling, Computers and Industrial Engineering, 40, 191-200.