Общее описание систем, имеющих сетевое представление технологических процессов и ограниченные ресурсы (стр. 1 )

Часть 2
Иерархическое планирование и принятие решений в сетевых системах

Глава 8  Трехуровневая модель планирования и принятия решений

8.1  Общее описание систем, имеющих сетевое представление технологических процессов и ограниченные ресурсы

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

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

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

Широко распространены производственные системы с сетевым представлением технологических процессов и ограниченными ресурсами: их удельный вес составляет до 80 % всех типов производств не только в Украине, но и во всем мире. К таким производствам, в частности, относятся:

–  производства дискретного типа;

–  производства «под заказ»;

–  рабочий цех;

–  производства по изготовлению партий;

–  строительные производства;

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

Производства с сетевым представлением технологических процессов и ограниченными ресурсами – это сложные виды производств, приближающиеся по сложности к гибким производствам [10, 34, 64]. Для большинства из них характерны следующие общие особенности [34, 56]:

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

–  сетевое представление технологического процесса, т. е. наличие отношений предшествования операций;

–  количество наименований деталей и их трудоемкость изменяются на протяжении достаточно коротких интервалов времени;

–  широкое многообразие оборудования для выполнения операций;

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

–  существенная разница в технологических маршрутах разных изделий;

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

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

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

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

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

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

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

Все эти особенности значительно усложняют процесс планирования и управления в современных условиях. Кроме того, в последние годы практически во всех областях промышленности отечественные предприятия встретились со следующими тенденциями [56]:

–  резкое увеличение номенклатуры и модификаций выпускаемой продукции;

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

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

–  насыщение рыночного спроса и, как следствие, снижение нормы прибыли и балансирование на уровне минимальной рентабельности;

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

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

Эти тенденции приводят к кризису управления и уже не позволяют эффективно планировать и управлять старыми «ручными» методами. Требование рынка «вырабатывать только то, что нужно, тогда, когда нужно, и столько, сколько нужно» [30] служит причиной необходимости более эффективного планирования и управления производством.

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

Основным средством преодоления кризиса является применение современных информационных технологий планирования и управления. К таким системам предъявляются следующие основные требования.

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

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

2. Иерархичность планирования. Система должна решать задачу планирования в комплексе, т. е. иметь в своем составе средства предварительного (стратегического), согласованного (тактического) и точного (операционного) планирования. Это подразумевает иерархичность модели планирования и реализацию взаимосвязи решений (решения нижнего уровня иерархии должны быть согласованы с решениями более высоких уровней с помощью обратной связи). В иерархическом подходе к планированию производства и управления детальная монолитная формулировка задачи, требующая интегрированного решения для всех уровней управления одновременно, заменяется последовательностью моделей, совместимых с иерархией решений, которые должны быть приняты [37].

3. Агрегация и дезагрегация как реализация иерархического планирования, т. е. обеспечение возможности работы с данными реальных размеров посредством укрупнения и последующего разукрупнения. Дискретные организационно-производственные системы, такие как мелкосерийное производство, являются сложными системами управления, трудно поддающимися автоматизации из-за огромных размерностей решаемых задач. Реальные производственные конструкторские массивы часто достигают размерности в сотни тысяч детале-операций, связанных между собой технологическими связями. Невозможно осуществить решение какой-либо оптимизационной задачи на графах такой размерности. Поэтому в состав системы необходимо включить процедуры агрегации и дезагрегации. Сначала принимаются агрегированные (стратегические и тактические) решения, они налагают ограничения, в пределах которых принимаются более детальные (эксплуатационные, операционные) решения. В свою очередь, детальные решения обеспечивают обратную связь для оценки качества агрегированных решений. Решения на более высоких уровнях иерархии базируются на агрегированной информации. Успех иерархического подхода в большой степени зависит от устойчивости между процедурами агрегации и дезагрегации и от взаимодействия между моделями на различных уровнях. Требования к агрегации/дезагрегации таковы:

–  должны учитываться основные временны'е ограничения (например, директивные сроки и отношения предшествования), ограничения на ресурсы;

–  процедура агрегации должна быть допустимой (дезагрегация должна давать исходную информацию);

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

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

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

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

Основные критерии планирования в условиях рынка следующие:

