Создание расписания на основе эвристических моделей

Актуальность: составление расписаний является одной из распространённых проблем, с которой сталкивалось и продолжает сталкиваться человечество в повседневной деятельности. С развитием индустриального общества и появлением нового высокопроизводительного, но при этом очень дорогого промышленного оборудования, потребовало новых подходов к планированию его использования. Мировое разделение труда привело к появлению десятков тысяч новых логистических цепочек по перемещению миллионов компонентов по всему миру. Эффективное планирование использования ресурсов, участвующих в производстве, обслуживании, доставке, строительстве позволяет снизить конечную стоимость продуктов и сделать их доступнее большему количеству людей. Цель: изучение теоретических основ дисциплины «построение расписаний» и использование одного из методов при выполнении практической работы. Задачи: в рамках данной работы будут изучены подходы к построению оптимальных расписаний, сами критерии оптимальности, направления дальнейших исследований.

---

Интересует сколько стоит курсач ? Посчитай на нашем онлайн-калькуляторе.

---

В практическом разделе работы продемонстрировать использование одного из подходов для разработки оптимального расписания смен сотрудников call-центра. Объект работы: разработка информационная системы (программы), позволяющей автоматизировать составление расписания смен сотрудников call-центра по различным критериям оптимальности. Предмет: действующая программа для построения оптимального расписания смен сотрудников call-центра. Методы: в работе использовались теоретические методы исследования (изучение, систематизация и анализ литературы по исследуемой теме; изучение и обобщение опыта по расчетам и построению оптимальных расписаний) и практические (разработка информационного продукта). Структура: для решения поставленной задачи: • будет изучена предметная область теории расписаний и различные алгоритмы построения оптимальных расписаний, в том числе эвристические подходы. • сформулированы требования к расписанию практической части работы, • выбран алгоритм для построения расписания с использованием эвристического подхода • проведена разработка программы и расчёт расписания • проведена визуализация полученного в результате расчёта расписания.

В работе была изучена предметная область «Теория расписаний», являющаяся частью раздела дискретной математики «Исследование операций». Были рассмотрены классические задачи, которые решает этот раздел и основные алгоритмические подходы, которые используются для решения этих задач. Появляются новые методики решения сложных комбинаторных задач, основанные на искусственном интеллекте, генетических алгоритмах, а также алгоритмах «подсмотренных» в мире природы и больших социальных структурах. Эти алгоритмы ещё на ранней стадии своего развития и изучения. Разработчики программных средств и математики-теоретики комбинируют различные подходы, пытаясь взять лучшее из каждого из них и получить решение, превосходящее по скорости и точности то, что было ранее. Задачи составления расписаний приходится решать не только в реальном мире (в промышленности, на транспорте, при проведении различного рода мероприятий, от учебных до спортивных разного уровня), но и в цифровом мире — при распределении нагрузки на ядра процессора, при балансировании нагрузки в дата-центрах, в различном сетевом оборудовании и т. д.). В этой сфере требуются быстродействующие алгоритмы составления расписаний, которые способны за доли секунд (а чаще и микросекунд) распределить нагрузку между ограниченным числом ресурсов, при гиперизменчивом характере нагрузки. Несмотря на бурное развитие вычислительной техники, сложность этих задач такова, что решение их методом «грубой силы» (перебором всех возможных вариантов решения) по-прежнему невозможно. В связи с чем остаются актуальными различные эвристические алгоритмы, позволяющие понизить NP сложность задач до P (полиномиальной сложности). В практической части работы было разработано расписание для сотрудников колл-центра, наилучшим образом удовлетворяющее поставленным условиям. Была использована открытая библиотека от компании Google, в которой реализовано множество стандартных алгоритмов дискретной оптимизации и современные подходы в составлении расписаний и решении других задач поиска решений задач, заданных параметрически. Разработанное решение может быть использовано в практике составления расписаний в различных организациях, где необходимо решение задачи типа «Employee Scheduling».

Теория расписаний. Задачи и алгоритмы / Лазарев А. А., Гафаров Е. Р. / Московский Государственный Университет / Москва, 2011 г., 222 стр. 2. Введение в прикладное дискретное программирование: теория и вычислительные алгоритмы / Сигал И.Х., Иванова А.П. /М.: Физматлит, 2002. 240 c. 3. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. / Хачатуров В.Р., Веселовский В.Е., Злотов А.В. и др. /Москва, Наука, 2000 4. Введение в теорию расписаний./ Танаев В.С., Шкурба В.В./ Наука, 1975 5. Комбинаторная оптимизация. Алгоритмы и сложность / Пападимитриу Х., Стайглиц К. /. М.: Мир, 1985. 512 с. 6. Метод Монте-Карло / Электронный ресурс / Режим доступа: открытый / Дата обращения: 29.03.2023 / URL: https://ru.wikipedia.org/wiki/Метод Монте-Карло 7. Алгоритм пчелиной колонии / Электронный ресурс / Режим доступа: открытый / Дата обращения: 29.03.2023 / URL: https://ru.wikipedia.org/wiki/Алгоритм пчелиной колонии 8. Генетические алгоритмы / учебно-методическое пособие / Панченко, Т. В., под ред. Ю. Ю. Тарасевича / Астрахань, Издательский дом «Астраханский университет», 2007. / 87 с. 9. National football league scheduling /Электронный ресурс / Режим доступа: открытый / Дата обращения: 29.03.2023 / URL: https://www.gurobi.com/case_studies/national-football-league-scheduling/ 10. OR-Tools-Google Optimization Tools /Электронный ресурс / Режим доступа: открытый / Дата обращения: 29.03.2023 / https://github.com/google/or-tools/ 11. Linear and Integer Optimization. Theory and Practice / Gerard Sierksma and Yori Zwols / CRC Press / 2015, 644 c. 12. Using and Understanding ortools' CP-SAT: A Primer and Cheat Sheet /Электронный ресурс / Режим доступа: открытый / Дата обращения: 29.03.2023 / https://github.com/d-krupke/cpsat-primer/ 13. Практикум по алгоритмизации и программированию на Python: / И. А. Хахаев / М. : Альт Линукс, 2010., 126 с.