Сложность некоторых задач теории расписаний и эволюционные алгоритмы их решения

Коваленко, Юлия Викторовна

Сложность некоторых задач теории расписаний и эволюционные алгоритмы их решения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Коваленко, Юлия Викторовна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Омск МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Сложность некоторых задач теории расписаний и эволюционные алгоритмы их решения»

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

005531944

На правах рукописи

КОВАЛЕНКО Юлия Викторовна

СЛОЖНОСТЬ НЕКОТОРЫХ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ И ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ ИХ РЕШЕНИЯ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

" 8 АВГ 2013

Новосибирск - 2013

005531944

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского».

Научный руководитель: кандидат физико-математических наук, доцент

Еремеев Антон Валентинович.

Официальные оппоненты: доктор физико-математических наук, профессор

Нурминский Евгений Алексеевич, кандидат физико-математических наук Черных Илья Дмитриевич.

Ведущая организация: ФГБОУ ВПО «Сибирский государственный

аэрокосмический университет имени академика М.Ф. Решетнева»

Защита состоится 11 сентября 2013 г. в 16 часов на заседании диссертационного совета Д 003.015.01 при Учреждении Российской академии наук Институт математики им. С.Л. Соболева СО РАН (630090, Новосибирск, пр. академика Коптюга, 4).

С диссертацией можно ознакомиться в библиотеке Института математики им. С.Л. Соболева СО РАН.

Автореферат разослан «16» ЩСЛА- 2013 г.

Ученый секретарь диссертационного совета д.ф.-м.н.

Ю.В. Шамардин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Теория расписаний является одним из важных направлений в области оптимизации и в настоящее время бурно развивается. Задачи теории расписаний возникают в самых разных отраслях, таких как промышленное производство, сфера обслуживания, строительство, транспорт и др.

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

Ряд работ (см., например, [3, 5, 6, 8, 10]) отличаются тем, что в них рассматриваются не отдельные операции, а технологии, представляющие собой набор операций, в результате действия которых может быть получен тот или иной продукт. Для выполнения технологии необходимо наличие некоторой совокупности машин, работающих одновременно, другими словами, имеет место группировка машин по технологиям (в [3, 5, 8, 10] такие технологии называются многопроцессорными работами).

ществлять поэтапно. Сначала без учета ограниченности ресурсов выбираются операции, по которым продукция будет выпускаться, их длительность и порядок выполнения, а затем составляется расписание с учетом ограничений на потребление ресурсов и отношений предшествования, определенных на предыдущих этапах (этапе). Последняя задача относится к задачам календарного планирования.

На практике встречается много вариаций задачи календарного планирования с ограниченными ресурсами, анализу которых посвящены работы Ги-мади Э.Х., Залюбовского В.В., Кононова A.B., Лазарева A.A., Севастьянова C.B., Серваха В.В., Brucker P., Garey H.R., Johnson D.S., Hartmann S., Kolisch R., Krämer A., Pritsker A.A.B, и др.

