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

• Коваленко, Юлия Викторовна
• кандидат физико-математических наук
• 2013

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

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Литература

Приложение 1

Приложение 2

Приложение 3

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

Введение

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

Первые задачи составления расписаний были сформулированы и исследованы в 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], когда сырье, поступающее через трубопровод, распределяется между реакторами, осуществляющими его переработку. Нераспределенная часть сырья не складируется и в дальнейшем производстве не используется. Поэтому в любой момент времени потребление сырья не может превышать его наличия. При этом наличие сырья зависит от времени и интенсивности потребления сырья работами меняются в процессе их выполнения.

В п. 2.1 для случая произвольных длительностей работ (без условия цело-численности) построена модель ЧЦЛП, с использованием которой выделен новый полиномиально разрешимый частный случай.

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

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

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

Результаты второй главы опубликованы в [18,23,30,31,33].

Третья глава посвящена исследованию задачи оптимальной рекомбинации для задачи составления расписаний с переналадками, представляющей собой частный случай рассматриваемой в первой главе задачи Р^е^, 8/ид|Стах при числе машин равном единице.

В п. 3.1 приводится постановка исследуемой задачи оптимальной рекомбинации, а в п. 3.2 доказывается ее ИР-трудность с использованием результатов Сердюкова А.И. [52]. В п. 3.3 предложен точный алгоритм решения рассматриваемой задачи оптимальной рекомбинации, основанный на переборе совершенных паросочетаний в специальном двудольном графе [52]. Данный алгоритм является более быстрым, чем модификация известного метода динамического программирования решения задачи коммивояжера [93]. Кроме того, доказано, что его трудоемкость полиномиальна для «почти всех» индивидуальных задач оптимальной рекомбинации.

С целью апробации предложенного оператора оптимальной рекомбинации в п. 3.4 разработан генетический алгоритм с его использованием. В проведен-

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

Результаты третьей главы приводятся в [21,22,34].

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

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

При изложении материала используются следующие обозначения: R+ (М+) - множество положительных (неотрицательных) вещественных чисел, Z+ (Z+) - множество положительных (неотрицательных) целых чисел.

Автор выражает благодарность своему научному руководителю Еремееву A.B. за полезные советы и замечания при выполнении данной работы.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Коваленко, Юлия Викторовна

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

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

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

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

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

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

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

100

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Коваленко, Юлия Викторовна, 2013 год

Литература

[1] Андрусенко С.К., Нурминский Е.А., Стецюк П. И. Численные эксперименты с новым классом алгоритмов в линейном программировании // Ж. вычисл. матем. и матем. физ. - 1987. - Т. 27, № 3. - С. 349 - 356.

[2] Баптист Ф., Карлье Ж., Кононов A.B., Керан М., Севастьянов C.B., Свириденко М. Структурные свойства оптимальных расписаний с прерываниями операций // Дискрет, анализ и исслед. операций. - 2009. - Т. 16, № 1. - С. 3 - 36.

[3] Борисовский П. А. Генетический алгоритм для одной задачи составления производственного расписания с переналадками // Тр. XIV Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск: ИСЭМ СО РАН, 2008. - Т. 4. - С. 166 - 173.

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

[5] Беллман Р. Динамическое программирование. - Москва: ИЛ, 1960. -400 с.

[6] Берж К. Теория графов и ее применения. - М.: Изд-во иностр. лит-ры, 1962. - 319 с.

[7] Васильев И. JI., Климентова К.Б. Метод ветвей и отсечений для задачи размещения с предпочтениями клиентов // Дискрет, анализ и исслед. операций. - 2009. - Т. 16, № 2. - С. 21 - 41.

[8] Глебов Н.И. Алгоритм составления оптимального расписания для двух работ // Управляемые системы. - 1968. - Вып. 1. - С. 14 - 20.

[9] Гимади Э.Х. О некоторых математических моделях и методах планирования крупномасштабных проектов // Модели и методы оптимизации. - Новосибирск: Наука, 1988. - С. 89 - 115.

[10] Гимади Э.Х., Глебов Н.И. Дискретные экстремальные задачи принятия решений: уч. пос. - Новосибирск: НГУ, 1991. - 76 с.

