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

Содержание

1. Содержательная постановка задачи синтеза оптимальных расписаний параллельно-последовательной обслуживающей системы. 3

2. Постановка задачи оптимизации расписаний параллельной системы с задержками поступления заявок. 5

3. Редукция задачи оптимизации расписаний параллельной системы в задачу частично-целочисленного линейного программирования. 8

4. Бикритериальная упрощенная формулировка задачи синтеза расписаний параллельной системы и алгоритм решения. 14

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

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

7. Последовательные многостадийные обслуживающие системы. Моделирование на смешанных сетях. 23

8. Модификации метода ветвей и границ оптимизации расписаний последовательных многостадийных обслуживающих систем (JSP) 28

9. Алгоритм неполной декомпозиции задач оптимизации расписаний последовательных обслуживающих систем. 32

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

11. Декомпозиционный алгоритм оптимизации расписаний многостадийных параллельно-последовательных обслуживающих систем.. 41

12. Приложение моделей и алгоритмов оптимизации расписаний многостадийных параллельно-последовательных систем. 46

13. Содержательная постановка задачи управления материальными потоками предприятия 50

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

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

16. Формальная постановка задачи оптимизации поставок. 68

17. Определение оптимальных цен продаж в задаче оптимизации управления входными и выходными материальными потоками. 72

18. Декомпозиционный алгоритм решения задачи оптимизации поставок. 80

19. Программные средства (ПС) оптимизации управления входными и выходными материальными потоками предприятия (целиком из монографии) 88

20. ПС оптимизации расписаний последовательных, параллельных и параллельно-последовательных систем.. 93

21. Имитационное моделирование производственных систем и процессов. Языки, системы ИМ. 96

22. Основные блоки СИМ Арена и их атрибуты. 100

23. Основные операторы языка GPSS. 107

24. Моделирование параллельных систем в СИМ Арена. 110

25. Моделирование последовательных систем в СИМ Арена. 126

26. Моделирование параллельных систем в GPSS world. 128

27 Моделирование последовательных систем в GPSS world. 130

28. Среда IBM ILOG CPLEX studio. Назначение, возможности, задачи моделирования, разрешимые и неразрешимые в этой среде. 132

29. Проекты IBM ILOG CPLEX studio, состав, назначение компонент. Основные элементы языка OPL. 134

Задача №1. 137

Задача №2. Job Shop. 144

Последовательные многостадийные обслуживающие системы. Моделирование на смешанных сетях.

Задача синтеза расписаний для подобных систем является NP-полной и именуется JobShop (JS). Рассмотрим многостадийную обслуживающую систему, состоящую из K различных приборов, которая обслуживает J заявок. Маршруты обслуживания заявок приборами фиксированы, но различны. Длительность обслуживания каждой заявки каждым прибором также различна. Одновременно одним прибором может обслуживаться только одна заявка. Прерываний обслуживания не допускается. Дисциплина обслуживания очередей – произвольная. Введем обозначения:

A - мн-во элементарных операций, U – множество следования операций, V – мн-во условий неодновременности выполнения операций. G=(A,U,V) – смешанный граф с множеством вершин A, множеством дуг U и множеством ребер V. При замене ребра дугой устанавливается отношение следования между двумя операциями. В случае графического решения используем метод критического пути. Однако, несмотря на легкость данного метода, аналитическое представление играет главенствующую роль.

Приложение моделей и алгоритмов оптимизации расписаний многостадийных параллельно-последовательных систем.

Рассмотрим второй подход к формализации задачи календарного планирования строительства скважин НГКМ с явным заданием последовательности бурения.

- время начала бурения куста скважин j.

Существует два подхода к построению алгоритмов оптимизации расписаний ППОС (параллельно-последовательные обслуживающие системы):

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

Второй: основа – комплекс моделей оптимизации расписаний парал-ых ОС с задержками гачала обслуживания (А11, А12, А13) и алгоритмов оптимизации расписаний послед-х систем (А22, А23).

