Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Это простейшая задача теории расписания.
Постановка задачи. Имеется некоторый прибор (станок, аппарат и так далее) и имеется заявок для обслуживания на этом приборе. Для каждой заявки указано – время обслуживания и – штраф за единицу времени ожидания в очереди, . Требуется указать оптимальную последовательность облуживания заявок на приборе, такую, чтобы суммарный штраф был минимальным.
Математическая модель. Пусть – последовательность обслуживания заявок на приборе, при которой первой обслуживается заявка с номером , второй – и так далее, последней – с номером . Это и будет план задачи. Множество всех планов обозначим через – это множество перестановок из чисел. Тогда ясно, что всего планов будет . Поэтому для этой задачи возможен полный перебор. Каждому плану поставим в соответствие штраф так что:
Задача обслуживания принимает вид:
(2)
Хотя возможен полный перебор, но он не рационален. Оптимальный план можно получить методом вариаций.
Определение. Простейшей вариацией перестановки называют такую перестановку , у которой по сравнению с переставлены местами две соседние заявки и .
, .
Подсчитаем, на сколько изменится штраф при переходе от к . Имеем:
Предположим, что оказалась оптимальной перестановкой . Это значит, что
(3)
(3) − необходимое условие оптимальности , а так как у задачи существует оптимальный план, то это необходимое условие будет и достаточным, то есть любая последовательность, которая удовлетворяет (3) будет оптимальной.
Согласно критерию оптимальности в первую очередь должны обслуживаться заявки с наибольшим относительным штрафом на единицу времени ожидания. Ясно, как без перебора найти оптимальную последовательность: для каждого подсчитать , полученные числа упорядочить по убыванию.
Рассмотрим частный случай, когда для всех заявок штраф одинаковый.
.
Тогда сократив в (3) числитель на эту общую величину, получим критерий оптимальности:
, (4)
согласно которому в первую очередь должны обслуживаться заявки с наименьшим временем исполнения.
Пример. Если в качестве прибора рассмотреть приёмную начальника, а в качестве заявок – посетителей, записавшихся к нему на приём. Для того чтобы суммарно посетители меньше страдали в очереди, начальник должен принимать, тех, у кого вопросы мелкие.
Дата публикования: 2015-01-23; Прочитано: 223 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!