Пример 5 Правила приоритетов для поступающих работ

УСТАНОВЛЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТИ РАБОТ

Расписание обеспечивает базис для назначения работ по рабо­чим центрам. Загрузка машин является методом контроля исполь­зования мощностей, который ясно показывает недогрузку и пере­грузку. Последовательности различает порядок, в котором работы должны быть выполнены в каждом центре. Например, предполо­жим, что пациенты назначены в медицинскую клинику для лече­ния. В каком порядке они должны пройти лечение? Должен быть обслужен первым пациент, который прибыл первым, или паци­ент, который нуждается в срочном лечении? Методы выбора последовательности обеспечивают такой необходимой информа­цией. Эти методы отсылают нас к правилам приоритетов запуска работ в рабочие центры.

Правила приоритетов для поступающих работ. Правила при­оритетов широко используются при подготовке диспетчерских сводок (листов) о порядке выполнения работ или обработки партий в цехе. Правила приоритетов обеспечивают построение последовательности, в которой работы должны быть выполнены. Разработано большое число этих правил, одни из них – статиче­ские, другие – динамические. Эти правила находят особенно ши­рокое применение в сложных по маршрутам движения потока дискретных производственных процессах, в которых обработка ведется партиями различной величины, а производство ориенти­ровано на независимый спрос. Правила приоритетов помогают минимизировать среднее время протекания процесса, среднее время завершения изготовления, среднее время пролеживания (ожидания) и максимизировать выход. Чтобы сравнить использо­вание правил приоритетов, было осуществлено несколько про­граммных экспериментов на основе моделирования. В этом раз­деле мы обсудим несколько хорошо известных правил и эффек­тивность их использования.

Наиболее популярными правилами приоритетов являются сле­дующие.

FCFS «Первый пришел – первый обслужен». Первая работа, при­бывающая в рабочий центр, выполняется первой.

EDD. Ранняя по дате исполнения. Работа с ранней датой завер­шения отбирается первой.

SPT. Кратчайшее время исполнения. Кратчайшая по времени выполнения работа обрабатывается первой и «убирается с дороги прочь».

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

Мы можем сравнить эти правила, просматривая пример 5.

Пять работ по листу металла ожидают назначения в рабочий центр. Продол­жительности процессов и даты их завершения относительно момента расчета приводятся ниже. Мы желаем определить последовательность выполнения процес­сов согласно: 1) FCFS, 2) SPT, 3) EDD, 4) LPT правил. Работы были обозначены буквами в порядке их прибытия.

Работа	Время про-цесса, дни	Срок выполнения работы, дни	Работа	Время про-цесса, дни	Срок выполнения работы, дни
А			D
В			Е
С			–

1. FCFS последовательность проста: А—В—С—D—Е. «Время потока» в систе­ме для этой последовательности измеряется временем ожидания каждой работы плюс время нахождения в рабочем процессе. Работа В, например, ожидает шесть дней, пока работа А находится в рабочем процессе, и затем еще требуется два дня выполнения процесса над работой В. Таким образом, работа будет завершена за восемь дней, что на два дня позже, чем требуется.

Последовательность работ	Время процесса	«Время потока»	Срок выполнения работы	Запаздывание работы
А
В
С
D
Е

«Первый пришел – первый обслужен». Результаты этого правила оцениваются следующими измерителями эффективности его использования:

а) Среднее время завершения работы = Сумма потоков времен / Число работ =

= 77 дней / 5 = 15.4 дня;

б) Среднее число работ в системе = Сумма потоков времен / Общее время процесса =

= 77 дней / 28 дней = 2.75 работ;

с) Среднее ожидание работы = Общее опоздание в днях / Число работ = 11 / 5 = 2.2 дня.

2. SPT в результате выполнения приводит к последовательности: В—D—А— —С—Е (см. ниже). Порядок следования определяется длительностью времени процесса с наивысшим приоритетом, приписываемым наикратчайшей работе.

Последовательность работ	Время процесса	«Время потока»	Срок выполнения работы	Запаздывание работы
А
В
С
D
Е

Показатели эффективности для SPT:

а) Среднее время завершения = 65 / 5 = 13 дней;

в) Среднее число работ в системе = 65 / 28 = 2.32 работ;

с) Среднее опоздание работы = 9 / 5 = 1.8 дня.

3. EDD обеспечивает такую последовательность: В—A—D—С—Е. Заметим, что работы выстраиваются в порядке возрастания даты исполнения работы.

Последовательность работ	Время процесса	«Время потока»	Срок выполнения работы	Запаздывание работы
А
В
С
D
Е

Измерители эффективности для EDD:

а) Среднее время завершения = 68 / 5 = 13.6 дня;

в) Среднее число работ в системе = 68 / 28 = 2.42 работ;

с) Среднее опоздание работы = 6 / 5 = 1.2 дня.

4. LPT в результате дает следующий порядок: Е—С—A—D—В.

Последовательность работ	Время процесса	«Время потока»	Срок выполнения работы	Запаздывание работы
А
В
С
D
Е

Измерители эффективности для наипродолжительного процесса:

а) Среднее ирсмя завершения = 103 / 5 = 20.6 дня;

в) Среднее число работ в системе = 103 / 28 = 3.68 работ;

с) Среднее опоздание работы = 48 / 5 = 9.6 дня.

Результаты всех четырех правил даны ниже.

Правило	Среднее время завершения, дни	Среднее число работ в системе	Среднее опоздание работы, дни
FCFS	15.4	2.75	2.2
SPT	13.0	2.32	1.8
HDD	13.6	2.42	1.2
LPT	20.6	3.68	9.6

Как мы видим из примера 5, LPT является методом, характе­ризующимся последовательностью выполнения работ с худшими измерителями эффективности в конкретном рабочем центре. SPT впереди по значению двух показателей и EDD – второй по ре­зультатам оценки (самая низкая средняя запаздываемость). Эта же картина результатов использования методов сохраняется и к ре­альной действительности. Очевидно, что ни одно из правил не достигает превосходства по всем критериям (измерителям). Опыт подтверждает это.

1. Наикратчайшее время процесса обычно является наилуч­шим методом при минимизации времени потока работ и миними­зирует среднее число работ в системе. Его главный недостаток состоит в том, что долгодлящиеся работы будут постоянно отодви­гаться назад, подчиняясь приоритету краткосрочных работ. По­требители могут отнестись к этому пессимистически, и поэтому возникнет необходимость ввести дополнительное регулирование прохождения долго длящихся работ в рабочем центре.

2. «Первый пришел – первый обслужен» не дает выигрыша по большинству критериев (правда, результаты не так уж плохи). Однако он имеет преимущество справедливости для потребителя, что очень важно в обслуживающих системах.

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

Критическое отношение. Другой тип правила последователь­ности. Критическое отношение (CR) есть индекс, получаемый как деление времени, оставшегося до срока выполнения работы (по плану), на остающееся время на исполнение работы. В противо­положность правилам приоритетов критическое отношение динамично. Оно может быть получено на любую дату и достаточно часто, и его использование развивает (обогащает) составление расписаний.

Критическое отношение дает приоритет работам, которые дол­жны быть выполнены, чтобы не нарушить расписание отгрузки. Работа с низким критически отношением (меньше 1,0) является работой, выпадающей из расписания, отстающей. Если CR в точности равно 1,0, работа находится в границах расписания. CR больше чем 1,0 означает, что работа опережает расписание и время ее выполнения не напряженно.

Выражение для определения критического отношения имеет вид:

CR = Оставшееся время / Оставшиеся рабочие дни =

= (Дата окончания – Текущая дата) / Остающееся (время выполнения) рабочее время