Пр: Стр-во 7 кустов скважин осущ-ся двумя неидентичными буровыми установками. Время и послед-ть стр-ва приведены в табл. Результаты оптимизации задачи сведены в табл. 2.6. Оптимальный график работы на рис 2.13. Формирование данных модели не требует предварительного разбиения планового периода на этапы и дополнительного оценивания длительностей этих этапов. Однако полученное решение будет грубым приближением. При использовании 2-ого подхода затруднен учет ряда важных обстоятельств. Согласно ему нельзя начинать строительство технологически зависимых скважин до окончания строительства предшествующих кустов. Это не отвечает действительности. В первом подходе это возможно реализовать, которй применим для среднесрочного и оперативного планирования и регулирования процессов обустройства НГКМ. Вместе с тем, первый подход (поэтапный) требует тонких настроек модели и многовариантных модельных расчетов для уточнения длительности этапов (величин исходных задержек начала строительства кустов скважин). Первоначальные оценки длительностей можно получить на основе второго подхода. Таким образом, перечисленные подходы являются сопряженными и взаимно дополняющими друг друга.

Производственные процессы

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

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

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

Основные операторы языка GPSS.

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

GENERATE 12,4,50,5,1 - генерация транзактов, интервалы времени между появлениями транзактов распределены равномерно в диапазоне [12-4, 12+4], первый транзакт появится с задержкой в 50 единиц модельного времени, всего будет создано 5 транзактов, приоритет транзактов равен единице.

GENERATE 12,4,50,,1 - то же, но количество генерируемых транзактов неограничено.

SEIZE PLOT - занятие устройства PLOT приходящим на его вход транзактом; если устройство занято, то транзакт задерживается в очереди к этому устройству.

RELEASE PLOT - освобождение устройства PLOT обслуженным транзактом.

ENTER MEM,12- занятие транзактом 12 единиц емкости в накопителе MEM.

LEAVE MEM,*2 - освобождение k единиц памяти в накопителе MEM, гдк k - значение 2-го параметра транзакта.

STR STORAGE 4096 - описание накопителя STR емкостью 4096 единиц.

TERMINATE 3 - удаление транзакта из системы, при этом содержимое итогового счетчика уменьшается на 3 единицы, моделирование заканчивается, если содержимое счетчика станет равным или меньше нуля.

ADVANCE A,B - задержка транзакта на время, определенное содержимым полей A и B, смысл величин, записываемых в этих подполях , такой же, как и в операторе GENERATE.

SPLIT 3,LLL,6 - копирование транзактов, в данном случае создаются три копии исходного транзакта, исходный транзакт направляется в следующий по порядку блок, а созданные копии - в блок с меткой LLL, при этом параметр 6 основного транзакта увеличивается на единицу, а транзактов - копий - на 2, 3, 4 соответственно.

ASSEMBLE 5 - объединение транзактов, первый из вошедших в блок транзактов продолжит движение в системе после того, как в блок придут еще четыре транзакта.

ASSIGN 2,NAP- изменение параметров транзактов, в данном случае второй параметр транзакта получит значение NAP.

TRANSFER ,MET - безусловная передача управления оператору с меткой (номером) MET.

QUEUE SQV- оператор организации очереди, длина очереди SQV увеличивается на единицу.

DEPART SQV - то же, но длина очереди уменьшается на единицу.

PRIORITY 2- транзакту присваивается приоритет 2.

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

START 100,,25 - занесение значения 100 в итоговый счетчик, вывод накопленных статистических данных производится с интервалом изменения содержимого итогового счетчика в 25 единиц.

Код:

GENERATE 7,2 ; генерирование требований с интервалом [5-9] ед.врем.

QUEUE 1 ; увеличение очереди на одно требование

SEIZE КAN ; Проверка занятости канала KAN

DEPART 1 ; Уменьшение очереди на одно требование

ADVANCE 6,3 ; Обслуживание требование в канале в течении [3-9] ед.врем.

RELEASE КAN ; Освобождение канала KAN

TERMINATE 1 ; Выход требования из системы

START 200 ; Начало моделирования с числом требований 200

Файлы моделей

Файлы моделей (расширение .mod) содержат все операторы OPL. Файл модели, как правило, содержит следующие компоненты:

Объявления данных

Объявления данных позволяют присвоить данным имена, упростив тем самым их использование в модели. Например, если таблица содержит стоимость доставки единицы материалов из расположения i в расположение j, то элемент данных можно назвать cost_ij, где i=1,...,n, j=1,...,n и n - это число расположений в модели. Объявление этих данных модели в OPL выглядит следующим образом:

int n = ... ;

float cost[1..n][1..n] = ... ;

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

Объявления переменных решений

Объявления переменных описывают имя и тип каждой переменной в модели. Например, количество материалов, доставленных из расположения i в расположение j, можно указать в переменной с именем shipij:

dvarint+ ship[1..n][1..n];

