Методы построения расписаний работ в производственных системах

 

Московский государственный технический университет  
имени Н.Э. Баумана 

МЕТОДЫ ПОСТРОЕНИЯ  
РАСПИСАНИЙ РАБОТ  
В ПРОИЗВОДСТВЕННЫХ  
СИСТЕМАХ 
 
 
Методические указания к лабораторной работе 
по курсу «Организационно-технологическое управление» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

М о с к в а  

Издательство МГТУ им. Н.Э. Баумана 

2 0 0 9  

 

УДК 331.015.13 
ББК 30.606 
М54 
Ре це нзе нт М.В. Овсянников 

 
 
М54  
      Методы построения расписаний работ в производственных системах : метод. указания к лабораторной работе по курсу «Организационно-технологическое управление» / М.С. Куняев, А.М. Сидоренко, А.С. Фирсов, Е.Н. Хоботов. — М.: Издво МГТУ им. Н.Э. Баумана, 2009. — 29, [3] с. 
 
Рассмотрены этапы и порядок выполнения лабораторной работы 
по изучению методов построения расписания работ в производственных системах дискретного типа. Приведены инструкции для работы  
с программным обеспечением, используемым в лабораторной работе.  
Для студентов 5-го курса, специализирующихся по кафедре РК-9 
и изучающих курс «Организационно-технологическое управление». 
 
УДК 331.015.13 
ББК 30.606 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

© Куняев М.С., Сидоренко А.М., 
Фирсов А.С., Хоботов Е.Н., 2009 
© МГТУ им. Н.Э. Баумана, 2009 

М54 

ВВЕДЕНИЕ 

Задачи теории расписаний (или задачи упорядочения) [1 – 3] 
возникают во многих сферах деятельности человека там, где существует возможность выбора той или иной последовательности выполнения работ или заданий. Такие задачи приобретают исключительно важное значение при планировании работ и различных 
видов деятельности на промышленных предприятиях как с непрерывным, так и с дискретным характером производства, при составлении расписаний отправления и прибытия поездов и самолетов и т. д.   
В реальных условиях задачи упорядочения так или иначе решаются, поскольку промышленные предприятия работали и до 
появления теории расписаний и работают сейчас, поезда отправляются и прибывают, а самолеты взлетают и приземляются. Однако, как показывает опыт работы многих систем и особенно производственных систем в машиностроении, правильно построенное 
расписание обработки деталей или заданий во многих случаях позволяет получать значительное сокращение сроков выполнения 
работ при сокращении простоев оборудования и тем самым повышать производительность соответствующих систем.  
Существует большое число различных постановок задач построения расписания, часть из которых будет изучаться в рамках 
данной лабораторной работы.  
Цель работы — ознакомиться с основными методами построения расписания работ.  

ЗАДАЧА ДЖОНСОНА 

Задача Джонсона формулируется следующим образом [1].  
Пусть имеется два станка, на которых требуется обработать L 
деталей. Каждая деталь обрабатывается сначала на первом станке, 
а потом — на втором. Известно время обработки каждой детали на 
каждом станке. Имеются также ограничения, которые состоят в 
следующем. 
1. На одном станке одновременно не может обрабатываться 
больше одной детали.  
2. Одна деталь одновременно не может обрабатываться на нескольких станках, причем обработка любой детали на первом 
станке должна завершиться раньше, чем начнется ее обработка на 
втором станке.  
В задаче требуется определить порядок запуска деталей на обработку, чтобы общее время обработки всех L деталей оказалось 
минимальным.  
Большая заслуга Джонсона была не только в том, что он обратил внимание на разную длительность обработки деталей на станках в зависимости от последовательности их обработки, но и в 
том, что он предложил алгоритм построения оптимального по 
времени расписания обработки деталей на двух станках при указанных выше предположениях.  
Задача Джонсона оказалась одной из двух задач в теории расписаний, для которых может быть построен алгоритм формирования оптимальных расписаний. К сожалению, для других задач, 
особенно для задач, имеющих прикладное значение, таких алгоритмов пока построить не удается.  
Задача Джонсона относится к конвейерным задачам — все детали обрабатываются на станках в одной и той же последовательности. 

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

 
1
1
min(
,
)
min(
,
),
i
i
i
i
A B
A
B
+
+
≤
 

