Управление очередями

Простейшее решение по составлению расписаний имеет так называемая задача директора. Сущность этой задачи заключается в следующем.

На прием к директору записалось несколько посетителей. Секретарь директора составил список в алфавитном порядке, указав для каждого требующуюся ему ориентировочную продолжительность приема. Фамилии записавшихся обозначены в списке их заглавными буквами (табл. 7.5).

На весь прием директор, как видно из таблицы, отвел 2 часа =120 минут, поэтому пришлось ограничиваться всего шестью посетителями. Является ли составленное расписание наилучшим?

 

Таблица 7.5

№ п/п	Фамилия (начальная буква)	Продолжительность приема, мин	Время ожидания, мин
	Б
	Д
	Е
	К
	С
	Т
Суммарное время 120 мин = 260 мин = = 2 часа = 4 часа 20 мин

С точки зрения общей продолжительности приема любая очередность посетителей равнозначна: суммарное время приема не меняется при любой его последовательности. А с точки зрения ожидания в очереди? Подсчитаем общее время ожидания как сумму времени ожидания всех посетителей. В нашем алфавитном списке оно составляет 260 минут = 4 часа 20 минут. Понятно, что это время желательно было бы уменьшить: ведь время ожидания – зря потраченное время. Но вот можно ли это сделать? Приведет ли расписание с другой последовательностью приема к экономии общего времени ожидания при сохранении намеченного суммарного времени приема?

Оказывается, получение такого расписания возможно. В одном из методов исследования операций – так называемой теории расписаний – доказывается, что наименьшее суммарное время ожидания получается при составлении расписания в порядке нарастания продолжительности приема. Составим такое расписание (табл. 7.6).

Таблица 7.6

 

	№ п/п	Фамилия (начальная буква)	Продолжительность приема, мин	Время ожидания, мин
	К
	Е
	Д
	Б
	Т
	С
Суммарное время 120 мин = 190 мин = = 2 часа = 3 часа 10 мин

Полученное оптимальное расписание позволяет уменьшить суммарное время ожидания на 1 час 10 минут. Это значительное сэкономленное время можно использовать на полезные дела.

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

Задачу директора иногда называют задачей одного станка. Ее дальнейшим развитием является задача двух станков. В чем ее суть?

Детали обрабатываются последовательно на двух станках. В табл. 7.7 показана продолжительность этой обработки для каждой из 10 деталей на двух станках. Нумерация деталей и последовательность их обработки взяты при этом произвольно.

 

Таблица 7.7

 

Номера деталей и последовательность их обработки
Продолжительность обработки на станке № 1, мин
Продолжительность обработки на станке № 2, мин

 

Расчет показывает, что суммарное время обработки всех деталей составляет 118 минут. Кроме того, существует время ожидания обработки первой поданной детали на станке № 2, равное 7 минутам, и время ожидания, пока освободится станок № 2 для обработки детали № 5, равное 11 минутам. Итого – обработка всех деталей на двух станках с учетом времени ожидания продолжается 136 минут.

В теории расписаний доказывается, что в задаче двух станков для обеспечения оптимальной последовательности обработки с наименьшим временем ожидания необходимо составлять расписание, руководствуясь следующими правилами:

1) выбирается деталь с наименьшей продолжительностью обработки на одном из станков; в нашем примере это № 9;

2) выбранная деталь помещается в начало очереди, если наименьшая продолжительность обработки соответствует станку № 1, или в конец очереди, если – станку № 2; в нашем примере деталь № 9 помещается в конец очереди;

3) столбец таблицы 7.7, ранее занятый выбранной деталью, вычеркивается;

4) выбирается деталь среди оставшихся со следующей наименьшей продолжительностью обработки на одном из станков; в нашем примере – деталь № 7;

5) выбранная деталь помещается в начало или конец очереди по указанному в пункте 2 правилу; в нашем примере деталь № 7 помещается в начало очереди;

6) вычеркивается соответствующий столбец таблицы.

И так далее.

В итоге можно получить оптимальное расписание работы двух станков (табл. 7.8).

 

Таблица 7.8

 

 

Последовательность обработки (порядковый номер очереди)
Номер детали
Продолжительность обработки на станке № 1, мин
Продолжительность обработки на станке № 2, мин

 

Полученное оптимальное расписание уменьшает время ожидания обработки до 2 минут (станок № 2 ждет в самом начале, пока станок № 1 обработает деталь № 7). Общее время обработки с учетом времени ожидания тем самым сокращается до 120 минут- на 12 %.

Заметим, что, не зная описанного простого правила, эту задачу не решить и опытному специалисту. Ведь чтобы выйти на оптимальное расписание, необходимо перебрать несколько миллионов вариантов очередности.

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

Говоря о составлении наилучших расписаний, нельзя обойти еще один важный для практики тип задач. Речь пойдет о так называемой задаче о назначениях.