Тема: Решение задачи минимизации суммарного штрафа в случае одинаковых продолжительностях обслуживания

Теория расписаний - это раздел исследования операций, в котором строятся и анализируются математические модели кaлендарного плaнировaния (т.е. упорядочивания во времени) различных целенаправленных действий с учетом целевой функции и различных ограничений [1]
Задачи теории расписаний, очевидно, связаны с построением расписаний, т.е. с упорядочиванием каких-либо операций (требований) повремени и/или по исполнителям (приборам). При этом необходимо принимать во внимание ограничения на порядок реализации требований,
ограничения, связанные с исполнителями и т.п. Целью решения этих задач,является построение допустимых расписаний, при котором учтены все ограничения,или, что является более сложным, - построение оптимального расписания по какому-либо критерию оптимальности.
Качество обучения студентов в вузах и, конечно же, результативность использования возможностей профессорско-преподавательского состава зависят в некоторой части от степени подготовки учебного процесса. Одной из важнейших частей учебного процесса является расписание занятий - организовывает ритм работы, оказывает влияние на творческую отдачу преподавателей, поэтому имеется возможность рассматривать его как причину оптимизации расходования не безграничных трудовых ресурсов - преподавательского состава. Или же та самая электронная очередь в банке, которая распределяет поток клиентов по их требованиям. В этой модели присутствуют моменты поступления, продолжительности и ожидаемые сроки окончания обслуживания требований. Здесь ограниченным ресурсом является время, которое так же нуждается в оптимизации. С этими и многими другими, более сложными моделями обслуживания определенных требований ежедневно сталкивается человечество. Этим и обусловлена актуальность исследования в области теории расписаний.
Большая часть задач теории расписаний является NP-полными. Вследствие этого, и разработка эффeктивных приближeнных алгоритмов для NP-полных задач тeории расписаний являeтся актуальным. [2]
Одной из известных задач теории расписаний является задача минимизации суммарного штрафа. Эта задача, как и большинство задач теории расписаний, относится к классу NP- полных в сильном смысле задач.

Купить

В ходе данной работы были изучены постановки и методы решения NP- полной задачи теории расписаний- минимизации суммарного штрафа при одинаковых продолжительностях обслуживания. Был разработан программный проект, включающий приближенные алгоритмы решения этой задачи. Также был проведен численный эксперимент сравнения решений, найденных предложенными алгоритмами с количеством требований 5, 6, 7, 8, 9, 10. Для каждой из указанных размерностей генерировалось 200 примеров. Для размерности 5 оптимальное расписание построено в 42% примеров; для размерности 6 в 33,8% примеров; для размерности 7 в 28,5% примеров; для размерности 8 в 27% примеров; для размерности 9 в 25,9% примеров; для размерности 10 в 23,1% примеров. Установлено, что в большинстве экспериментов значение целевой функции приближенного расписания превосходит оптимальное значение не более, чем в 1,5 раза. Превышение значения целевой функции приближенного расписания относительно оптимального значения более чем в 1,5 раза замечены не больше чем в 14% случаев.Также необходимо отметить, что результаты, полученные с помощью приближенного метода (алгоритма для решения взвешенной задачи о назначениях) с ростом продолжительности обслуживания, ухудшаются, а именно, при увеличении продолжительности обслуживания на 2, процент совпадения значения целевой функции приближенного алгоритма с оптимальным значением уменьшается в 0,7 раз в среднем. Тоже самое наблюдается при увеличении количества требований. Поэтому, хочется отметить, что решение, полученное приближенным алгоритмом будет близко к оптимальному решению, если продолжительности обслуживания, количество требований будут небольшие, а также когда требования можно перенумеровать одновременно по не убыванию моментов поступления и директивных сроков.
Купить