Тема: Исследование алгоритма решения задачи минимизации суммарного штрафа

Сегодня мир развивается с огромной скоростью. Постоянно расширяются масштабы современного производства, усложняются и делегируются процессы, возникает необходимость в координации работы различных отраслей. Людям приходиться принимать решения, зачастую связанные с большими затратами и сложными условиями. Принимаемые решения направлены на достижение определённых целей и имеют систему ограничений. Эти цели могут быть реализованы разным способом, с различными затратами и временем. Успешное решение невозможно без повышения качества управления производственными процессами и технологическими объектами. Для этого необходимо применение научных методов моделирования и оптимизации производственно-экономических и технологических ситуаций. Немаловажную роль в достижении этой цели играет последовательность выполнения поступающих задач. Выбрать верно данную последовательность помогает теория расписаний.
Введение в теорию расписаний
Задачи теории расписаний - задачи оптимизации процесса обслуживания конечного множества требований в системе, содержащей конечное множество приборов.
Нужно обслужить на одном приборе n требований с момента времени t. Пронумеруем их:
1,...,n
Обслуживание элементов множества N:
N = { 1,...,n }
Запрещены искусственные простои прибора, прерывание в обслуживании требований и одновременное обслуживание требований. 
Для каждого требования заданы параметры V j £ N: ij - момент поступления требования j на обслуживание.
Pj > 0 - длительность обслуживания требования j.
dj - директивный срок момента времени, к которому желательно завершить. Wj - вес, приоритет, значимость требования.
GN - граф, отношения предшественников задаются ориентированным графом без контуров.
Купить

В результате выполнения дипломной работы был исследован приближенный алгоритм решения задачи минимизации суммарного штрафа с применением метода решения задачи о назначениях.
В работе реализовано сведение задачи минимизации суммарного штрафа с одинаковыми продолжительностями обслуживания к задаче о назначениях, а также запрограммирован алгоритм решения задачи о назначениях. В качестве точного метода был выбран метод перебора.
Алгоритмы были реализованы на языке программирования Python в среде PyCharm 3.6.
Было сгенерировано пять тысяч примеров с различными
продолжительностями и различным количеством требований, были
получены решения этих примеров приближенным алгоритмом и проведено исследование приближенного алгоритма. В ходе этого исследования было выявлено, что приближенный алгоритм дает 100% совпадение с точным при количестве требований равным одному, но чем больше количество требований, тем менее точно работает приближенный алгоритм. При количестве требований равном 10 количество совпадений приближенного алгоритма с точным алгоритм становится равным нулю.
Реализованный алгоритм имеет простой и удобный интерфейс и может быть использован в дальнейшем для расчетов.

Купить