Здесь возможны варианты:
- деталь ждет обработки на k -ом станке, тогда
- деталь не ждет обработки
-
при aij0 деталь j на i -ом станке не обрабатывается по технологии.2) На одном станке нельзя одновременно обрабатывать две детали j и s . Моменты начала обработки двух деталей должны отстоять как минимум на длину обрабатывания детали, которая идет первой.
xisij ( сначалаобрабатывается j)Но мы не знаем, какая деталь идет первой, поэтому условия xijis ( сначалаобрабатывается s) альтернативные, т.е. работает одно или другое.
Чтобы реализовать эту ситуацию введем дополнительную целочисленную переменную yijk
.Обозначим верхнюю границу продолжительности производственного цикла через T .
Тогда можно записать:
T aij 1 yijs xis xij aij (*) T ais yijs xij xis ais (**) xis xij TИсследуем данную конструкцию:
А) xij xis 0 . Ситуация невозможна, т.к. это означает одновременную обработку двух деталей на станке.
В (*) y ijs 0 , (**) y ijs 1 .
Б) xij xis 0 , то (*) yijs 0 ; (**) yijs {0,1} . Значит yijs 0 (единственное возможное значение). В) xij xis 0 , то (*) yijs {0,1} ; (**) yijs 1 .Значит yijs 1 (единственное возможное значение). Таким образом, формальная конструкция (*) и (**) реализует альтернативные условия.
3) Момент окончания обработки на j ой детали на i -ом станке не превышает искомую длину производственного цикла t : xij aij t . Целевая функция задачи f t min . Таким образом имеем модель: f min xkjaijВследствие большого разнообразия производственных условий возможностей производства универсальная постановка задачи календарного планирования невозможна.
Приведенная постановка является наиболее простой.
Ограничения задачи могут быть дополнены следующими:
- условиями на сроки окончания отдельных работ;
- требование учета различных проиводственных факторов (труд, материалы, оборудование);
- требование учета дополнительных производственных факторов, сопровождающих процесс производства – особенностей технологии.
В качестве критериев оптимальности в этой задаче может быть использованы и другие критерии, которые делятся на 2 группы:
1) критерии, зависящие от общей продолжительности обработки изделий. К ним относятся: минимум простоев оборудования; максимум показателя использования оборудования; минимум издержек на незавершенное производство
2) критерии, которые являются функцией заданных сроков готовности: минимум суммарного отставания от сроков; минимум издержек, связанных с невыполением работ в срок; минимум числа отстающих работ.
4) Модель задачи о покрытии.
Задача о покрытии
Общий вид: n
c j x j min
j 1 n
a ij x j b i , i 1, m
j 1
x j {0,1}, a ij {0,1} Если cj 1, j, то простая задача о покрытии; если cj R , то взвешенная задача о покрытии.Описание конкретных постановок задач о покрытии проводится на логическом языке в терминах синтеза схем с использованием булевых функций, связывающих входы и выходы устройства.
Тогда задачей синтеза является построение схемы, реализующей дополнительную булеву функцию, затем среди полученной совокупности схем выбираются в соответствии с заданным критерием. 5) Особые задачи.
Неоднородная ТЗ с фиксированными доплатами
В качестве задачи с разрывной функцией цели рассмотрим ТЗ с фиксированными доплатами или неоднородную ТЗ.
Постановка: i 1, m - пункты производства, ai - объемы производства; j 1, n - пункты назначения, bi - потребности.Кроме того, по условиям перевозки требуется дополнительно платить dij ден.ед. независимо от величины груза в случае, если груз перевозится из i в j .
Интерпретация доплаты dij может быть: плата за аренду авто, дорожный сбор на крупных дорожных сооружениях, таможенная политика и т.д.
Модель. В связи с новыми условиями целевая функция ТЗ становится принципиально другой. Это функция, в которой прежнее cij становится зависимой от того, перевозится груз или нет.
Здесь переменных целочисленных нет.
Чтобы численно реализовать такую модель сведем ее к ЧЦЗ. - определим величины Mij min{ ai, bj} i, j-
введем переменные yij {0,1} и условия xijMij yij .m n
Тогда F ( cij xij dij yij ) .
i 1 j 1
Рассмотрим, как работает в оптимальном плане:
- если yij 0 , то xij 0 ;
- если yij 1 , то xij Mij неравенство излишнее (по построению);
-
если xij 0 , то yij должен быть нулем, иначе план не оптимальный и его можно улучшить; - Если xij 0 , то yij 1 .Таким образом, переменные yij {0,1} «согласуют» плату за аренду и действие – осуществление перевозки.
В схему ТЗ с фиксированными доплатами укладывается также задача о смесях, имеющие фиксированные доплаты (фиксированная стоимость заказа, компоненты смеси, не зависящие от заказываемого количества).
Распределительная задача (обобщенная ТЗ)
Рассматривается транспортное предприятие с j 1, n транспортными линиями (маршрутами). В соответствии с планом графика по j -ой линии надо выполнить bj рейсов. Фонд наличных транспортных средств (транспортный парк) представлен i 1, m типами транспортных единиц с полными резервами времени ai .Заданы затраты времени на выполнение i -ой транспортной единицей рейса j - tij и затраты денежных средств cij .
Надо оптимизировать расстановку транспортных единиц по рейсам так, чтобы суммарные затраты были минимальными.
Введем обозначение: xij - количество i -го транспорта на j -ом маршруте.
Модель:
(2)(3)
(4)
Распределительная задача с фиксированными доплатами
Пусть дополнительно в постановке обобщенной ТЗ нужно учесть следующее: выпуск транспортных средств i на маршрут j связан с дополнительными затратами времени
, не зависящие от числа рейсов, и денежных средств dij .Тогда затраты средств cij будут зависеть от того, будет ли транспортное средство i содержать хотя бы один рейс по маршруту j или нет.
Таким образом: cij (5)
dij , xijАналогично, для затрат времени: tij ( xij )
(6)Получили модель: