Чейз, Ричард, Б., Эквилайн, Николас, Дж., Якобе, Роберт, Ф. Производственный и операционный менеджмент

Подождите немного. Документ загружается.

751

установленным срокам или порядку поступления заказов. Другие правила, тоже простые,

могут требовать несколько большей информации для того, чтобы определить какой-либо

числовой показатель, как, например, правила критического отношения (ниже приведены

определения основных правил приоритетов). А такие правила, как правило Джонсона

(также обсуждается ниже), применяемое при планировании работ для некоторой

совокупности станков, для определения порядка выполнения работ использует

соответствующую вычислительную процедуру. Десять самых распространенных правил

формирования приоритетов перечислены во врезке, озаглавленной "Десять правил

формирования приоритетов для планирования последовательности работ".

Правильность установления приоритетов оценивается эффективностью

календарного плана, которая проявляется в следующем.

1. Соблюдение сроков, установленных заказчиками или определенных

последующими операциями.

2. Минимизация "продолжительности потока", т.е. времени, которое затрачивается

на выполнение работы в данном процессе.

3. Минимизация объемов незавершенного производства.

4. Минимизация простоев станков и рабочих.

Правила и методы формирования приоритетов

Планирование л работ на одним станке

Сравним в статике некоторые из 10 правил формирования приоритетов

календарного планирования в случае, когда на одном станке нужно выполнить четыре

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

работ на одном станке или просто "л/1".) Теоретически сложность задач планирования

возрастает при увеличении количества станков, а не при увеличении количества работ,

которые должны быть выполнены на этих станках; таким образом, единственным

ограничением на n в случае одного станка является только то, что п должно быть вполне

определенным, конечным числом. Рассмотрим следующий пример.

Пример 17.1. Задача n работ на одном станке

Майк Моралес — руководитель компании Legal Copy-Express, которая

предоставляет услуги по копированию печатных материалов для юридических контор,

расположенных в центре Лос-Анджелеса. В начале недели свои заказы разместили пять

клиентов. Запланированы следующие сроки выполнения этих заказов.

Десять правил формирования приоритетов для планирования последовательности

работ

1. FCFS (First-Come, First-Served) — первый вошел — первым обслужен. Работы

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

2. SOT (Shortest Operating Time) — по кратчайшему времени выполнения. Сначала

выполняется работа с самым коротким временем выполнения, затем среди оставшихся работ опять

отыскивается и выполняется работа с самым коротким временем выполнения и т.д.

3. Ddate (Due Date) — по установленным срокам окончания. Первой выполняется работа с

самым ранним сроком окончания. DDate — когда речь идет о всей работе; OPNDD — когда речь

идет о следующей операции.

4. SD (Start Date) — по ранней дате начала выполнения, определяемой как установленная

дата выполнения работы, минус время выполнения работы. Первой выполняется работа с самой

752

ранней датой начала выполнения.

5. STR (Slack Time Remaining) — по наименьшему остающемуся запасу времени. Этот запас

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

временем выполнения работы. Работы с самым коротким запасом времени выполняются первыми.

6. STR/OP (Slack Time Remaining per Operation) — по наименьшему оставшемуся запасу

времени на одну операцию. Заказы с самым коротким STR/OP выполняются первыми. STR/OP

вычисляется следующим образом:

7. CR (Critical Ratio) — по критическому отношению. Вычисляется как разность между

установленной датой выполнения и текущей датой, деленная на время выполнения работы.

Работы с наименьшим критическим отношением выполняются первыми.

8. QR (Queue Ratio) — по коэффициенту очередности. Вычисляется как время, остающееся

по графику, деленное на плановое время пребывания в очереди. Заказы с наименьшим

коэффициентом очередности выполняются первыми.

9. LCFS (Last-Come, First-Served) — последний вошел — первым обслужен. Это правило

часто применяется по умолчанию. При поступлении очередной работы она размещается на

вершине пирамиды. Плановик первой выбирает последнюю поступившую работу (с вершины) и

эта работа выполняется первой.

10. Random — в произвольном или случайном порядке. Руководители или плановики

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

момент времени.

Источник. Этот список (с некоторыми изменениями) заимствован из книи Donald W.

Fogarty, John H. Blackstone, Jr. and Thomas R. Hoffmann, Production and Inventory Management

(Cincinnati: South-Western Publishing, 1991), p. 452-453.

Работа (в порядке

поступления)

время выполнения (дни)

Дата, до которой должен быть

выполнен заказ

А 3 5

В 4 6

С 2 7

D 6 9

Е 1 2

Все заказы требуют использования устройства цветного копирования, оно есть в