[11] Гимади Э.Х., Залюбовский В.В., Севастьянов C.B. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками // Дискрет, анализ и исслед. операций. Сер. 2. - 2000. - Т. 7, № 1. - С. 9 - 34.

[12] Гмурман В.Е. Теория вероятностей и математическая статистика: уч. пос. - М.: Высшее образование, 2006. - 479 с.

[13] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982. - 416 с.

[14] Еремеев A.B. Генетические алгоритмы и оптимизация: уч. пос. -Омск: Изд-во ОмГУ, 2008. - 48 с.

[15] Еремеев A.B. О связи динамического программирования и многокритериальных эволюционных алгоритмов: препринт. - Омск: Изд-во ОмГУ, 2008. - 20 с.

[16] Еремеев A.B. О сложности оптимальной рекомбинации для задачи коммивояжера // Дискрет, анализ и исслед. операций. - 2011. - Т. 18, № 1.

- С. 27 - 40.

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

- С. 223.

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

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

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

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

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

ногория, г. Будва, 2012 г.: сборник докладов. - М.: Торус Пресс, 2012. - С. 245 - 248.

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

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

[24] Забудский Г. Г. Построение моделей и решение задач размещения на плоскости с запрещенными зонами // Автомат, и телемех. - 2006. -Вып. 12. - С. 136 - 141.

[25] Заозерская Л.А. Об одном алгоритме перебора L-классов для решения задачи о покрытии множества // Труды XI Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск: ИСЭМ СО РАН, 1998. - Т. 1. - С. 139 - 142.

[26] Зуховицкий С.И., Радчик И.А. Математические методы сетевого планирования. - М.: Наука, 1965. - 296 с.

[27] Илъев В.П. Оценки погрешности приближенного алгоритма для задачи о раскраске графа // Тр. XIII Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск: ИСЭМ СО РАН, 2005. - Т. 1. - С. 491 - 495.

[28] Карп P.M. Сводимость комбинаторных проблем // Кибернетический сборник. - М.: Мир, 1975. - Вып. 12. - С. 16 - 38.

[29] Китаев А., Шенъ А., Вялый М. Классические и квантовые вычисления. - М.: МЦНМО, ЧеРо, 1999. - 192 с.

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

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

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

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

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

[35] Коваленко Ю.В. Модель с непрерывным представлением времени для задачи составления расписаний с группировкой машин по технологиям //

Математические структуры и моделирование. - Омск: ОмГУ, 2013. -Т. 27, № 1. - С. 46 - 55.

[36] Колоколов A.A. Методы дискретной оптимизации: уч. пос. - Омск: Ом-ГУ, 1984. - 75 с.

[37] Колоколов A.A., Аделъшин A.B., Ягофарова Д.И. Решение задачи выполнимости с использованием метода перебора L-классов // Информационные технологии. - 2009. - № 2. - С. 54 - 59.

[38] Колоколов A.A., Леванова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения // Вестник Омского университета. - 1996. - № 1. - С. 21 - 23.

[39] Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. - М.: Наука, 1975. - 360 с.

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

[41] Корбут A.A., Финкелъштейн Ю.Ю. Дискретное программирование. -М.: Наука, 1969. - 368 с.

[42] Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.

- М.: МЦИМО, 2001. - 960 с.

[43] Лазарев A.A., Гафаров Е.Р. К решению задачи построения расписания выполнения проекта // Автомат, и телемех. - 2008. - Вып. 12.

- С. 86 - 104.

[44] Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. -М.: Наука, 1983. - 208 с.

[45] Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации // Информационные технологии. - 1999. - № 1. -С. 2-7.

[46] Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. - 512 с.

[47] Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы, теория и практика. - М.: Мир, 1980. - 476 с.

[48] Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. - М.: Горячая линия-Телеком, 2006. - 452 с.

[49] Севастьянов C.B., Ситтерс P.A., Фишкин A.B. Построение расписаний выполнения независимых работ на идентичных параллельных машинах с прерываниями и миграционными задержками // Автомат, и телемех. - 2010. - Вып. 10. - С. 90 - 99.

[50] Семенкин Е. С. Эволюционные алгоритмы поддержки принятия решений при управлении сложными системами // Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Ре-шетнева. - 2005. - № 3. - С. 83 - 85.

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

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