где Аi — время выполнения работы i на первой машине; Bi — время 
выполнения работы i на второй машине. 
Для представления, анализа и выбора последовательности работ обычно используют специальные диаграммы, предложенные в 
1912 г. Г. Ганттом и называемые его именем.  
Рассмотрим принципы построения таких диаграмм на примере 
построения расписания конвейерной обработки трех деталей на 
двух станках.  
Пусть обработка первой детали на первом станке занимает  
30 мин, время ее обработки на втором станке — 5 мин, время обработки второй детали на первом станке 10 мин, а на втором —  
15 мин. Кроме того, пусть обработка третьей детали на первом 
станке занимает 5 мин, а на втором станке — 30 мин.  
Исходная информация для этой задачи может быть записана в 
виде таблицы (табл. 1).  

Таблица 1 

Время обработки, мин 

Деталь 
на первом станке 
на втором станке 

Первая  
30 
5 

Вторая  
10 
15 

Третья  
5 
30 

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

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

 
 
Рис. 1. Диаграмма Гантта для задачи Джонсона 
 
В приведенной на рис. 1 диаграмме Гантта была выбрана последовательность обработки деталей в соответствии с табл. 1. Однако существуют и другие последовательности обработки деталей. 
Например, детали можно обрабатывать в следующем порядке: сначала вторую деталь, затем третью и потом первую.  
Рассмотрим случай, когда детали обрабатываются в одной последовательности на первом и втором станках. Диаграмма Гантта 
для такой последовательности обработки деталей будет иметь вид, 
представленный на рис. 2.  
 

 
 
Рис. 2. Диаграмма Гантта для другой последова- 
тельности обработки деталей в задаче Джонсона 
 
Из рис. 2 ясно, что общее время обработки деталей сократилось с 85 до 60 мин. Таким образом, из данного примера очевидно, 
что изменение последовательности обработки деталей может при
t, мин 

t, мин 

t, мин 

t, мин

водить к весьма заметному изменению времени обработки деталей 
благодаря сокращению времени простоев оборудования. 
Рассмотрим еще одну последовательность обработки деталей,  
когда сначала обрабатывается третья деталь, затем — вторая и, 
наконец, — первая. Эта последовательность определена по теореме Джонсона и является оптимальной. Пусть в том же порядке детали обрабатываются и на втором станке. Диаграмма Гантта будет 
иметь вид, представленный на рис. 3.  
 

 
 
Рис. 3. Диаграмма Гантта для оптимальной последова- 
тельности обработки деталей в задаче Джонсона 
 
На рис. 3 видно, что общее время обработки деталей еще более 
сократилось и составляет 55 мин.  
Таким образом, рассмотренные выше примеры демонстрируют 
возможности методов теории расписаний значительно сокращать 
время обработки деталей или выполнения заданий в результате 
сокращения времени простоев оборудования без вложения дополнительных средств на замену оборудования более производительным или на изменение технологии изготовления.  
Важной характеристикой построенного расписания является 
коэффициент загрузки оборудования.  
Коэффициент загрузки оборудования равен отношению времени обработки деталей на этом оборудовании ко всему времени 
использования оборудования, т. е. от начала обработки на производственном участке первой детали до завершения обработки на 
этом оборудовании последней детали. Коэффициент загрузки вычисляют для каждой единицы оборудования отдельно, его значение всегда меньше единицы.  
Оптимальный порядок обработки деталей в задаче Джонсона 
может также формироваться на основе алгоритма, предложенного 
Беллманом.  

t, мин 

t, мин 

Приведем его описание. 
Разобьем все множество деталей на два подмножества J1 и J2, 
которые определяются следующим образом:  

 
1
1
2
{ |
},
i
i
J
i t
t
=
>
    
2
1
2
{ |
}
i
i
J
i t
t
=
≤
,  

где t1i — время обработки i-й детали на первом станке; t2i — время 
обработки i-й детали на втором станке. 
Сначала на обработку запускаются детали из подмножества J2, 
а затем — из подмножества J1. 
Внутри множества J2 детали упорядочиваются по возрастанию 
времени обработки на первом станке, т. е. чем меньше время обработки детали на первом станке, тем раньше деталь запускается на 
обработку. Если время обработки на первом станке оказалось одним и тем же для нескольких деталей, то первой запускается на 
обработку та деталь, у которой время обработки на втором станке 
больше. 
Внутри множества J1 детали упорядочиваются по убыванию 
времени обработки на втором станке, т. е. чем больше время обработки детали на втором станке, тем раньше деталь запускается на 
обработку. Если время обработки на втором станке оказалось одним и тем же для нескольких деталей, то первой из них запускается на обработку та деталь, у которой время обработки на первом 
станке меньше. 
Установленная таким образом последовательность запуска оказывается оптимальной в том смысле, что обеспечивает наименьшее время обработки всех  деталей. 
Еще одной задачей, для решения которой может быть построен 
оптимальный алгоритм, является задача определения расписаний 
двух машин при условии, что каждая работа состоит максимум из 
двух операций. Джексон показал [1], что эта задача есть обобщение задачи Джонсона и что для ее решения требуется лишь небольшая модификация алгоритма Джонсона. Это значит, что задача 
с 
произвольным 
числом 
работ 
требует 
сравнительно 
небольшого объема вычислений. 
Решение начинается с разбиения числа работ п на четыре подмножества следующим образом: 
{А} — подмножество работ, состоящих из единственной операции, выполняемой на машине 1; 

