Аннотация
В статье указывается актуальность задач планирования, дается формальная постановка комбинаторной задачи календарного планирования класса job-shop scheduling и показываются сложности данного класса задач. Приводится обзор наиболее распространенных точных и приближенных методов решения. Для каждого метода перечисляются примеры и проводится анализ применимости сильных и слабых сторон методов для задач класса job-shop. Метод полного перебора всех вариантов теоретически позволяет найти точное решение, но не используется, так как требует больших затрат времени. Методы направленного перебора, например ветвей и границ, применимы только для некоторых частных случаев. Наиболее эффективными являются методы, которые, во-первых, выполняют решение задачи многократно и используют опыт, полученный на предыдущих решениях, а во-вторых, используют рандомизацию и механизмы, используемые в природе. К таким алгоритмам относятся алгоритм имитации отжига, поиск с запретами, эволюционные алгоритмы и алгоритмы роевого интеллекта. Указанные алгоритмы требуют регуляции своих параметров, поэтому для лучшей производительности алгоритмы должны быть настроены для адаптации к условиям задач, иными словами, необходимо применять механизмы метаоптимизации и машинного обучения.

 

Список литературы
1. Батищев Д.И., Власов С.Е., Булгаков И.В. Решение задачи «слепого» упорядочивания с помощью генетических алгоритмов // Труды конференции по генетическим алгоритмам. – М., 1996. – С. 32–35.

2. Карпенко А.П. Популяционные алгоритмы глобальной поисковой опти-мизации. Обзор новых и малоизвестных алгоритмов. – М.: Новые технологии, 2012. – 32 с. – (Приложение к журналу «Информационные технологии»; № 7).

3. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения: сборник лекций молодежных и научных школ по дискретной математике и ее прило-жениям. – М.: Издательство центра прикладных исследований при механико-математическом факультете МГУ, 2000. – С. 87–117.

4. Матренин П.В., Секаев В.Г. Оптимизация адаптивного алгоритма му-равьиной колонии на примере задачи календарного планирования // Програм-мная инженерия. – 2013. – № 4. – С. 34–40.

5. Матренин П.В. Разработка и исследование адаптивных методов роевого интеллекта в задачах календарного планирования // Автоматика и програм-мная инженерия. – 2013. – № 1 (3). – С. 109–114.

6. Матренин П.В., Секаев В.Г. Системное описание алгоритмов роевого интеллекта // Программная инженерия. – 2013. – № 12. – С. 39–45.

7. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации // Информационные технологии. – 1999. – № 1. –

С. 2–7.

8. Секаев В.Г. Использование алгоритмов комбинирования эвристик при построении оптимальных расписаний // Информационные технологии. – 2009. – № 10. – С. 61–64.

9. Скиена С. Алгоритмы. Руководство по разработке: пер. с англ. – 2-е изд. – СПб.: БХВ-Петербург, 2013. – 720 с.

10. Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. – М.: Наука, Главная редакция физико-математи-ческой литературы, 1989. – 328 с.

11. Beni G., Wang J. Swarm intelligence in cellular robotic systems // Robots and biological systems: towards a new bionics? – Berlin; Heidelberg: Springer 1993. – P. 703–712. – (NATO ASI Series. Series F: Computer and Systems Sciences; vol. 102, pt. 7).

12. Bierwirth C. A generalized permutation approach to job shop scheduling with genetic algorithms / University of Bremen, Department of Economics. – Bremen, Germany, 1995. – 11 p. – URL: 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,

N 1. – P. 29–41.

15. Glover F., Laguna M. Tabu search. Vol. 22. – Boston: Kluwer academic publishers, 1997. – 408 p.

16. Exponentially better than brute force: solving the job-shop scheduling problem optimally by dynamic programming / J.A.S. Gromicho, J.J. van Hoorn,

F. Saldanha-da-Gama, G.T. Timmer / Faculdade de Ciências da Universidade de Lisboa. – Lisboa, 2009. – 14 p. – URL: 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 optimiza-tion // Applied Soft Computing. – 2010. – Vol. 10, iss. 2. – P. 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. – P. 297–310.