[53] Симанчёв Р.Ю., Уразова И. В. Целочисленная модель задачи минимизации общего времени обслуживания параллельными приборами единичных требований с предшествованиями // Автомат, и телемех. - 2010. - Вып. 10. - С. 100 - 106.

[54] Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы. - М.: Наука, 1984. - 384 с.

[55] Танаев B.C., Ковалев М.Я., Шафранский Я.М. Теория расписаний. Групповые технологии. - Мн.: Институт технической кибернетики HAH Беларуси, 1998. - 290 с.

[56] Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. - М.: Наука, 1989. - 328 с.

[57] Танаев B.C., Шкурба В.В. Введение в теорию расписаний. - М.: Наука, 1975. - 256 с.

[58] Хачиян Л. Г. Полиномиальные алгоритмы в линейном программировании // Доклады АН СССР. - 1979. - Т. 244. - С. 1093 - 1096.

[59] Ху Т. Целочисленное программирование и потоки в сетях. - М.: Мир, 1974. - 520 с.

[60] Aggarwal С., Orlin J., Tai R. An optimized crossover for maximum independent set // Oper. Res. - 1997. - Vol. 45. - P. 225 - 234.

[61] Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M. Complexity and approximation: combinatorial optimization

problems and their approximability properties. - Berlin: Springer-Verl., 1999. - 529 p.

[62] Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems // Journ. Heuristics. - 1998. - Vol. 4, N 2. - P. 107 - 122.

[63] Benders J.F. Partitioning procedures for solving of mixed-variables programming problems // Numer. Math. - 1962. - Vol. 4, N 3. - P. 238 - 252.

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

[65] Bianco L., Blazewicz J., Dell'Ohno P., Drozdowski M. Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors // Ann. Oper. Res. - 1995. - Vol. 58. - P. 493 - 517.

[66] Bianco L., Dell'Ohno P., Speranza M.G. Nonpreemptive scheduling on independent tasks with prespecified processor allocations // Naval Research Logistics Quarterly. - 1994. - Vol. 41. - P. 959 - 971.

[67] Blazewicz J., Dell'Ohno P., Drozdowski M., Speranza M.G. Scheduling multiprocessor tasks on three dedicated processors // Information Processing Letters. - 1992. - Vol. 41. - P. 275 - 280. Corrigendum: Vol. 49. - P. 269 - 270.

[68] Borisovsky P.A., Dolgui A., Eremeev A.V. Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder // Eur. J. Oper. Res. - 2009. - Vol. 195, N 3. - P. 770 - 779.

[69] Bozoki G., Richard J. P. A branch-and-bound algorithm for the continuous-process job-shop scheduling problem // AHE Transactions. - 1970. - Vol. 2, N 3. - P. 246 - 252.

[70] Brucker P., Knust S., Schoo A., Thiele О. A branch and bound algorithm for the resource-constrained project scheduling problem // Eur. J. Oper. Res. - 1998. - Vol. 107. - P. 272 - 288.

[71] Brucker P., Krämer A. Polynomial algorithms for resource constrained and multiprocessor task scheduling problems // Eur. J. Oper. Res. - 1996. -Vol. 90, N 2. - P. 214 - 226.

[72] Cavicchio D.J. Adaptive search using simulated evolution: Ph.D. thesis. -Ann Arbor: University of Michigan Press, 1970. - 244 p.

[73] Cook W., Seymour P. Tour merging via branch-decomposition // INFORMS Journ. Comput. - 2003. - Vol. 15, N 2. - P. 233 - 248.

[74] Cotta СAlba E., Troya J.M. Utilizing dynastically optimal forma recombination in hybrid genetic algorithms // Proc. 5th International Conference on Parallel Problem Solving from Nature. - Berlin: SpringerVerl., 1998. - P. 305 - 314. (Lect. Notes Comput. Sei.; Vol. 1498).

[75] Dantzig G., Fulkerson R., Johnson S. Solution of a large-scale traveling salesman problem // Oper. Res. - 1954. - Vol. 2. - P. 393 - 410.

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

[77] Dolgui A., Eremeev A., Guschinskaya O. MIP-based GRASP and genetic algorithm for balancing transfer lines // Matheuristics: Hybridizing

