Сущность метода ветвей и границ.Стратегии ветвления. Алгоритмы решения различных задач методом ветвей и границ.Классификация и методы решения задач теории расписаний.

Введение Повышение эффективности принимаемых решений во всех областях человеческой деятельности, в том числе и военном деле, предполага­ет решение широкого круга задач оптимизации. Среди множества задач оптимизации можно выделить задачи, в которых параметры управления (искомые переменные) принимают целочисленные значения. Одним из методов решения таких задач является метод ветвей и границ. Сущность метода ветвей и границ заключается в построении де­рева возможных решений, определении оценки границ решения и исклю­чении из рассмотрения вариантов, которые не могут привести к опти­мальному. Из сущности метода вытекают две проблемы, которые необ­ходимо решить при применении метода ветвей и границ. Как осуществить ветвление и каким методом вычислить оценку границ решения? Решение первой проблемы связано с построением дерева возможных ва­риантов и поиском оптимального решения. В настоящее время применя­ются различные способы ветвления, такие как фланговое, фронтальное, локально-избирательное, глобально-поисковое. Эффективность алгоритмов метода ветвей и границ определяется точностью способа определения оценки границы решения. Низкая точ­ность ведет к увеличению рассматриваемых вершин, что в свою оче­редь увеличивает время решения задачи и объем требуемой памяти ЭВМ, единого метода определения оценки границ решения нет. Выбор мето­да в большинстве случаев основывается на учете специфики решаемой задачи. Многие задачи оптимального принятия решений требуют упорядо­чения во времени фиксированной системы ресурсов для выполнения определенной совокупности работ. От выбора постановки и качества решения таких задач существенно зависит рациональная организация работ. В связи с большим разнообразием анализируемых ситуаций ис­следование таких задач осуществлялось в рамках различных научных дисциплин. Поиск общего подхода к решению данного класса задач позволил в пятидесятые годы выделить их в общий раздел, получив­ший наименование теории расписаний. В учебном пособии последовательно рассматриваются: сущность метода ветвей и границ; стратегии ветвления; алгоритмы решения различных задач методом ветвей и границ; классификация и методы решения задач теории расписаний. Изложение сопровождается примерами по применению рассмотренных алгоритмов. Пособие может быть рекомендовано курсантам, обучающимся по специальности 230105, и адъюнктам соответствующих специальностей. 1 Транспортная задача линейного программирования 1.1 Постановка транспортной задачи К задачам линейного программирования сводится большой класс во­енных, экономических и инженерных задач. Для решения этих задач может быть использован наиболее универсальный симплексный метод. Однако некоторые задачи могут быть сформулированы относительно просто, и для их решения пригодны специальные методы линейного программирования, значительно более эффективные, чем универсаль­ный метод. Эти задачи можно описать общей математической моделью, состоящей из ряда линейных уравнений. Впервые такая модель была использована для планирования оптимальных схем перевозок, поэтому она получила название транспортной задачи. Такое название задачи и методов ее решения является условным, так как эта математическая мо­дель и методы ее решения могут быть использованы для решения не только транспортной, но и целого ряда других задач. Транспортная задача находит широкое применение в военном деле при решении задач материально-технического обеспечения операций, целераспределения, организации ремонта и восстановления техники. Математически транспортная задача формулируется следующим об­разом. Требуется минимизировать: (1.1) при ограничениях: , i=1,…, m; (1.2) , j=1,…,n; (1.3) , i=1,…, m, j=1,…,n, (1.4) где сij - стоимость перевозки единицы груза из i-го пункта отправления до j- того пункта назначения; xij- количество гpyза, перевезенного из i-того пункта отправления в j-тый пункт назначения; ai- запасы груза на i-том пункте отправления; bj-потребности в грузе на j-том пункте назначения. Условия (1.2) и (1.3) означают, что количество груза, вывозимого из i-того пункта отправления, равно запасам груза в этом пункте, и количе­ство груза, ввозимого в j-тый пункт назначения, равно потребностям в грузе для данного пункта назначения. Из условия (1.4) следует, что общие запасы и потребности в грузе равны. Показателем эффективности плана перевозок является стоимость, по­этому сформулированную задачу называют транспортной задачей по критерию стоимости. Величина сij может иметь не только стоимостный смысл. Например, сij может означать расстояние, время, расход топлива и т. п. Обычно исходные данные транспортной задачи задаются в виде таблицы. Таблица 1.1 ПН по В1 … Вn ai A1 C11 … C1n a1 … … … … … Am Cm1 … Cmn am ьj b1 … bn Задача (1.1)-(1.4) является задачей линейного программирования и мо­жет быть решена симплексным методом. Однако основная особенность этой задачи: равенство единице коэффициентов в уравнениях (1.2),(1.3) позволила разработать специальные методы ее решения, более эффек­тивные, чем симплексный метод. Научное исследование транспортной задачи началось еще в 30-х го­дах, когда советский ученый А. Н. Толстой разработал своеобразный метод ее решения для случая, когда имеется не более двух пунктов от­правления. В работе Л. В. Канторовича «Математические методы организации и планирования производства», вышедшей в 1939 г., изложен метод раз­решающих множителей и указано, что он пригоден для решения транс­портной задачи. В 1949 г. Л. В. Канторович и М. К. Гавурин предложи­ли один из наиболее эффективных методов решения транспортной за­дачи - метод потенциалов. При решении транспортной задачи на ЭВМ наиболее эффективен венгерский метод, разработанный в конце 50-х годов. Идейно все методы решения транспортной задачи можно разделить на две группы. В методах первой группы ищется допустимое (опорное) решение, которое удовлетворяет условиям (1.2), (1.3), и с помощью последователь­ности итерации улучшается допустимое решение. В методах второй группы ищется оптимальное решение, для которого могут не удовле­творяться условия (1.2), (1.3), и последовательно сокращаются невязки ог­раничений до получения допустимого оптимального плана. Поэтому методы первой группы обычно называют методами последовательного улучшения плана, методы второй группы - методами последователь­ного сокращения невязок ограничений. Так как для методов первой группы необходимо предварительное определение опорного (допустимого) плана, то рассмотрим различные способы его определения. При решении задач большой размерности вручную эти способы могут быть использованы для приближенного решения транспортных задач. 1.2 Способы определения опорного плана транспортной задачи Решение транспортной задачи начинается с определения допу­стимого решения, т.е. опорного решения. Особенность транспортных задач (ТЗ) от ОЗЛП заключается в том, что такое решение всегда суще­ствует. Простейшим способом определения опорного плана является так называемый способ «северо-западного угла». Сущность его поясним на конкретном примере. Допустим, что требуется определить опорный план для ТЗ, исходные данные для которой приведены в таблице 1.2. Будем заполнять ее перевозками постепенно начиняя с левой верхней клетки («северо-западного» угла таблицы). Первой заполняется клетка А1-B1. Спрос пункта назначения В1 составляет 30 единиц, запасы пункта от­правления А1 - 40 единиц. Следовательно, спрос В1 можно полностью удовлетворить за счет запасов А1. Следующая клетка А1-В2. Спрос пункта назначения В2-100 единиц, оставшиеся запасы пункта отправления A1-10 единиц; назначаем перевозку А1-В2- 10 единиц. Так как запасы пункта отправления А1 полностью исчерпаны, то перехо­дим к пункту отправления А2. Рассмотрим клетку А2-В2. Неудовлетво­ренный спрос В2 составляет 90 единиц, запасы А2- 80 единиц. Назнача­ем перевозку А2-В2 80 единиц. Запасы пункта отправления А2 полно­стью исчерпаны, переходим к распределению запасов пункта отправле­ния А3. Пункту назначения В2 требуется еще 10 единиц; пункту назначения В3 -50 единиц. Запасы пункта отправления А3 составляют 60 единиц. На­значаем перевозку А3-В2-10 единиц, А3-В3-50 единиц. Полученное распределение перевозок приведено в табл. 1.3. Таким образом, способ «северо-западного угла» весьма прост, но полученный с его помощью план может существенно отличаться от оптимального плана. Таблица 1.2 ПН по В1 В2 В3 ai A1 10 1 3 40 A2 6 2 5 80 A3 12 5 14 60 ьj 30 100 50 180 Таблица 1.3 ПН по В1 В2 В3 ai A1 10 30 1 10 3 40 A2 6 2 80 5 80 A3 12 5 10 14 50 60 ьj 30 100 50 180 Лучшие результаты дает способ наименьшего элемента в матрице. Сущность этого способа рассмотрим на этом же примере (табл. 1.4). В табл. 1.2 выбираем клетку с минимальным элементом. Такой клеткой яв­ляется А1-В2. Потребности пункта назначения В2 составляют 100 еди­ниц, запасы пункта отправления А1- 40 единиц. Назначаем перевозку А1- В2 - 40 единиц. Так как запасы пункта отправления А1 полностью исчер­паны, то первую строку исключаем из дальнейшего рассмотрения. Оп­ределяем следующую клетку А2-В2 с минимальным элементом. Неудов­летворенные запасы пункта назначения В2 - 60 единиц, запасы пункта отправления А2 - 80 единиц, назначаем перевозку А2-В2 - 60 единиц. Ана­логичным образом назначаем все остальные перевозки указанные в табл.1.4. Таблица 1.4 ПН по В1 В2 В3 ai A1 10 1 40 3 40 A2 6 2 60 5 20 80 A3 12 30 5 14 30 60 ьj 30 100 50 180 Еще более точное приближение опорного плана к оптимальному дает способ Фогеля (способ предложен американским ученым У. Фогелем). Способ Фогеля рассмотрим на примере задачи, приведенной в табл. 1.2. Процесс начинается с определения разностей между двумя наименьши­ми элементами каждой строки и каждого столбца табл. 1.2. Обозначим эти разности i и j соответственно. Например, в строке A1 минимальный элемент равен 1, следующий за ним по величине элемент-3, разность между ними -2. Эта и другие разности по строкам и столбцам выписаны в табл. 1.5. Затем из всех разностей строк и столбцов выбираем наиболь­шую. В нашем примере это 3 =7 в строке А3. Определяем клетку с ми­нимальным элементом в этой строке А3В2 и в эту клетку записываем по­ставки А3-В2 60 единиц. Запасы пункта отправления A3 исчерпаны. Ис­ключаем строку А3 из рассмотрения и определяем новые разности. В нашем примере разности не изменились, но в общем случае они могут и пересчитываться. Определяем следующую максимальную разность 4, которой соответствует минимальный элемент в клетке А2-В1 -6. Назнача­ем перевозки А1-В2 и аналогичным образом продолжаем вычислитель­ную процедуру до назначения всех перевозок. Результаты назначения приведены в табл. 1.5 Таблица 1.5 ПН по В1 В2 В3 i ai A1 10 1 3 40 2 40 A2 6 30 2 40 5 10 3 80 A3 12 5 60 14 7 60 j 4 1 2 ьj 30 100 50 180 Сравним опорные планы, полученные рассмотренными способами. Опорный план, полученный способом «северо-западного угла» (см. табл. 1.3) дает следующую стоимость перевозок: L1 = 10*30+1*10+2*80+5*10+14*50 = 1220 Опорному плану, полученному способом наименьшего элемента (см. табл. 1.4), соответствует L2, = 1*40 + 2* 6О + 5*20 + 12*30 + 14*30=1040 Наиболее точные результаты дает опорный план, полученный спосо­бом Фогеля (см. табл. 1.5): L3 = 5* 60 + 6*30+2* 40+5*10+3* 40=730. Однако каждый из этих способов не гарантирует, что полученный опорный план является оптимальным. Для уточнения опорного плана разработан ряд методов. 1.3 Метод потенциалов Идея метода потенциалов заключается в том, что для проверки допустимого плана на оптимальность для каждого столбца и строки определяются числа и , которые называются потенциалами. С помощью потенциалов легко вычисляются индексы свободных клеток. Рассмотрим транспортную задачу в общем виде (1.5) при ограничениях ; (1.6) . (1.7) Определим функцию Лагранжа для задачи (1.5)-(1.7): , (1.8) где , . Так как и ограничения заданы в виде равенств, то условия экстремума имеют вид Выполнив дифференцирование (1.8), получим ; (1.9) ; (1.10) ; (1.11) . (1.12) Условия (1.11), (1.12) совпадают с условиями (1.6), (1.7). Из условий (1.9), (1.10) видно, что при ; (1.13) при . (1.14) Условие (1.13) позволяет находить потенциалы для допустимого базисного решения. Из условия (1.14) следует выражение для определения индексов свободных клеток . (1.15) Итак, рассчитав потенциалы можно рассчитать индексы свободных клеток и проверить допустимый план на оптимальность. Если условие (1.15) не выполняется, то из всех свободных клеток, для которых , выбирается одна с максимальным по абсолютной величине индексом. Для этой свободной клетки строится цикл и производится перераспределение плана перевозок. Вычислительный процесс заканчивается при выполнении условия (1.15) для всех свободных клеток. Рассмотрим пример решения транспортной задачи методом потенциалов. Исходные данные для решения и допустимый план представлены в табл. 1.6. Определим потенциалы и . Потенциал первой строки выбираем произвольно, например . В первой строке находится одна базисная клетка . Следовательно, . Зная , можно найти . Используя следующую базисную клетку , определяем . По базисным клеткам третьей строки последовательно рассчитываем . Зная потенциалы строк и столбцов, рассчитываем индексы свободных клеток: Так как , то данный план не является оптимальным. Таблица 1.6 Таблица 1.7 Отрицательный индекс имеет свободная клетка . Составляем для этой клетки цикл , , , производим перераспределение перевозок и рассчитываем потенциалы для нового опорного плана (табл. 1.7). По потенциалам определяем индексы свободных клеток: Все индексы положительны. Следовательно, данный план является оптимальным. Таким образом, вычислительный алгоритм метода потенциала включает следующие операции: 1) определяем опорный план; 2) рассчитываем для базисного опорного плана потенциалы; 3) определяем индексы свободных клеток и проверяем план на оптимальность; 4) при наличии отрицательных индексов выбираем из них индекс с максимальным абсолютным значением и производим для соответствующей свободной клетки перераспределение плана перевозок, после чего переходим к п. 2. Метод потенциалов ­– простой и эффективный метод решения транспортной задачи. Наиболее удобен метод для расчетов вручную. При использовании ЭВМ метод менее удобен, так как построение циклов на ЭВМ связано с большими затратами машинного времени 1.4 Венгерский метод Наиболее эффективным методом решения транспортной задачи на ЭВМ является венгерский метод. Вычислительные эксперименты, поставленные на ЭВМ, показали, что венгерский метод в 2-4 раза эффективнее метода потенциалов. В основу метода положены теоремы, доказанные венгерскими математиками Д.Кенигом и Е.Эгервари. На основании этих теорем американские математики Г.Кун и Д.Манкрес разработали метод, который справедливо был назван венгерским. Венгерский метод относится к методам последовательного сокращения навязок ограничений. Метод основан на двух теоремах. Теорема 1. Если план минимизирует при выполнении ограничений , , то этот план минимизирует и при тех же ограничениях, где ; , ; , – константы приведения матрицы. Теорема 2. Если и можно указать такой план перевозок , для которого =0 и выполняются ограничения задачи, то полученный план перевозок оптимален. Вторая теорема очевидна, так как при минимальное значение целевой функции не может быть меньше нуля. Для доказательства первой теоремы представим в виде . Так как значения сумм не зависят от , то и L достигают минимума при одних и тех же значениях . Из теоремы 1 следует, что прибавление и вычитание некоторого числа из всех элементов строки или столбца матрицы не изменяет оптимального плана. Если все перевозки назначены на нулевые элементы матрицы , то целевая функция =0. Таким образом, идея метода заключается в том, чтобы путем прибавления или вычитания констант приведения ui и vj из всех элементов строк и столбцов матрицы преобразовать ее к такому виду, чтобы все ее элементы были неотрицательны и все перевозки можно было назначить по нулевым элементам. Несмотря на идейную простоту венгерского метода, его вычислительный алгоритм является достаточно сложным. Рассмотрим его основные шаги. 1. Преобразуем исходную матрицу таким образом, чтобы в каждом столбце и каждой строке был хотя бы один нулевой элемент. Для этого вычитаем минимальные элементы столбцов из всех элементов соответствующих столбцов с последующим вычитанием минимальных элементов строк из всех элементов соответствующих строк. 2. Определим начальный план , назначая перевозки способом «северо-западного угла» в нулевые элементы . 3. Определим невязки по строкам и столбцам и суммарную невязку ∆=. Если ∆=0, то полученный план является допустимым и оптимальным. Если ∆>0, то план недопустимый и дальнейшая вычислительная процедура направлена на ликвидацию невязок. 4. Выделяем знаком «+» столбцы , для которых . 5. Находим среди невыделенных элементов минимальный элемент h. При h=0 переходим к п. 7, при h>0–к п. 6. 6. Вычитаем h из всех элементов невыделенных строк и прибавляем h ко всем элементам выделенных столбцов. Возвращаемся к п. 5. 7. Отметим нулевой элемент h матрицы знаком «штрих» (0´). 8. Проверяем невязку строки, в которой находится 0´. При =0 переходим к п. 9, при >0–к п. 13. 9. Выделяем в знаком «плюс» строку, в которой находится 0´. 10. В выделенной строке по последовательно проверяем в выделенных столбцах значения . При >0 переходим к п. 12. 11. Открываем в выделенный столбец (знак «+») и отмечаем нулевой элемент этого столбца, находящийся в выделенной строке, звездочкой (0*). 12. Если проверены все выделенные столбцы , переходим к п. 5, в противном случае – к п. 10. 13. Строим цепочку по столбцу от 0´ к 0*, по строке от 0* к 0´. Цепочка начинается от 0´, находящегося в столбце с >0, и заканчивается в 0´, находящемся в столбце с >0. Возможен случай, когда цепочка содержит только один 0´, т.е . 0´ находится в строке и столбце, для которых >0 и >0. 14. Определяем величину сокращения невязки: , где – невязка строки. В которой находится первый 0´ цепочки; –невязка столбца, в котором находится последний 0´ цепочки; –минимальное значение перевозок, соответствующее 0*, входящему в цепочку. Если в цепочку входит один 0´, то . 15. Находим новый план, прибавляя к элементам , соответсвующим 0´ цепочки, и вычитая из элементов , соответствующим 0* цепочки. Остальные элементы остаются без изменений. 16. Раскрываем все выделенные столбцы и строки, стираем у нулевых элементов знаки штриха и звездочки, переходим к п. 3. Поясним основные шаги алгоритма на конкретном примере с матрицей = Запасы и потребности указаны справа и внизу у соответствующих строк и столбцов. Выполнив п. 1 алгоритма, получим = , = В каждом столбце и строке имеется нулевой элемент. В соответствии с п. 2 и 3 определяем начальный план и рассчитываем невязки = Суммарная невязка ∆=100>0. План не является допустимым, поэтому переходим к пп. 4, 5. Выделив знаком «плюс» столбцы с =0, получим = Определим среди невыделенных элементов минимальный h=min(0,2,7)=0. так как h=0, то переходим к пп.7,8,9,10,11,12, выполнив которые, получим = Возвращаемся к п. 5 и находим h=min{1,2,0,7}=0. так как h = 0, то, повторно выполнив пп. 7,8,9,10,11,12 и получив = возвращаемся к п. 5. Находим h=min{1,2,7}=1. Так как h=1>0, то переходим к п. 6, выполнив который, получим = Вновь возвращаемся к п. 5 и находим h=min{0;1}=0. Так как h=0, то, выполнив пп. 7, 8, получим = Невязка =50>0, поэтому переходим к п. 13 и строим цепочку, указанную в матрице . В соответствии с пп. 14, 15, 16, 3 находим =min{50,40,50}=40, уточняем план, снимаем отметки в матрице и рассчитываем невязки. Новый план: =. Суммарная невязка ∆=20>0. Так как ∆>0, то продолжаем вычислительный процесс. Последовательно выполнив пп. 4, 5, 7, 8, 9, 10, 12, 5, 6, 5, 7, 8, 13, получим матрицу = в которой цепочка включает лишь один 0´. Выполнив пп. 14, 15, 16, 3, получим новый план = Так как ∆=0, то план является допустимым и оптимальным. Рассмотренный пример наглядно показывает, что венгерский метод формализован, но достаточно сложен. Поэтому он эффективен при расчетах на ЭВМ. Эффективность венгерского метода может быть повышена, если первоначальное преобразование матрицы (п. 1) производить до тех пор, пока не будут выполняться условия (1.16) где . Условия (1.16) означают, что число нулевых элементов каждой строки и столбца матрицы должно обеспечивать возможность распределения всех запасов по нулевым элементам i-той строки и всех потребностей по нулевым элементам j-того столбца. Выполнение условий (1.16) обеспечивает получение начального плана , более близкого к оптимальному, что уменьшает невязки и число итераций при поиске допустимого плана. Например, для рассмотренного примера с исходной матрицей = после выполнения п. 1 получаем = Условия (1.16) не выполняются для второй строки и третьего столбца. Вычитая из элементов второй строки 1 и прибавляя ее к элементам первого столбца (в противном случае в первом столбце c1,2 = -1), получим = Вычитая из элементов третьего столбца 1 и прибавляя ее к элементам первой строки, получим = Окончательно получим = Условия (1.16) выполняются. Определив исходный план способом Фогеля = и рассчитав невязки , убеждаемся, что полученный план является оптимальным. Вычислительные эксперименты, выполненные на ЭВМ, показали, что приведение матрицы с учетом условий (1.16) в 1,5–2 раза повышает эффективность венгерского метода. 2. Сетевые модели оптимального планирования При управлении разработками сложных программ и войсками возникает задача рационального планирования и координации большого комплекса различных работ (операций, действий). Примерами таких работ могут быть: перевооружение армии или отдельных её частей; подготовка и проведение военной операции; выполнение комплексной НИР или ОКР и т.д. Характерным для таких сложных комплексов связанных между собой работ является то, что отдельные работы не могут быть выполнены независимо друг от друга, выполнение ряда работ не может быть начато раньше, чем завершены другие. Рациональное планирование комплекса работ требует, в частности, ответа на следующие вопросы: Как распределить имеющиеся материальные средства и трудовые ресурсы между звеньями комплекса? В какие моменты начинать и когда заканчивать отдельные звенья? Какие могут возникнуть препятствия к своевременному завершению комплекса работ и как их устранить? и т.д. При планировании сравнительно небольшого (по количеству звеньев) комплекса работ ответы на такие вопросы даёт руководитель, причём без специальных математических расчётов на основе опыта и здравого смысла. Однако когда речь идёт об очень сложных, дорогостоящих комплексах работ, состоящих из большого числа звеньев, сложным образом обуславливающих друг друга, такие приёмы становятся недопустимыми. В таких случаях возникает необходимость в специальных методах, позволяющих обоснованно ответить на поставленные выше вопросы и другие. Одним из математических методов современной теории управления большими системами, широко применяемым на практике, является метод сетевого планирования и управления (СПУ). Методы СПУ были разработаны сравнительно недавно (первая публикация относится к 1958 г.). Так как они разрабатывались в разных странах, возникло несколько их разновидностей: СПУ - в СССР, PERT и СРМ - в США и др. В 1957 году группа ученых, разрабатывая метод управления реализацией проекта программы "Полярис" Главного управления вооружений ВМС США, создала специальный метод планирования и контроля проектных работ, названный методом анализа и оценки программ (Program Evaluation and Review Technique - PERT). Программа "Полярис" состояла из 60 тыс. операций, при этом требовалось координировать работу около 3800 подрядчиков. Метод обеспечивал руководству информацию к любому моменту времени о выполняемых работах, ответственных исполнителях, а также о вероятности своевременного завершения как отдельных работ, так и всего комплекса в целом. Метод PERT применяется в планировании научно-исследовательских и опытно-конструкторских разработок, для которых характерна неопределенность в оценке затрат времени, необходимого для выполнения отдельных операций (работ). Метод СРМ применяется тогда, когда оценки времени операций детерминированные. Широкое применение СПУ нашло при разработке и внедрении АСУ, так как при этом приходится планировать большое число работ и согласовывать их выполнение между большим количеством исполнителей. 2.1 Основные понятия сетевого планирования и управления. Построение сетевых планов Сетевое планирование и управление включает три основных этапа: - структурное планирование; - календарное планирование; - оперативное управление. Структурное планирование начинается с выделения операций (работ). Затем определяются их продолжительности и строится сетевой график (модель), который анализируется с целью улучшения. Иногда этот этап называется предварительным планированием комплекса работ. Конечной целью календарного планирования является построение календарного графика, определяющего моменты начала и окончания каждой операции, а также ее взаимосвязи с другими операциями программы. Кроме того, календарный график должен давать возможность выявлять критические операции (с точки зрения времени), которым необходимо уделять особое внимание, и резервы времени на некритических операциях. Этот этап называют также исходным планированием комплекса работ. Оперативное управление процессом реализации программы заключается в использовании сетевого графика и календарного плана для составления периодических отчетов о ходе выполнения программы. Основой метода СПУ является сетевой график (сетевая модель), отражающий (ая) логическую взаимосвязь и взаимообусловленность входящих в него элементарных операций (работ). Сетевые графики с математической точки зрения представляют собой орграфы без контуров, дугам или вершинам которых приписаны некоторые числовые значения. В системах СПУ используются следующие, наиболее распространенные способы построения сетевых графиков: 1) сетевые графики в терминах "дуги-операции". В таких графиках вершины, называемые событиями, соответствуют моментам времени начала или окончания одной или нескольких операций, а дуги - операциям; 2) сетевые графики в терминах "дуги-связи", в которых операции изображаются вершинами сети, а дуги показывают порядок выполнения (взаимосвязь) отдельных операций. Каждый из способов построения сетевых графиков имеет как преимущества, так и недостатки. Учитывая, однако, что первый способ получил большее практическое применение в нашей стране, в дальнейшем сетевые графики будем рассматривать в терминах "дуги-операции". В сетевом графике различают три вида событий: исходное, завершающее и промежуточное. Исходное - это такое событие, с которого начинается выполнение комплекса операций. Завершающее соответствует достижению конечной цели, т.е. завершению комплекса операций. Сетевые графики с несколькими завершающими событиями называются многоцелевыми. К промежуточным относятся все прочие события. События обозначаются кружками или другими геометрическими фигурами. Предполагается, что события не имеют продолжительности и наступают как бы мгновенно. Моментом свершения события считается момент окончания выполнения всех входящих в это событие операций. Пока не выполнены все входящие в событие операции, не может свершиться само событие, а следовательно, не может быть начата ни одна из непосредственно следующих за ним операций. Различают три вида операций: 1) активная (действительная) операция (→) - процесс, требующий затрат времени и ресурсов (разработка проекта, подвоз материалов, выполнение монтажных работ и т.д.); 2) пассивная операция (ожидание) ( ) - процесс, требующий только затрат времени (затвердение бетона, естественная сушка штукатурки перед началом малярных работ, рост растений и т.д.); 3) фиктивная операция ( ), или логическая зависимость, отражает технологическую или ресурсную зависимость в выполнении некоторых операций. Рис.2.1 При построении сетевых графиков необходимо соблюдать определенные правила: 1) в сети не должно быть событий (кроме исходного), в которые не входит ни одна дуга; 2) не должно быть событий (кроме завершающего) из которых не выходит ни одной дуги; 3) сеть не должна содержать контуров; 4) любая пара событий сетевого графика может быть соединена не более чем одной дугой. Если изобразить одновременно (параллельно) выполняемые три различные операции b, c, d с общими начальным и конечным событиями (рис. 2.2), то возникает путаница из-за того, что различные операции имеют одно и то же обозначение (2,5). В этом случае рекомендуется ввести дополнительные события и соединить их с последующими фиктивными операциями (рис. 2.3); 5) если какие-либо операции могут быть начаты до полного окончания непосредственно предшествующей им операции, то последнюю целесообразно представить как ряд последовательно выполняемых операций, завершающихся определенными событиями. Например, если операции c и d могут быть начаты до полного окончания операции b, то операцию b рекомендуется разбить на элементарные операции b1, B2 и B3 и представить выполнение всех операций в виде графика, изображенного на рис. 2.4. Для отражения технологической или ресурсной зависимости в выполнении операций применяют фиктивные операции. Если операции c может выполняться после завершения операций a и b, а операция d - только после завершения операции b, то зависимость представлена на рис. 2.5, из которого видно, что операция c следует за операцией a и фиктивной операцией (2,3). В свою очередь (2,3) следует за операцией b. Тогда в силу транзитивности выполнение операции b предшествует выполнению операции c. Построение сетевого графика начинается с составления списка операций (работ), подлежащих выполнению. Таблица 2.1 № п/п Работа Опирается на работы 1 2 3 4 5 6 7 8 9 10 а1 а2 а3 а4 а5 а6 а7 а8 а9 а10 --- а1, а2 --- а1, а2, а3 --- --- а1, а6, а10 а3 а7, а3, а8 а4, а5 а3 Последовательность операций в списке произвольная. Порядок нумерации операций осуществляется в соответствии с последовательностью их записи в списке. Перечень операций тщательно продумывается и в зависимости от конкретных условий с определенной степенью детализируется. Операции, включенные в список, характеризуются определенной продолжительностью, которая устанавливается на основе действующих нормативов или по аналогии с ранее выполнявшимися операциями. Такие временные оценки называются детерминированными. Если же нормативные данные временных оценок операций отсутствуют, то определяются вероятностные оценки. После составления списка операций приступают к процедуре построения сети. При построении сетевого плана важно правильно нумеровать события. Правильной называется такая нумерация, при которой начальное событие каждой работы имеет номер меньший, чем конечное. На графе это соответствует тому, что каждое ребро выходит из вершины с меньшим номером, чем та, в которую она заходит. Для получения правильной нумерации событий рекомендуется следующий порядок. Отыскивается исходное событие (т.е. вершина, в которую не входит ни одно ребро) и присваивается ему номер 1. Затем вычеркиваются все выходящие из этой вершины ребра и на оставшиеся части графа снова отыскивается вершина, в которую не входит ни одно ребро. Событию, соответствующему этой вершине, присваивается номер 2. Рассмотренные процедуры продолжаются до полного завершения нумерации. Если при очередном вычеркивании окажется, что не одна, а две и более вершин не имеют входящих в них ребер, то очередные номера этим событиям присваиваются произвольно. После нумерации событий каждая работа получает цифровое обозначение с помощью двух цифр, первая из которых указывает номер начального события, а вторая - номер конечного события. Построение сетевых графиков скоротечных комплексов операций, когда из-за недостатка времени нет возможности производить оптимизационные расчеты, осуществляется с учетом технологических и ресурсных ограничений. Построение графиков нескоротечных комплексов операций, когда достаточно времени для их исследования, выполняется лишь с учетом технологических ограничений. Такой подход обеспечивает минимальную продолжительность выполнения комплекса операций. После построения графика рассчитываются его временные параметры и производится оптимизация по ресурсам или другим показателям, для чего используются формальные методы оптимизации. Таким образом, сетевой график в терминах "дуги-операции" является наглядным средством отображения последовательности работ (операций) и событий, а также их взаимной связи. Для устранения неоднозначности и обеспечения удобства расчетов параметров (особенно с помощью ЭВМ) необходимо соблюдать специальные правила построения и нумерации вершин графа, представляющего собой сетевой график. 2.2 Расчет временных параметров сетевого графика Для управления ходом выполнения комплекса операций, представленного сетевой моделью, необходимо располагать количественными параметрами элементов сети. К таким параметрам относятся: продолжительность выполнения всего комплекса операций, сроки выполнения отдельных операций и их резервы времени. Важнейшим параметром сетевого графика является также критический путь. Различают следующие виды путей: полный, предшествующий событию, следующий за событием. Путь сетевого графика называется полным, если его начальная вершина совпадает с исходным событием, а конечная - с завершающим. Предшествующий событию путь - это путь от исходного события до данного. Следующий за событием путь есть путь от данного события до завершающего. Критическим называется полный путь, имеющий наибольшую продолжительность во времени. Операции и события, принадлежащие критическому пути, называются соответственно критическими операциями и критическими событиями. Суммарная продолжительность операций, принадлежащих критическому пути, равна критическому времени tкр выполнения комплекса операций в целом. На графике критический путь, как правило, выделяется жирной линией. Расчет параметров сетевого графика может осуществляться различными методами: расчет по формулам, вычисления непосредственно на сетевом графике, табличный и матричный методы. Расчет по формулам выполняется следующим образом. Пусть продолжительности выполнения операций (работ) tij известны и приписаны соответствующим дугам сетевого графика (рис. 2.6). Прежде всего определяются ожидаемые (ранние) сроки свершения события сетевого графика, т.е. моменты времени, раньше которых события не могут свершиться. При этом следует учитывать, что любое событие не может свершиться раньше того, как будут закончены (выполнены) все работы, входящие в него. Исходное событие означает момент начала выполнения комплекса операций, следовательно, =0. Событие (2) свершится, очевидно, спустя 2 ед. времени после свершения события (1), так как время выполнения операции (1,2) равно 2. Следовательно, = +t12 = 0 + 2 = 2. Событию (3) предшествуют два пути: µ1=(1-3) и µ2= (1-2-3). Продолжительность первого пути равна 1 единицу времени, а второго 2 ед. времени, так как t12 + t23 = 2 + 0 = 2. Продолжительность второго пути можно найти добавлением к ожидаемому сроку свершения события (2) времени выполнения операции (2,3), т.е. + t23 = 2+ 0 = 2. Поскольку событие (3) может свершиться не раньше момента окончания всех входящих в него операций, то = max ( + t13; + t23) = max (0+1; 2+0) = 2. В событие (4) входят две дуги, исходящие из событий (1) и (3), для которых ожидаемые сроки свершения найдены. Следовательно, ожидаемый срок свершения события (4) = max ( + t14; + t34) = 2. Аналогично находятся ожидаемые сроки свершения событий (5), (6) и (7). Значения , i=1,…,7 приписаны соответствующим событиям на рис. 2.6. Общую формулу для нахождения ожидаемых сроков свершения событий можно записать так: = 0; = ( + tij), j = 2,3,...,n где G+ - подмножество дуг сети, входящих в событие (j). Ожидаемый срок свершения события (7) = 11 совпадает с критическим временем (суммарной продолжительностью операций, принадлежащих критическому пути). Возвращаясь теперь от завершающего события к исходному, можно выделить операции, принадлежащие критическому пути. Из трех операций, входящих в событие (7), tкр=11 определила операция (5,7), выполнение которой начинается после свершения события (5) и продолжается три единицы времени ( + t57 = 8 + 3 = 11). Момент свершения события (5) определила операция (3,5), так как + t35 = 2 + 6 = 8. В свою очередь момент свершения события (3) определила операция (2,3), а события (2) - операция (1,2). Эти операции на графике рис. 2.5 выделены жирной линией. Таким образом, критический путь µкр = ( 1-2-3-5-7 ). Увеличение времени выполнения любой операции, принадлежащей критическому пути, ведет к увеличению времени выполнения комплекса операций. Увеличение же времени выполнения или задержка с выполнением некритических операций может не отразиться на сроке свершения завершающего события. Например, время выполнения операции (4,5) может быть увеличено или начало ее выполнения может быть отсрочено на 1 ед. времени, и это не отразится на сроке свершения события (5), а следовательно, и всего комплекса операций. Начало выполнения операции (4,7) может быть отсрочено на 3 ед. времени. Отсюда следует, что для события (4), не лежащего на критическом пути, существует предельный (поздний) срок свершения. Если обозначить предельный срок свершения любого события сетевого графика через , и принять, что ожидаемый и предельный сроки свершения завершающего события (n) совпадают = , предельный срок свершения любого события сетевого графика равен минимальной разности между предельными сроками окончания операций, исходящих из данного события, и временем выполнения соответствующих операций. Нахождение предельного срока осуществляется по формуле: = ( -tij), i=1,2,3,...,n-1 где G- - подмножество дуг сети, исходящих из события (i). В примере = = 11. Этот показатель для оставшихся событий определяется следующим образом. Из события (5) исходит одна операция, следовательно, = - t57 = 11 - 3 = 8. Аналогично, = - t67 = 10. Из события (4) исходят три операции, поэтому = min( - t45; - t46; - t47) = min (8-3; 10-1; 11-4) = 5. Аналогично = 2, = 2 и = 0 ( на рис. 2.6 предельные сроки свершения событий указаны в скобках). Для критических событий эти сроки совпадают с ожидаемыми. Некритические события имеют резервы времени, которые показывают, на какой предельно допустимый срок может задержаться свершение событий без изменений срока свершения завершающего события. Резерв времени Ri события (i) равен разности между предельным и ожидаемым сроком его свершения: Ri = - . Ожидаемые и предельные сроки свершения событий находятся в диалектическом единстве со сроками начала и окончания операций: 1. Ранний срок начала выполнения операции (i,j) равен ожидаемому сроку свершения (i)-го события =; 2. Поздний срок окончания операции совпадает с поздним сроком свершения ее конечного события = ; 3. Поздний срок начала выполнения операции равен разности между предельным сроком свершения ее конечного события и продолжительностью = (- tij); 4. Ранний срок окончания операции равен сумме ожидаемого срока свершения ее начального события и продолжительности = + tij. Сроки выполнения операций находятся в границах, определяемых параметрами: , , , . Следовательно, операции, как и события, могут иметь некоторый резерв времени. Различают четыре разновидности резервов времени операций: • полный, • свободный, • частный первого вида • частный второго вида. Полный резерв времени операции показывает, на сколько можно сдвинуть начало выполнения операции или увеличить ее продолжительность, не изменяя ожидаемого срока свершения начального события, при условии, что конечное для данной операции событие свершится не позднее своего предельного срока. Величина полного резерва времени вычисляется по формуле = - (+ tij) = - . Свободный резерв времени операции показывает, на сколько можно увеличить продолжительность или отсрочить начало выполнения операции (i,j) при условии, что начальное и конечное ее события свершаются в ожидаемое время: = - ( + tij) = - . Частный резерв времени первого вида - это запас времени, которым можно располагать при выполнении операции (i,j) в предположении, что начальное и конечное ее события свершаются в предельные сроки: = - ( + tij) = - . Частный резерв времени второго вида - это запас времени, которым можно располагать при выполнении операции (i,j) в предположении, что ее начальное событие свершится в предельное, а конечное - в ожидаемое время. Для некоторых операций интервал времени между предельным сроком свершения начального события и ожидаемым сроком свершения конечного события может быть меньше их продолжительности. В этом случае принимается равным нулю. Определяется частный резерв времени второго вида по формуле: = max( - - tij; 0). Резервы времени операции (4,6) сетевого графика (рис.2.6) определяются как = - ( + t46) = 10 - (4+1) = 5; = - ( + t46) = 5 - (4+1) = 0; = - ( + t46) = 10 - (5+1) = 4; = max( - - t46; 0) = (5-5-1; 0) = 0. Таким образом, расчет временных параметров сетевого плана позволяет определить минимально возможную продолжительность всего комплекса работ (сумм работ, составляющих критический путь) и те работы, длительность которых может быть увеличена для сокращения затрат на их выполнение. Кроме того, могут быть определены те работы, сокращение длительности выполнения которых (за счет привлечения дополнительных средств) позволит уменьшить общее время выполнения всего комплекса работ. 2.3 Учёт неопределённости при сетевом планировании Неопределенность при сетевом планировании возникает в том случае, когда продолжительность операций (работ) не удается определить точно, а имеются лишь вероятностные оценки tij. При этом сетевой график имеет вероятностную (стохастическую) структуру. Стохастическая структура означает, что все операции включаются в сеть с некоторой вероятностью. Например, в научно-исследовательских и опытно-конструкторских разработках не известны не только продолжительность отдельных операций, но и их перечень, а также структура сети. Расчет параметров и анализ сетей случайной структуры связан с известными трудностями. Поэтому на практике обычно применяются детерминированные сети со случайными временными оценками операций. Такие сети называются вероятностными. При исследовании вероятностных сетей могут встретиться два случая: 1) операции не являются новыми, и приближенно известна для каждой из них функция распределения продолжительности выполнения; 2) операции являются новыми, малоизученными, и для них функции распределения продолжительностей неизвестны. В первом случае по известной функции распределения можно определить среднее значение продолжительности выполнения каждой операции (математическое ожидание) и дисперсию. Во втором случае применяется метод усреднения. Исходными данными для метода ускорения являются вероятностные оценки продолжительности каждой операции: tijmin - минимальная продолжительность (оптимистическая оценка) операции; tijmax - максимальная продолжительность (пессимистическая оценка) операции; tijНВ - наиболее вероятная продолжительность (мода) операции. Эти оценки времени задаются ответственным исполнителем или группой экспертов. Исследования, проведенные в нашей стране и за рубежом, позволили обосновать возможность использования бета - распределения в качестве типового распределения продолжительности операций с оценками a, b и m. Функция плотности бета -распределения (рис. 2.7) имеет вид Рис.2.7 f(t) = C(t-a)p (b-t)q для aW , то W . В том случае, когда на (N-1) -м ярусе все возможные решения исчерпаны, то осуществляется пере­ход на (N-2) -й ярус и анализируется возможность и целесооб­разность ветвления. Возможность определяется структурой дерева, а целесообразность - путем сравнения нижней границы решения F(X) с величиной W*. Если ветвление возможно и W(Х)1), верхняя граница определяется по каждому из ограничений отдельно. При этом используются выражения, аналогичные (3.16) – (3.18). Верхняя граница определяется из условия (3.20) где определяется с помощью выражения, аналогичного выражению (3.17). Выбор очередной переменной для включения в множество S производится с помощью условия (3.21) где . Особенность заключается в том, что в многомерных задачах возможен вариант, когда . В этом случае в множество S включается , т. е. =0. Рассмотрим особенности решения задачи с несколькими ограничениями (К>i) на простом примере. Требуется определить вектор , обеспечивающий при ограничениях: . Исходные данные для расчета приведены в таблице 3.4. Таблица 3.4 i 1 2 3 4 5 6 7 8 9 10 Ci 6 4 5 6 4 8 6 2 3 1 d1i 3 4 1 2 1 4 3 2 3 1 d2i 1 1 5 2 2 4 6 1 3 1 h1i 2 1 5 3 4 2 2 1 1 1 h2i 6 4 1 3 2 2 1 2 1 1 На первом шаге . Для каждого из ограничений рассчитываем =23, =22. Значит, наиболее жестким ограничением является второе ограничение и . Из условия (1.30) следует, что xr = x1. Отдельно по каждому из ограничений рассчитываем =23, =23, =22, =18. Следовательно, =22, =18. Так как >, то в множество S включаем х1=1. На втором шаге . Рассчитав =22 и выбрав xr = x2 (М=2), определяем =15, =23, =22, =20. Следовательно, =15, =20. Так как >, то в множество S включаем =0. Аналогичным образом выполняются расчеты на всех последующих шагах, результаты которых приведены в таблице 3.5. Вычислительный процесс иллюстрируется рисунком 3.10, на котором представлено дерево возможных вариантов. На шестом шаге и - первое приближенное решение. Так как для всех оставшихся ветвей выполняются условия и , то полученное решение является оптимальным. Таким образом, рассмотренный алгоритм может быть использован для решения как одномерных, так и многомерных задач целочисленного программирования. Алгоритм сравнительно прост, позволяет учитывать на каждом шаге оптимизации жесткость каждого из ограничений и обеспечивает высокую точность оценки верхней границы целевой функции. 3.6 Решение линейных целочисленных задач Рассмотрим следующую задачу. Требуется определить вектор , обеспечивающий (3.22) при ограничениях ; (3.23) , (3.24) где . При решении задачи (3.22) – (3.24) методом ветвей и границ условие целочисленности (3.24) заменяется условием . (3.25) Для рассмотрения алгоритма решения задачи введем обозначения: - множество индексов n-переменных основной задачи; В – множество индексов базисных переменных, полученных при решении задачи (3.22), (3.23), (3.25); Z=U\В – множество свободных переменных; S – множество индексов переменных, включенных в S-частичное решение задачи методом ветвей и границ; S1 – множество переменных, вошедших в S-частичное решение задачи методом ветвей и границ. - верхняя граница решения, полученная при включении в множество S1 переменной xn. Для решения задачи (3.22), (3.23), (3.25) могут быть различные методы, например, симплекс-метод. Однако для сокращения времени определения границ целесообразно использовать метод обратных матриц (МОМ). Решение задачи (3.22) – (3.249) включает: определение оптимального значения целевой функции С(Х) и соответствующего , полученных при решении задачи (3.22), (3.23), (3.25) с помощью МОМ. Найденное значение С(Х) представляет собой верхнюю границу истинного целочисленного значения, поскольку при выполнении условия (3.24) значение целевой функции может лишь уменьшиться. На основании признака оптимальности МОМ , а для . Величина Δn представляет собой оценку n-ой переменной, а разрешающий вектор совпадает с оптимальным решением двойственной задачи по отношению к задаче (3.22), (3.23), (3.25). ТЕОРЕМА. Величина является верхней границей при ветвлении свободных переменных. ДОКАЗАТЕЛЬСТВО. Пусть задано оптимальное решение двойственной по отношению к (2.17), (2.18), (2.20). Тогда верхняя граница при включении в S-частичное решение xn определяется выражением: ; . На основании первой теоремы двойственности , а по определению . Тогда . Теорема доказана. Из теоремы следует, что при решении задач (3.22) – (3.24) ветвление следует начинать со свободных переменных и в порядке убывания их оценок, т. е. первой рассматриват переменную xm, имеющую . При ветвлении базисных переменных хn() верхняя граница решения определяется решением МОМ следующей задачи линейного программирования: (3.26) при ограничениях (3.27) , (3.28) где Для отсечения бесперспективных вариантов используется условие , где С0 – значение достигнутого рекорда. Таблица 3.6 N K tp[C] Mn M0 Lp Алг 1 Алг 2 Алг 1 Алг 2 Алг 1 Алг 2 Алг 1 Алг 2 10 1 2 3 4 5 0,74 0,76 1,15 3,22 3,14 1,38 4,53 3,11 6,44 10,75 475 858 350 879 571 475 815 325 652 402 233 523 229 466 382 233 515 211 389 469 194 127 318 234 239 349 467 511 648 20 1 2 3 4 5 1,21 4,78 5,09 13,33 37,30 5,77 18,86 36,21 90,16 94,83 1359 3111 1585 2464 5408 1359 3800 1485 5400 3898 839 1588 1283 2016 4482 879 1064 1158 3492 4256 753 562 1235 2493 887 2198 3289 4931 5630 30 1 2 3 1,63 5,32 16,80 26,57 97,94 116,79 3761 6744 8403 3761 8544 8751 2603 7650 8665 2611 6650 7673 898 534 2640 5993 7062 В таблице 3.6. приведены результаты вычислительного эксперимента решения задачи (3.22) – (3.24), проведенного на ЭВМ ЕС-1045. При этом сравнивались результаты двух алгоритмов. Алгоритм 1 – в соответствии рассмотренным выше порядком. Алгоритм 2 – ветвление осуществлялось в порядке номеров переменных, а нижняя граница в каждом случае определялась путем решения задачи (3.22), (3.23), (3.25) с учетом включенных в множество S1 переменных. В качестве характеристик алгоритмов использовались средние значения времени решения задачи – tp, числа просмотренных Мn, отсеченных М0 вершин и числа линейных задач lр. Данные для задач моделировались следующим образом Сn, akn () – как независимые целые случайные числа, равномерно распределенные в диапазоне [1,100], правые части ограничений вычислялись по формуле . Результаты экспериментального исследования алгоритмов, полученные путем решения десяти задач различной размерности, показывают, что время решения задачи по алгоритму 2 в 18-42 раза меньше, чем алгоритма 1. Уменьшение времени решения объясняется уменьшением в 1,4 – 40 раз числа решений линейной задачи. Незначительное увеличение числа просмотренных вершин дерева ветвления свидетельствует о достаточно точном определении границ решения с помощью оценок свободных переменных. 4 Задачи теории расписаний 4.1 Предмет и классификация задач теории расписаний Необходимость планирования и управления сложными процессами, включающими большое число взаимосвязанных работ, требующих многочисленных исполнителей, привела к разработке календарных планов или расписаний. Основная цель теории расписаний – разработка календарных планов функционирования исследуемой системы с указанием сроков выполнения отдельных работ по каждому исполнителю, который обеспечивает оптимальную последовательность их выполнения, наиболее полную загрузку оборудования и согласование по времени отдельных процессов. Так как основу расписаний составляют календарные планы, то в отечественной науке задачи теории расписаний называют задачами календарного планирования. Таким образом, предметом теории являются математические методы решения задач календарного планирования, представляющие собой временную увязку множества работ, выполняемых на заданном оборудовании, направленную на достижение заданной цели. Возникновение теории расписаний, как раздела исследования операций, относится к середине XX века. Но лишь с появлением ЭВМ и общим развитием методов дискретной оптимизации теория расписаний получила широкое развитие. В то время был сформулирован ряд задач, которые и составляют основу данной науки. Являясь разделом исследования операций, теория расписаний занимается изучением специфических моделей, имеющих место в оперативно-календарном планировании, и разработкой математических методов построения наилучших (оптимальных), в смысле заданного критерия эффективности календарных планов. В большинстве случаев модели, изучаемые в теории расписаний, могут быть отнесены к классу детерминированных. Это значит, что обстановка, в которой приходится разрабатывать план, полностью определена, т.е. четко известна цель и значения всех факторов. Но наряду с ситуациями такого рода в последнее время большое внимание уделяется исследованиям, в которых приходится принимать решения в условиях риска. Большой вклад в развитие теории расписаний внесли советские ученые Шкурба В. В., Михалевич В. С., Португал В. М. и др. В теории расписаний используются следующие понятия: операция – элементарная работа, подлежащая выполнению; машина – устройство для выполнения отдельных операций; система обслуживания – множество всех машин, предназначенных для выполнения операций. Операции и работы характеризуются временем tij – время выполнения операции по обработке j-го изделия на I-й машине. В зависимости от порядка обработки изделий машинами различают конвейерную систему обслуживания и систему с произвольным порядком обработки изделий. В конвейерной системе порядок обработки всех изделий одинаков, т.е. все изделия обслуживаются в одной и той же последовательности. В системе с произвольным обслуживанием последовательность обработки изделий машинами различна. При решении задач теории расписания наиболее часто используются следующие критерии: минимизация общей продолжительности обработки изделий; минимизация суммарного или максимального отставания сроков обработки изделий от заданных; минимизация простоев машин или межоперационных задержек изделий. Для учета экономических характеристик систем обслуживания используются: потери от запаздывания обработки изделий от заданных сроков; производственные затраты на выполнение операций и другие. Все задачи теории расписаний, с учетом особенностей, можно условно разделить на три группы задач: согласования, распределения и упорядочения. В задачах согласования основное внимание уделяется выбору длительности операций (работ) при заданном их распределении по машинам. Поэтому эти задачи часто называют задачами сетевого планирования и управления. В задачах распределения предполагается, что одна и та же машина может выполнять различные операции или их наборы. Необходимо определить в некотором смысле распределение операций между машинами. Простейшей из задач распределения является задача о назначениях (целераспределения). В задачах упорядочения распределения операций по машинам и длительность их выполнения предполагаются заданными. Необходимо указать эффективную стратегию управления подачи изделий на выполнение операций каждой машиной. Результатом решения задач является расписание, представленное в той или иной форме. Все формы представления расписаний могут быть разделены на три группы: графические, аналитические и табличные. Графическое представление позволяет наиболее наглядно изобразить исследуемый процесс. К данной форме представления относятся: графики Ганта, планировочные графики, сетевые графики и т.п. График Ганта (рис. 4.1.) представляет собой хронограмму занятости различных машин, механизмов, рабочих мест и т.д. Каждая операция на графике изображается масштабированным отрезком прямой, соответствующей длительности выполнения операции. Моменты начала и конца операций изображаются знаками ┌ и ┐. Рабочее место Время 1 2 3 4 5 6 7 8 9 10 11 12 № 1 № 2 Рис. 4.1 График Ганта Планировочный график (рис. 4.2) – это схематическое изображение процесса, состоящего из ряда операций. При построении планировочного графика каждой операции отводится отдельная строка, в которой указывается ее наименование, и проводится линия, соответствующая продолжительности операции. Как ни наглядны бывают формы графического представления расписаний, все они обычно сопровождаются и таблицами с численными характеристиками графиков. Во многих случаях табличное представление является общепринятым, в достаточной мере наглядным и не требующим дополнительных пояснений. № п/п Наименование операции (работы) НЕДЕЛИ 1 2 3 4 5 6 7 8 1 Изучение задания и подбор необходимой литературы 2 Обоснование проводимых исследований 3 Выбор показателей эффективности и разработка постановки задач 4 Разработка алгоритмов и программ 5 Экспериментальная проверка программ 6 Оформление пояснительной записки и чертежей Рис. 4.2. Пример планировочного графика выполнения курсовой (дипломной) работы В табл. 4.1. приведен пример расписания обработки изделий на двух рабочих местах. Таблица 4.1 № рабочего места № изделия 1 2 Начало Окончание Начало Окончание 1 2 3 4 1 3 7 1 3 7 9 1 3 7 15 3 6 15 17 Среди аналитических форм задания расписаний можно выделить форму задания с помощью вектора функции времени. Так, например, для задания расписания, представленного на рис. 4.1, достаточно задать вектор функции S(t) = {S1(t), S2(t)}, (где S1(t) – описывает загрузку рабочего места №1, S2(t) – рабочего места №2). Если Si(t) = 0 (i=1, 2), то значит, что i-е рабочее место в момент времени t простаивает, если же Si(t) = К (i=1, 2), то это значит, что i-е рабочее место выполняет операцию по обработке К-го изделия. Тогда вектор-функция для расписания, представленного на рис. 4.1, имеет вид Для решения задач теории расписаний используется большинство известных в настоящее время идей и методов оптимизации. Прогресс в развитии методов решения экспериментальных задач, эвристического программирования, моделирования и т. д. в той или иной мере оказал влияние и на развитие методов построения оптимальных расписаний. Все методы решения задач теории расписаний можно разделить на точные и приближенные. К точным методам относятся задачи линейного и целочисленного программирования, методы ветвей и границ и динамического программирования. Среди приближенных методов основную группу составляют эвристические методы, в той или иной мере отражающие опыт, накопленный в результате многократного построения расписаний в практически однотипных условиях. Несколько меньшее распространение получили методы статистического моделирования, позволяющие построить расписание, близкое к искомому, в результате некоторой совокупности случайным образом выбираемых расписаний. Таким образом, задачи теории расписаний включают в свой состав задачи согласования, распределения и упорядочения. Исходными данными для решения задач являются количество изделий и машин, длительность выполнения операций. Применяя точные и приближенные методы решения задач теории расписаний определяют оптимальные календарные планы, которые могут быть представлены в графической, табличной или аналитической форме. 4.2 Задачи теории расписаний при конвейерной обработке изделий Рассмотрим общую задачу теории расписаний, которая формулируется следующим образом. Имеется М машин для обработки N изделий. Каждое изделие должно пройти обработку на всех машинах в определенном порядке, причем каждая машина может выполнить только одну операцию. Одновременно на машине может обрабатываться только одно изделие, начатая обработка не может быть прервана, а последующая операция может начаться только после окончания предыдущей. Время обработки изделий на машинах задано матрицей . Необходимо пределить такую последовательность обработки изделий, при которой общее время обработки изделий было бы оптимальным. Сформулированная задача относится к задачам упорядочения и для ее решения могут применяться различные методы. Наиболее простой эффективный метод разработан для решения задачи при М=2 (алгоритм Джонсона). 4.2.1 Алгоритм Джонсона В основу алгоритма Джонсона положена идея минимизации времени простоя второй машины. Алгоритм Джонсона (рис. 4.3)включает: 1. Определение затрат времени , соответствующих обрабатываемым изделиям (где t1j – затраты времени на выполнение операции 1-й машиной c j-м изделием; t2j – то же второй машиной) (символ 1). 2. Если , то производится проверка, сколько изделий имеют одинаковое и равное t1 время выполнения операции на 1-й машине. При одном изделии оно включается в начало плана (после первых изделий, включенных в план). Если изделий больше одного, то в начало плана включается изделие, которое имеет меньшее время обработки на второй машине. Осуществляется переход к пункту 5 (символы 3, 9 - 11). 3. Если , то производится проверка, сколько изделий имеют одинаковое и равное t3 значение времени обработки на второй машине. При одном изделии оно включается в план перед последним, включенным в план. Если изделий больше одного, то включается в план перед последними изделие, имеющее меньшее время обработки на первой машине. Осуществляется переход к пункту 5 (символы 4, 13 - 15). 4. Если , то j-е изделие (соответствующее ti) ставится после первых включенных в начало плана, а К-е (соответствующее t2) перед последними включенными в конце плана (симолы 5,6). 5. Исключаются характеристики включенных в план изделий из множеств {t1j}, {t2k} (символ 7). 6. Повторение пунктов 1 – 5 до тех пор, пока не все изделия будут включены в план. Полученный план является оптимальным (символы 1, 8, 17). Рассмотрим работу алгоритма на примере решения задачи, исходные данные для которой приведены в таблице 4.2. . Минимальное значение . Так как , то 5-е изделие включается в план первым. Исключаем пятое изделие. , так как , то 6-е изделие включается в план 8-м, исключается 6-е изделие. , так как , то 7-е изделие ставится на втрое место, а 3-е на седьмое. Исключаются 3-е и 7-е изделия. . Имеются два изделия с временем обработки на первой машине, равным 5, так как 4-е изделие имеет меньшее время обработки на второй машине, то оно включается в план третьим. Исключается 3-е изделие. Таблица 4.2 Исходные данные Номер изделия j Время обработки на 1-й машине, t­1j Время обработки на 2-й машине, t2j 1 2 3 4 5 6 7 8 9 10 5 5 1 5 4 5 8 8 4 6 3 2 5 7 , 8-е изделие исключается и включается в план четвертым. , . Имеются два изделия с временем обработки на второй машине, равным 8, так как 1-е изделие имеет меньшее время обработки на первой машине, то оно ставится в план шестым и исключается. . Оставшееся второе изделие включается в план пятым. Определим последовательность обработки, составляется расписание обработки изделий на машинах. При этом момент окончания обработки j-го изделия на i-й машине определяется рекуррентным соотношением: , (4.1) где . Полученный план обработки изделий приведен в таблице 4.3. Таблица 4.3 Номер изделия j Машина 1 Машина 2 начало операции конец операции начало операции конец операции 5 7 4 8 2 1 3 6 1 5 10 15 25 34 39 1 5 10 15 25 34 39 44 1 5 10 15 25 34 42 46 4 10 14 22 30 42 46 48 Алгоритм Джонсона может быть использован и при обработке изделий на 3-х машинах, если выполняется условие или . (4.2) При выполнении одного из условий (4.2) оптимальная последовательность обработки определяется по суммам и . (4.3) Таким образом, алгоритм Джонсона позволяет решить задачу составления расписания обработки изделий на двух машинах. Решение же задачи для трех машин возможно только для определенных условий (4.2). Наиболее общим методом решения задач теории расписаний является метод ветвей и границ. 4.2.2 Алгоритм метода ветвей и границ При решении сформулированной общей задачи теории расписания методом ветвей и границ примем локально-избирательное ветвление, основанное на следующих предположениях. Так как общее число возможных вариантов построения плана равно N!, то на первом шаге рассматривается N вариантов, предполагающих, что первым будет стоять в плане 1,2,…, N изделие. На втором шаге, для лучшего решения, рассматривается N-1 вариант (без варианта, включенного первым), третьим N-2 варианта и т. д. Для рассмотрения способа ветвления введем обозначения: U – множество всех изделий; S – множество изделий, включенных в план; tнij(S), toij(S) время начала и окончания обработки множества изделий S, включенных в план на i-й машине. Очевидно ; (4.4) , (4.5) где S’ – множество изделий, включенных в план на предыдущем шаге; tij – элемент, включаемый во множество S; tно(0)=0; t0о(0)=0. Способ определения нижней границы определяется из следующих допущений: нижняя граница – H(S) определяется для каждой машины отдельно, причем предполагается, что простоев нет. Причем время обработки множества оставшихся изделий на оставшихся машинах U/S минимально и равно . (4.6) Тогда нижняя граница для каждой машины может быть определена как , (4.7) где toi(S) – время обработки S изделий на i-й машине, причем ti(0) = 0. Так как время окончания обработки j-го изделия определяется максимальным временем освобождения машин, то . (4.8) Исходя из сформулированных допущений, порядок решения задачи методом ветвей и границ, алгоритм которого приведен на рис. 4.4. и включает: 1. Задание начальных условий решения. Множества U, S=0; - шаг решения задачи (символ 1). 2. Изменение шага решения и последовательный просмотр всех изделий. Если изделие включено в множество S, то переход к следующему изделию, если нет, то к пункту 3. Если рассмотрены все изделия, то к пункту 6. (Символы 2 - 4). 3. Для каждой машины () по зависимостям (4.4.) – (4.7) вычисляются величины (символ 5). Определение нижней границы H(S) для данного изделия (символ 6). 4. Выбор изделия, имеющего минимальную нижнюю границу, и включение его в множество S. Переход к пункту 2 (символ 7). Таблица 4.4 Номер изделия Время обработки на машинах 1 2 3 1 2 3 4 5 3 2 5 3 8 3 2 8 3 2 6 7 3 2 4 5. Построение дерева решений и проверка, имеются ли висячие вершины с меньшим значением нижней границы, чем получено решение. Если нет, то полученное решение оптимально. В противном случае переход к следующему пункту (символы 8 - 10). 6. Выбор висячей вершины, имеющей минимальную нижнюю границу. Определение шага решений S и соответствующего множества S. Переход к пункту 2. (Символ 11). Рассмотрим алгоритм решения задачи на конкретном примере для 5-ти изделий и 4-х машин, исходные данные для которой приведены в таблице 4.4. Таблица 4.5 № шага № изделия 1 2 3 h1(S) h2(S) h3(S) H(S) S U\S tн1 t01 tN2 tн1 t02 t03 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 1 2 3 4 5 3 2 5 3 8 3 2 5 3 8 6 4 13 6 10 6 4 13 6 10 12 11 16 8 14 3+23 2+24 5+21 3+24 8+18 6+17 4+18 13+12 6+18 10+18 12+16 11+15 16+19 8+20 14+18 28 26 35 28 32 2 1-5 1,5 2 2 1 3 4 5 2 2 2 2 2 5 7 5 7 2 5 7 5 7 4 8 15 8 12 4 11 15 11 12 11 17 18 15 16 - 5+21 7+19 5+21 10+16 - 8+15 15+10 18+16 12+16 - 17+9 18+12 13+13 16+11 - 26 30 26 28 2,1 3-5 3 2 1 3 4 5 2 5 5 5 2 5 10 8 13 2 5 10 8 13 4 8 18 17 15 4 11 18 17 17 11 17 21 9 21 - - 10+16 8+19 13+13 - - 18+7 11+13 15+13 - - 21+6 19+7 21+5 - - 27 27 28 2,1,3 4,5 4 2 1 3 4 5 2 5 10 10 2 5 10 13 18 2 5 10 13 18 4 8 18 21 20 4 11 18 21 21 11 17 21 23 25 - - - 13+14 18+8 - - - 21+6 20+5 - - - 23+4 25+2 - - - 27 28 2,1,3,4 5 5 2 1 3 4 5 2 5 10 13 2 5 10 13 21 2 5 10 18 21 4 8 18 21 23 4 11 18 21 23 11 17 21 23 27 - - - - - - - - - - - - - - - - - - - - 2,1,3, 4,5 Процесс решения задачи представлен в табл. 4.5. Дерево решений представлено на рис. 4.5. Из анализа дерева вариантов решений следует, что имеется висячая вершина S={2,4}, для которой нижняя граница, равная 26, меньше полученного решения. Следовательно, начиная с 3 шага, для S={2,4} процесс решения повторяется. Решение приведено в табл. 4.6. Таблица 4.6 № шага № изделия 1 2 3 h1(S) h2(S) h3(S) H(S) S U\S tн1 t01 tN2 tн1 t02 t03 1 2 3 4 5 6 7 8 9 10 11 12 13 14 3 2 4 1 3 5 2 5 5 5 2 5 8 10 13 2 5 8 10 13 4 8 11 18 15 4 11 13 18 15 11 13 19 21 19 - - 8+19 10+17 13+17 - - 11+14 18+8 15+14 - - 19+7 21+10 19+9 - - 27 31 28 2,4 Из результатов, приведенных в табл. 4.6. следует, что полученное значение нижних границ не меньше полученного решения и в дальнейшем не может уменьшиться. Следовательно, решение, полученное на 5-м шаге табл. 4.6, является оптимальным планом. Таким образом, метод ветвей и границ позволяет решать общую задачу теории расписаний при конвейерной обработке изделий. При вычислении нижней границы решения предполагается, что простоев машин нет, а на оставшихся машинах суммарное время обработки минимальное. 4.3 Особенности решения задач теории расписаний при различном порядке обработки изделий В общем случае последовательность обработки изделий на машинах может быть различной. В этом случае каждое изделие должно дополнительно характеризоваться последовательностью обработки. Наиболее простой алгоритм решения задачи теории расписаний при различном порядке обработки изделий разработан для варианта с двумя машинами (модифицированный алгоритм Джонсона). Он включает: 1. Разбиение всего множества изделий на четыре подмножества: А – подмножество изделий, которые обрабатываются только на первой машине; В – подмножество изделий, которые обрабатываются только на второй машине; АВ –подмножество изделий, в которых первая операция выполняется на первой машине, вторая – на второй; ВА – подмножество изделий, в которых первая операция выполняется на второй машине, вторая – на первой. 2. Определение оптимальной обработки изделий отдельно для подмножеств АВ и ВА. Для поиска оптимальных планов используется алгоритм Джонсона. 3. Построение оптимального плана обработки всех изделий. При этом на первой машине первоначально обрабатываются изделия из подмножества АВ, затем А и в последнюю очередь ВА. На второй машине первоначально обрабатываются изделия из подмножества ВА, затем В и в последнюю очередь АВ. Последовательность обработки изделий из подмножеств А и В может быть произвольная. При числе машин больше двух для решения задачи может быть использован метод ветвей и границ. Применяются два подхода для оценки нижней границы решения. Первый подход. Для каждого изделия определяется длительность выполнения всех оставшихся операций Tj0 начала очередной, не включенной в расписание операции. Нижняя граница находится как . (4.9) Второй подход. Для каждой машины вычисляется общая длительность всех невключенных в расписание операций и минимально возможное время Tio начала выполнения очередной операции. Нижняя граница в этом случае находится из условия . (4.10) Первый подход эффективен, если имеются изделия, для которых общая длительность операций, не включенных в расписание, превышает аналогичную величину для других изделий. Второй подход используется в тех случаях, когда общая загрузка одной из машин значительно превосходит загрузку остальных машин. Метод ветвей и границ применим только для решения небольших задач. Очень часто для решения задач теории расписаний применяется метод, основанный на использовании различных правил предпочтения, определяющих выбор очередного изделия для включения в план. Наиболее часто используются следующие правила предпочтения: выбор операции с минимальной длительностью выполнения; выбор операции, относящейся к изделию с максимальной длительностью всех неупорядоченных операций; выбор операции, относящейся к изделию с минимальной длительностью выполнения всех неупорядоченных операций; равновероятный выбор очередной операции. Содержание Введение……………………………………………………………………….. 1.Транспортная задача линейного программирования………………............... 1.1 Постановка транспортной задачи…………………………………….. 1.2 Способы определения опорного плана транспортной задачи………. 1.3 Метод потенциалов…………………………………………………….. 1.4 Венгерский метод……………………………………………………..... 2. Сетевые модели оптимального планирования……………………………….. 2.1 Основные понятия сетевого планирования и управления. Построение сетевых планов……………………………………………………… 2.2 Расчет временных параметров сетевого графика……………………... 2.3 Учёт неопределённости при сетевом планировании…………………. 2.4 Оптимизация комплекса операций по времени………………………. 2.5 Оптимизация комплекса по стоимости………………………………… 3. Основы метода ветвей и границ………………………………………………. 3.1 Общая характеристика метода. Обобщенный алгоритм……………… 3.2 Способ ветвления в задачах дискретной оптимизации……………….. 3.3Применение метода ветвей и границ для решения задач целераспределения………………………………………………………………….. 3.4 Алгоритм ветвей и границ для решения одномерных линейных задач с булевыми переменными……………………………………….. 3.5 Особенности решения задач с булевыми переменными при нескольких ограничениях………………………………………………………... 3.6 Решение линейных целочисленных задач…………………………….. 4. Задачи теории расписаний…….. …………………………………………….. 4.1 Предмет и классификация задач теории расписаний………………… 4.2 Задачи теории расписаний при конвейерной обработке изделий……. 4.3 Особенности решения задач теории расписаний при различном порядке обработки изделий……………………………………………….. 3 4 4 6 9 12 18 19 24 28 31 33 39 39 42 46 56 63 68 71 71 76 84 Редактор Сидорова А.Д. Технический редактор Колюпанова С.А. Формат 6084/16. Подписано к печати 18.12.2008 г. Зак. 206. Объём: 5,06 усл. печ. л.; 4,85 уч.-изд. л. Типография ТАИИ