Лекция: Задача обслуживания заявок на одном приборе

Это простейшая задача теории расписания.

Постановка задачи. Имеется некоторый прибор (станок, аппарат и так далее) и имеется заявок для обслуживания на этом приборе. Для каждой заявки указано – время обслуживания и – штраф за единицу времени ожидания в очереди,. Требуется указать оптимальную последовательность облуживания заявок на приборе, такую, чтобы суммарный штраф был минимальным.

Математическая модель. Пусть – последовательность обслуживания заявок на приборе, при которой первой обслуживается заявка с номером, второй – и так далее, последней – с номером. Это и будет план задачи. Множество всех планов обозначим через – это множество перестановок из чисел. Тогда ясно, что всего планов будет. Поэтому для этой задачи возможен полный перебор. Каждому плану поставим в соответствие штраф так что:

Задача обслуживания принимает вид:

(2)

Хотя возможен полный перебор, но он не рационален. Оптимальный план можно получить методом вариаций.

Определение. Простейшей вариацией перестановки называют такую перестановку, у которой по сравнению с переставлены местами две соседние заявки и .

, .

Подсчитаем, на сколько изменится штраф при переходе от к. Имеем:

Предположим, что оказалась оптимальной перестановкой. Это значит, что

(3)

(3) − необходимое условие оптимальности, а так как у задачи существует оптимальный план, то это необходимое условие будет и достаточным, то есть любая последовательность, которая удовлетворяет (3) будет оптимальной.

Согласно критерию оптимальности в первую очередь должны обслуживаться заявки с наибольшим относительным штрафом на единицу времени ожидания. Ясно, как без перебора найти оптимальную последовательность: для каждого подсчитать, полученные числа упорядочить по убыванию.

Рассмотрим частный случай, когда для всех заявок штраф одинаковый.

.

Тогда сократив в (3) числитель на эту общую величину, получим критерий оптимальности:

, (4)

согласно которому в первую очередь должны обслуживаться заявки с наименьшим временем исполнения.

Пример. Если в качестве прибора рассмотреть приёмную начальника, а в качестве заявок – посетителей, записавшихся к нему на приём. Для того чтобы суммарно посетители меньше страдали в очереди, начальник должен принимать, тех, у кого вопросы мелкие.