Metaheuristics and Mathematical Programming / Maniezzo V., Stutzle T., Voss S. - Berlin: Springer-Verl., 2010. - P. 189 - 208. (Annals of Information Systems; Vol. 10).

[78] Dolgui A., Eremeev A.V., Kovalyov M.Y., Kuznetsov P.M. Multi-product lot sizing and scheduling on unrelated parallel machines // HE Transactions.

- 2010. - Vol. 42, N 7. - P. 514 - 524.

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

[80] Drozdowski M. Scheduling for parallel processing. - London: Springer-Verl., 2009. - 386 p.

[81] Du J., Leung J. Y-T. Complexity of scheduling parallel task systems // SIAM J. Discrete Math. - 1989. - Vol. 2, N 4. - P. 472 - 478.

[82] Eremeev A.V. On complexity of optimal recombination for binary representations of solutions // Evolutionary Computation. - 2008. - Vol. 16, N 1. - P. 127 - 147.

[83] 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.

[84] 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.

[85] Gimadi E., Sevastianov S. On solvability of the project scheduling problem with accumulative resorces of an arbitrary sign // Operations Research Proceedings. - Berlin: Springer-Verl., 2002. - P. 241 - 246.

[86] Goldberg D., Thierens D. Elitist recombination: an itegrated selection recombination GA // Proc. first IEEE World Congress on Computational Intelligence. - Piscataway, New Jersey: IEEE Service Center, 1994. - Vol. 1.

- P. 508 - 512.

[87] Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. Optimization and approximation in deterministic sequencing and scheduling: a survey // Ann. Discrete Math. - 1979. - Vol. 5. - P. 287 - 326.

[88] Grotschel M., Lovasz L., Schrijver A. The Ellipsoid method and its consequences in combinatorial optimization // Combinatorica. - 1981. -Vol. 1. - P. 169 - 197.

[89] Guschinskaya 0., Dolgui A. Comparative analysis of exact and heuristic methods for a transfer line balancing problem: research report N 2007-500007. - Saint-Etienne: Ecole des Mines de Saint-Etienne, 2007. - 37 p.

[90] Handbook of metaheuristics / Edt. by Glover F., Kochenberger G.A. -Boston: Kluwer Acad. Publ., 2002. - 560 p.

[91] Hardgrave W. W., Nemhauser G. A geometric model and graphical algorithm for a sequencing problem // Oper. Res. - 1963. - Vol. 11, N 6. - P. 889 - 900.

[92] Hazir O., Giinalay Y., Erel E. Customer order scheduling problem: a comparative metaheuristics study // Int. Journ. of Adv. Manuf. Technol.

- 2008. - Vol. 37. - P. 589 - 598.

[93] Held M., Karp R.M. A dynamic programming approach to sequencieng problems // SIAM J. Appl. Math. - 1962. - Vol. 10. - P. 196 - 210.

[94] Holland J.H. Adaptation in natural and artificial systems. - Ann Arbor: University of Machigan Press, 1975. - 183 p.

[95] 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.

[96] Hromkovic J. Algorithmics for hard problems. Introduction to combinatorial optimization, randomization, approximation and heuristics. - Berlin: Springer-Verl., 2004. - 536 p.

[97] 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.

[98] Icmeli 0., Erenguc S.S. A branch and bound procedure for the resource constrained project scheduling problem with discounted cash flows // Management Sci. - 1996. - Vol. 42, N 10. - P. 1395 - 1408.

[99] Ierapetritou M.G, Floudas C.A. Effective continuous-time formulation for short-term scheduling: I. multipurpose batch process // Ind. Eng. Chem. Res. - 1998. - Vol. 37. - P. 4341 - 4359.

[100] Ierapetritou M.G, Floudas C.A. Effective continuous-time formulation for short-term scheduling: II. continuous and semi-continuous processes // Ind. Eng. Chem. Res. - 1998. - Vol. 37. - P. 4360 - 4374.

[101] Itai A., Papadimitriou C.H., Szwarcfiter J.L. Hamilton paths in grid graphs // SIAM J. Comput. - 1982. - Vol. 11, N 4. - P. 676 - 686.

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

[103] Kallrath J., Ererneev A., Borisovsky P., Kovalenko J. Scheduling using continuous-time formulations: technical report. - Ludwigshafen: BASF SE, Scientifc Computing, 2010. - 337 p.