Среди точных методов решения задач теории расписаний и календарного планирования следует выделить метод ветвей и границ (Bianco L., Bozoki G., Brucker P., Dell'Ohrio P., Knust S., Richard J.P., Schoo A., Speranza M.G., Thiele О. и др.) и схему динамического программирования (Беллман Р., Ковалев М.Я., Сервах В.В., Танаев B.C., Шафранский Я.М. и др.). Еще одним перспективным направлением является сведение исходной задачи к задаче целочисленного линейного программирования (Борисовский П.А., Гимади Э.Х., Еремеев A.B., Симанчев Р.Ю., Floudas С.А., Kallrath J., Lenstra J.K. и др.).

Как было отмечено ранее, при решении NP-трудных задач важное значение имеют приближенные алгоритмы с гарантированной оценкой точности и эвристики. Значительный вклад в область разработки таких алгоритмов внесли Агеев A.A., Гимади Э.Х., Глебов Н.И., Кельманов A.B., Корбут A.A., Кочетов Ю.А., Перепелица В.А., Попков В.К., Хачай М.Ю., Dorigo M., Glover S., Hochbaurn D., Holland J., Johnson D., Kirkpatrick S., Lovász L., Reeves C.R., Woeginger G. и др.

Эволюционные алгоритмы (ЭА), такие как генетические алгоритмы (ГА), эволюционные стратегии и алгоритмы генетического программирования, успешно применяются при решении задач оптимизации. Особенностью этих алгоритмов является имитация процесса эволюции биологической популяции, где особи соответствуют пробным точкам пространства решений, а при-

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

Работоспособность ГА существенно зависит от выбора оператора кроссин-говера, где происходит обмен признаками между родительскими генотипами. Актуальным направлением исследований является изучение статуса сложности и построение алгоритмов решения задачи оптимальной рекомбинации, в которой необходимо отыскать наилучший возможный результат оператора кроссинговера для заданных родительских генотипов. Целесообразность решения (точного или приближенного) задачи оптимальной рекомбинации в операторах кроссинговера подтверждается экспериментально в работах Гу-щинской О., Долгого А., Еремеева A.B., Aggarwal С., Balas Е., Cook W., Ibaraki Т., Niehaus W., Orlin J., Seymour P., Yagiura M. и др.

Цель диссертации - исследование сложности задач составления производственных расписаний, построение и анализ эволюционных алгоритмов решения этих задач.

С учетом поставленной цели решались следующие задачи:

• выделить NP-трудные и эффективно разрешимые частные случаи задач составления производственных расписаний, в которых учитываются группировка машин по технологиям и ресурсные ограничения возобновимого типа;

• построить эволюционные алгоритмы решения указанных задач;

• провести теоретическое и экспериментальное исследование разработанных алгоритмов.

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

Методы исследования. Обоснованность и достоверность научных результатов и выводов, содержащихся в диссертационной работе, базируются на

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

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

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

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

Модель целочисленного линейного программирования и алгоритм динамического программирования, известные для дискретного варианта задачи календарного планирования с возобновимым ресурсом, впервые обобщены на случай переменной интенсивности потребления и поступления ресурса. Обобщение алгоритма динамического программирования позволило выделить новые нсевдополиномиально и полиномиально разрешимые частные случаи, а также разработать многокритериальный ЭА. Средняя трудоемкость данного ЭА до первого достижения оптимума близка к трудоемкости алгоритма динамического программирования, а его операторы имеют вычислительную сложность того же порядка, что и базовые операторы алгоритма динамического программирования.

Основные результаты диссертации заключаются в следующем.

1. Установлены новые №-трудные частные случаи задачи составления

расписаний с группировкой машин по технологиям при нулевых длительно-

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

2. Разработаны генетические алгоритмы с равномерным кроссинговером и с оптимальной рекомбинацией для задачи составления расписаний с группировкой машин по технологиям. Доказано, что при решении задачи без прерываний эти алгоритмы сходятся к оптимуму «почти наверное», построены экспоненциальные верхние оценки среднего числа итераций до первого достижения оптимума. Экспериментально установлено преимущество генетического алгоритма с оптимальной рекомбинацией по сравнению с пакетом СРЬЕХ и с генетическим алгоритмом, использующим равномерный кроссинговер.

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

4. Для дискретного случая задачи календарного планирования с переменной интенсивностью потребления и поступления ресурса возобновимого типа предложены алгоритмы динамического программирования и выделены новые полиномиально и псевдополиномиалыго разрешимые частные случаи. Разработан многокритериальный эволюционный алгоритм на базе динамического программирования и построена верхняя оценка его средней трудоемкости до первого достижения оптимума.

5. Доказана КР-трудность задачи оптимальной рекомбинации для задачи минимизации общего времени завершения на одной машине. Разработан точный алгоритм решения данной задачи оптимальной рекомбинации, трудоемкость которого полиномиальна для «почти всех» пар родительских решений.

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

Практическая и теоретическая ценность. Работа имеет теоретический и экспериментальный характер. Полученные результаты применимы

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

Апробация работы. Результаты диссертации докладывались на следующих конференциях: Всероссийской конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2009 и 2012), Российской конференции «Дискретная оптимизация и исследование операций» (Республика Алтай, 2010), XIV Всероссийской конференции «Математическое программирование и приложения» (г. Екатеринбург, 2011), VIII Международной научно-технической конференции «Динамика систем, механизмов и машин» (г. Омск, 2012), IX Международной конференции «Интеллектуализация обработки информации» (г. Будва, Черногория, 2012), Региональной научно-практической студенческой конференции «Молодежь третьего тысячелетия» (г. Омск, 2010 и 2011), а также на семинарах в Омском государственном университете им. Ф.М. Достоевского, Сибирском государственном аэрокосмическом университете имени академика М.Ф. Решетнева, Институте математики им. С.Л. Соболева и его Омском филиале.

Публикации. Основные результаты диссертации опубликованы в 13 научных работах, три из них - в изданиях из списка ВАК [18, 20, 25]. Конфликт интересов с соавторами отсутствует.

Структура и объем работы. Диссертация изложена на 129 страницах, состоит из введения, трех глав, заключения, списка литературы (127 наименований) и приложений (14 страниц).

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

имеет несколько технологий производства, при выполнении которых исполь-

зуется несколько машин, работающих одновременно. Если машина переключается с одной технологии на другую, то необходимо выполнять переналадку. Пусть тп - число машин, к - число продуктов и d- общее число технологий. Требуется составить расписание, минимизирующее общее время окончания производства всех продуктов. В соответствии с нотацией [5, 10] рассматриваемая задача обозначается через P\setu pmtn, shu]\Cmax, если допускается прерывание выполнения технологий, и P|setj, S;u,|Cmax - в противном случае.

Bianco L., Blazewicz J., Dell'Ohno P., Drozdowski M., Hoogeven J.A., Jansen К., Kubale M., Porkolab L., Speranza M.G., van de Velde S.L., Veltman B. и др. анализировали сложность задач составления расписаний с группировкой машин по технологиям, в которых длительности переналадок равны нулю. В задачах составления производственных расписаний, исследуемых Борисовским П.А., Долгим А., Еремеевым A.B., Ковалевым М.Я., рассматриваются технологии, задействующие при своем выполнении одну машину, но уже при наличии переналадок. В [6] технологии рассматриваются при обсуждении постановки задачи, однако, в модели они в явном виде не представлены.

В п. 1.1 настоящей работы продолжается исследование сложности задачи составления расписаний с группировкой машин по технологиям. При ненулевых длительностях переналадки задачи P|setj, з;ц,|Стах и P|set,, pmtn, sluq\Cmzx. становятся NP-трудными в сильном смысле уже в случае одной машины, так как к ним сводится метрическая задача о кратчайшем гамильтоно-вом пути. Комбинация результатов [8, 10, 14] позволила установить трудпорс-шаемый частный случай этих задач при нулевых длительностях переналадки, когда для всякого продукта имеется одна технология производства, а каждая машина пригодна для работы только по двум технологиям (теорема 1.1).

В диссертации выделен новый труднорешаемый частный случай рассматриваемых задач при нулевых длительностях переналадки, а именно доказана

Теорема 1.2.1. Задачи P|set;, щщ = 0|Cmax u P|setb pmtn, sbtq = 0|CmaJC NP-трудны в сильном смысле даже в частном случае, когда требуется произвести один продукт с использованием технологий одинаковой производительности, задействующих при своем выполнении не более 3 машин.

2. При любом е > 0 не существует полиномиального приближенного алгоритма с точностью аппроксимации dl~e для решения задач P|seti, pmtn, Slug = 0|Cmax « P|setj, sluq = 0|Cmax, даже если число продуктов k = 1.