Ключевое слово dvar позволяет объявить переменную решения. Поскольку тип int+ разрешает только положительные целые значения, оператор объявляет массив положительных целых переменных.

Объявление службы

Модель составления расписаний начинается с объявления службы, которое выглядит следующим образом: using CP;

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

• Функция цели

Функция цели - это выражение, которое требуется оптимизировать. Она должна содержать переменные и данные, объявленные ранее в файле модели. Функция цели объявляется с помощью ключевого слова minimize или maximize. Пример: minimize endOf(tasks["moving"]);

Этот оператор указывает, что требуется максимально сократить конец переменной интервала tasks["moving"].

• Ограничения

Ограничения описывают условия, необходимые для осуществимого решения модели. Ограничения объявляются в блоке subject to. Пример:

subject to {

forall(t in Tasks)

forall(s in successors[t])

endBeforeStart(tasks[t], tasks[s]);

}

Этот оператор объявляет набор ограничений очередности.

· Операторы сценариев

Файлы данных

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

n = 3;

c = [[0.0 1.5 2.3]

[1.5 0.0 3.7]

[2.3 3.7 0.0]];

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

Файлы параметров

При изменении значений параметров по умолчанию новые значения параметров сохраняются в файле параметров проекта.

В файлах параметров (.ops) сохраняются пользовательские значения параметров при изменении значений параметров по умолчанию языка OPL, программирования в ограничениях (CP Optimizer) и математического программирования (CPLEX).

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

Задача №1.

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

Положим K^’=2, следовательно S=4.

1) Если у нас на некотором этапе два варианта с одинаковыми временами, то берем любой вариант на наше усмотрение.

2) Мы начинаем отбрасывать половину из вариантов на том этапе, когда количество вариантов будет больше S, которое по условию у нас будет равно 4.

3) Мы рассчитываем задержку исходя из разности задержки рассматриваемого этапа и суммы предыдущих задержек (фактических, а не данных по условия) и времени обработки конкретного станка. Это можно подсчитать в уме.

Для тех, кто не хочет считать в уме (для этого надо перебирать варианты как делала я, т.е. берем оптимальный вариант, найденный на предыдущем шаге и пишем его два раза а справа дописываем сначала: 1 0, потом 0 1): смотрим на столбец предыдущего этапа, где есть Мах(…,…)=… соответствующего оптимального варианта. Заполняем f для следующего после него варианта который оканчивается на 1 0. Первое число в Мах – это сумма всех фактических задержек и времен обработки предыдущих шагов для этого варианта. Сравниваем его с задержкой, рассматриваемого этапа и если задержка больше данного числа, то разницу между ними прибавляем к времени обработки данного варианта. В противном случае ничего не прибавляем, а пишем только время обработки. Далее переходим к варианту, который оканчивается на 0 1. Ему соответствует второе число Max. Производим с ним аналогичную операцию, как и с предыдущим вариантом.

Результаты первого этапа (Хij, где i–номер станка, j–номер заявки)

Этап 1	Х11	Х21	Fi,1
Заявка 1			(3,0)	Max(3,0)=3
		(0,4)	Max(0,4)=4

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

Результаты 2-ого этапа

Этап 2	Х11	Х21	Х12	Х22	Fi,2
Заявка 1 + Заявка 2					(2,0)	Max(5,0)=5
				(0,3+2)	Max(3,5)=5
				(2+2,0)	Max(4,4)=4
				(0,3)	Max(0,7)=7

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

Результаты третьего этапа и отсев вариантов. Выделила то, что берем на следующий этап.

Этап 3	Х11	Х21	Х12	Х22	Х13	Х23	Fi,3
Заявка 1 + Заявка 2 + Заявка 3							(3,0)	Max(8,0)=8
						(0,2+4)	Max(5,6)=6
						(3+1,0)	Max(7,5)=7
						(0,2)	Max(3,7)=7
						(3,0)	Max(7,4)=7
						(0,2)	Max(4,6)=6
						(3+4,0)	Max(7,7)=7
						(0,2)	Max(0,9)=9

Результаты четвертого этапа и отсев вариантов

Этап 4	Х11	Х21	Х12	Х22	Х13	Х23	Х14	Х24	Fi,4
Заявка 1 + Заявка 2 + Заявка 3 + Заявка 4									(4+1,0)	Max(10,6)=10
								(0,4)	Max(5,10)=10
								(4,0)	Max(11,5)=11
								(0,4+1)	Max(7,10)=10
								(4,0)	Max(11,4)=11
								(0,4+2)	Max(7,10)=10
								(4+2,0)	Max(10,6)=10
								(0,4)	Max(4,10)=10