–  выполнение заказов точно в срок;

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

–  минимизация суммарного взвешенного момента выполнения заданий;

–  минимизация суммарного штрафа как за опережение, так и за запаздывание заданий относительно директивных сроков;

–  минимизация длины расписания (момента окончания выполнения последнего задания).

5. Модульность алгоритмического обеспечения – выделение общих алгоритмических блоков базовых алгоритмов для решения различных задач и их комби­ни­рование на основе очевидного конструктивного анализа для эффективного системного проектирования алгоритмов.

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

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

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

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

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

Иерархическое планирование [91, 92, 93, 94, 135] представляет философию для решения комплексных задач и является общим для широкого разнообразия систем с помощью соответствующего выбора схем и методов агрегации и дезагрегации. Иерархический подход к планированию обеспечивает эффективное выполнение функции управления на каждом уровне организационной структуры.

Рассмотрим некоторые ключевые проблемы, решаемые при разработке и реализации моделей оптимизации для производственного планирования [131]. Любая задача планирования начинается с определения требований заказчика, которые должны быть удовлетворены планом производства. В большинстве случаев будущие требования наилучшим образом известны только частично, а часто неизвестны вообще. С учетом того, что любой прогноз неизбежно неточен, нужно решить, как учесть эту неопределенность.

Ключевой выбор – какие решения по планированию следует включить в модель. По определению, модели производственного планирования, направленные на снижение стоимости производства, включают решения относительно количества производственных запасов и незавершенного производства. Но кроме того, может приниматься решение о приобретении и распределении ресурсов, например, пополнении рабочей силы и модернизации обучения текущей рабочей силы. Нужно сделать выбор относительно того, какие ресурсы следует включить в модель и как моделировать их применение. Можно включить только самый критичный или ограничивающий ресурс, например, узкое место. В другом случае, когда нет доминирующего ресурса, нужно моделировать ресурсы, которые могут ограничить производство.

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

Важное значение имеет выбор периода времени и горизонта планирования. В литературе различают понятия периодов времени «большой сегмент» и «ма­лый се­г­мент». Период времени – большой сегмент, если обычно в пределах этого периода вырабатывается множество изделий; в малом сегменте вырабатывается не более одного изделия. Для моделей больших сегментов необходимо решать задачу составления расписаний – определения последовательности запусков производства, назначенных на какой-либо период времени.

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

Для решения задач производственного планирования обычно используют объемные методы и методы календарного планирования. В качестве примера объемных методов планирования приведем модель оптимизации для производственного планирования, если имеются [131]:

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

–  множество разделенных (распределенных между всеми изделиями) ресурсов;

–  периоды времени большого сегмента;

–  линейные затраты.

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

Переменные решения: pit – производство элемента (изделия) i на протяжении периода времени t; qit – запасы элемента i в конце периода времени t.

Параметры: T, I, K – число периодов времени, элементов, ресурсов, соответственно; aik – количество ресурса k, необходимое на единицу производства элемента i; bkt – количество ресурса k, доступное в периоде t; dit – требование для элемента i в периоде t; cpit – переменная удельная стоимость производства элемента i в периоде времени t; cqit – удельная стоимость сохранения запасов элемента i в периоде времени t.

Теперь сформулируем линейную модель P1

(8.1)

при ограничениях:

; (8.2)
; (8.3)
.

Целевая функция (8.1) минимизирует переменные затраты производства плюс затраты на сохранение запасов по всем изделиям на горизонте планирования, включающем T периодов.

Уравнение (8.2) – набор ограничений баланса запасов, которые уравнивают снабжение изделия на протяжении периода его требования или использования. В любом периоде снабжением для изделия являются запасы из предыдущего периода qi, t–1 плюс производство в периоде pit. Это снабжение может использоваться, чтобы удовлетворить требование в периоде dit, или остаться в запасе как qit. Поскольку мы требуем, чтобы запасы были неотрицательными, эти ограничения обеспечивают удовлетворение требования по каждому изделию в каждом периоде. На входе задаются начальные запасы для каждого изделия, а именно qi0.

