Содержание к диссертации
Введение
1. Задачи теории расписаний и сложность их решения 8
1.1. Формулировки задач 8
1.2. Алгоритмическая сложность решения задач 17
2. Построение циклических расписаний для производственной линии 26
2.1. Слоишость и свойства задач с различными критериями 27
2.2. Задача минимизации времени цикла с ограничением 34
2.3. Алгоритм для задачи минимизации времени цикла с ограничением 37
3. Аппроксимационные схемы решения задач . 53
3.1. Основные определения 53
3.2. Аппроксимационная схема для задачи минимизации времени цикла с ограничением 55
3.3. Аппроксимационная схема для задачи о поставках продукции с одним потребителем 57
4. Задача построения расписания для производственной системы открытого типа 72
4.1. Исследование структуры оптимальных решений 72
4.2. Модель целочисленного программирования и ее свойства 95
Заключение 103
Список использованной литературы 105
- Алгоритмическая сложность решения задач
- Слоишость и свойства задач с различными критериями
- Аппроксимационная схема для задачи о поставках продукции с одним потребителем
- Исследование структуры оптимальных решений
Введение к работе
На многих предприятиях производство представляет собой сложный технологический процесс, для управления которым требуется решать большое число задач эффективного распределения ресурсов и построения расписаний. В связи со сложностью рассматриваемых задач при принятии решений целесообразно использовать модели и методы системного анализа, исследования операций и оптимизации. Изучению таких задач и построению алгоритмов их решения посвящены [4,6,8,14,19,31,32,34,53,58,64] и другие работы.
В последние годы значительное внимание уделяется составлению циклических расписаний [44,56,70], которые часто используются в производственных системах в силу их простоты и удобства применения. Сложность задач построения циклических расписаний исследовалась в [55,56,60,63,65,70]. В силу трудности большинства таких задач основное внимание исследователей уделяется построению приближенных и эвристических алгоритмов. Такие алгоритмы предлагаются в [38,40,44,68]. С другой стороны, в [56,70] разработаны точные алгоритмы решения задач, основанные на методе ветвей и границ.
Исследование задач построения расписаний для классических производственных систем, например, систем открытого типа, также представляет большой научный интерес ввиду их широкой известности и практической важности [29,43].
Среди методов получения оптимальных решений задач построения расписаний следует выделить метод динамического программирования [2], метод ветвей и границ [43,56,70], различные алгоритмы комбинаторного характера [4,31,32,53,59].
При разработке методов решения задач теории расписаний важную роль играют свойства оптимальных решений, на основе которых поиск оптимального решения можно вести на сужении множества до-
пустимых решений. Данный подход применяется к задаче построения расписания в производственной системе открытого типа [37,41].
Другим перспективным направлением является сведение задачи построения расписания к задаче целочисленного линейного программирования (ЦЛП). Этот подход используется, например, в [44,56]. В ряде известных методов решения задач ЦЛП применяется сведение исходной задачи к последовательности задач непрерывной оптимизации. На этом подходе основаны алгоритмы отсечения [3,11,34,35], декомпозиции [39], перебора L-классов [12], методы ветвей и границ [15,34].
Алгоритмическая сложность решения задач
Под массовой задачей (или просто задачей) мы будем понимать некоторый общий вопрос, на который следует дать ответ. Обычно задача содержит несколько параметров, или свободных переменных, конкретные значения которых не определены. Задача П определяется следующей информацией: (1) общим списком всех ее параметров, (2) формулировкой тех свойств, которым должен удовлетворять ответ или, другими словами, решение задачи.
Индивидуальная задача I получается из массовой задачи 77, если всем параметрам задачи П присвоить конкретные значения.
Под алгоритмом будем понимать общую, выполняемую шаг за шагом процедуру решения задачи. Для определенности можно считать ее программой для ЭВМ, написанной на формальном машинном языке. Будем говорить, что алгоритм решает массовую задачу П, если он применим к любой индивидуальной задаче І Є П и обязательно дает ее решение.
Вообще говоря, нам нужен "эффективный" алгоритм для решения задачи. В самом широком смысле понятие эффективности связано со всеми вычислительными ресурсами, необходимыми для работы алгоритма. Однако обычно под "самым эффективным" алгоритмом понимается самый быстрый. Поскольку ограничения по времени часто являются доминирующим фактором, определяющим пригодность конкретного алгоритма для практики, основное внимание мы сосредоточим главным образом на этом виде ресурсов.
Время работы алгоритма удобно выражать в виде функции одной переменной, характеризующей размер индивидуальной задачи, то есть объем входных данных, требуемых для описания этой задачи. Такой подход удобен, поскольку в дальнейшем сравнительная сложность задач будет оцениваться через их размеры.
Для этого обратим внимание на то, что описание индивидуальной задачи, которое мы даем в терминах входа для ЭВМ, можно рассматривать как одну конечную цепочку (или слово) символов, выбранных из конечного входного алфавита. Невзирая на то, что существуют различные пути описания данной индивидуальной задачи, предположим, что заранее выбран некоторый определенный способ и что с каждой массовой задачей связана некоторая фискированная схема кодирования, которая отображает индивидуальные задачи в соответствующие цепочки символов. Входная длина индивидуальной задачи / Є П определяется как число символов в цепочке, полученной применением к задаче / схемы кодирования для массовой задачи П, и обозначается L(I). Именно это число, то есть входная длина, и используется в качестве формальной характеристики размера индивидуальной задачи.
Временная сложность алгоритма отражает требующиеся для его работы затраты времени. Это функция, которая каждой входной длине п ставит в соответствие максимальное (по всем индивидуальным задачам длины п) время, затрачиваемое алгоритмом на решение индивидуальных задач этой длины.
Разные алгоритмы имеют различную временную сложность, и выяснение того, какие алгоритмы "достаточно эффективны", а какие "совершенно неэффективны", всегда будет зависеть от конкретной ситуации. Однако теоретики, занимающиеся разработкой и анализом алгоритмов, предлагают для сравнения эффективности алгоритмов один простой подход, позволяющий существенно прояснить ситуацию. Речь идет о различии между полиномиальными и экспоненциальными алгоритмами.
Будем говорить, что функция f(n) есть 0(д(п)), если существует константа с, такая, что \f(n)\ с\д(п)\ для всех значений п 0. Полиномиальным алгоритмом (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность равна 0(р(п)), где р(п) - некоторая полиномиальная функция, а п -входная длина. Алгоритмы, временная сложность которых не поддается подобной оценке, называются "экспоненциальными". Различие между двумя указанными типами алгоритмов становится особенно заметным при решении задач большого размера.
Массовая задача П называется полиномиально разрешимой, если существует полиномиальный алгоритм ее решения. Класс всех полиномиально разрешимых задач обозначается через Р.
Множество всех массовых задач включает в себя не только полиномиально разрешимые, но и более трудоемкие задачи, в том числе и такие, для которых вообще не существует алгоритмов решения (10 проблема Гильберта о разрешимости диофантовых уравнений).
Чтобы ограничить это множество реально решаемыми задачами, рассматривалась модель вычислительного устройства с "оракулом" (недетерминированная машина Тьюринга). Класс задач, полиномиально разрешимых на недетерминированной машине Тьюринга, обозначается через NP. Этот класс очень широк и содержит фактически все прикладные задачи. Очевидно, что Р С NP.
Рассмотрим основные положения теории iVF-полных задач. Из соображений удобства эта теория строится только для задач распознавания свойств. Такие задачи имеют только два возможных решения - "да" или "нет". Выражаясь абстрактно, задача распознавания П состоит просто из двух множеств: множества Dn всех возможных индивидуальных задач и множества Yn (Yn Є Dn) индивидуальных задач с ответом "да".
Стандартная форма, которая применяется для описания задач, состоит из двух частей. В первой части дается описание условия задачи в терминах различных компонент - множеств, графов, функций, чисел и так далее. Во второй части в терминах условия формулируется вопрос, предполагающий один из двух ответов - "да" или "нет". Это описание определяет множества Yn и Dn очевидным образом. Индивидуальная задача принадлежит Dn в том и только в том случае, когда она может быть получена из стандартной формы описания подстановкой конкретных значений во все компоненты условия. Индивидуальная задача принадлежит Yn в том и только в том случае, когда ответом на вопрос задачи будет "да".
Слоишость и свойства задач с различными критериями
Рассмотрим задачу построения циклического расписания для производственной линии, состоящей из т различных машин. На этой линии необходимо произвести большую партию однотипных деталей. Все детали проходят одинаковый технологический маршрут обработки, состоящий из п операций. Операция,; требуетpj 6 Z+ единиц времени выполнения на машине rrtj (j = 1,... , п). Машины в технологическом порядке могут повторяться. На машине не может одновременно выполняться более одной операции. Прерывания в выполнении операций недопустимы.
Дадим определение циклического расписания. Обозначим через t(j; к) время начала выполнения j-ой операции А:-ой детали. Расписание является циклическим, если для любого j = 1,... ,п и для любого к Є Z выполняется t(j; к) = t(j; к — 1) + С или t(j; к) = tj + Ск, где tj = t(j; 0) и С - время цикла или циклическое время. Циклическое расписание определяется заданием времени начала выполнения каждой операции для одной из деталей. Для определенности будем искать значения tj (j = 1,..., /і).
Кроме времени цикла, введем еще две характеристики циклического расписания. Это F - время нахождения детали в системе, то есть промежуток времени между началом выполнения первой операции детали и завершением выполнения последней операции этой детали, и h - число одновременно обрабатываемых деталей, то есть максимальное число деталей, одновременно находящихся в обработке.
Рассмотрим следующие варианты задач построения циклического расписания: 1) минимизация циклического времени С; 2) одновременная минимизация С и F; 3) минимизация F при ограниченном С; 4) минимизации С при ограниченном h.
Задача построения циклического расписания с критерием минимизации времени цикла полиномиально разрешима [44]. Минимальное время цикла при этом равно Идея алгоритма проста. Начинаем укладывать операции в порядке, установленном технологией обработки детали, пытаясь уложить их тогда, когда освобождается нужная машина. Если при этом нарушается отношение предшествования операций, то передвигаем выполнение текущей операции вперед на время, равное С . Очевидно, что по построению полученное расписание является циклическим со временем цикла, равным С . Недостаток циклического расписания с минимальным временем цикла в том, что выполнение детали растягивается на долгое время. Это требует транспортировки и хранения незавершенных деталей, большей потребности в оборотных ресурсах. В [24] построен класс примеров, в которых время F нахождения детали в системе очень большое, причем незначительное увеличение времени цикла приводит к существенному уменьшению F. Рассмотрим этот класс. Для изготовления детали нужно выполнить 2г операций, причем нечетные операции выполняются на машине 1, а четные операции под номерами 2к выполняются на машинах к, где г Очевидно, что минимальная длина цикла равна г. В этом случае наименьшее время нахождения детали в системе равно F = 2г -\ P2r, г а время реальной обработки равно г + р2Г. Видно, что F отлича-ется от времени реальной обработки почти на г единиц. То есть при большом количестве операций эта разница уже существенна. г Увеличим время цикла незначительно на величину р2к 1. То К л. гда Ci = r+ P2r ,F\ = г+ p2k- Можно заметить, что F отличается от F\ чуть менее, чем на г, то есть незначительное увеличение времени цикла вызвало большой скачок во времени нахождения детали в системе. Этот пример показывает, что стремление к наибольшей производительности вызывает порой большой проигрыш во времени нахождения детали в системе. Недостаток циклического расписания с минимальным временем цикла в том, что детали при выполнении часто простаивают. Таким образом, кроме производительности линии, це лесообразно рассматривать и другие критерии.
Аппроксимационная схема для задачи о поставках продукции с одним потребителем
Обратимся к случаю 3x3. Найдем, сколько фактор-классов критических путей имеется в этом случае. Рассмотрим всевозможные комбинации вхождения операций в критический путь. Этих комбинаций 29 — 1 = 512 — 1 = 511, так как каждая операция либо входит в критический путь, либо не входит, а случай, когда ни одна операция не выбрана, нас не интересует. Далее по вышеуказанному отношению эти комбинации разбиваются на фактор-классы. Получаем, что их всего 25. Они все представлены в таблице, где номер фактор-класса - это наименьшая по величине добавка А, встречающаяся среди элементов этого фактор-класса. Это удобно, так как есть взаимно однозначное соответствие между фактор-классом и номером фактор-класса.
Очевидно, классы путей, определяемые конфигурациями под номерами 1, 3 и 10, не определяют критический путь, так как длины этих путей меньше нижней границы общего времени обслуживания, что невозможно для критического пути.
Классы путей, определяемые конфигурациями под номерами 14, 78, 84, 85, 118, также не определяют критический путь, так как в графе критических путей комбинаций таких путей нет.
Следовательно, остается 17 фактор-классов, элементы которых могут быть критическими путями, но, оказывается, среди них можно выделить те фактор-классы, представители которых никогда не будут доминировать другие оптимальные критические пути.
Будем говорить, что критический путь обладает свойством недоминируемости, если существует вход задачи, для которого данный критический путь является недоминируемым оптимальным критическим путем.
Свойство недоминируемости того или иного критического пути или отсутствие этого свойства распространяется на весь фактор-класс, содержащий конфигурацию этого критического пути.
Доказательство: Заметим, что для эквивалентных критических путей множества входов, для которых они являются оптимальными, совпадают. Пусть к - критический путь и / - множество входов, для которых он является оптимальным. Пусть для любого входа из / он доминируется каким-то другим. Обозначим через К фактор-класс, содержащий критический путь к. Докажем, что все критические пути из фактор-класса К также доминируются каким-то критическим путем из множестве /. Предположим, что для некоторого входа і существует недоминируемый критический путь к Є К. Произведем перенумерацию приборов и требований таким образом, чтобы новый критический путь совпал с к. Получаем, что для входа і критический путь к недоминируемый, что противоречит условию.
Это означает, что если мы докажем свойство недоминируемости или его отсутствие для какого-то критического пути, то тем самым мы докажем свойство недоминируемости или его отсутствие для любого эквивалентного данному критического пути.
В силу утверждения 4.1 отсутствие недоминируемости фактор-класса будем доказывать путем доказательства отсутствия недоминируемости для какого-нибудь элемента из этого фактор-класса, причем доказываем для тех входов задачи, для которых существует оптимальное расписание с таким критическим путем.
Заметим, что если длительности операций таковы, что всевозможные их суммы различны, то это означает, что все расписания с различными критическими путями (с точностью до последовательности операций в них) различны по длине. Поэтому конфигурация критического пути в оптимальном расписании единственна. Очевидно, этот критический путь и будет недоминируемым.
Утверждение 4.2. Рассмотрим задачу с различными по длине критическими путями. Пусть I- множество входов этой задачи, 1\ -множество входов обычной задачи (то есть входов задачи, не обладающих свойством различия критических путей по длине). Пусть М - множество тех классов критических путей, которые могут быть оптимальными для задачи с различными по длине критическими путями, М\- множество классов недоминируемых критических путей для обычной задачи. Тогда М = М\.
Доказательство. Очевидно, что I С 1\. Поэтому М С М\. Докажем, что М\ С М. Рассмотрим произвольный вход обычной задачи г. Пусть к Є М\. Докажем, что к 6 М. Если г I, то с помощью добавления к длительности каждой операции соответствующей степени двойки получаем задачу, в которой все критические пути различны по длине. В результате решения этой задачи получим оптимальное расписание с критическим путем к\, принадлежащем множеству М.
Очевидно, что это расписание остается допустимым и оптимальным и при переходе к прежним длительностям, причем к\ - недоминируемый критический путь и для обычной задачи. Получается, что мы нашли еще один недоминируемый критический путь для обычной задачи, а это означает, что с точностью до последовательности операций критические пути к и к\ совпадают. Поэтому М\ сМи М = М\.
В предположении, что все критические пути различны по длине покажем, что представители некоторых классов критических путей доминируются какими-нибудь другими критическими путями.
Исследование структуры оптимальных решений
Обратимся к случаю 3x3. Найдем, сколько фактор-классов критических путей имеется в этом случае. Рассмотрим всевозможные комбинации вхождения операций в критический путь. Этих комбинаций 29 — 1 = 512 — 1 = 511, так как каждая операция либо входит в критический путь, либо не входит, а случай, когда ни одна операция не выбрана, нас не интересует. Далее по вышеуказанному отношению эти комбинации разбиваются на фактор-классы. Получаем, что их всего 25. Они все представлены в таблице, где номер фактор-класса - это наименьшая по величине добавка А, встречающаяся среди элементов этого фактор-класса. Это удобно, так как есть взаимно однозначное соответствие между фактор-классом и номером фактор-класса.
Очевидно, классы путей, определяемые конфигурациями под номерами 1, 3 и 10, не определяют критический путь, так как длины этих путей меньше нижней границы общего времени обслуживания, что невозможно для критического пути.
Классы путей, определяемые конфигурациями под номерами 14, 78, 84, 85, 118, также не определяют критический путь, так как в графе критических путей комбинаций таких путей нет. Следовательно, остается 17 фактор-классов, элементы которых могут быть критическими путями, но, оказывается, среди них можно выделить те фактор-классы, представители которых никогда не будут доминировать другие оптимальные критические пути. Определение 4.4. Будем говорить, что критический путь обладает свойством недоминируемости, если существует вход задачи, для которого данный критический путь является недоминируемым оптимальным критическим путем. Утверждение 4.1. Свойство недоминируемости того или иного критического пути или отсутствие этого свойства распространяется на весь фактор-класс, содержащий конфигурацию этого критического пути.
Доказательство: Заметим, что для эквивалентных критических путей множества входов, для которых они являются оптимальными, совпадают. Пусть к - критический путь и / - множество входов, для которых он является оптимальным. Пусть для любого входа из / он доминируется каким-то другим. Обозначим через К фактор-класс, содержащий критический путь к. Докажем, что все критические пути из фактор-класса К также доминируются каким-то критическим путем из множестве /. Предположим, что для некоторого входа і существует недоминируемый критический путь к Є К. Произведем перенумерацию приборов и требований таким образом, чтобы новый критический путь совпал с к. Получаем, что для входа і критический путь к недоминируемый, что противоречит условию.
Это означает, что если мы докажем свойство недоминируемости или его отсутствие для какого-то критического пути, то тем самым мы докажем свойство недоминируемости или его отсутствие для любого эквивалентного данному критического пути.
В силу утверждения 4.1 отсутствие недоминируемости фактор-класса будем доказывать путем доказательства отсутствия недоминируемости для какого-нибудь элемента из этого фактор-класса, причем доказываем для тех входов задачи, для которых существует оптимальное расписание с таким критическим путем.
Заметим, что если длительности операций таковы, что всевозможные их суммы различны, то это означает, что все расписания с различными критическими путями (с точностью до последовательности операций в них) различны по длине. Поэтому конфигурация критического пути в оптимальном расписании единственна. Очевидно, этот критический путь и будет недоминируемым.
Утверждение 4.2. Рассмотрим задачу с различными по длине критическими путями. Пусть I- множество входов этой задачи, 1\ -множество входов обычной задачи (то есть входов задачи, не обладающих свойством различия критических путей по длине). Пусть М - множество тех классов критических путей, которые могут быть оптимальными для задачи с различными по длине критическими путями, М\- множество классов недоминируемых критических путей для обычной задачи. Тогда М = М\.
Доказательство. Очевидно, что I С 1\. Поэтому М С М\. Докажем, что М\ С М. Рассмотрим произвольный вход обычной задачи г. Пусть к Є М\. Докажем, что к 6 М. Если г I, то с помощью добавления к длительности каждой операции соответствующей степени двойки получаем задачу, в которой все критические пути различны по длине. В результате решения этой задачи получим оптимальное расписание с критическим путем к\, принадлежащем множеству М. Очевидно, что это расписание остается допустимым и оптимальным и при переходе к прежним длительностям, причем к\ - недоминируемый критический путь и для обычной задачи. Получается, что мы нашли еще один недоминируемый критический путь для обычной задачи, а это означает, что с точностью до последовательности операций критические пути к и к\ совпадают. Поэтому М\ сМи М = М\.
В предположении, что все критические пути различны по длине покажем, что представители некоторых классов критических путей доминируются какими-нибудь другими критическими путями.