Результаты пятого этапа и отсев вариантов

Этап 5

Х11

Х21

Х12

Х22

Х13

Х23

Х14

Х24

Х15

Х25

Fi,5

Заявка 1 + Заявка 2 + Заявка 3 + Заявка 4 + Заявка 5

(2+3,0)

Max(10,10)=10

(0,4)

Max(5,14)=14

(2+1,0)

Max(10,10)=10

(0,4)

Max(7,14)=14

(2+1,0)

Max(10,10)=10

(0,4)

Max(7,14)=14

(2,0)

Max(12,6)=12

(0,4+2)

Max(10,12)=12

Результаты шестого этапа и отсев вариантов

Этап 6

Х11

Х21

Х12

Х22

Х13

Х23

Х14

Х24

Х15

Х25

Х16

Х26

Fi,6

Заявка 1 + Заявка 2 + Заявка 3 + Заявка 4 + Заявка 5 + Заявка 6

(4,0)

Max(14,10)=14

(0,3)

Max(10,13)=13

(4,0)

Max(14,10)=14

(0,3)

Max(10,13)=13

(4,0)

Max(14,10)=14

(0,3)

Max(10,13)=13

(4,0)

Max(16,6)=16

(0,3+4)

Max(16,13)=16

Результаты последнего этапа и выбор наилучших вариантов

Этап 7

Х11

Х21

Х12

Х22

Х13

Х23

Х14

Х24

Х15

Х25

Х16

Х26

Х17

Х27

Fi,7

Заявка 1 + Заявка 2 + Заявка 3 + Заявка 4 + Заявка 5 + Заявка 6 + Заявка 7

(3,0)

Max(17,10)=17

(0,4+2)

Max(14,16)=16

(3+2,0)

Max(15,13)=15

(0,4)

Max(10,17)=17

(3+2,0)

Max(15,13)=15

(0,4)

Max(10,17)=17

(3+2,0)

Max(15,13)=15

(0,4)

Max(10,17)=17

Наилучшее расписание 1

Наилучшее расписание 2

Наилучшее расписание 3

Задача №2. Job Shop

Найти оптимальное по быстродействию расписание последовательной системы (JSP)

Обозначим тройкой (i,j,q) операцию обслуживания детали i станком j в q-й по очереди раз. Построим дизъюнктивную сетевую модель обслуживающей системы в представлении «узел-операция» (рисунок 1). Дуги (стрелки) обозначают последовательность выполнения операций, ребра (прямые линии) — конфликты за станок.

Рисунок 1 — Дизъюнктивная сеть

Экономико-математическая модель задачи в общем виде представлена формулами 1–6.

(1)

(2)

(3)

(4)

Формула 4 по-другому может быть записана в виде формул 5 и 6.

время начала выполнения операции i (5)

(6)

Булевы переменные =1, если операцию i решено выполнять раньше операции j, и =0 в противном случае.

B>0 — некоторое большое число, превышающее величиной длительность самой трудоемкой операции в системе. Примем его равным 100.

— время выполнения операции i

Для рассматриваемой задачи экономико-математическая модель представлена формулами 7–28.

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

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

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

V = { , ,

}

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

Убрала конфликты и нарисовала диаграмму Ганта обработки партий деталей. Партии подписаны слева, на отрезках написаны номера станков. Если идти от 0 направо, видны однозначные конфликты (когда интервалы, требующие одинаковые станки, заходят друг на друга). Это , Далее конфликтность я определяла в зависимости от расстояния между интервалами, требующими один станок. Опять идем от 0 направо. Между операциями 111 и 211 интервал 1 час, так же как между операциями 211 и 112, 211 и 312. Ранжируем . Между операциями 311 и 211 интервал 3 часа. Между операциями 111 и 312 интервал 4 часа. Между операциями 311 и 112 интервал 6 часов.

Для оценки нижней границы задачи уберем все конфликты (ребра) и посчитаем критическое время как для обычного сетевого графика (рисунок 2).

Рисунок 2

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

Выбирать ребра будем по принципу максимального приоритета (для чего и ранжировали). При этом будем проверять сеть на отсутствие циклов.

Шаг 1. Выбираем ребро

Подзадача 1.1

(111, затем 311)

Подзадача 1.2

(311, затем 111)