Уравнение (8.3) – набор ограничений ресурса. Производство в каждом периоде ограничено готовностью множества распределенных ресурсов, где производство одной единицы изделия i требует aik единиц ресурса k для k = 1, 2,..., K. Обычные ресурсы – разные виды обрабатывающей рабочей силы, погрузочно-разгрузочные механизмы и разные виды транспорта.

Количество переменных решения равно 2IT, а количество ограничений равно IT + КТ. Для любого реалистичного размера задачи мы можем решить линейную модель P1 любым алгоритмом линейного программирования, например таким, как симплекс-метод.

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

Объемные методы применяются в случае, когда цикл изготовления изделий намного меньше интервала планирования. Однако эти методы не учитывают технологию изготовления изделий. Полученные объемными методами соответствия между необходимыми и имеющимися в наличии ресурсами не отображают действительной картины, так как в результате изготовления изделия, предложенного в технологическом порядке, необходимость ресурса того или иного вида возникает не на протяжении всего периода планирования, а лишь в то время, когда наступает очередь выполнения соответствующей работы. Таким образом, планирование объемными методами приводит к неравномерности загрузки оборудования [63].

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

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

Календарным планом (расписанием) является совокупность календарных сроков начала выполнения всех операций, определенных исходя из анализа имеющихся ресурсов. При этом календарный план должен удовлетворять всем требованиям, которые следуют из сформулированных производственных ограничений. Задача календарного планирования, как правило, формулируется как оптимизационная: из всех допустимых (удовлетворяющих наложенным ограничениям) календарных планов необходимо выбрать такой, который обеспечивает экстремальное значение заданного критерия оптимальности.

Производственная программа предприятия формируется на основе портфеля заказов. Задача формирования производственной программы предприятия состоит в выборе более удобного для предприятия набора заказов для включения его в производственную программу. Под «выгодностью» заказов понимается то, что этот набор должен обеспечить достижение заданного уровня технико-экономических показателей работы предприятия, и при этом некоторая функция-критерий должна достигать своего экстремального значения [66]. Сформированная на этапе текущего планирования производственная программа предприятия должна быть детализирована во времени и донесена до конкретных производственных подразделений на этапе оперативно-календарного планирования (ОКП).

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

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

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

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

В современных условиях рыночных отношений, когда планирование должно осуществляться по принципу «вырабатывать только то, что нужно, тогда, когда нужно и столько, сколько нужно» [30], целесообразно построение на основе агрегированной информации моделей, использующих сетевое представление технологии изготовления изделий. Такие агрегированные модели позволяют с достаточной детализацией описать планируемые производственные процессы.

Задачи агрегации (агрегирования) представляют собой один из наиболее методически сложных классов задач ТР. В решении проблемы агрегации могут быть выделены четыре взаимозависимые задачи: выбор приема агрегирования; определение уровня агрегации и ресурсов; формирование структуры агрегированных технологических моделей; формирование агрегированных нормативов.

В качестве агрегированных элементов модели планирования используются агрегированные работы (операции), ресурсы, интервалы времени. Агрегирование работ осуществляется с помощью конструкторского, технологического, комплектного агрегирования, построения «обобщенных операций» и «обобщенного маршрута».

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

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

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

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

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

Второй уровень модели планирования (согласованное планирование), координирующий функционирование подразделений предприятия, состоит в распределении производственной программы на плановый период по критериям, согласованным с общим критерием оптимальности.

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

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

На третьем уровне строится пооперационный план функционирования подразделений с привязкой к оборудованию по критериям, согласованным с критерием оптимальности деятельности предприятия.

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

–  компоненты, повышающие уровень загрузки оборудования;

–  компоненты, минимизирующие отклонение фактических сроков выпуска деталей от плановых сроков;

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

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

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

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

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

Рассмотрим следующую задачу теории расписаний. Имеется множество ма­шин M = {M1, M2, …, Mm} и множество заданий J = {J1, J2, …, Jn}, которые нужно вы­полнить. Для каждого задания JjÎJ известна длительность его выполнения tij на машине MjÎM. Обуславливается, что в эту длительность может быть включено время подготовки или переналадки для от­дель­ных операций, а также то, что каждое задание может обрабатываться каждой машиной максимум один раз.

В [96] предложена следующая запись для описания задач ТР: [n/m/l, l/F], где n – количество заданий, m – количество машин. Если m > 1, то l принимает такие значения:

