АННОТАЦИЯ 2
ВВЕДЕНИЕ 6
1 ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ 7
1.1 Классификация задач 7
1.2 Постановки задач теории расписаний 8
1.2.1 Одноприборная задача минимизации числа запаздывающих требований 8
1.2.2 Задачи цеха 9
1.2.3 Классическая постановка задачи планирования проекта с ограниченными
ресурсами RCPSP 9
1.2.4 Частные случаи задачи RCPSP с одним ресурсом 10
1.3 Выводы по разделу 10
2 СОСТАВЛЕНИЕ РАСПИСАНИЯ ДЛЯ РАБОТНИКОВ 11
2.1 Постановка задачи теории расписаний . 11
2.2 Алгоритм поиска расписания 12
2.2.1 Алгоритм диспетчеризации 12
2.2.2 Алгоритм муравьиные колонии 12
2.3 Результаты тестирования алгоритма 13
2.4 Выводы по разделу 15
3 ПРОЕКТИРОВАНИЕ ПРОГРАММЫ 16
3.1 Требования к программе 16
3.2 Разработка пользовательского интерфейса 17
3.3 Проектирование базы данных 22
3.3.1 Выделение сущностей предметной области 22
3.3.2 ER-модели сущностей 23
3.3.3 Представление сущностей в виде элементов реляционной базы данных 25
3.4 Разработка алгоритма 29
3.4.1 Модуль авторизации 31
3.4.2 Модуль формирования заявок .....31
3.4.3 Модуль составления расписания 32
3.4.4 Модуль просмотра статистики 35
3.4.5 Программный эксперимент 36
3.5 Выводы по разделу 37
ЗАКЛЮЧЕНИЕ 38
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 39
ПРИЛОЖЕНИЕ 1. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ 40
ПРИЛОЖЕНИЕ 2. ТЕКСТ ПРОГРАММЫ 49
На практике часто возникают задачи, связанные с эффективным распределением ограниченных ресурсов. Ресурсы могут быть разного типа: прибыль, время, работники, станки и т.д. Также различаются и критерии эффективности решений (целевые функции), и методы поиска решения. Вследствие этого появляются различные постановки задачи: задача о назначениях; задачи распределения ресурсов; задачи массового обслуживания; задачи календарного планирования (теории расписаний); задачи транспортного типа (выбора маршрутов перевозок); задачи сетевого планирования и управления; задачи планировки и размещения объектов.
Одной из функций отдела технического обслуживания на предприятии является организация и руководство работой инженеров, выполняющих техническое обслуживание заявок. Чтобы оформить заявку, оператору достаточно заполнить информацию о ней, указать причины и дату выполнения. В дальнейшем чтобы распределить задачи между работниками, оператору нужно выбрать инженеров (из числа пришедших на работу), и программа сама распределит работы между ними с учетом временных ограничений.
Инженеры, в свою очередь, могут получить задачи на день на свои смартфоны. Там уже будет указано время и место очередной заявки. Отчитаться о работе они могут в конце рабочего дня, отправив изменения на сервер.
Возникает проблема, связанная с составлением расписания, которую можно отнести к задаче распределения ресурсов.
Целью выпускной квалификационной работы являлась разработка приложения для автоматизации процесса распределения заявок.
На примере отдела технического обслуживания можно сформулировать задачи следующим образом:
- если известны оценки эффективности для каждого работники при выполнении разных работ, и нужно назначить на каждую работу по одному работнику, можно сформировать задачу о назначении;
- если оценки для работ не известны, а каждому рабочему нужно назначить больше одной работы, причем для работ заданы сроки выполнения, то здесь пригодятся методы теории расписаний;
- если работы связаны с перевозкой оборудования, и известны расстояния между пунктами наличия и пунктами назначения, возникает транспортная задача.
Для инженеров сложно дать объективную оценку их способности выполнять различные работы, зато можно указать примерную длительность однотипных работ. Поэтому можно свести задачу к задаче теории расписаний и с учетом временных рамок составить оптимальное расписание, если такое возможно. Решение подобной задачи позволит отделу технического обслуживания минимизировать число требований, выполнение которых запаздывает.
Получено приложение «Заявки инженерам», помогающее отделу технического обслуживания при работе учитывать заявки и распределять их по исполнителям.
Разработан пользовательский интерфейс для настольного приложения и мобильного.
Для хранения и обработки данных, разработана информационная система, хранящая информацию о заявках, построена ER-диаграмма. База данных была нормализована, и находится в форме Бойса-Кодда.
В процессе написания программы были выделены модули для выполнения следующих функций:
- предоставления доступа авторизованным пользователям;
- формирование заявок в электронном виде с использованием шаблонов;
- составление расписания на день;
- получение статистики причин и пользователей заявок.
Изучены некоторые задачи и методы теории расписаний. Поставлена задача распределения заявок. Приведена классификация с использованием нотации Грэхема и найдено место в этой классификации для данной задачи.
Реализован алгоритм составления расписания, основанный на методе муравьиные колонии и алгоритме диспетчеризации. Проведено тестирование алгоритма с разными значениями параметров и выбраны наиболее удачные.
В качестве возможных функциональных расширений, можно ввести для инженеров специализацию и перестроить алгоритм, чтобы он назначал заявки в соответствии с компетенцией инженера выполнять определенную работу.