{В} — подмножество работ, состоящих из единственной операции, выполняемой  на машине 2; 
{АВ} — подмножество работ, состоящих из двух операций, из 
которых первая выполняется машиной 1, а вторая — машиной 2; 
{ВА} — подмножество работ, состоящих из двух операций, из 
которых первая выполняется машиной 2, а вторая — машиной 1. 
После этого работы из подмножества {АВ} упорядочиваются в 
соответствии с алгоритмом Джонсона независимо от остальных 
работ, и то же проделывается с работами из подмножества{ВА}. 
Упорядочение работ из подмножеств {А} и {В} не влияет на максимальную длительность выполнения всех работ и может быть 
произвольным. Джексон показал, что оптимальным является следующий порядок выполнения работ: 
а) машина 1 выполняет работы из {АВ}, затем из {А}, затем из 
{ВА}; 
б) машина 2 выполняет работы из {ВА}, затем из {В}, затем из 
{АВ}, причем порядок выполнения работ внутри каждого из подмножеств сохраняется. 
Легко увидеть, что такое расписание оптимально. Действительно, поскольку длительности выполнения операций фиксированы, то 
качество расписания фактически определяется длиной свободных 
интервалов (длительностей простоя) между выполнением отдельных операций. Если подмножество {ВА} пусто, то очевидно, что 
для работ из подмножеств {А}, {В} и {АВ} расписание является оптимальным и при этом длительность простоя машины 2 минимальна. Рассмотрим теперь работы из подмножества {ВА}. Они могут 
быть выполнены на машине 2 без простоев между операциями, выполнение же их на машине 2 прежде остальных работ  приведет к 
возможной задержке выполнения работ из подмножества {АВ} на 
этой машине. Последнее обстоятельство может лишь уменьшить 
простои между выполнением операций работ подмножества {АВ} 
на машине 2. Очевидно, что нет смысла рассматривать расписания, 
в которых работы из подмножества {АВ} выполняются машиной 2 
до окончания всех работ из подмножеств {ВА} и {В}. Действительно, допустим, что мы попытаемся выполнить работу K из подмножества {ВА} на машине 2 во время простоя Xj последней между выполнением работ I и J из подмножества {АВ}. Даже в том случае, 
если значение Xj больше, чем длительность выполнения работы K, 

эту работу можно выполнить до работы I, так как в худшем случае 
выполнение работы I будет задержано, время простоя Xj уменьшится, но момент начала выполнения работы J останется прежним и, 
следовательно, не изменится максимальная длительность прохождения. Аналогичные рассуждения устанавливают оптимальность 
упорядочения работ для машины 1.  

ИСПОЛЬЗОВАНИЕ ПРИОРИТЕТНЫХ ПРАВИЛ  
ДЛЯ ПОСТРОЕНИЯ РАСПИСАНИЙ 

Наиболее эффективными для решения задач теории расписаний являются методы искусственного интеллекта. Применение 
этих методов основано на использовании приоритетных (или решающих) правил, которые весьма похожи на продукционные правила. Использование таких правил для решения задач теории расписаний можно пояснить с помощью схемы, представленной на 
рис. 4. Приоритетными правилами при такой схеме построения 
расписания обработки определяется порядок запуска деталей на 
обработку.  
Следует отметить, что для решения одних задач с использованием приоритетных правил определяется порядок запуска деталей 
на обработку для всей производственной системы, а для решения 
других задач — порядок запуска деталей на конкретный станок. 
Все зависит от поставленной задачи и выбранной стратегии ее решения.  
Приоритетные правила условно можно разделить на два класса — 
простые и сложные.  
К простым приоритетным правилам относят правила с одним 
предусловием. Предусловия простых правил нельзя представить в 
виде совокупности нескольких предусловий.  
Комбинированные приоритетные правила имеют предусловия, 
которые представляют собой комбинацию простых предусловий. 
Обычно комбинированные приоритетные правила применяют в 
том случае, когда невозможен однозначный выбор по простому 
правилу или когда необходимо расширить число учитываемых параметров и характеристик обработки.