Здесь же с использованием точек событий [6] сформулированы модели частично целочисленного линейного программирования для задач P|seti, S[Uq|Cmax И P|seti; pmtn, s;U9|Cmax в общей постановке и для случая, когда длительности переналадки удовлетворяют неравенству треугольника. Точка событий представляет собой некоторый набор технологий и моменты начала и окончания выполнения технологий из этого набора. В одной точке событий каждая машина может быть задействована не более чем в одной технологии.

Предложенные модели позволили выделить новые полиномиально разрешимые частные случаи. Задачу P|set*, s/u,|Cmax, в которой число технологий ограничено константой, обозначим через P|setf, s¡uq, d = const|Cmax. Доказана

Теорема 1.3. Задача P|setj, shiq, d = const|Cmax полиномиально разрешима.

Задачу P|set;, pmtn, sluq\Cmax, в которой длительности переналадки удовлетворяют неравенству треугольника, а число машин и продуктов ограничено константой, обозначим через Pm|setj, pmtn, Asiuq, k = const|Cmax- Доказана

Теорема 1.4. Задача Pm|setj, pmtn, Asitl<?, k = const|Cmax полиномиально разрешима.

Построенные модели учитывают технологии в явном виде и имеют меньшее число переменных и ограничений, чем модель [6] в применении к исследуемой задаче. Моделирование технологий в явном виде позволило разработать эволюционные алгоритмы, где кодировка решений основана на выборе совокупности технологий.

В пп. 1.2 и 1.3 предложены генетические алгоритмы с равномерным крос-синговером и с оптимальной рекомбинацией. Решение задачи представляется в обоих ГА генотипом, состоящим из двух подстрок, одна из которых (подстрока назначений) определяет технологии, участвующие в производстве про-

дуктов, а вторая (подстрока порядка) - порядок выполнения выбранных технологий. Алгоритмы основываются на решении серии подзадач пониженной размерности в соответствии с моделью, построенной в п. 1.1.

Исследована сходимость разработанных ГА (теоремы 1.6 и 1.7) и получены экспоненциальные оценки сверху на среднее число итераций до первого достижения оптимума (утверждения 1.2 и 1.3). Введем обозначения: Рс - вероятность равномерного кроссинговера; Рп - вероятности мутации для подстрок назначений и порядка соответственно; £ - число итераций ГА.

Теорема 1.6. Если Р,\ е (0,1), Рп £ (0,1] и Рс е [0,1), то при решении задачи Р|8е^, 8;и,|Стах ГА с равномерным кроссинговером сходится к оптимуму «почти наверное» при £ —» оо.

Теорема 1.7. Если Р^ € (0,1) и Р71 € (0,1], то при решении задачи Р|Бе^, Б^Стах ГА с оптимальной рекомбинацией сходится к оптимуму «почти наверное» при £ —» оо.

В п. 1.4 представлены результаты вычислительного эксперимента, проведенного на построенных случайным образом тестовых примерах. Эксперимент показал существенное преимущество ГА с оптимальной рекомбинацией по сравнению с непосредственным применением пакета решения задач частично целочисленного программирования СРЬЕХ и с ГА, использующим равномерный кроссинговер.

Результаты первой главы опубликованы в [15, 17, 18, 24, 27].

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

Наиболее изучена задача календарного планирования с возобновимыми ресурсами, в которой функции, определяющие ресурсные ограничения (интенсивности потребления ресурсов каждой работой и функции количества

имеющихся ресурсов), предполагаются постоянными, а длительности работ

- целочисленными. Для этой задачи построена модель целочисленного линейного программирования [12], проведен анализ сложности [1, 7], а также предложены алгоритмы ее решения [1, 9, 13].

В настоящей работе рассматривается задача календарного планирования с возобовимым ресурсом в более общем виде, когда функции, определяющие ресурсные ограничения, являются кусочно-постоянными. Имеется т машин. Для каждой машины I задана последовательность работ = (г},..., г'/1), которые должны быть выполнены на данной машине в указанном порядке. Работы различных машин могут находиться в отношении предшествования. Длительность р{ работы г € /¡, I = 1,... ,тп, разбивается на периоды, в которые интенсивность потребления ресурса данной работой постоянна. Длительность горизонта планирования Н также разбивается на периоды, в которые наличие ресурса постоянно. Задачи такого рода возникают, например, в химическом производстве, когда сырье, поступающее через трубопровод, распределяется между реакторами, осуществляющими его переработку.

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

Теорема 2.1. Задача календарного планирования с возобновимым ресурсом полиномиально разрешима, если общее число периодов работ, когда ресурс потребляется, и число периодов наличия ресурса ограничены константой.

В п. 2.2 исследуется дискретный случай, когда все работы имеют целочисленные длительности, также как и интервалы постоянства функций, определяющих ресурсные ограничения. Для этого случая построена модель целочисленного линейного программирования и рассмотрен ряд ее модификаций. Разработан алгоритм динамического программирования (ДП), подобный алгоритму из [1], который основан на вычислении всевозможных состояний выполнения работ и переборе моментов времени Ь = .. ,Н. Для каждого состояния и момента времени Ь с помощью рекуррентной формулы определяется возможность достижимости этого состояния в момент t. Трудоемкость

алгоритма составляет 0(2'"lmH(up+l)m), где и = max Щ,р = max max pi.

1=1,...,m i=l,...,m ieli

Следовательно, имеет место

Теорема 2.3. Задача календарного планирования с возобновимым ресурсом в дискретном случае является псевдополиномиалъно разрешимой, если число машин ограничено константой.

Кроме того, анализ сложности алгоритма ДП при числе машин, ограниченном константой, позволяет установить полиномиальную разрешимость варианта дискретного случая задачи, когда интенсивности потребления ресурса работами и количество имеющегося ресурса заданы для каждого единичного интервала (теорема 2.2).

Для случая единичных длительностей работ предложена модификация разработанного алгоритма ДП с лучшей оценкой трудоемкости 0(2т(тп + bmax){u + l)m)i гДе Ьшах ~ число периодов наличия ресурса, и имеет место

Теорема 2.4. Задача календарного планирования с возобновимым ресурсом в дискретном случае является полиномиально разрешимой при единичных длительностях работ, если число машин ограничено константой.

С использованием результатов [4] для дискретного случая разработан многокритериальный эволюционный алгоритм на базе динамического программирования. Основная идея данного подхода заключается в том, что особи содержат информацию о некоторых свойствах частичных решений задачи, позволяющих эволюционному алгоритму достраивать имеющиеся особи до оптимальных, подобно методам ДП. Средняя трудоемкость построенного ЭА до первого достижения оптимума не превосходит 0(Н22тт(ир + l)m(log# + rn\og(up + 1))), а вычислительная сложность каждого оператора, также как и трудоемкость обработки состояний в алгоритме ДП, составляет 0(т) (утверждение 2.2).

В п. 2.3 приводятся результаты экспериментального исследования алгоритма ДП. Эксперимент показал перспективность использования данного алгоритма при решении задач, имеющих практическую значимость. Особенно это проявляется на задачах с большим числом работ при малом числе машин. Вместе с тем указан класс задач, на которых алгоритм ДП показывает

существенно худшие результаты по сравнению с пакетом CPLEX.

Результаты второй главы опубликованы в [16, 21, 22, 23, 25]. Третья глава посвящена исследованию задачи оптимальной рекомбинации для задачи, обозначаемой в теории расписаний через 11 «ии | Стах и являющейся частным случаем задачи 8;цд[Стах при числе машин т = 1.

В п. 3.1 приводится постановка исследуемой задачи оптимальной рекомбинации. Рассмотрим задачу 1|зг,и |Стах. Задано множество работ V, которые должны быть выполнены на единственной машине. Каждая работа у Е V характеризуется длительностью ру. Прерывание выполнения работ не допускается. В каждый момент времени машина не может быть задействована более чем в одной работе. Если машина переключается с одной работы на другую, то необходимо выполнять переналадку. Пусть вт1 - длительность переналадки с работы у на работу и для всех у,и € V, где V ф и. Требуется составить расписание, минимизирующее время завершения всех работ.

Обозначим через 7г = (7Г1,..., к\у\) перестановку, определяющую порядок

выполнения работ, а именно, тг; - работа, выполняемая г-той по счету. Пусть

И-1

й(7г) = А'7г,,т:,+1- Тогда задача эквивалентна поиску такой перестановки 7г*, ¿=1

при которой минимизируется суммарная длительность переналадки в (я-*).

В настоящей главе для 1|зга|Стах рассматривается задача оптимальной рекомбинации, где для произвольных заданных родительских решений 7т1 и 7Г2 требуется найти перестановку 7г', такую что

1) 7Г- = тг} или 7г- = 7Г? для всех г = 1,..., |У|;

2) 7г' имеет минимальное значение целевой функции з(тт') среди всех перестановок, удовлетворяющих условию 1).

В п. 3.2 исследуется сложность задачи оптимальной рекомбинации 1) - 2). С использованием результатов Сердюкова А.И. [2] доказана

Теорема 3.1. Задача оптимальной рекомбинации 1) - 2) для 1|5„и|Стах NР-трудна в сильном смысле.

Отметим, что из этой теоремы следует ИР-трудность аналогичной задачи оптимальной рекомбинации для P|setг, в^Сщах-

В п. 3.3 разработан точный алгоритм решения задачи оптимальной рекомбинации 1) - 2), основанный на переборе совершенных паросочетаний в спе-

циальном двудольном графе [2]. Доказано, что «почти все» индивидуальные задачи оптимальной рекомбинации имеют не более допустимых решений и разрешимы предложенным алгоритмом за время 0(|^|1п|У|) (теорема 3.2). С целью апробации данного алгоритма оптимальной рекомбинации в п. 3.4 разработан ГА с его использованием. В проведенном эксперименте на каждом из рассмотренных тестовых примеров из библиотеки TSPLIB генетический алгоритм находил оптимальное решение более чем в 30% испытаний. В ходе работы данного ГА в большинстве случаев возникали индивидуальные задачи оптимальной рекомбинации с не более чем \V\ допустимыми решениями и мощность множества их допустимых решений уменьшалась с ростом числа итераций ввиду снижения разнообразия популяции.

Результаты третьей главы опубликованы в [19, 20, 26].

В заключении приводятся основные результаты диссертации.

Список литературы

[1] Сервах В.В. Эффективно разрешимый случай задачи календарного планирования с возобновимыми ресурсами // Дискрет, анализ и исслед. операций. Сер. 2. - 2000. - Т. 7, № 1. - С. 75-82.

[2] Сердюков А.И. О задаче коммивояжера при наличии запретов // Управляемые системы. - 1978. - Вып. 17. - С. 80-86.

[3] Bianco L., Blazewicz J., Dell'Ohno P., Drozdowski M. Scheduling preemptive multiprocessor tasks on dedicated processors // Performance Evaluation. -1994. - Vol. 20. - P. 361-371.

[4] Doerr В., Eremeev A., Neumann F., Theile M., Thyssen С. Evolutionary algorithms and dynamic programming // Theor. Comput. Sei. - 2011. -Vol. 412. - P. 6020-6035.

[5] Drozdowski M. Scheduling multiprocessor tasks - An overview // Eur. J. Oper. Res. - 1996. - Vol. 94. - P. 215-230.

[6] Floudas C.A., Kallrath J., Pitz H.J., Shaik M.A. Production scheduling of a large-scale industrial continuous plant: short-term and medium-term scheduling // Comp. Chem. Engng. - 2009. - Vol. 33. - P. 670-686.

[7] Garey M.R., Johnson D.S. Complexity results for multiprocessor scheduling under resource constraints // SIAM J. Comput. - 1975. - Vol. 4, N 4. -P. 397-411.

[8] Hoogeven J.A., van de Velde S.L., Veltman B. Complexity of scheduling multiprocessor tasks with prespecified processors allocations // Discrete Appl. Math. - 1994. - Vol. 55. - P. 259-272.

[9] Icmeli O., Erenguc S.S. A tabu search procedure for the resource constrained project scheduling problem with discounted cash flows // Comput. Oper. Res.

- 1994. - Vol. 21, N 8. - P. 841-853.

[10] Jansen K., Porkolab L. Preemptive scheduling with dedicated processors: applications of fractional graph coloring // Journ. Scheduling. - 2004. -Vol. 7. - P. 35-48.

[11] Pochet Y., Wolsey L.A. Production planning by mixed integer programming

- Berlin, Heidelberg, New York: Springer-Verl., 2006. - 477 p.

[12] Pritsker A.A.B., Waiters L.J., Wolfe P.M. Multiproject scheduling with limited resources: a zero-one programming approach // Management Sci. - 1969. -Vol. 16. - P. 93-107.

[13] Servakh V.V., Shcherbinina T.A. A fully polynomial time approximation scheme for two project scheduling problems // Inform. Control Problems in Manufact.: A Proc. of 12th IFAC Intern. Symp. / Edt. by Dolgui A., Morel G., Pereira C.E. - Saint-Etienne: Elsevier Science, 2006. - Vol. 3. - P. 129-134.

[14] Zuckerman D. Linear degree extractors and the inapproximability of max clique and chromatic number // Theory of computing. - 2007. - Vol. 3. -P. 103 - 128.

Публикации автора по теме диссертации

[15] Еремеев A.B., Коваленко Ю.В. Приближенное решение одной задачи составления расписаний для многопродуктового производства //IV Всероссийская конференция «Проблемы оптимизации и экономические приложения»: материалы конф. - Омск: Полигр. центр КАН, 2009. - С. 223.

[16] Еремеев A.B., Коваленко Ю.В. Календарное планирование производства с непрерывным поступлением сырья // Российская конференция «Дискретная оптимизация и исследование операций»: материалы конф. - Новосибирск: Изд-во Ин-та математики, 2010. - С. 138.

[17] Еремеев A.B., Коваленко Ю.В. Задача составления расписаний с группировкой машин по технологиям и эволюционные алгоритмы ее решения / / Тезисы докладов XIV Всероссийской конференции «Математическое программирование и приложения». - Екатеринбург: УрО РАН, 2011.

- С. 172-173. (Информационный бюллетень Ассоциации математического программирования; № 12).

[18] Еремеев A.B., Коваленко Ю.В. О задаче составления расписаний с группировкой машин по технологиям // Дискрет, анализ и исслед. операций.

- 2011. - Т. 18, № 5. - С. 54-79.

[19] Еремеев A.B., Коваленко Ю.В. О сложности оптимальной рекомбинации для некоторых задач на перестановках // «Интеллектуализация обработки информации»: 9-я международная конференция. Черногория, г. Будва, 2012 г.: сборник докладов. - М.: Торус Пресс, 2012. - С. 245-248.

[20] Еремеев A.B., Коваленко Ю.В. О сложности оптимальной рекомбинации для одной задачи составления расписаний с переналадками // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, № 3. - С. 13-26.

[21] Еремеев A.B., Коваленко Ю.В., Тиле М. Эволюционный алгоритм для одной задачи календарного планирования // «Динамика систем, механизмов и машин»: материалы VIII Междунар. науч.-техн. конф. -Омск: Изд-во ОмГТУ, 2012. - Кн. 3. - С. 31-34.

[22] Коваленко Ю.В. Решение задачи календарного планирования производства с непрерывным поступлением сырья // «Молодежь третьего тысячелетия»: XXXIV региональная научно-практическая студенческая конференция: сборник статей секции «Физико-математические науки». -Омск: Изд-во ОмГУ, 2010. - С. 21-24.

[23] Коваленко Ю.В. Экспериментальное исследование моделей целочисленного линейного программирования для одной задачи календарного планирования // «Молодежь третьего тысячелетия»: XXXV региональная научно-практическая студенческая конференция: сборник статей секции «Физико-математические науки». - Омск: Изд-во ОмГУ, 2011. -С. 16-19.

[24] Коваленко Ю.В. Генетический алгоритм для задачи составления расписаний с группировкой машин по технологиям // «Динамика систем, механизмов и машин»: материалы VIII Междунар. науч.-техн. конф. -Омск: Изд-во ОмГТУ, 2012. - Кн. 3. - С. 46-48.

[25] Коваленко Ю.В. О задаче календарного планирования с возобновимым ресурсом // Автомат, и телемех. - 2012. - Вып. 6. - С. 140-153.

[26] Коваленко Ю.В. Теоретическое и экспериментальное исследование задачи оптимальной рекомбинации для одной задачи теории расписаний II «Проблемы оптимизации и экономические приложения»: материалы V Всероссийской конф. - Омск: Изд-во ОмГУ, 2012. - С. 137.

[27] Коваленко Ю.В. Модель с непрерывным представлением времени для задачи составления расписаний с группировкой машин по технологиям // Математические структуры и моделирование. - Омск: ОмГУ, 2013. - Т. 27, № 1. - С. 46-55.

Подписано в печать 19.07.2013 Формат 60x84/16. Бумага офсетная. Оперативный способ печати. Усл. печ. л. 1,25. Тираж 140 экз. Заказ № 534

Отпечатано в «Полиграфическом центре КАН» 644122, г. Омск, ул. Красный Путь, 30 тел. (3812) 24-70-79, 8-904-585-98-84

E-mail: pc_kan@mail.ru Лицензия ПЛД № 58-47 от 21.04.97

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Коваленко, Юлия Викторовна, Омск

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского»

На правах рукописи

КОВАЛЕНКО Юлия Викторовна

СЛОЖНОСТЬ НЕКОТОРЫХ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ И ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ

ИХ РЕШЕНИЯ

01.01.09 — дискретная математика и математическая кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель к.ф.-м.н., доцент Еремеев А.В.

Омск - 2013

Оглавление

Введение.................................. 4

1. Задача составления расписаний с группировкой машин по технологиям .............................. 15

1.1. Постановка задачи и анализ ее сложности........................15

1.2. Генетический алгоритм с равномерным кроссинговером .... 25

1.3. Генетический алгоритм с оптимальной рекомбинацией..........35

1.4. Вычислительный эксперимент ....................................38

2. Задача календарного планирования с переменной интенсивностью потребления и поступления ресурса возобновимого типа.................................... 40

2.1. Постановка задачи и анализ ее сложности............ 41

2.2. Дискретный случай ........................ 52

2.3. Вычислительный эксперимент .................. 76

3. Оптимальная рекомбинация для задачи минимизации общего времени завершения на одной машине ............. 78

3.1. Постановка задачи оптимальной рекомбинации..................78

3.2. ЫР-трудность задачи оптимальной рекомбинации ..............80

3.3. Решение задачи оптимальной рекомбинации ....................85

3.4. Экспериментальное исследование задачи оптимальной рекомбинации в генетическом алгоритме................................93

Заключение................................. 98

Литература.................................100

Приложение 1...............................116

Приложение 2...............................122

Приложение 3...............................126

Введение

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

Первые задачи составления расписаний были сформулированы и исследованы в 50-х годах прошлого столетия. Теория расписаний стала отдельным направлением в области оптимизации благодаря работам Конвея Р.В., Максвелла B.JI. и Миллера JI.B. [39], Танаева B.C. и Шкурбы В.В. [57], Беллма-на Р. [5], Бруккера П. [71], Глебова Н.И. [8], Михайлевича B.C. [44] и др. Сейчас это направление активно развивается в работах Гимади Э.Х., Ковалева М.Я., Кононова A.B., Лазарева A.A., Серваха В.В., Севастьянова C.B. и других авторов [2,11,40,43,49,51,55,64,78,83,85,95,102,121].

Большое практическое значение имеют задачи составления расписаний для производства, где в процессе выполнения операций на имеющемся множестве машин происходит получение одних веществ из других. Вещества подразделяются на сырье, промежуточные и окончательные продукты. Различают задачи с прерываниями и без прерываний. В задачах с прерываниями каждая операция может быть прервана и возобновлена позднее (см., например, [2,49,64]), а в задачах без прерываний - не допускаются прерывания выполнения операций (см., например, [66,81]). Продукты могут производиться либо непрерывно [100,105], либо партиями [78,99]. Кроме того, необходимо учитывать погрузку, хранение и транспортировку продуктов, переналадку машин и т. д. Теоретическое и экспериментальное исследование такого рода задач представлено, например, в [3,4,55,78,83,103,105,110,114,120].

Ряд работ (см., например, [64,79,83,95,102,110]) отличаются тем, что в них рассматриваются не отдельные операции, а технологии, представляющие собой набор операций, в результате действия которых может быть получен тот или иной продукт. Для выполнения технологии необходимо наличие некоторой совокупности машин, работающих одновременно, другими словами, имеет место группировка машин по технологиям (в [64,79,95,102] такие технологии называются многопроцессорными работами).

Кроме того, на производстве часто возникают задачи теории расписаний, где для выполнения операций требуются различного рода ограниченные ресурсы (например, сырье, электроэнергия, людские ресурсы и др.). Решение таких задач в рамках декомпозиционного подхода [114] целесообразно осуществлять поэтапно. Сначала без учета ограниченности ресурсов выбираются операции, по которым продукция будет выпускаться, их длительность и порядок выполнения, а затем составляется расписание с учетом ограничений на потребление ресурсов и отношений предшествования, определенных на предыдущих этапах (этапе). Последняя задача относится к задачам календарного планирования.

На практике встречается много вариаций задачи календарного планирования с ограниченными ресурсами, анализу которых посвящены работы [9,11,40,43,51,71,84,85,104,115,116,121,123].

Среди точных методов решения задач теории расписаний и календарного планирования следует выделить схему динамического программирования (ДП) [5,51,55,78], метод ветвей и границ [66,69,70,116] и различные комбинаторные подходы [10,26,54,56,64,91]. Еще одним перспективным направлением является сведение исследуемой задачи к задаче целочисленного линейного программирования (см., например, [3,9,53,83,95,100,105,109,116]). В ряде известных методов решения задач целочисленного линейного программирова-

ния (ЦЛП) используется приведение исходной задачи к последовательности задач непрерывной оптимизации. На таком подходе основаны методы отсечения [7,36,59], декомпозиции [38,63], ветвей и границ [24,41,59], алгоритмы перебора L-классов [25,37,38] и др.

Большинство задач теории расписаний и календарного планирования относятся к числу NP-трудных, поэтому возможности точных алгоритмов существенно ограничены в связи с высокой размерностью входных данных. В такой ситуации актуальным является детальное исследование сложности, на основе которого можно оценить перспективы разработки алгоритмов с заданными характеристиками как для задачи в общей постановке, так и для ее частных случаев. Также при решении NP-трудных задач важное значение приобретают приближенные и эвристические алгоритмы.

Приближенные алгоритмы находят допустимое решение с гарантированной оценкой точности за полиномиальное время [49,61,96,121]. Эвристические алгоритмы также находят допустимое решение за приемлемое время, но, как правило, не имеют априорной оценки погрешности [4,90,104,111,116]. Отметим, что для некоторых задач не может существовать приближенного алгоритма с какой-либо практически приемлемой гарантированной оценкой точности. Этот факт делает более актуальной разработку метаэвристик, в частности, эволюционных алгоритмов.

Эволюционные алгоритмы (ЭА), такие как генетические алгоритмы, эволюционные стратегии и алгоритмы генетического программирования, успешно применяются при решении практических задач оптимизации [45,50,106, 117,118]. Особенностью этих алгоритмов является имитация процесса эволюции биологической популяции, где особи соответствуют пробным точкам пространства решений задачи, а приспособленность особей к условиям окружающей среды - значениям целевой функции в этих точках. Процесс случайного

поиска в ЭА эвристически направляется значениями целевой функции в просмотренных точках пространства решений. Новые решения-потомки строятся посредством случайных операторов, модифицирующих полученные ранее пробные точки.

Для поиска приближенных решений задач большой размерности широкое распространение получили генетические алгоритмы (ГА) [3,15,48,68,77, 94,118]. Каждая особь представляется в ГА как некоторая строка символов, называемая генотипом. Под значением целевой функции генотипа будем понимать значение целевой функции решения {фенотипа), ему соответствующего. При этом в случае задачи минимизации чем меньше значение целевой функции генотипа, тем больше он имеет шансов быть выбранным в качестве родительского. Популяция развивается за счет отбора родительских особей с помощью оператора селекции и применения к ним случайных операторов, имитирующих мутацию генотипов и рекомбинацию родительских генотипов (кроссинг о в ер) [48].

Работоспособность ГА существенно зависит от выбора оператора кроссин-говера. Актуальным направлением исследований является изучение статуса сложности и построение алгоритмов решения задачи оптимальной рекомбинации, в которой необходимо отыскать наилучший возможный результат оператора кроссинговера для заданных родительских генотипов. Целесообразность решения (точного или приближенного) задачи оптимальной рекомбинации в операторах кроссинговера ГА подтверждается экспериментально в работах [60,62,73,77,126].

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