l = O: (open shop) – система произвольного типа;

l = P: каждое задание может быть обработано только на одной из m идентичных машин (параллельные машины, parallel-shop).

Добавление дальнейших условий приводит к описанию моделей job shop, поточного производства (flow shop) и перестановочного поточного производства (permutation flow shop).

Определение 8.1. Flow Shop: модель flow shop предусматривает серию машин, пронумерованных 1, 2, 3, …, m. Каждое задание состоит точно из m операций. Первая операция любого задания может выполняться машиной 1, вторая – машиной 2 и т. п. Каждое задание проходит все m машин в однонаправленном порядке. Если не каждое задание состоит из m операций, то длительность выполнения этих несуществующих операций равна нулю. Отношение порядка в этой модели предусматривает, что для каждого задания операция i–1 должна быть завершена машиной i–1 раньше, чем машиной i будет начато выполнение операции i.

Определение 8.2. Job Shop: модель job shop обуславливает наличие множества машин, которые обозначаются индексом k. Задание обозначается индексом i, а опе­рации – индексом j. Выполнение каждой операции машинами обозначается мно­же­ст­вом элементов, которые состоят из 3-х индексов: i – задание, которому прина­д­ле­жит операция; j – номер операции; k – машина, на которой необходимо выполнить указанную операцию. Поток операций зада­ния может не быть однонаправленным. Любое из заданий может также исполь­зовать машину неоднократно.

Параметр l применяется для фиксации таких условий выполнения заданий:

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

tree: отношение порядка на множестве заданий имеет структуру дерева. Это означает, что каждая вершина имеет максимум одного пред­шественника (входящее дерево) или каждая вершина имеет максимум одного преемника (выходящее дерево). Дальнейшее выполнение задания может осуществляться только после окончания выполнения всех его предшественников.

Для этих постановок задач отношения порядка задается с помощью графа GP.

tij = 1: все длительности выполнения равны единице;

pmtn: разрешены прерывания выполнения заданий машинами.

Кроме этого, с помощью параметра l обозначается наличие длитель­но­стей под­го­товки, директивных сроков, длительностей ожидания для заданий, длитель­нос­тей простаивания для машин и т. п.

Параметр F описывает целевую функцию.

Для классификации задач ТР более часто используется трехпозиционная но­та­ция формы a/b/g, которую предложили Грэм, Лоулер, Ленстра, Ринной Кен [130].

Первая позиция a = a1a2 определяет тип задачи (a1Î{°, F, J, O, I}) и количество машин (a2).

a1 = F – обозначает поточное производство (Flow-Shop), в котором каждая задача обслуживается машинами в определенном установленном порядке M1 ® M2 ® … ® Mm. В этом случае технологические маршруты выполнения всех заданий одинаковы.

a1 = J (Job-Shop) – технологические маршруты выполнения всех заданий четко установлены, но для разных заданий отличаются.

Отсутствие любых ограничений на технологический маршрут отвечает случаю Open-Shop и обозначается a1 = O.

a1 = I (Parallel-Shop) – все машины идентичны. Каждое задание Jj состоит из одной операции длительностью tj, которая может быть выполнена на любой машине.

Если a1 = °, где ° – пустой символ, то тогда рассматривается одномашинная задача. Если a1 = °, то a2 = 1. Другие типы задач можно получить с помощью комбинации этих моделей.

Если a2 – натуральное число, то количество машин четко определено и равно a2. В случае a2 = ° количество машин – переменное.

С помощью второй позиции b задаются дополнительные условия и ограни­че­ния к задаче, например, возможность прерывания в выполнении заданий, запрет ожидания заданий, наличие ограниченных ресурсов, момент готовности к выпол­нению (момент запуска), директивный срок;

b Í {b1, b2, b3}, где b1Î{°, prec1, prec2},

b2 Î {°, chain, chain-wip, tree, tree1, tree2},

b3 Í {tij = 1, pmtn, ri ³0}.

Если b1 ¹ °, то для заданий задано отношение порядка, т. е. задания не могут выполняться машинами в произвольной последовательности. Это отношение задается ориентированным ацикличным графом на множестве вершин {J1, J2,…, Jn}. Различают несколько видов отношения порядка: