Abstract
This article describes the importance of scheduling, provides a formal statement of the combinatorial job-shop scheduling problem, and shows the complexity of the problem. A review of the most common methods of exact and approximate methods was given. For each method examples was listed and the methods was analysis applied to the job-shop scheduling problems, strengths and weaknesses of the methods were identified. Brute force method theoretically allows to find the exact solution, but is not used, as it is time-consuming. Direct enumeration methods such as brand and bound, are applicable only for some particular cases. Are more efficient algorithms that, firstly, the problem is solved repeatedly and gradually formed the final decision based on the experience of previous decisions, and secondly, using randomization and approaches based on the mechanisms used by nature. These algorithms include Simulated Annealing, Tabu Search, Evolutionary algorithms and Swarm Intelligence algorithms. These algorithms require the parameters settings, so for the best performance the algorithms should be tuned to adapt to the conditions of the problem, in other words, to apply mechanisms meta-optimization and machine learning.
Keywords: planning, scheduling, optimization methods, evolutionary optimization, swarm intelligence, simulated annealing, heuristics, metaoptimization
References
1. Batishev D.I., Vlasov S.Y., Bulgakov I.V. «Blind» regulation of problem solving using genetic algorithms. Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA’96). Moscow, Russia, Russian Academy of Sciences, 1996, pp. 143–155
2. Karpenko A.P. Populyatsionnye algoritmy global'noi poiskovoi optimizatsii. Obzor novykh i maloizvestnykh algoritmov. Prilozhenie k zhurnalu "Informatsionnye tekhnologii", no. 7 [Population algorithms for global continuous optimization. Review of new and little-known algorithms. Supplement to the "Information Technology", no. 7]. Moscow, Novye tekhnologii Publ., 2012. 32 p.
3. Kochetov Yu.A. [Probabilistic methods of local search for discrete optimization problems]. Diskretnaya matematika i ee prilozheniya. Sbornik lektsii molodezhnykh i nauchnykh shkol po diskretnoi matematike i ee prilozheniyam [Discrete mathematics and its applications. A collection of lectures for youth and scientific schools in discrete mathematics and its applications]. Moscow, Publisher Center for Applied Research at the Mechanics and Mathematics Faculty of Moscow State University, 2000, pp. 87–117.
4. Matrenin P.V., Sekaev V.G. Optimizatsiya adaptivnogo algoritma murav'inoi kolonii na primere zadachi kalendarnogo planirovaniya [Optimizing adaptive ant colony algorithm on the example of scheduling problem]. Programmnaya inzheneriya – Software Engineering, 2013, no. 4, pp. 34–40.
5. Matrenin P.V. Razrabotka i issledovanie adaptivnykh metodov roevogo intellekta v zadachakh kalendarnogo planirovaniya [Development and research of adaptive methods Swarm intelligence in the scheduling problem]. Avtomatika i programmnaya inzheneriya – Automation and Software Engineering, 2013, no. 1 (3), pp. 109–114.
6. Matrenin P.V., Sekaev V.G. Sistemnoe opisanie algoritmov roevogo intellekta [System approach to swarm intelligence]. Programmnaya inzheneriya – Software Engineering, 2013, no. 12, pp. 39–45.
7. Norenkov I.P. Evristiki i ikh kombinatsii v geneticheskikh metodakh diskretnoi optimizatsii [Heuristics, and combinations thereof in genetic methods of discrete optimization]. Informacionnye tehnologii – Information technologies, 1999, no. 1, pp. 2–7.
8. Sekaev V.G. Ispol'zovanie algoritmov kombinirovaniya evristik pri postroenii optimal'nykh raspisanii [Use of algorithms of a heuristics combination at construction of optimum schedules]. Informacionnye tehnologii – Information technologies, 2009, no. 10, pp. 61–64.
9. Skiena S.S. The algorithm design manual. Second ed. London, Springer+ Business Media, 2008. 730 p. (Russ. ed.: Skiena S. Algoritmy. Rukovodstvo po razrabotke. 2-e izd. St. Petersburg, BHV-Peterburg, 2013. 720 p.).
10. Tanaev V.S., Sotskov Yu.N., Strusevich V.A. Teoriya raspisanii. Mnogostadiinye sistemy [Scheduling theory. Multi-stage system]. Moscow, Nauka, Glavnaya redaktsiya fiziko-matematicheskoi literatury, 1989. 328 p.
11. Beni G. Wang J. Swarm intelligence in cellular robotic systems. Robots and Biological Systems: towards a new bionics? NATO ASI Series. Series F: Computer and Systems Sciences. Berlin, Heidelberg, Springer, 1993, vol. 102, pt. 7, pp. 703–712.
12. Bierwirth C. A generalized permutation approach to job shop scheduling with genetic algorithms. University of Bremen, Department of Economics, 1995. 11 p. Available at: http://neuro.bstu.by/ai/To-dom/My_research/Papers-0/For-courses/Job-SSP/bierwirth95generalized.pdf (accessed 20.12.2014)
13. Brucker P., Knust S. Complex scheduling. Berlin, Heidelberg, Springer-Verlag, 2006. 284 p.
14. Dorigo M. The ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics. Pt. B, 1996, vol. 26, no. 1, pp. 29–41.
15. Glover F., Laguna M. Tabu search. Vol. 22. Boston, Kluwer academic publishers, 1997. 408 p.
16. Gromicho J.A.S., Hoorn J.J. van, Saldanha-da-Gama F., Timmer G.T. Exponentially better than brute force: solving the job-shop scheduling problem optimally by dynamic programming. Faculdade de Ciências da Universidade de Lisboa, December, 2009. 14 p. Available at: https://www.fc.ul.pt/sites/default/files/fcul/ unidinvestig/cio/Working%20Papers%202009/12.2009.pdf (accessed 20.12.2014)
17. Pedersen M.E.H., Chipperfield A.J. Simplifying particle swarm optimization. Applied Soft Computing, 2009, vol. 10, iss. 2, pp. 618–628.
18. Pezzella F. Merelli E. A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operational Research, 2000, vol. 120, pp. 297–310.
