DJOB SHOP SCHEDULING WITH KRILL HERD ALGORITHM

Abstract

Krill herd algorithm is a recently proposed swarm based metaheuristic algorithm for solving real life problems. In the literature, the performance of the algorithm has been tested on non-linear continuous optimization problems. In this study, the performance of the krill herd algorithm is tested on job shop scheduling problems, which is one of combinatorial optimization problems, for the first time in the literature. Job shop scheduling problems are one of the most complex and important problems with representative characteristics to other hard combinatorial optimization problems. This study provides some idea about krill herd algorithm’s possible performance for solving other combinatorial optimization problems.

Keywords

• Krill herd algorithm, Job shop scheduling problem, Metaheuristic algorithms, Swarm intelligence

KRİL SÜRÜSÜ ALGORİTMASI İLE ATÖLYE ÇİZELGELEME

Abstract

Kril sürüsü algoritması gerçek hayat problemlerini çözmek amacıyla yakın dönemde literatüre kazandırılmış sürü temelli metasezgisel algoritmalardar biridir. Algoritmanın performansı literatürde sürekli-sayı değişkenlere sahip doğrusal olmayan optimizasyon problemleri üzerinde denenmiştir. Bu çalışmada kril sürüsü algoritmasının performansı literatürde ilk kez kombinatoryal optimizasyon problemlerinden biri olan atölye tipi çizelgeleme problemleri üzerinde test edilmiştir. Atölye tipi çizelgeleme problemleri, diğer zor kombinatoryal optimizasyon problemlerini temsil eden önemli bir problem türü olduğundan, bu çalışma algoritmanın diğer kombinatoryal problemlerdeki olası performansı hakkında ön bilgiler vermektedir

Keywords

• Krill sürüsü algorithması, Atölye çizelgeleme problemi, Metasezgisel algoritmalar, Sürü zekası

References

1. Adams J., Balas E., Zawack D. (1988): "The Shifting Bottleneck Procedure for Job Shop Scheduling", Management Science, Cilt 34, No. 3, s.391-401.
2. Aiex R. M., Binato S., Resende M. G. C. (2003): "Parallel GRASP with Path-Relinking for Job Shop Scheduling", Parallel Computing, Cilt 29, No. 4, s.393-430.
3. Anandaraman C. (2011): "An Improved Sheep Flock Heredity Algorithm for Job Shop Scheduling and Flow Shop Scheduling Problems", International Journal of Industrial Engineering Computations, Cilt 2, No. 4, s749-764.
4. Baker K. R. (1974): "Introduction to Sequencing and Scheduling", New York: Wiley.
5. Baykasoğlu A. (2002): "Linguistic-Based Meta-Heuristic Optimization Model for Flexible Job Shop Scheduling", International Journal of Production Research, Cilt 40, No. 17, 4523- 4543.
6. Baykasoğlu A., Hamzadayı A., Köse S. Y. (2014): "Testing the Performance of Teaching– Learning Based Optimization (TLBO) Algorithm on Combinatorial Problems: Flow Shop and Job Shop Scheduling Cases", Information Sciences, Cilt 276, No. 0, s.204-218.
7. Beasley J. E. (1990): "OR-Library: Distributing Test Problems by Electronic Mail", Journal of the Operational Research Society, Cilt 41, No. 11, s.1069-1072.
8. Bierwirth C., Mattfeld D. C. (1999): "Production Scheduling and Rescheduling with Genetic Algorithms", Evolutionary Computation, Cilt 7, No. 1, s.1-17.

9. Brucker P., Jurisch B., Sievers B. (1994): "A Branch and Bound Algorithm for the Job-Shop Scheduling Problem", Discrete Applied Mathematics, Cilt 49, No. 3, s.107-127.
10. Cheng R., Gen M., Tsujimura Y. (1996): "A Tutorial Survey of Job-Shop Scheduling Problems Using Genetic Algorithms—I. Representation", Computers and Industrial Engineering, Cilt 30, No. 4, s.983-997.
11. Fisher H., Thompson G. L. (1963): "Probabilistic Learning Combinations of Local Job Shop Scheduling Rules", Englewood Cliffs, NJ: Prentice-Hall.
12. Gandomi A. H., Alavi A. H. (2012): "Krill Herd: A New Bio-Inspired Optimization Algorithm", Communications in Nonlinear Science and Numerical Simulation, Cilt 17, No. 12, s.4831-4845.
13. Gen M., Cheng R. (2000): "Genetic Algorithms and Engineering Optimization", Cilt 7, John Wiley & Sons.
14. Giffler B., Thompson G. L. (1960): "Algorithms for Solving Production-Scheduling Problems", Operations Research, Cilt 8, No. 4, s.487-503.
15. Gonçalves J. F., Resende M. G. C. (2014): "An Extended Akers Graphical Method with a Biased Random-Key Genetic Algorithm for Job-Shop Scheduling", International Transactions in Operational Research, Cilt 21, No. 2, s.215-246.
16. Hasan S. M. K., Sarker R., Essam,D., Cornforth D. (2009): "Memetic Algorithms for solving job-shop scheduling problems", Memetic Computing, Cilt 1, No. 1, 69-83.
17. Hofmann E. E., Haskell A. G. E., Klinck J. M., Lascara C. M. (2004): "Lagrangian Modelling Studies of Antarctic Krill (Euphausia Superba) Swarm Formation", ICES Journal of Marine Science, Cilt 61, No. 4, s.617-631.
18. Hong Wei G., Liang S., Yan Chun L., Feng Q. (2008): "An Effective PSO and AIS-Based Hybrid Intelligent Algorithm for Job-Shop Scheduling", Systems, Man and Cybernetics, Part A: Systems and Humans, Cilt 38, No. 2, s.358-368.
19. Jain A. S., Meeran S. (1999): "Deterministic Job-Shop Scheduling: Past, Present and Future", European Journal of Operational Research, Cilt 113, No. 2, s.390-434.
20. Lawrence S. (1984): "Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques (Supplement)", Pittsburg: Carnegie Mellon University.
21. Lin T. L., Horng S. J., Kao T. W., Chen Y. H., Run R. S., Chen R. J., Kuo I. H. (2010): "An Efficient Job-Shop Scheduling Algorithm Based on Particle Swarm Optimization", Expert Systems with Applications, Cilt 37, No. 3, s.2629-2636.
22. Luh G. C., Chueh C. H. (2009): "A Multi-Modal Immune Algorithm for the Job-Shop Scheduling Problem", Information Sciences, Cilt 179, No. 10, s.1516-1532.
23. Nowicki E., Smutnicki C. (1996): "A Fast Taboo Search Algorithm for the Job Shop Problem", Management Science, Cilt 42, No. 6, 797-813.
24. Potts C. N., Strusevich V. A. (2009): "Fifty Years of Scheduling: a Survey of Milestones", Journal of the Operational Research Society, Cilt 60, No. 1, s.41-s.68.
25. Price H. J. (1989): "Swimming Behavior of Krill in Response to Algal Patches: A Mesocosm Study", Limnology and Oceanography, Cilt 34, No. 4, s.649-659.
26. Roy P. K., Paul C. (2014): "Optimal Power Flow Using Krill Herd Algorithm", International Transactions on Electrical Energy Systems.
27. Sha D. Y., Hsu C. Y. (2006): "A Hybrid Particle Swarm Optimization for Job Shop Scheduling Problem", Computers and Industrial Engineering, Cilt 51, No. 4, s.791-808.
28. Singh V., Sood M. M. (2013): "Krill Herd Clustering Algorithm Using DBSCAN Technique", International Journal of Computer Science & Engineering Technology, Cilt 4, No. 3. s.197- 201
29. Wang G. G., Gandomi A. H., Alavi A. H. (2013): "A Chaotic Particle-Swarm Krill Herd Algorithm for Global Numerical Optimization", Kybernetes, Cilt 42, No. 6, s.962-978.
30. Wang G. G., Gandomi A. H., Alavi A. H. (2014): "An Effective Krill Herd Algorithm with Migration Operator in Biogeography-Based Optimization", Applied Mathematical Modelling, Cilt 38, No. 9, s.2454-2462.
31. Wang G. G., Gandomi A. H., Alavi A. H. (2014): "Stud Krill Herd Algorithm", Neurocomputing, Cilt 128, No. 1, s.363-370.
32. Wang G. G., Guo L., Gandomi A. H., Alavi A. H., Duan H. (2013): "Simulated Annealing- Based Krill Herd Algorithm for Global Optimization", Abstract and Applied Analysis, Cilt 11.
33. Wang G., Guo L., Gandomi A. H., Cao L., Alavi A. H., Duan H., Li J. (2013): "Lévy-Flight Krill Herd Algorithm", Mathematical Problems in Engineering, Cilt 2013, Article ID 682073, doi:10.1155/2013/682073
34. Wang G., Guo L., Wang H., Duan H., Liu L., Li J. (2014): "Incorporating Mutation Scheme into Krill Herd Algorithm for Global Numerical Optimization", Neural Computing and Applications, Cilt 24, No. 3, s.853-871.
35. Yang J. H., Sun L., Lee H. P., Qian Y., Liang Y. C. (2008): "Clonal Selection Based Memetic Algorithm for Job Shop Scheduling Problems", Journal of Bionic Engineering, Cilt 5, No. 2, s.111-119.