[104] Kolisch R., Hartmann S. Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis // Project scheduling: recent models, algorithms and application / Edt. by Weglarz J. - Boston: Kluwer Acad. Publ., 1999. - P. 147 - 178.

[105] Kondili E., Pantelides C.C., Shan N. Production planning for the rational use of energy in multiproduct continuous plants // Comp. Chem. Engng.

- 1993. - Vol. 17. - P. 123 - 136.

[106] Koza J.R. Genetic programming II: automatic discovery of reusable programs (complex adaptive systems). - Cambridge, MA: MIT Press, 1994. - 746 p.

[107] Kubale M. Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors // Eur. J. Oper. Res. - 1996. - Vol. 94. - P. 242 - 251.

[108] Lawler E.L... Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. The traveling salesman problem: a guided tour of combinatorial optomization. -New York: John Wiley & Sons Ltd., 1985. - 361 p.

[109] Lenstra J.K., Shmous D.B., Tardos E. Approximation algorithms for scheduling unrelated parallel machiens // Math. Prog. - 1990. - Vol. 46.

- P. 259 - 271.

[110] Lin X., Floudas C.A., Modi S., Juhasz N.M. Continuous-time optimization approach for medium-range production scheduling of a multiproduct batch plant // Ind. Eng. Chem. Res. - 2002. - Vol. 41. - P. 3884 - 3906.

[111] Local Search in Combinatorial Optimization / Edt. by Aarts E.H.L., Lenstra J.K. - New York: John Wiley & Sons Ltd., 1997. - 315 p.

[112] Orpen P., Mannila H. On approximation preserving reductions: complete problems and robuts measures: technical report C-1987-28, Department of Computer Science. - Helsinki: University of Helsinki, 1987.

[113] Peschel M., Riedel C. Use of vector optimization in multiobjective decision making // Conflicting Objectives in Decision / Edt. by Bell D.E., Keeney R.L., Raiffa H. - Chichester: Wiley, 1977. - P. 97 - 121.

[114] Pochet Y., Wolsey L.A. Production planning by mixed integer programming. - Berlin, Heidelberg, New York: Springer-Verl., 2006. - 477 p.

[115] Pritsker A.A.B., Watters L.J., Wolfe P.M. Multiproject scheduling with limited resources: a zero-one programming approach // Management Sei.

- 1969. - Vol. 16. - P. 93 - 107.

[116] Project scheduling: recent models, algorithms and applications / Edt. by Weglarz J. - Boston: Kluwer Acad. Publ., 1999. - 552 p.

[117] Rechenberg I. Evolutionsstrategie: optimerung technicher Systeme nach prinzipen der biologischen Evolution. - Schtuttgart: Formann-Holzboog Verl., 1973. - 170 p.

[118] Reeves C.R. Genetic algorithms for the operation researcher // INFORMS J. Comput. - 1997. - Vol. 9, N 3. - P. 231 - 250.

[119] Rudolph G. Finite markov chain results in evolutionary computation: A tour d'horizon // Fundamental Informaticae. - 1998. - Vol. 35, N 1 - 4.

- P. 67 - 89.

[120] Sargent R., Zhang X. The optimal operation of mixed production facilities-extensions and improvements // Сотр. Chem. Engng. - 1998. - Vol. 22.

- P. 1287 - 1295.

[121] 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.

[122] Sotskov Y.N., Shakhlevich N.V. NP-hardness of shop-scheduling problems with three jobs // Discrete Appl. Math. - 1995. - Vol. 59, N 3. - P. 237 - 266.

[123] Sprecher AKolisch R., Drexl A. Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem // Eur. J. Oper. Res. - 1995. - Vol. 80. - P. 94 - 102.

[124] Ullman J.D. NP-complete scheduling problems //J. Comput. Syst. Sci.

- 1975. - Vol. 10, N 4. - P. 384 - 393.

[125] URL: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

- TSPLIB. - 1995. (дата обращения: 05.04.2013).

[126] Yagiura M., Ibaraki T. The use of dynamic programming in genetic algorithms for permutation problems // Eur. J. Oper. Res. - 1996. - Vol. 92.

- P. 387 - 401.

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

- P. 103 - 128.

116