2020-05-12
112
Рассмотрим задачу, связанную с построением расписания обработки 
типов деталей на 
станках, которая была рассмотрены выше. Строгая формулировка данной задачи имеет следующий вид [11].
Пусть имеется типов деталей, которые обрабатываются на производственном участке, состоящем из станков разных типов. Для каждой детали задан свой технологический маршрут обработки, т. е. заданы последовательность обработки на станках и время обработки 
-й детали 
(
) на 
-м (
) используемом станке. Считается, что на одном станке одновременно может выполняться только одна операция 
(
) по обработке детали и каждая деталь в процессе своей обработки не может возвращаться на станок, на котором она ранее обрабатывалась, т. е. в маршруте обработки каждой детали отсутствуют циклы. Кроме того, будем считать, что переналадки станков для обработки новой детали не требуется, т. е. времена переналадок оборудования при переходе обработки с одной детали на другую равны нулю или включены во времена обработки детали.
|
|
|
В задаче требуется определить такую последовательность запуска деталей на обработку, чтобы время изготовления всех деталей было бы минимальным.
Для описания модели, позволяющей строить оптимальное с точки зрения быстродействия расписание обработки деталей, введем следующие обозначения:
− момент начала обработки -й детали на -м станке.
− элемент матрицы 
, обладающий свойством:
Введение такой постоянной матрицы позволяет для каждой операции (
) по обработке -й детали назначить станок, на котором эта операция будет выполняться.
Поскольку на каждом станке может одновременно выполняться только одна операция по обработке любой детали, то для любой пары деталей 
и 
должно выполняться только одно из неравенств
или 
.
Из выполнения первого неравенства следует, что на станке обработка детали должна предшествовать обработке , а при выполнении второго неравенства на станке обработка детали должна предшествовать обработке .
В общем случае на станке обработка детали может выполняться раньше обработки детали или наоборот. Одновременно разные детали на одном станке обрабатываться не могут. Поэтому в модели должно выполняться только одно из этих ограничений.
Для обеспечения этого условия введем в модель булевы переменные 
следующим образом:
Одновременно переменные и 
не могут быть равны 1 или 0, поскольку всегда либо одна деталь обрабатывается раньше другой на одном станке, либо наоборот. Других вариантов быть не может, так как все детали должны быть обработаны, а на одном станке недопустима обработка двух и более деталей одновременно. Поэтому в модель должны быть введены ограничения:
|
|
|
.
Для сокращения размерности модели переменные выражаются из этого уравнения следующим образом:
.
Теперь построим ограничения, позволяющие определять порядок запуска деталей на обработку. Эти ограничения имеют следующий вид:
, (10.26)
, (10.27)
где 
− достаточно большая положительная величина, выбираемая так, чтобы выполнялось только одно из равенств 
или 
и, соответственно, одно из неравенств:
или .
Для этого величину можно выбирать, например, из условия:
.
Как уже отмечалось выше, для каждой детали в соответствии с технологическим маршрутом задан порядок обработки деталей на станках производственного участка. Для построения ограничений, позволяющих соблюдать заданный порядок обработки каждой детали на используемых станках, заметим, что сумма 
определяет момент начала выполнения операции по обработке детали на соответствующем станке. В соответствии с этим для обеспечения заданного порядка обработки каждой детали должны выполняться ограничения:
, 
, (10.28).
Для минимизации времени обработки всех деталей в модель включаются ограничения на время завершения последней операции по обработке каждой детали, которые имеют следующий вид:
, (10.29)
где 
− элемент матрицы , равный единице, если последняя операция по обработке детали выполняется на станке , 
− величина, которая определяет длительность обработки типов деталей и минимизируется в функционале модели:
. (10.30)
Расчеты данной модели сводятся к решению задачи смешанного линейного программирования с булевыми переменными. Переменными в данной модели являются , размерность которых равна 
, булевыми переменными являются переменные , размерность которых равна 
.
Количество ограничений вида (10.28) в данной модели будет равно 
, количество ограничений вида (10.29) будет равно , количество ограничений вида (10.26) и (10.27) будет равно соответственно по 
.
Наличие большого количества булевых переменных весьма затрудняет получение оптимального расписания даже для «небольших» по размерности задач, несмотря на использование современных вычислительных средств, и пакетов прикладных программ, предназначенных для решения задач смешанного линейного программирования с булевыми переменными.