компании в единственном экземпляре. М-р Моралес должен принять решение о

последовательности выполнения указанных пяти заказов. Критерием оценки является

минимальная продолжительность потока (Flow Time). Допустим, что м-р Моралес,

пытаясь проявить справедливость по отношению ко всем своим клиентам, решил

воспользоваться правилом FCFS.

Решение 1. Правило FCFS

Правило FCFS дает следующие результаты (см. таблицу ниже).

Сравнивая установленные даты завершения каждой работы с соответствующей

продолжительностью потока, обнаруживаем, что только работа А будет завершена

вовремя. Работы В, С, D и Е будут просрочены на 1, 2, 6 и 14 дней соответственно. В

среднем любая из работ будет просрочена на (0 + 1 + 2 + 6 + 14)/5 = 4,6 дней.

753

Календарный план, составленный по правилу FCFS

Последовательность

работ

Время

обработки

(дни)

Дата, к которой должен быть

выполнен заказ (дни с начала

периода планирования)

Продолжительность

потока (дни)

А 3 5 0 + 3 = 3

В 4 6 3 + 4 = 7

С 2 7 7 + 2 = 9

D 6 9 9 + 6= 15

Е 1 2 15 + 1 = 16

Общая продолжительность потока = 3 + 7 + 9+15 + 16 = 50 дней

Средняя продолжительность одной работы в потоке = 50/5 = 10 дней

Решение 2. Правило SOT

Рассмотрим применение правила SOT. В нашем случае м-р Моралес присваивает

наивысший приоритет заказу с самым коротким временем выполнения.

Правило SOT дает следующие результаты.

Календарный план, составленный по правилу SOT

Последовательность

работ

Время

обработки

(дни)

Дата, до которой должен быть

выполнен заказ (дни с начала

периода планирования)

Продолжительность

потока (дни)

Е 1 2 0+1 = 1

С 2 7 1+2 = 3

А 3 5 3 + 3 = 6

В 4 6 6 + 4 = 10

D 6 9 10 + 6= 16

Общая продолжительность потока =1+3 + 6 + 10 + 16 = 36 дней

Средняя продолжительность одной работы в потоке = 36/5 = 7,2 дней

Применение правила SOT позволяет сократить среднюю продолжительность одной

работы в потоке в сравнении с результатами использования правила FCFS. Кроме того,

работы £ и С будут завершены раньше обусловленного срока, а завершение работы А

запоздает только на один день. В среднем любая из работ будет просрочена на (0 + 0 + 1 +

4 + 7)/5 = 2,4 дня.

Решение 3. Правило DDATE

Если м-р Моралес решит воспользоваться правилом DDATE, календарный план

примет следующий вид.

Календарный план, составленный по правилу DDATE

Последовательность

работ

Время

обработки

(дни)

Дата, до которой должен быть

выполнен заказ (дни с начала

периода планирования)

Продолжительность

потока (дни)

754

Е 1 2 0 + 1 = 1

А 3 5 1 +3 = 4

В 4 6 4 + 4 = 8

С 2 7 8 + 2 = 10

D 6 9 10 + 6 = 16

Общая продолжительность потока =1+4 + 8 + 10+16 = 39 дней

Средняя продолжительность одной работы в потоке = 39/5 = 7,8 дней

В этом случае будут просрочены работы В, С и D. В среднем любая из работ будет

просрочена на (0 + 0 + 2 + 3 + 7)/5 = 2,4 дня.

Решение 4. Правила LCFS, RANDOM и STR

Ниже указаны результирующие продолжительности потока в случае применения

правил LCFS, RANDOM (произвольный порядок) и STR.

Последовательность

работ

Время Д обработ- ж

ки (дни) Ki

ата, до которой долен

быть выполнен за->з (дни с

начала пе-юда

планирования)

Продолжительность

потока (дни)

Правило LCFS

Е 1 2 0 + 1=1

D 6 9 1+6 = 7

С 2 7 7 + 2 = 9

В 4 6 9 + 4 = 13

А 3 5 13 + 3=16

Общая продолжительность потока = 46 дней

Средняя продолжительность одной работы в потоке = 9,2 дней

Среднее запаздывание = 4,0 дня

Правило Random (произвольный выбор)

D 6 9 0 + 6 = 6

С 2 7 6 + 2 = 8

А 3 5 8 + 3 = 11

Е 1 2 11 + 1 =12

В 4 6 12 + 4=16

Общая продолжительность потока = 53 дня

Средняя продолжительность одной работы в потоке = 10,6 дней

Среднее запаздывание = 5,4 дней

Правило STR

Е 1 2 0+1 = 1

А 3 5 1 +3 = 4

В 4 6 4 + 4 = 8

D 6 9 8 + 6= 14

С 2 7 14 + 2 = 16

Общая продолжительность потока = 43 дня

Средняя продолжительность одной работы в потоке = 8,6 дней

Среднее запаздывание = 3,2 дня

755

Сравнение правил формирования приоритетов

Ниже приведены результаты сравнения различных правил формирования

приоритетов применительно к компании м-ра Моралеса.

Правило

Общая

продолжительность

потока (дни)

Средняя

продолжительность

одной работы в потоке

(дни)

Среднее запаздывание

(дни)

FCFS 50 10 4,6

SOT 36 7,2 2,4

DDate 39 7,8 2,4

LCFS 46 9,2 4,0

Random 53 10,6 5,4

STR 43 8,6 3,2

Очевидно, что в данном случае применение правила SOT более выгодно по

сравнению со всеми остальными правилами. Но всегда ли соблюдается эта

закономерность? На этот вопрос можно ответить положительно. Более того, существует

математически строгое доказательство того, что правило SOT обеспечивает оптимальное

решение для случая л/1 и по таким критериям оценки, как среднее время ожидания и

среднее время завершения. В сущности, это простое правило столь эффективно, что его

называют "важнейшей концепцией задачи определения последовательности работ в

целом"

R.W. Conway, William L. Maxwell and Louis W. Miller, Theory of Scheduling (Reading. MA: Addison-Wesley,

1967), p. 26. Классическая книга по данному вопросу.

Планирование n работ на двух станках

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

является задача я/2, когда две или большее количество работ нужно выполнить на двух

станках в определенной последовательности. Как и в случае л/1, здесь также существует

метод, который приводит к оптимальному решению в соответствии с определенными

критериями. Метод, который в честь его разработчика называется правилом Джонсона

(Johnson's rule), состоит в минимизации продолжительности потока — с момента начала

первой работы до момента завершения последней работы. Правило Джонсона

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

1. Составить список затрат операционного времени для каждого задания на обоих

станках.

2. Выбрать самое короткое операционное время.

3. Если это время отвечает первому станку, запланировать выполнение задания

первым на первом станке; если же оно отвечает второму станку, запланировать его

выполнение последним.

4. Повторять пп. 2 и 3 для каждой оставшейся работы до тех пор, пока не будет

полностью составлен календарный план.

Пример 17.2. Задача n работ на двух станках

Эту процедуру можно проиллюстрировать, составив календарный план выполнения

756

четырех работ на двух станках.

Решение

Этап 1. Составить список затрат операционного времени для каждого задания на

обоих станках.

Работа Операционное время на станке 1 Операционное время на станке 2

А 3

В 6 8

С 5 6

D 7 4

Этапы 2 и 3. Выбрать самое короткое операционное время. Работа А является самой

короткой на станке 2, поэтому ее выполнение планируется последним. (После этого

работа А не участвует в дальнейшем рассмотрении.)

Этап 4. Повторять этапы 2 и 3, пока не будет полностью определена

последовательность работ и составлен календарный план. Выберем кратчайшее

операционное время среди оставшихся работ. Самое короткое операционное время

оказывается у работы D на станке 2, поэтому она выполняется "второй с конца".

(Напоминаем, что "первой с конца" является работа А.) Теперь уже не подлежат

планированию работы А и D. Среди оставшихся самое короткое операционное время

оказывается у работы С на станке 1. Работа С выполняется первой. Теперь у нас остается

только работа б, у которой автоматически оказывается самое короткое операционное

время на станке 1. Таким образом, в соответствии с этапом 3, она выполняется второй с

начала. (В первую очередь по плану уже должна выполняться работа С.)

Итак, мы пришли к следующей последовательности выполнения работ: С—>В—

>D—>A, а время потока составляет 25 дней, что является минимумом. Кроме того, мы

минимизировали общее время простоя и среднее время простоя. Окончательный вариант

календарного плана представлен на рис. 17.2.

Результат выполнения указанных этапов планирования: работы, имеющие самое

короткое операционное время, оказываются в начале и конце графика. Таким образом, мы

максимизируем время параллельной работы двух станков, минимизируя при этом общее

операционное время, которое требуется для выполнения указанных работ.

Метод получения оптимальных решений Джонсона удается распространить на

случай я/3. Если же возникает потребность решить подобные задачи для случаев более

сложных, чем л/3, что чаще всего и происходит на практике, аналитическими методами

поиска оптимальных ре шении воспользоваться невозможно — их попросту не

существует. Причина этого заключается в том, что, даже если на первый станок работы

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

превращается в динамическую, и перед станками в потоке начинают образовываться

очереди.

757

Рис. 17.2. Оптимальный план работ, составленный по правилу Джонсона

Планирование определенного количества работ на таком же количестве

станков

В цехе возможны ситуации, когда есть необходимое количество станков разных

типов, но способных выполнять одинаковые работы при разной стоимости обработки и

нужно выполнить разные работы одновременно на этих станках. В этом случае задача

заключается не в том, чтобы выяснить, какую работу выполнять первой, а в том, как

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

оптимальным. В таком случае нужно воспользоваться методом назначений.

Метод назначений (Assignment Method) представляет собой особый случай

транспортного метода (Transportation Method), используемого в линейном

программировании. Его можно применять к ситуациям, где имеется п источников

поставки и п потребителей (например, пять работ на пяти станках), а цель заключается в

минимизации или максимизации той или иной меры эффективности. Этим методом

удобно пользоваться в приложениях, связанных с распределением работ по рабочим

центрам, людей — по работам и т.п. Метод назначений подходит для решения задач,

имеющих следующие характеристики.

1. Имеется п "предметов", которые требуется распределить по п "получателям".

2. Каждый предмет должен быть назначен одному, и только одному, получателю.

3. Может использоваться только один критерий (например, минимальные затраты,

максимальная прибыль или минимальное время выполнения).

Пример 17.3. Метод назначений

Допустим, что у составителя календарного плана есть пять работ, которые можно

выполнять на любом из пяти станков (п = 5). Затраты на выполнение каждого сочетания

"работа-станок" представлены в табл. 17.2. Составитель календарного плана желает

провести назначение с использованием критерия минимальных затрат. В этом случае

существует 5! = 120 возможных вариантов назначений.

Решение

Эту задачу можно решить с помощью метода назначений, который состоит из

четырех этапов.

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

этой строке. (Таким образом, в каждой строке появится по крайней мере по одному нулю.)

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

других чисел в этом столбце. (Таким образом, в каждом столбце появится по крайней мере

по одному нулю.)

Определить, равно ли числу n минимальное количество горизонтальных и

вертикальных линий, необходимых для перечеркивания всех нулей в матрице. Если равно,

значит нам уже удалось найти оптимальное решение, поскольку назначения "работа-

станок" должны осуществляться по полученным нулевым элементам. Если минимальное

количество линий, необходимых для перечеркивания всех нулей, меньше n, перейти к п. 4.

Провести наименьшее возможное число линий через все нули. (Эти линии могут

быть теми же, которые использовались в п. 3.) Вычесть наименьшее из неперечеркнутых

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

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

Перечисленные этапы отражены в табл. 17.3, которая описывает рассматриваемый

нами пример.

758

Таблица 17.2. Матрица назначений, отображающая затраты в долларах на станочное выполнение

каждой из пяти работ

Станок

Работа А В С D Е

I 5 6 4 8 3

II 6 4 9 8 5

III 4 3 2 5 4

IV 7 2 4 5 3

V 3 6 4 5 5

Обратите внимание, что, несмотря на наличие двух нулей в трех строках и трех

столбцах решение, представленное в табл. 17.3, для этой задачи единственное возможное

решение, поскольку, чтобы удовлетворить требованию "назначать один раз по нулю",

работу III можно назначить только на станок С. У других задач может быть несколько

оптимальных решений (это зависит, разумеется, от соответствующих затрат).

Таблица 17.3. Процедура решения матрицы назначений

Этап 1. Сокращение строк — из каждой строки в наименьшее число в строке.

вычитается

Станок

Работа А В С D Е

I 2 3 1 5 0

II 2 0 5 4 1

III 2 1 0 3 2

IV 5 0 2 3 1

V 0 3 1 2 2

Этап 3. Перечеркнуть минимальным числом линий все нули и проверить с помощью

подсчета линий. Здесь минимальное количество линий, перечеркивающее все нули, равно

4, а необходимо 5 — по числу столбцов или строк, т.е. необходимое для получения

оптимального решения условие не выполняется, и поэтому переходим к п. 4.

Станок

Работа А В С D Е

I 2 3 1 3 0

II 2 0 5 2 1

III 2 1 0 1 2

IV 5 0 2 1 1

V 0 3 1 0 2

Снова проверяем решение перечеркиванием линиями и получаем, что их

минимально необходимое число равно 5, т.е. это оптимальное решение.

759

Станок

Работа А В С D Е

I 1 3 0 2 0

II 1 0 4 1 1

III 2 2 0 1 3

IV 4 0 1 0 1

V 0 4 1 0 3

Этап 2. Сокращение столбцов — из каждого столбца вычитается наименьшее число в

столбце.

Станок

Работа А В С D Е

I 2 3 4 3 0

II 2 0 5 2 1

III 2 1 0 1 2

IV 5 0 2 1 1

V 0 3 1 0 2

Этап 4. Вычесть наименьшее число из неперечеркнутых чисел и прибавить его к

числам на пересечении линий, проведенных в п. 3. Наименьшее число из

неперечеркнутых равняется 1.

Станок

Работа А В С D Е

I 1 3 0 2 0

II 1 0 4 1 1

III 2 2 0 1 3

IV 4 0 1 0 1

V 0 4 1 0 3

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

Работа I — на станок Е 3

Работа II — на станок В 4

Работа III — на станок С 2

Работа IV — на станок D 5

Работа V — на станок А 3

Общие затраты $17

Основой метода назначений нематематического характера является необходимость

минимизации издержек неиспользованных возможностей (Opportunity Costs)

. Если бы,

например, мы решили назначить работу I не на ста-нвк Е, а на станок А, нам пришлось бы

пожертвовать возможностью сэкономить $2 = ($5 — $3). Алгоритм назначения, в

сущности, выполняет подобные сравнения для всей совокупности альтернативных

назначений, сокращая строки и столбцы, как описано в пп. 1 и 2. Аналогичные сравнения

он выполняет и в п. 4.

760

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

заключается в следующем. Дополнительные нули вводятся в матрицу путем вычитания изо всех ячеек

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

появляться в этой матрице. Чтобы избавиться от отрицательных чисел, величину, равную наибольшему

отрицательному числу, нужно прибавить к каждому элементу строки или столбца, в котором он встречается.

Это приводит ко вторичному добавлению этой величины к каждой ячейке, которая лежит на пересечении

строки и столбца и в которые уже были внесены изменения. В итоге строки и столбцы, через которые

проходят линии, возвращаются к своим исходным значениям, а на пересечениях линий — возрастают на

величину, которая вычтена из незачеркнутых ячеек. (Читатель может проверить справедливость этих

рассуждений, решив данный пример без использования линий.)

Интерактивное календарное планирование с помощью системы JOB

В системе JOB, разработанной Дж. Праетом и А. Шартнером (J.M. Pruett and A. Schartner),

используется модель, которая обеспечивает возможность вмешательства человека в процесс

составления календарного плана работы и балансирования загрузки обрабатывающих центров. В

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

интерактивный и полуинтерактивный.

При использовании последовательного режима компьютер автоматически планирует

рабочие заказы (Work Orders) в соответствии с тем или иным правилом формирования

приоритетов (например, на основе самой ранней установленной даты выполнения заказа),

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

человек-плановик планирует рабочие заказы последовательно, один за другим. С помощью

системы JOB плановик разрабатывает в интерактивном режиме календарный план; при этом

плановик одновременно учитывает как необходимость планирования рабочих заказов, так и

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

сочетание интерактивного и последовательного режимов.

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

подхода, но с учетом заранее установленных пороговых значений загрузки группы оборудования

(обычно они устанавливаются на уровне 100%). В случае превышения порогового значения

загрузки группы оборудования алгоритм останавливает процесс планирования и ожидает

вмешательства человека (интерактивный режим) для устранения чрезмерной загрузки

оборудования. Как только проблема с загрузкой оборудования для данного рабочего заказа

разрешена, алгоритм (последовательный режим) получает разрешение возобновить процесс

планирования.

Такой интерактивный процесс предусматривает использование календарных планов,

которые — в виде столбиковых диаграмм — строит и отображает на своем экране компьютер.

Управление системой JOB осуществляется с помощью различных меню. Эта система позволяет

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

среднее время цикла, перегруженные и недогруженные группы оборудования, а также рабочие

заказы с запаздыванием и опережением установленных сроков.

Источник. James M. Pruett and Andreas Schartner, "JOB: An Instructive Job Shop Scheduling

Environment", International Journal of Operations & Production Management, November 1993, p. 4-34.

Планирование выполнения n работ на m станках

Сложные производства характеризуются наличием многих обрабатывающих

центров, выполняющих множество различных работ, периодически поступающих на эти

обрабатывающие центры на протяжении всего рабочего дня. Если на т станках требуется

выполнить п работ, причем все работы последовательно выполняются на всех станках, то

для этой совокупности работ существует (п!)

разных графиков работы. Из-за огромного

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

производств, компьютерное моделирование (см. Дополнение к этой главе) в подобных

ситуациях является единственным реальным способом определить относительные

достоинства различных правил формирования приоритетов. Как и в случае п работ на

одном станке, было проведено сравнение эффективности 10 (и больше) правил