С учетом поставленной цели решались следующие задачи:

• выделить ЫР-трудные и эффективно разрешимые частные случаи задач составления производственных расписаний, в которых учитываются группировка машин по технологиям и ресурсные ограничения возобновимого типа;

• построить эволюционные алгоритмы решения указанных задач;

• провести теоретическое и экспериментальное исследование разработанных алгоритмов.

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

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

Впервые рассмотрена задача оптимальной рекомбинации для задачи составления расписаний с группировкой машин по технологиям. Доказана ИР-

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

Модель целочисленного линейного программирования и алгоритм динамического программирования, известные для дискретного варианта задачи календарного планирования с возобновимым ресурсом, впервые обобщены на случай переменной интенсивности потребления и поступления ресурса. Обобщение алгоритма динамического программирования позволило выделить новые псевдополиномиально и полиномиально разрешимые частные случаи, а также разработать многокритериальный эволюционный алгоритм. Средняя трудоемкость данного ЭА до первого достижения оптимума близка к трудоемкости алгоритма динамического программирования, а его операторы имеют вычислительную сложность того же порядка, что и базовые операторы алгоритма динамического программирования.

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

Содержание работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложений.

В первой главе описывается и исследуется задача составления расписаний с группировкой машин по технологиям, возникающая, например, при производстве пластмасс и представляющая собой частный случай задачи, предложенной в [83]. Особенностью постановки является то, что каждый продукт имеет несколько технологий производства, при выполнении которых используется сразу несколько машин, работающих одновременно. Если машина переключается с одной технологии на другую, то необходимо выполнять переналадку. В соответствии с известной нотацией [65,78,102] рассматриваемая задача обозначается через Р^е^, рггЛп, 51щ\Стах, если допускается прерывание выполнения технологий, и Р^е^, 81Щ\Стах - в противном случае.

В [65,67,79,95,102,107] проводится анализ сложности задач составления расписаний с группировкой машин по технологиям, в которых длительности переналадок машин равны нулю. В задачах составления производственных расписаний [3, 78] рассматриваются технологии, задействующие при своем выполнении только одну машину, но уже при наличии переналадок. В [83] технологии рассматриваются при обсуждении постановки задачи, однако, в модели они в явном виде не представлены. Такой подход приводит к моделям частично целочисленного линейного программирования (ЧЦЛП) достаточно большой размерности, для решения которых применяется метод декомпозиции [83,99,100].

В настоящей работе продолжается исследование сложности задачи составления расписаний с группировкой машин по технологиям. В п. 1.1 выделены новые ИР-трудные и полиномиально разрешимые случаи. Здесь же с использованием точек событий [99] построены модели ЧЦЛП для задачи в общей

постановке и для случая, когда длительности переналадки удовлетворяют неравенству треугольника. Предложенные модели учитывают технологии в явном виде и имеют меньшее число переменных и ограничений, чем модель [83] в применении к исследуемой задаче. Моделирование технологий в явном виде позволило разработать для решения задач большой размерности эволюционные алгоритмы, где кодировка решений основана на выборе совокупности технологий.

В пп. 1.2 и 1.3 предложены генетические алгоритмы с равномерным крос-синговером и с оптимальной рекомбинацией. В процессе их выполнения решается серия подзадач пониженной размерности в соответствии с моделью ЧЦЛП, построенной в п. 1.1. Исследована сходимость разработанных ГА, получены экспоненциальные оценки сверху на среднее число итераций до первого достижения оптимума.

Проведен вычислительный эксперимент на построенных случайным образом тестовых примерах, показавший существенное преимущество ГА с оптимальной рекомбинацией по сравнению с непосредственным применением пакета решения задач частично целочисленного программирования СРЬЕХ и с ГА, использующим равномерный кроссинговер. Описание результатов эксперимента представлено в п. 1.4.

Результаты первой главы приводятся в [17,19,20,32,35].

Во второй главе описывается и исследуется задача календарного планирования с возобовимым ресурсом и критерием минимизации общего времени завершения работ. Возобновимый ресурс [11, 51] характеризуется тем, что для каждой работы задается интенсивность потребления ресурса в каждый из моментов ее выполнения. Суммарная интенсивность потребления ресурса по всем работам, выполняемым в любой момент времени не должна превосходить количества ресурса, имеющегося в наличии в данный момент.

В [51,84,121,123] рассматривается задача календарного планирования с возобновимыми ресурсами, в которой функции, определяющие ресурсные ограничения (интенсивности потребления ресурсов каждой работой и функции количества имеющихся ресурсов), предполагаются постоянными, а длительности работ - целочисленными. Построена модель ЦЛП [115,123] этой задачи, проведен анализ сложности [51,84], а также предложены точные и приближенные алгоритмы ее решения [51,97,98,121].

В настоящей работе рассматривается задача календарного планирования с возобовимым ресурсом в более общем виде, когда функции, определяющие ресурсные ограничения, являются кусочно-постоянными. Задачи такого рода возникают, например, в химическом производстве [103], когда сырье, поступающее через трубопровод, распределяется между реакторами, осуществляющими его переработку. Нераспределенная часть сырья не складируется и в дальнейшем производстве не используется. Поэтому в любой момент времени потребление сырья не может превышать его наличия. При этом наличие сырья з