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

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

003494535

Сербах Владимир Вицентьевич

АНАЛИЗ СЛОЖНОСТИ И РАЗРАБОТКА АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ И ТЕОРИИ РАСПИСАНИЙ

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

АВТОРЕФЕРАТ

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

2 5 МАР 2910

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

003494535

Работа выполнена в Учреждении Российской Академии наук Омском филиале Института математики им. С.Л. Соболева СО РАН

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

Севастьянов C.B.

доктор физико-математических наук Гордон B.C.

доктор технических наук Павлов В.Н.

Ведущая организация: Учреждение Российской Академии наук

Институт вычислительной математики и математической геофизики СО РАН

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

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

/

Автореферат разослан «_ _2_» -М&-Р ^ &2010 г.

Ученый секретарь

диссертационного совета Д.003.015.01, доктор физико-математических наук

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

Общая характеристика работы

Актуальность работы. Теория расписаний и календарное планирование образуют одно из важных и интересных направлений в области оптимизации и в настоящее время переживают период бурного развития. Это связано, прежде всего, с появлением принципиально новых видов продукции, технологий, интенсификацией производства, его непрерывным обновлением и совершенствованием. Стремительное развитие систем связи, интернета, логистических структур ставит перед математиками новые задачи, в том числе в области теории расписаний. На практике возникает множество разнообразных задач календарного планирования производства и сбыта продукции, эффективного использования оборудования и других ресурсов, согласования работы различных служб и так далее. Возникнув в середине 50-х годов прошлого века, теория расписаний усилиями таких ученых, как Глебов Н.И., Михалевич B.C., Танаев B.C., Шкурба В.В., Беллман Р., Бруккер П., Джонсон Д., Джонсон С., Фридман Д. и других превратилась в содержательную научную дисциплину со своей структурой и методами исследования. В настоящее время это направление активно развивается в работах Гимади Э.Х., Гордона B.C., Ковалева М.Я., Кононова A.B., Севастьянова C.B., Сотскова Ю.Н., Струсевича В.А., Тимковского В.Г., Войгенгера Г. и многих других российских и зарубежных ученых.

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

Большой интерес представляют многостадийные задачи Джонсона, Акерса-Фридмана, переналадки оборудования, исследование которых во многом предопределило развитие теории расписаний. Задача Джонсона, известная в литературе под названием Flow-Shop, заключается в минимизации времени обработки деталей на конвейерной линии, состоящей из последовательно расположенных машин. Технологические маршруты всех деталей совпадают, но длительности обработки могут отличаться. Задача с двумя машинами полиномиально разрешима. Однако уже для трех машин задача является NP-трудной в сильном смысле н привлекает внимание многих исследовате-

лей. Разномаршрутная задача Акерса-Фридмана или Job-Shop представляет собой обобщение задачи Джонсона. В ней также необходимо обработать детали на машинах, но технологические маршруты различны, и деталь может поступать на некоторые машины многократно. На практике встречается много вариаций разномаршрутной задачи, которые еще недостаточно исследованы.

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

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

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

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

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

Имеется несколько направлений анализа сложности решения №-трудных задач: исследование зависимости сложности построения решения задачи от значения отдельных параметров входной информации; выделение так называемого "ядра" сложности и построение семейств труднорешаемых примеров; поиск эффективно разрешимых случаев; исследование трудоемкости построения приближенных решений в зависимости от точности приближения.

Анализ сложности ЫР-трудных задач в зависимости от параметров задачи оказывается наиболее эффективным способом оценки перспектив построения алгоритмов ее решения. В задаче о рюкзаке NP-тpyднocть обусловлена объемом рюкзака, тогда как от количества предметов трудоемкость алгоритма динамического программирования зависит линейно. Такой же анализ может быть проведен и для других задач. Например, в разномаршрутной задаче обработки деталей ЫР-трудность в сильном смысле связана с числом деталей, то есть при обработке небольшого числа деталей может быть построен эффективный алгоритм поиска оптимального расписания.

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

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

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

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

Если получение точного решения задачи требует слишком много времени, то используются приближенные алгоритмы. Здесь опять приходит на помощь анализ сложности, так как современная теория позволяет оценить время построения решения в зависимости от заданной точности. Разработке приближенных алгоритмов решения задач посвящено значительное число работ Гимади Э.Х., Ковалева М.Я., Севастьянова C.B. и многих других авторов. Как показывают современные результаты, для одних задач существуют полиномиальные по времени аппроксимациошше схемы (PTAS и FPTAS), с помощью которых можно получить приближенное решение с любой заданной относительной погрешностью. Для других задач не существует аппроксима-ционной схемы, но удается построить приближенные алгоритмы с константной оценкой точности. Для задач третьего класса ни при какой относительной погрешности невозможно построение полиномиального алгоритма (при условии Р ф NP). Естественно, важным представляется вопрос о том, к какому классу относится та или иная задача. В настоящее время исследование вопросов построения приближенных алгоритмов и, в частности, полиномиальных аппроксимационных схем является интенсивно развивающимся направлением при разработке алгоритмов решения задач дискретной оптимизации.

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

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

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

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

Для достижения цели были поставлены следующие задачи: 1) провести подробный структурный анализ сложности решения многостадийных задач с различными критериями и дополнительными ограничениями; 2) исследовать задачи календарного планирования с различными типами ресурсов и критериями оптимизации, в том числе и задачи планирования производственных инвестиционных проектов; 3) разработать точные и приближенные алгоритмы их решения.

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

Научная новизна результатов состоит в следующем: проведен подробный структурный анализ сложности решения разномаршрутной задачи (JobShop) с различными критериями, выделены новые полиномиально разрешимые случаи одномаршрутной задачи (Flow-Shop) с тремя машинами и задачи переналадки оборудования, предложены и обоснованы соответствующие алгоритмы; исследована задача обработки партии однотипных деталей со сложным технологическим маршрутом при разных критериях и ограничениях; на основе метода динамического программирование проведен анализ сложности задачи календарного планирования в зависимости от структуры входных данных и видов ресурсов; предложены алгоритмы решения некоторых задач оптимизации прибыли инвестиционных проектов.

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

• Всесоюзной конференции "Проблемы хозяйственного освоения БАМ" (Новосибирск, 1977);

• Всесоюзных совещаниях "Методы и программы решения оптимизационных задач на графах и сетях" (Улан-Удэ, 1982; Новосибирск, 1984, 1989);

• Всесоюзной конференции "Методы математического программирования и программное обеспечение" (Свердловск, 1984);

• Межреспубликанских семинарах по дискретной оптимизации (Судак, 1985, Ялта, 1987, Алушта, 1989, Ужгород, 1990);

• Всесоюзной школе "Дискретная оптимизация и компьютеры" (Таштагол, 1987);

• Всесоюзном семинаре "Дискретная оптимизация и исследование операций" (Новосибирск, 1990);

• Всесоюзной школе-семинаре "Декомпозиция и координация в сложных системах" (Алушта, 1990);

• Всесоюзной школе-семинаре "Статистический и дискретный анализ данных и экспертное оценивание" (Одесса, 1991);

• Всероссийских конференциях "Математическое программирование и приложения" (Екатеринбург, 1993, 1995);

• Международной конференции "Проблемы оптимизации и экономические приложения" (Омск, 1997);

• Международном симпозиуме "Комбинаторика, теория графов, алгоритмы и приложения" (Прага, 1998);

• Международной Сибирской конференции по исследованию операции (Новосибирск, 1998);

• Международном семинаре "Модели и алгоритмы в календарном планировании и теории расписаний МАРЗР-99" (Ренессе, Нидерланды, 1999);

• Международном семинаре "Методы дискретной оптимизации в расписаниях и компьютерном дизайне" (Минск, 2000);

• Международном семинаре "Модели и алгоритмы в календарном планировании и теории расписаний МАР8Р-01" (Модане, Франция, 2001);

• Российских конференциях "Дискретный анализ и исследование операций "(Новосибирск, 2000, 2002, 2004);

• Международной конференции по исследованию операций (Клагенфурт, Австрия, 2002);

• Всероссийских конференциях "Проблемы оптимизации и экономические приложения" (Омск, 2003, 2006, 2009);

• Международном совещании "Методы дискретной оптимизации в производстве и логистике"(Омск - Иркутск, 2004);

• Международной конференции "Комбинаторная оптимизация" (ЕССО, Минск, 2005);

• Российской конференции "Дискретная оптимизация и исследование операций" (Владивосток, 2007);

• Азиатских школах-семинарах "Оптимизация сложных систем" (Новосибирск, 2006, Киргизия, 2007, Немал, 2008);

• Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Северобайкальск, 2008);

• Международной научной конференции "Дискретная математика, алгебра и их приложения" (Минск, 2009);

• а также на семинарах в Институте информационных технологий и прикладной математики СО АН СССР, Институте математики им. C.JI. Соболева СО РАН и его Омском филиале, Омском государственном университете им. Ф.М. Достоевского.

Публикации. По теме диссертации опубликовано более 60 работ, из них 29 статей, в том числе 10 в центральных и зарубежных журналах.

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

Основное содержание работы

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

Одномаршрутная задача Джонсона заключается в минимизации времени обработки п деталей на конвейерной линии, состоящей из m машин. Каждая деталь проходит один и тот же технологический маршрут обработки, последовательно обрабатываясь на машинах 1,2,..., т. Время обработки деталей на каждой машине может быть различным. Одновременная обработка нескольких деталей на одной машине невозможна. Данная задача обозначается в литературе как Ее исследовали Джонсон Д., Глебов Н.И., Севастьянов C.B. и многие другие авторы. Особый интерес представляет задача трех машин F3\\Cmax. Несмотря на простоту формулировки, она является NP-трудной в сильном смысле.

Обозначим времена обработки детали г на первой, второй и третьей машине через а», bj и с,; соответственно. Известно несколько полиномиально разрешимых случаев. Отметим следующие из них:

b-, < min{a,;, С;}, i = 1,2,..., n; o-i < bi < a, i = 1,2,..., n; Q < bi < a-i, i = 1,2,..., n.

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

Теорема 1.1. Задача Джонсона с тремя машинами при условии

min{a,, с/} < bi < maxfa,;, с,}, г = 1,2,..., п,

полиномиально разрешима с трудоемкостью 0(п?) операций.

Рассматриваемая в параграфах 1.2-1.4 разномаршрутная задача или Jobshop, является обобщением задачи Flow-shop. Требуется обработать п деталей на т машинах. Обработка детали j заключается в последовательном выполнении г,- операций. Операция i детали j выполняется на машине rriij непрерывно в течение б единиц времени, г = 1,2,...,г;-, j = 1,2,...,гг. Последовательность (m\j,rri2j, ■ ■ ■ ,nirjj) называется технологическим маршрутом обработки детали j. Совместное выполнение двух операций на одной машине не допускается. В некоторых постановках могут быть заданы дополнительные параметры: директивный срок dj G Z+, к которому желательно завершить обработку детали j, Wj - ее весовой коэффициент и другие. Данную задачу принято обозначать как J||F(Ci, Сг>...,Сп), где С,- - время завершения обработки детали j,j~l,'2,..., п.

Для оценки качества расписаний используются самые различные критерии: общий срок обработки деталей Стах, средневзвешенное время завершения Cj-> суммарный взвешенный штраф за нарушение директивных сроков J2 щТ-j, максимальное запаздывание Lnwx, число деталей, обработка которых не завершена в срок Uj и другие. Разномаршрутная задача с каждым из этих критериев является NP-трудной в сильном смысле. В работе предложен общий алгоритм решения задачи Job-Shop, основанный на схеме динамического программирования, позволяющий решать задачу с дополнительными ограничениями и различными критериями. Установлена псевдополиномиальная разрешимость задачи Job-Shop при фиксированном числе деталей.

Теорема 1.2. Разномаршрутная задача J||Cmax минимизации общего вршени обработки деталей при условии, что количество обрабатываемых

деталей п ограничено константой, разрешима за псевдополиномиальное время.

Аналогичное утверждение о псевдополиномиальной разрешимости задачи с фиксированным числом деталей доказано и для других критериев. Эти результаты вытекают также из более поздних работ Миддендорфа М. и Тим-ковского В.Г.

На основе предложенного алгоритма для задачи с критериями Стах и Csr и фиксированным числом деталей разработана вполне полиномиальная ан-проксимационная схема.

Теорема 1.3. Для разномаршрутной задачи J||Cmax минимизации общего времени обработки деталей при условии, что количество деталей п

ограничено константой, существует вполне полиномиальная аппроксима-

2 11

ционпая схема трудоемкости 0(п2(^~)"), где N = rj - общее чиыо

операций всех деталей.

Данный подход использовался и для задачи минимизации сред-

невзвешенного времени завершения обработки деталей. Однако, построить вполне полиномиальную аппроксимационную схему удалось только при равных весовых коэффициентах Wj. Трудоемкость схемы для этого критерия удалось уменьшить до 0{п2{~)п).

В работах Глебова Н.И., Севастьянова C.B., Сотскова Ю.Н. предложены полиномиальные алгоритмы решения разномаршрутной задачи с двумя деталями J\n — 2\F(Ci,C2). В параграфе 1.4 построен еще один полиномиальный алгоритм решения задач J\n = 2|Cmax и J\n — 2|С^, учитывающий различные дополнительные ограничения на совместное выполнение операций. Трудоемкость алгоритма - 0(Llog2 L) операций, где L - число нар операций различных деталей, совместное выполнение которых запрещено.

Одной из важных проблем в теории расписаний является переналадка оборудования. В параграфе 1.5 рассматривается базовая модель этой задачи. Имеется машина, на которой необходимо обработать п деталей. Время настройки машины после завершения обработки детали г на выпуск детали j составляет c,j. Требуется определить, в какой последовательности обрабатывать детали, чтобы общее время переналадки машины было минимально. Эта задача NP-трудна в сильном смысле даже при условии, что все Су равны О или 1. Известно несколько полиномиально разрешимых случаев описанных в работах Гилмори П.С. и Гомори P.E., Гарфинкеля P.C., Сисло М.М. и других. В данном параграфе также выделен содержательный случай, для которого построен алгоритм полиномиальной трудоемкости.

Матрица ||с;,|| называется ленточной с шириной ленты t, если при \i—j\ > t

имеет место с¡^ = оо .

Теорема 1.4. Задача минимизации времени переналадки оборудования на матрицах ленточной структуры разрешима за время 0(пЬ\).

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

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

Задача заключается в следующем. На производственной линии, состоящей из т различных машин М\, М-2,..., Мт, необходимо обработать партию из п однотипных деталей. Обработка детали заключается в последовательном выполнении г операций (0г,02,... ,Ог). Операция С^- выполняется на машине Мт в течение р^ единиц времени, ] = 1,2,... ,г. Машины в технологическом маршруте могут повторяться. Прерывания операций запрещены. Одновременное выполнение двух и более операций на одной машине не допускается. Различные варианты постановок зависят от выбранных критериев и дополнительных производственных ограничений.

В параграфах 2.1-2.3 исследуются так называемые циклические расписания обработки партии однотипных деталей. Циклические расписания играют важную роль в организации производства. Они обеспечивают ритмичность загрузки оборудования и исполнителей, позволяют эффективно планировать как поставки ресурсов, так и сбыт продукции. Обозначим через зц- время начала выполнения операции О, детали к. Расписание называется циклическим, если для любого у = 1,2,...,г и для любого к 6 2 выполняется = 5-/ + С (к — 1), где = 5;ч и С - длина цикла или циклическое время.

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

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

Сложность задач построения циклических расписаний при различных ограничениях исследовалась Холлом Н.Г., Ли Т.Е., Хеннен С., Познером М., Раунди Р. и другим учеными. В силу трудности большинства таких задач основное внимание исследователей уделяется построению приближенных и эвристических алгоритмов.

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

Теорема 2.1. Задача минимизации времени цикла при условии, что число одновременно обрабатываемых деталей ограничено фиксированной величиной Н, является псевдополиномиалъио разрешимой с трудоемкостью 0(Р2Н~1), где Р - суммарная длительность всех операций одной детали.

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

emu О

В параграфе 2.2 предлагается малотрудоемкий псевдополиномиальный алгоритм минимизации времени цикла при одновременной обработке не более двух деталей с трудоемкостью 0(Рг2 log2 г). При условии отсутствия к концу цикла незавершенных операций задача полиномиально разрешима, и расписание с минимальной длиной цикла может быть построено за 0(r3log2 r) элементарных операций.

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

Теорема 2.3. Задача минимизации времени и,икла при наличии запретов на простой между некоторыми операциями детали является NP-трудной в сильном смысле.

С другой стороны, показано, что при условии обработки детали без простоев задача полиномиально разрешима. Кроме того, доказано, что если в технологическом маршруте число пар операций, которые не требуют условия "no-wait ограничено константой, то задача минимизации длины цикла является псевдополиномиально разрешимой.

В параграфе 2.4 рассматривается задача минимизации общего времени обработки однотипных деталей. Доказана следующая теорема:

Теорема 2.4. Задача минимизации общего времени обработки однотипных деталей является NP-трудной.

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

В главе 3 исследуется сложность общей задачи календарного планирования с ограниченными ресурсами в следующей постановке. Необходимо выполнить множество взаимосвязанных работ V = {1,2,... ,N}. Взаимосвязь задается частичным порядком Е. Если (г, j) 6 Е, то выполнение работы j не может начаться до завершения работы г. Пусть КГ - множество возобновимых, а К" - множество складируемых ресурсов. На период Т планирования проекта для любого t = 1,2,... ,Т в момент t — 1 поступает Qk(t) единиц ресурса вида к 6 Ка, и во временном полуинтервале [t — 1 , i) имеется Qk(t) единиц ресурса вида к 6 К' . Каждая работа г € V характеризуется длительностью р; G и потребностью qf (г) в ресурсе вида к С Kr\J К" в интервале [т - 1, г), г = 1,2,... ,p.j. В некоторых постановках могут быть заданы директивные сроки d, 6 2/ + завершения выполнения работы г G V. Предполагается, что каждая работа выполняется непрерывно. Требуется определить такие сроки выполнения работ проекта с учетом технологического порядка, директивных сроков и ограничений на ресурсы, при которых достигается оптимальное значение некоторой целевой функции.

Изложение построено следующим образом. Сначала рассматривается простейшая задача календарного планирования с единственным ресурсом возобновимого типа. Длительности pj всех работ равны единице, потребление ресурса q} также единичное, и в наличии имеется Q единиц ресурса. Данная задача P\prec,pj = l|Cmax является NP-трудной в сильном смысле. В параграфе 3.2 на основе схемы динамического программирования разработан алгоритм, трудоемкость которого равна Oil-—) I, где п - ширина ча-

стнчного порядка Е. Отсюда вытекает, что если ширина частичного порядка ограничена константой, то задача P\prec,pj = l|Cmax является полиномиально разрешимой.

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

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

Далее исследуются задачи с ресурсными ограничениями. Ресурсы, используемые при выполнении работ, делятся на возобновимые и складируемые. К возобновимым ресурсам относятся рабочая сила, оборудование, производственные мощности, а к складируемым материалы с длительным сроком хранения, финансы, сырье. Невостребованный объем складируемого ресурса переходит на следующий период времени, но при использовании он не восстанавливается. Наиболее изучена сложность задачи календарного планирования с возобновимыми ресурсами и критерием общего времени завершения всех работ. Для задачи со складируемыми ресурсами важный результат получен Гимади Э.Х., Залюбовским В.В., Севастьяновым C.B.: если все используемые ресурсы - складируемого типа, то задача календарного планирования с критерием СП1ах является полиномиально разрешимой. К сожалению, этот результат является уникальным и не обобщается на другие критерии. В параграфе 3.3 доказана NP-трудность в сильном смысле для задачи с критерием

сь

Теорема 3.1. Задача календарного планирования со складируемыми ресурсами и критерием среднего времени завершения работ является NP-трудной в сильном смысле даже в огучае работ единичной длительности.

В параграфах 3.4-3.5 описываются варианты алгоритма динамического программирования для решения задач календарного планирования с различными критериями и типами ресурсов. Для задачи с постоянным уровнем возобновимых ресурсов и критериями Стах и С£ трудоемкость предлагаемого

алгоритма не превосходит где т = \КГ\ - общее число видов

ресурсов, Р - суммарная длительность всех работ, п - ширина частичного порядка. Если используются ресурсы произвольного типа и их наличие меняется во времени, то трудоемкость алгоритма выше и ограничена величиной 0(Рпт(^-) ), где т = \Ка\ + \КТ\ - общее число видов ресурсов. Точно такую же оценку трудоемкости имеют алгоритмы решения задач с другими рассматриваемыми критериями. Для анализа трудоемкости оценим длину входа задачи

г т N N т р,

2ЛГ+Е Е +Е рг+Е Е Е О*) ^

1=1 к=1 ¿=1 »'=1 к—Л г=1

< 'Ш + Тт 1о§2 Я тах + N 1о§2 Ртах + тР 1о§2 дтах, где <2тах = тах тал С?*^), рпюх -- тахр,:, дтах = тах тах тахд-'(т).

«=1.ГЬ=1,т г=1,Л' »=1,^ к—1.т т=1,р;

Трудоемкость алгоритма 0(Рпт(^)п) зависит полиномиально от всех параметров, кроме ширины п частичного порядка.

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

Таким образом, можно сделать важный вывод, что для рассматриваемой задачи ЫР-трудность в сильном смысле заключена именно в ширине частичного порядка. Обратим внимание на некоторые особенности теории сложности. Если потребление ресурсов при выполнении работ равномерно q^{т) = то длина входа уменьшается до величины 2N + Ттlog2Qmax + N\og2pnшx + пШ 1о§2 <7тах> и тот же самый алгоритм становится псевдоноди-номиальным. Этот парадокс легко объясним, так как длина входа существенно уменьшилась, а трудоемкость алгоритма осталась прежней.

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

Для задачи с равномерным уровнем возобновимых ресурсов: д^'(т) = д-\ = и критериями Стах и С^ удалось построить аппроксимационные схемы. Их описание дано в параграфе 3.6.

Теорема 3.3. Если ширина п заданного на. множестве работ частичного порядка ограничена константой, то для задачи календарного планирования проектов с ограничениями на возобновимые ресурсы и критерием оби^его вршени завершения работ существует вполне полиномиальная аппрокси-мациоппая схема трудоемкости 0(пт(—)п), где N - количество работ проекта, am- число видов ресурсов.

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

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

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

Впервые в качестве критерия прибыль проекта предложил использовать Расселл А. в 1970 году. Задача была сформулирована как задача нелинейного программирования, но без ограничений на ресурсы. Эти работы были продолжены Гринольдом P.C., Демеулемеестером Е., Херроеленом В., Эльмахра-би С.Е., Петтерсоном Д. и другими. Таварес, Л. предложил метод, в основе которого лежит динамическое программирование. Этот метод успешно применялся для решения крупномасштабных проектов строительства железных дорог в Португалии. Янгом К., Талбортом Ф., Петтерсоном Д. исследовались задачи с реинвестированием прибыли.

Под инвестиционным проектом будем понимать совокупность взаимосвязанных работ V — {1,2,..., А^} с заданным частичным порядком их выполнения Е. Рассматривается единственный ресурс складируемого типа финансовый. На период планирования проекта [О,Т) в момент времени Ь — 1 имеются финансовые ресурсы объемом К(1), Ь = 1,2,..., Т. Работа з 6 V характеризуется длительностью pj £ 2+ и потребностью к^{т) в складируемом ресурсе в интервале [т — 1, г), где т = 1,2,... Предполагается, что каждая работа выполняется без прерываний. Доход, получаемый от выполнения работы j £ V, может быть распределен по времени и задан потоком поступлений сДт), где т = 1,2,... ,ру Чистой приведенной прибылью работы з называется величина

Р1 I \ р> и / \

МРу. = У с^ -у к^ 3 ¿а+гог-1'

где го - цена капитала на рынке или ставка рефинансирования. Как и ранее, через в] обозначим момент начала выполнения работы з & V, а через N1 = {з € V | < Ь ^ вз + - множество работ, выполняемых в интервале [£ — 1, ¿). Получаем модель:

АГРУ (Б) = У" ,**РУ[ -> гаах г г г

Е Ек& - ч) < Е +Е Е- е =] '2>

jeNl ¿=1 ¿еЛ',

^< (г,з)еЕ\ ^>0, з = \,2,...

В параграфе 4.2 установлено, что задача календарного планирования проектов со складируемыми ресурсами и критерием чистой приведенной прибыли является ^-трудной в сильном смысле даже в случае работ единичной длительности. Алгоритм динамического программирования, предложенный в параграфе 3.3, адаптирован для этой модели и, таким образом, результат о полиномиальной разрешимости задачи календарного планирования при фиксированной ширине частичного порядка справедлив и для ИРУ-критерия при возможности реинвестирования получаемого дохода.

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

реть модель следующего вида:

NPVj

^D(t)-(l+r)D(t-l) h (1 + гоГ1

—¥ max

f=1 4jeNt

jm

+D(t) - (1 + r)D(t - l)j >0, t* = 1,2.....Г;

Si+pi^Sj, (i,j)eE; s7' > 0, i = 1,2,... ,ЛГ.

где 7J(i) - общий объем кредитов, необходимый для неотрицательности баланса платежей с учетом кредитов, взятых в предыдущие годы, а г - ставка по кредитам. В данной модели величины D(t) являются переменными. Несмотря на наличие в модели дополнительных переменных, удалось доказать следующую теорему:

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

Одной из важных составляющих инвестиционного проектирования является понятие риска. Несмотря на многочисленные публикации по исследованию рисков, для задач календарного планирования производственных инвестиционных проектов эта тема проработана недостаточно глубоко. Параграф 4.4 посвящен моделированию ситуации, когда поступления с,-(т) являются случайными величинами. При этом количество параметров, необходимых для оценки качества расписаний, существенно возрастает. Кроме математического ожидания чистой приведенной прибыли приходится вычислять ее дисперсию и вероятность невыполнения проекта при заданных объемах ресурсов. Самым информационным с точки зрения анализа расписания является вероятностное распределение баланса платежей в каждый момент времени.

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

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

Имеется п инвестиционных проектов и начальный капитал К. Пусть к/, - вложения в проект г, а & - прибыль от его выполнения, причем является случайной величиной с математическим ожиданием тгц = МИзвестны ковариации пц — — — M£j). Дискретным инвестиционным портфелем называется вектор х = (х\,х2, ■■■,х71), где x.t = 1, если проект i реализуется, u I; = 0 - в противном случае. Ключевыми характеристиками портфеля являются математическое ожидание прибыли проекта

п п п п

Trip = = mixi 11 Риск (дисперсия прибыли) Vp — Е JZ l'ijxi'xj-

i=1 i=l ¿=1j=1 Выпишем модель задачи:

п п

Е Е '';./ xixi

I--1 j=l

п

Е THiXi —> max

л

J2 k>xi ^

»=i

X,;G{0,1}, i — 1,2,... , n.

Под решением двз'хкритериальной задачи будем понимать построение полного множества альтернатив. В работе показано, что при целочисленных значениях величин т,; мощность полного множества альтернатив задачи формирования инвестиционного портфеля не превосходит Сп, где С - средняя прибыль проектов (величина, не зависящая от п). Несмотря на такой оптимистичный результат, имеет место теорема.

Теорема 4.3. Задача построения полного множества альтернатив при выборе инвестиционных проектов является NP-трудной в сильном смысле.

Основное внимание в параграфе 4.5 сосредоточено на поиске эффективно разрешимых случаев. При независимых проектах для построения полного

множества альтернатив предлагается алгоритм исевдополиномиальной труп

доемкости 0(пКМ2), где М = ]СШ<-

¿=1

Аналогичный результат удается получить, когда все проекты линейно зависимы. Тогда существует случайная величина £ и = а* + где а*, Д: -некоторые коэффициенты, г — 1,2,...,п. Целевая функция принимает вид

п

(Еßixi)2D(i, min. Для реализации алгоритма динамического программи-

г=1

рования потребуем, чтобы коэффициенты были целочисленными. Пусть В\ — 53 Ai 53 А- Методом динамического программирования ре-

>:/},<() г:Д>0

таем серию подзадач

j

53 miXj max f-i

bi < ¿/?A;<b2, ;=l

53 ^г^»' — «=1

x, e{0,1}, г = 1,2,..., j,

для j = 1,2,..., ?г, fc = 1,2,..., К и целых b\ 6 [£?i,0]; b2 £ [0, Полное множество альтернатив формируем из решений подзадач при j = п и к = А'. Трудоемкость этого алгоритма 0(riKB\B2) исевдополиномиально зависит от длины записи входных данных.

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

линейная комбинация II базисных независимых случайных величин i/V», то

я я и

есть = оц + Pihiph- Тогда риск выражается как 53 Z>(V>a)(53 А/»х>)2> и ft=-i 1 ;.=i решается задача с линейными ограничениями

п

nil '', > max

?=1

bm<t,№><b2h, ft = 1,2,..., Я,

/=i

£ kiXl < К, ?=-l

^ e {од}, ?; = i,2,...,n,

H

что гарантирует верхнюю оценку 53 ¿^(i/'/i)(max{|ii1/,j, б2/,.})2 для риска порт-

/1=1

феля. Чтобы построить полное множество альтернатив, необходимо решить задачу для целочисленных by, 6 (jBi/,,0], b2h 6 \0,B2it], где B\h — 53 А/и B2h = 53 A'»> A = 1,2,...,Я. Трудоемкость алгоритма составит 0(пЯЯпД21Я12Я22 • • • ВШВ2Н).

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

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

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

1. Доказана псевдополиномиальная разрешимость разномаршрутной задачи с различными критериями при фиксированном числе деталей; выделен полиномиально разрешимый случай задачи Джонсона для трех машин.

2. Исследованы задачи обработки партии однотипных деталей: разработан алгоритм решения задачи минимизации времени цикла при ограничении числа одновременно обрабатываемых деталей; доказана ОТ-трудность в сильном смысле задачи минимизации циклического времени при ограничениях на простой между операциями; установлена ИР-трудность задачи минимизации общего времени обработки партии однотипных деталей.

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

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

5. Предложены и исследованы модели планирования инвестиционных проектов: доказана ЫР-трудность в сильном смысле задачи календарного планирования с критерием максимизации чистой приведенной прибыли; разработан алгоритм решения задачи максимизации прибыли с учетом реинвестирования дохода и возможности использования кредитов; исследована сложность задачи формирования инвестиционного портфеля в дискретной постановке.

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

[1] Гимади Э.Х., Сервах В.В., Сокольская Т.И. Программная реализация на ЭВМ модели календарного планирования строительства БАМ // Материалы 2 Всесоюзной конференции "Проблемы хозяйственного освоения ВАМ", Новосибирск, 1977.

[2] Еремеев A.B., Романова A.A., Сервах В.В., Чаухан С.С. Приближенное решение одной задачи управления поставками // Дискретный анализ и исследование операций, Сер.2, 2006. - Т.13, N.l. - С.27-39.

[3] Корнеева М.В., Сервах В.В. Об одной дискретной задаче выбора инвестиционных проектов // Материалы 14 Байкальской международной школы-семинара "Методы оптимизации и их приложения", Северобай-кальск, 2008. - Т.5. - С.308-316.

[4] Марыкина М.В., Сервах В.В. Алгоритм решения задачи выбора инвестиционных проектов // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2006. - С.110.

[5] Межецкая М.А., Сервах В.В. О задаче обработки партий однотипных деталей // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2006. - С. 111.

[6] Межецкая М.А., Сервах В.В. О задаче минимизации общего времени выпуска партии однотипных деталей // Материалы 14 Байкальской международной школы-семинара "Методы оптимизации и их приложения", Северобайкальск, 2008. - Т.1. - С.468-474.

[7] Межецкая М.А., Сервах В.В. О задаче обработки партии однотипных деталей со сложным технологическим маршрутом // Третья Международная научная конференция "Танаевские чтения", Минск, 2007. -С.119-121.

[8] Романова A.A., Сервах В.В. О структуре оптимальных расписаний в задаче с нефиксированными маршрутами размерномти 3x3 // Препринт, Омский государственный университет, Омск, 2002. 40с.

[9] Романова A.A., Сервах В.В. О структуре оптимальных расписаний в задаче с нефиксированными маршрутами // Материалы Российской конференция "Дискретный анализ и исследование операций", Новосибирск, 2002. - С.221.

[10] Романова A.A., Сервах B.B. О построении циклических расписаний для задачи обработки однотипных деталей // Материалы Российской конференции "Дискретный анализ и исследование операций", Новосибирск,

2004.-С. 175.

[11] Романова A.A., Сервах В.В. Алгоритмы решения одной задачи построения циклических расписаний // Труды 13 Байкальской международной школы-семинара "Методы оптимизации и их приложения", Иркутск,

2005. - Т.5. С.131-135.

[12] Романова А. А. Сервах В.В., Планирование выпуска партии однотипных деталей со сложным маршрутом обработки // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2006. - С.52.

[13] Романова A.A., Сервах В.В. Задача построения циклического расписания с минимальным временем цикла и дополнительными ограничениями // Материалы 14 Байкальской международной школы-семинара "Методы оптимизации и их приложения", Северобайкальск, 2008. - Т.1.

С.491-497.

[14] Романова A.A., Сервах В.В. Оптимизация выпуска однотипных деталей на основе циклических расписаний // Дискретный анализ и исследование операций, 2008. - Т. 15, N5. - С.47-60.

[15] Романова A.A., Сервах В.В. Об одной задаче построения циклического расписания /'/ Информационный бюллетень Ассоциации мат. программирования №11, Екатеринбург, УрО РАН, 2007. - С.206.

[16] Романова A.A., Сервах В.В. Задача построения циклического расписания с дополнительными ограничениями // Материалы Российской конференции «Дискретная оптимизация и исследование операций» (Владивосток, 2007), Новосибирск: Изд-во Ин-та математики, 2007. -С. 135.

[17] Сервах В.В. О задаче Акерса-Фридмана // Материалы 15 Всесоюзной студенческой конференции Новосибирск,1977. - С.54-63.

[18] Сервах В.В. О задаче Акерса-Фридмана //В кн. Управляемые системы, Новосибирск, 1983. -Вып.23. - С.70-81.

[19] Сервах В.В. Алгоритм, решения задачи Акерса-Фридмаиа // Материалы научно-технической конференции "Методы математического программирования и программное обеспечение", Свердловск, 1984. С.99.

[20] Сервах B.B. Некоторые свойства трсхстаночной задачи Джонсона // В кн. Дискретная оптимизация и численные методы решения прикладных задач, Новосибирск, ВЦ СО АН СССР, 1986. - С.99-115.

[21] Сервах В.В. Задача коммивояжера на ленточных графах // Тезисы докладов 3 Всесоюзной школы "Дискретная оптимизация и компьютеры", М.ДЭМИ, 1987. - С.58.

[22] Сервах В.В. Задача коммивояжера на ленточных графах // В кн. Управляемые системы, Новосибирск, 1988. - Вып.28. - С.45-55.

[23] Сервах В.В. Календарное планирование с работами единичной длительности // Материалы Межреспубликанского семинара по дискретной оптимизации, Киев, 1990. - С.66.

[24] Сервах В.В. Алгоритм решения задачи календарного планирования с единичными длительностями работ /'/ В кн. Дискретная оптимизация и анализ сложных систем, ВЦ СО АН СССР, Новосибирск, 1989. - С.99-107.

[25] Сервах В.В. Задача сетевого планирования с ограниченными ресурсами j/ Тезисы докладов 4 Всесоюзного совещания "Методы и программы решения оптимизационных задач на графах и сетях", Новосибирск, 1989. -4.2. - С.100.

[26] Сервах В.В. О линейном размещении ориентированного взвешенного графа, // Материалы 4 Всесоюзной школы-семинара "Статистический и дискретный анализ данных и экспертное оценивание", Одесса, 1991. -С.113.

[27] Сервах В.В. Эффективные алгоритмы для некоторых задач календарного планирования /'/ В кн. Методы решения и анализа задач дискретной оптимизации. Сб.научных трудов под ред. A.A. Колоколова, Омск, ОмГУ, 1992. - С.94-106.

[28] Сервах В.В. Задачи календарного планирования со штрафами за превышение директивных сроков /'/ Инф. бюллетень N4 Ассоциации математического программирования. Тез. докл. конференции "Математическое программирования и приложения", Екатеринбург, 1993. - С.76.

[29] Сервах В.В. Моделирование и оптимизация на транспортной сети города // Тезисы докладов Международной конференции "Проблемы оптимизации и экономические приложения", Омск, 1997. - С.140.

[30] Сервах B.B. Схема динамического программирования для некоторых задач теории расписаний // Материалы Международной сибирской конференции по исследованию операций, Новосибирск, 1998. - С.91.

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

[32] Сервах В.В., О задаче оптимального выбора инвестиционных проектов // Тезисы Всеросийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2003. - С.109.

[33] Сервах В.В. Полиномиально разрешимый случай трехстаиочной задачи Джонсона // Дискретный анализ и исследование операций, Сер. 2, 2006. - Т.13, N.2. - С.44-55.

[34] Сервах В.В. Некоторые задачи календарного планирования инвестиционных проектов // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2009. - С.87.

[35] Сервах В.В. О слоэ/сности задачи построения расписаний с фиксированным числом однотипных деталей // Материалы Международной конференции "Дискретная математика, алгебра и их приложения", Минск 2009. - С. 111.

[36] Сервах В.В., Сергунов A.B. Анализ сложности задачи выбора инвестиционных проектов // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2009. - С. 162

[37] Сервах В.В., Сухих С.Л. Гибридный алгоритм для задачи календарного планирования проектов с учетом реинвестирования прибыли // Автоматика и телемеханика, 2004. - N.3. - С.100-107.

[38] Сервах В.В., Щербинина Т. А. О задаче календарного планирования проекта с различными критериями и складируемыми ресурсами // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2006. - С.93.

[39] Сервах В.В., Щербинина Т. А. Гибридные алгоритмы для некоторых задач календарного планирования проектов // XIII Всероссийская конференция "Математическое программирование и приложения", Екатеринбург, 2007. - С.213-214.

[40] Сервах В.В., Щербинина Т. А. Алгоритмы решения задач календарного планирования с различными критериями // Материалы 14 Байкальской международной школы-семинара "Методы оптимизации и их приложения", Северобайкальск, 2008. - Т.1 - С.506-513.

[41] Сервах В.В., Щербинина Т. А. О ааожности задачи календарного планирования проектов // Вестник НГУ. Серия: математика, механика, информатика, 2008. - Т.8, Вып.З. - С.105-111.

[42] Сервах В.В., Щербинина Т. А. О сложности задачи календарного планирования со складируемыми ресурсами // Российская конференция «Дискретная оптимизация и исследование операций»: Материалы копф. (Владивосток, 2007). — Новосибирск: Изд-во Ин-та математики, 2007. -С.136.

[43] Сервах В.В., Щербинина Т.А. Алгоритм решения задачи календарного планирования с критерием средневзвешенного времени завершения работ // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2009.

[44] Bubnova Е.А., Servakh V.V. Combination of branch and bound algorithm and programming for project management problem // International Conference on Operations Research, Abstract. Klagenfurt, Austria, 2002. -P. 135.

[45] Chauhan S.S., Eremeev A.V., Kolokolov A.A., Servakh V.V. Concave cost supply management problem with single mariufacturing unit //' In A. Dolgui, J. Soldek, O. Zaikin (Eds.) Supply chain optimisation. Kluwer. Acad. Pbs. 2004. - P. 167-174.

[46] Chauhan S.S., Eremeev A.V., Kolokolov A.A., Servakh V.V. On solving concave cost supply management, problem with single manufacturing unit // Proceedings of Production System Design, Supply Chain Management and Logistics Conference. Miedzyzdroje, Poland, 2002. - P. 147-154.

[47] Chauhan S.S., Eremeev A.V., Romanova A.A., Servakh V.V. Approximation of linear cost supply management problem with lower-bounded demands // Discrete Optimization in Production and Logistics, Second International Workshop: proceedings, Omsk-Irkutsk, 2004. - P.16-21.

[48] Chauhan S.S., Eremeev A.V., Romanova A.A., Servakh V.V., Woeginger G. J. Approximation of the supply scheduling problem. // Operations Research Letters. V. 33 (3), May 2005. P.249-254.

[49] Eremeev A.V., Romanova A.A., Chauhan S.S., Servakh V.V. Approximate Solution of the Supply Management Problem // Journal of Applied and Industrial Mathematics, 2007. V.l, N. 4. - P.l-9.

[50] Romanova A.A., Servakh V.V. On some cyclic machine scheduling problem // Abstracts of International Conference of the European Chapter on Combinatorial Optimization, Minsk, 2005. - P.58-59.

[51] Romanova A.A., Servakh V.V. On the Cyclic Schedules for Shop Scheduling Problem with Identical Jobs // International Conference on Operations Research, Abstract Guide. Karlsruhe (Germany), 2006. - P.231.

[52] Servakh V.V. Dynamic programming algorithms for somescheduling problems // ECCO VIII, Conf. of European Chapter of Combinatorial Optimization, Poznan, May 1995: Abstracts. Poznan,1995. - P.80.

[53] Servakh V.V. Scheduling under Resourse Constraints and DueDates // Fifth Czech-Slovak Internationzl Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague,July 1998, Abstracts. - P.89.

[54] Servakh V.V. Polynomially solvable case of the three-stage flow-shop problem // Fourth Workshop on Models and Algorithms for Planning and Scheduling Problems, The Netherlands, 1999 Abstracts, - P.46.

[55] Servakh V.V. A dynamic programming algorithm for some project management problems j j Proceedings of the International Workshop "Discrete optimization methods in scheduling and computer-aided design", Minsk, 2000. P.90-92.

[56] Servakh V.V. A dynamic programming algorithm for scheduling under resource constraints // Firth Workshop on Models and Algorithms for Planning and Scheduling Problems, 2001. - P.99.

[57] Servakh V.V. A polynomially solvable case of the three machine johnson problem. Journal of Applied and Industrial Mathematics, Springer Science, 2008. V.2, N. 3. - P.397-405.

[58] Servakh V.V., Shcherbinina T.A. On some approximation of solution of resource constrained project scheduling problem j I Abstracts of International Conference of the European Chapter on Combinatorial Optimization, Minsk, 2005. - P.64.

[59] Servakh V.V., Shcherbinina T.A. A fully polynomial time approximation scheme for two project scheduling problem j j Preprints of 12th IFAC

Symposium on Information Control Problems in Manufacturing, France, Vol.3. 2006,- P.419-424.

[60] Servakh V.V., Shcherbinina T.A. A Fully Pohjnomial Time Approximation Scheme For Tow Project Scheduling Problems // Reprinted from information control problems in manufacturing 2006, A Proc. Vol. from the 12th IFAC International Symposium, 3 V., Ed. by A. Dolgui, G. Morel and C.E. Pereira, Pages XV-XXXVII, Copyright (2006), with permission from Elsevier, 2007.

- P.l 29-134.

[61] Servakh V.V., Shcherbinina T.A. Complexity of project scheduling problem with nonrenewable resources // Abstract of International Conference of Operations Research in the Service Industry, Germany, 2007. - P.167.

[62] Servakh V.V., Soukhikh S.L. Some cases of the Project Management Problem with profit reinvestment // International Conference on Operations Research: Book of Abstracts. Duisburg, 2001. - P.74.

[63] Servakh V.V., Soukhikh S.L. The Reinvestment of Profit for the Project Management Problem // Eighth International Workshop on Project Management and Scheduling (PMS 2002), Abstract - Valencia, Spain, 2002.

- P.318-321.

Отпечатано с оригинала-макета, предоставленного автором

Подписано в печать 22 февраля 2010 г. Формат бумаги СО х 84 1/16. Тираж 100 эк-з. Заказ N 262.

Копировальный центр «Акцент», ИП Загурскпй C.B. 641021, г. Омск, ул. Лермонтова, 8

Введение <

1 Исследование многостадиных задач теории расписаний

1.1 Полиномиально разрешимый случай задачи Джонсона с тремя машинами.

1.2 Алгоритм динамического программирования построения точного решения разномаршрутной задачи.

1.3 Эффективные алгоритмы решения разномаршрутной задачи с фиксированным числом деталей.

1.4 Полиномиальный алгоритм для разномаршрутной задачи с двумя деталями

1.5 Полиномиально разрешимый случай задачи минимизации времени переналадки оборудования

2 Задачи оптимизации обработки партии однотипных деталей

2.1 Задача минимизации времени цикла с ограничением на число одновременно обрабатываемых деталей.

2.2 Алгоритм решения задачи при условии одновременной обработки на линии не более двух деталей.

2.3 Задача минимизации цикла с запретами на простой между операциями.

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

3 Задачи календарного планирования проектов

3.1 Постановки задач

3.2 Задача календарного планирования при наличии частичного порядка.

3.3 Сложность задач с различными критериями и ресурсными ограничениями . . <.

3.4 Алгоритм решения задачи минимизации общего срока выполнения проектов.

3.5 Алгоритмы решения задачи планированиия проектов с различными критериями.

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

3.7 Гибридный алгоритм для задач календарного планирования с единичными длительностями работ

4 Задачи максимизации прибыли при планировании проектов

4.1 Календарное планирование проектов с критерием чистой приведенной прибыли.

4.2 Сложность задач максимизации прибыли.

4.3 Задачи календарного планирования с кредитами и реинвестированием прибыли.

4.4 Моделирование рисков при планировании проектов.

4.5 Задача выбора проектов.

Теория расписаний и календарное планирование являются одними из важных и интересных направлений в области оптимизации и в настоящее время переживают период бурного развития. Это связано, прежде всего, с появлением принципиально новых видов продукции, технологий, интенсификацией производства, его непрерывным обновлением и совершенствованием. Стремительное развитие систем связи, интернета, логистики ставит перед математиками новые задачи, в том числе в области теории расписаний. На практике возникает множество разнообразных задач календарного планирования производства и сбыта продукции, эффективного использования оборудования и других ресурсов, согласования работы различных служб и так далее. Возникнув в середине 50-х годов прошлого века, теория расписаний усилиями таких ученых, как Глебов Н.И., Михалевич B.C., Танаев B.C., Шкурба В.В., Беллман Р., Бруккер П., Джонсон Д., Джонсон С., Фридман Д. и других превратилась в содержательную научную дисциплину со своей структурой, развитыми исследовательскими подходами [2, 16,26,30,38,82,85,87,89,90,106,129,145,150]. В настоящее время это направление активно развивается в работах Гимади Э.Х, Гордона B.C., Ковалева М.Я., Кононова A.B., Севастьянова C.B., Сотскова Ю.Н., Струсевича В.А., Тимковского В.Г., Войгенгера Г. и многих других российских и зарубежных ученых [12,32,81,83,84,132,134-136,158,159,161,204,205,215,220,221].

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

Большой интерес представляют многостадийные задачи Джонсона [150], Акерса-Фридмана [89], переналадки оборудования [3], исследование которых во многом предопределило развитие теории расписаний. Задача Джонсона, известная в литературе под названием Flow-Shop, заключается в минимизации времени обработки деталей на конвейерной линии, состоящей из последовательно расположенных машин. Технологические маршруты всех деталей совпадают, но длительности обработки могут отличаться. В [150] предложен полиномиальный алгоритм решения задачи с двумя машинами. Однако уже для трех машин задача является NP-трудной в сильном смысле [127] и привлекает внимание многих исследователей [15,18,87,88,108]. Разномаршрутная задача Акерса-Фридмана [89] или Job-Shop представляет собой обобщение задачи Flow-Shop. В ней также необходимо обработать детали па машинах, но технологические маршруты различны, и деталь может поступать на некоторые машины многократно. На практике встречается много вариаций разпомаршрутной задачи, которые еще недостаточно исследованы [101,113].

Еще одна важная задача - минимизация общего времени переналадки оборудования [3]. Ее приходится решать при доставке заготовок и материалов, развозке продукции, настраивании оборудования. Эта задача является составной частью многих прикладных постановок. Наличие в технологическом процессе переналадки оборудования или транспортировки делает задачу составления расписаний NP-трудной в сильном смысле. Однако, несмотря на этот факт, за счет специфики производства в некоторых случаях удается разработать эффективные алгоритмы построения расписаний [130,131,211].

Широкий класс актуальных задач связан с обработкой партии однотипных деталей со сложным технологическим маршрутом [86,100,101,139, 186]. Различные технологические ограничения на временные разрывы между операциями, число одновременно обрабатываемых деталей, количество позиций для их промежуточного складирования, а также дополнительные затраты на транспортировку и хранение деталей приводят к разным поста-новокам, требующих подробного анализа. Значительное внимание уделяется составлению циклических расписаний [104,138,139,168,183,186], которые часто используются в производственных системах в силу их простоты и удобства применения.

Важным направлением дискретной оптимизации является календарное планирование сроков выполнения совокупности взаимосвязанных работ в условиях ограниченных ресурсов [12,38,42,96,97,102,176,182]. Такие задачи возникают при реализации космических и военных программ, разработке месторождений, строительстве и реконструкции предприятий, проектировании новых изделий, их запуске в производство и так далее. Особую актуальность они приобретают при планировании крупномасштабных проектов, требующих больших капитальных затрат [8,13,14]. Необходимо выделить задачи календарного планирования инвестиционных проектов, направленных на получение прибыли [94,117,123,191,207]. В них, кроме ресурсных ограничений, приходится учитывать возможность реинвестирования получаемой прибыли и использования кредитов, изменения рыночной конъюнктуры, вероятностный характер основных параметров проекта.

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

Имеется несколько направлений анализа сложности NP-тpyдныx задач. Во-первых, исследование зависимости трудоемкости построения решения задачи от величины отдельных параметров входной информации. Во-вторых, выделение так называемого "ядра" сложности и построение семейств труднорешаемых примеров. В-третьих, поиск эффективно разрешимых подслучаев. В-четвертых, исследование трудоемкости построения приближенных решений в зависимости от точности приближения.

Кроме широко распространенных понятий полиномиальной разрешимости и ИР-трудности [31] ниже будем использовать также понятия псевдополиномиальной разрешимости и ОТ-трудности в сильном смысле [17]. Алгоритм решения массовой задачи называется псевдополиномиальным, если его трудоемкость полиномиально зависит от длины записи входных данных и значения максимального из числовых параметров. При ограничении числовых параметров сверху некоторой наперед заданной константой псевдополиномиальный алгоритм становится полиномиальным. Задача, для которой существует такой алгоритм, называется псевдополиноми-ально разрешимой. Если при ограничении числовых параметров задача остается ЫР-трудной, то ее называют МР-трудной в сильном смысле. Поэтому будем придерживаться трех градаций сложности задачи: полиномиально разрешимая, псевдополиномиально разрешимая, ЫР-трудная в сильном смысле.

Анализ сложности ИР-трудных задач в зависимости от параметров задачи оказывается наиболее эффективным способом оценки перспектив построения алгоритмов ее решения. В задаче о рюкзаке [152] ИР-трудность обусловлена объемом рюкзака, тогда как от количества предметов трудоемкость алгоритма динамического программирования зависит линейно [115]. Такой же анализ может быть сделан и для других задач. Например, в раз-номаршрутной задаче обработки деталей NP-трудность в сильном смысле связана с числом деталей, то есть при обработке небольшого числа деталей может быть построен эффективный алгоритм поиска оптимального расписания [67,169].

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

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

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

Если получение точного решения задачи требует слишком много времени, то используются приближенные алгоритмы. Здесь опять приходит на помощь анализ сложности, так как современная теория позволяет оценить время построения решения в зависимости от заданной точности. Разработке приближенных алгоритмов решения задач посвящено значительное число работ [11,149,190,205,221]. Как показывают современные результаты, ряд оптимизационных задач имеет некоторый "предел приближаемости". Для одних задач существуют полиномиальные по времени аппроксимаци-онные схемы (РТАБ и РРТАБ), когда при любом фиксированном е > 0 удается предложить полиномиальный алгоритм с относительной погрешностью, не превосходящей е. Для других задач удается построить приближенные алгоритмы с константной оценкой точности. Для задач третьего класса ни при какой относительной погрешности невозможно построение полиномиального алгоритма (при условии Р ф АЛР). Естественно, важным представляется вопрос о том, к какому классу относится та или иная задача. В настоящее время исследование вопросов построения полиномиальных аппроксимационных схем является интенсивно развивающимся направлением при разработке алгоритмов решения задач дискретной оптимизации [5,6,128,146].

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

Для доказательства NP-трудности задачи обычно используется полиномиальная сводимость задач [17,31,152,164]. Доказательство полиномиальной разрешимости задачи конструктивно, то есть приводится конкретный алгоритм, имеющий полиномиальную трудоемкость. В данной работе, при анализе сложностных свойств задачи, большое внимание уделяется использованию схемы динамического программирования [2,9,10], на основе которой удается построить целое семейство точных и приближенных алгоритмов [20,50,54,58,67,73,111,112,195,196]. В работе на многочисленных примерах показано, что такой подход позволяет не только решать задачи, но и является мощным инструментом исследования их сложности. Полиномиальная и псевдополиномиальная разрешимость задач, существование вполне полиномиальной аппроксимационной схемы и многие другие теоретические результаты часто доказываются путем построения конкретного алгоритма, основанного на схеме динамического программирования.

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

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

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

В диссертации проведен подробный структурный анализ сложности решения разномаршрутной задачи (Job-Shop) с различными критериями, выделены новые полиномиально разрешимые случаи одномаршрутной задачи (Flow-Shop) с тремя машинами и задачи переналадки оборудования, предложены и обоснованы соответствующие алгоритмы. Исследована задача обработки партии однотипных деталей со сложным технологическим маршрутом при разных критериях и ограничениях. На основе метода динамического программирование проведен анализ сложности задачи календарного планирования в зависимости от структуры входных данных и видов ресурсов, предложены алгоритмы решения некоторых задач оптимизации прибыли инвестиционных проектов.

Диссертация состоит из введения, четырех глав и заключения.

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

1. Доказана псевдополиномиальная разрешимость разномаршрутной задачи с различными критериями при фиксированном числе деталей; выделен полиномиально разрешимый случай задачи Джонсона для трех машин.

2. Исследованы задачи обработки партии однотипных деталей: разработан алгоритм решения задачи минимизации времени цикла при ограничении числа одновременно обрабатываемых деталей; доказана трудность в сильном смысле задачи минимизации циклического времени при ограничениях на простой между операциями; установлена КР-трудность задачи минимизации общего времени обработки партии однотипных деталей.

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

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

5. Предложены и исследованы модели планирования инвестиционных проектов: доказана КР-трудность в сильном смысле задачи календарного планирования с критерием максимизации чистой приведенной прибыли; разработан алгоритм решения задачи максимизации прибыли с учетом реинвестирования дохода и возможности использования кредитов; исследована сложность задачи формирования инвестиционного портфеля в дискретной постановке.

Заключение

1. Айгнер M. Комбинаторная теория. - М.: Мир. 1982. - 558 с.

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

3. Белламан Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сб., М.:Мир. N.9 - С.219-222.

4. Бронштейн Е.М., Спивак С. Как сформировать оптимальный портфель./ / Рынок ценных бумаг, 1997. Вып.14.

5. Воегингер Г.Д., Севастьянов C.B. Линейная аппроксимационная схема для многопроцессорной задачи Open Shop // Дискретный анализ и исследование операций 1999. - Серия 1, Т.6, N 2. - С. 3-22.

6. Гене Г.В., Левнер Е.В. Эффективные приближенные алгоритмы для комбинаторных задач. Препринт, ЦЭМИ, Москва, 1981.

7. Гимади Э.Х., Сервах В.В., Сокольская Т.И. Программная реализация на ЭВМ модели календарного планирования строительства БАМ // Материалы 2 Всесоюзной конференции "Проблемы хозяйственного освоения БАМ", Новосибирск, 1977.

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

9. Гимади Э.Х., Глебов Н.И. Экстремальные задачи принятия решений. Новосибирск: Новосиб. ун-т, 1982.

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

11. И. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики, М: Наука, 1975. Вып. 31. - С. 35-42.

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

13. Гимади Э.Х., Пузынина Н.М., Севастьянов C.B. О некоторых экстремальных задачах реализации крупный проектов типа БАМ // Экономика и мат. методы, 1979. Вып. 5. - С. 1017-1020.

14. Глебов Н.И. Некоторые случаи сводимости т-станочной задачи Джонсона к задачам с двумя станками. Управляемые системы, Новосибирск, 1978. Вып. 17. - С.46-51.

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

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

17. Данильченко A.M., Левченко С.Н., Панишев A.B. Приближенный алгоритм решения задачи трех станков //Автоматика и телемеханика, 1985. № 7.

18. Емец O.A., Емец Е.М. Моделирование некоторых инвестиционных задач с помощью евклидовой комбинаторной оптимизации// Экономика и математические методы, 2000. Вып. 2. - С. 101-104.

19. Еремеев A.B., Романова A.A., Сервах В.В., Чаухан С.С. Приближенное решение одной задачи управления поставками // Дискретный анализ и исследование операций, Сер.2, 2006. Т. 13, N.1. - С.27-39.

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

21. Ковалев М.М. Дискретная оптимизация (целочисленное программирование). Минск: Б ГУ, 1977. 192 с.

22. Козлов М.К., Шафранский В.В. Календарное планирование выполнения комплексов работ при заданной динамике поступления складируемых ресурсов // Изв. АН СССР. Техническая кибернетика. 1977. -N.4. С. 75-81."

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

24. Колоколов A.A. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исслед. операций, Новосибирск, 1994. Т.1, N 2. - С. 18-39.

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

26. Корнеева М.В., Сервах В.В. Об одной дискретной задаче выбора инвестиционных проектов // Материалы 14 Байкальской международнойшколы-семинара "Методы оптимизации и их приложения", Северобай-кальск, 2008. Т.5. - С.308-316.

27. Косточка A.B. Дискретная математика: Учеб. Пособие. Ч. 2, Новосибирск: Изд-во Новосиб. ун-та, 1985.

28. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения. Сборник лекций молодежных и научных школ по дискретной математике и ее приложениям, М: МГУ, 2001. С. 87-117.

29. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.

30. Кук С.А. Сложность процедур вывода теорем // Киберн. сб. Новая серия, 1975. вып.12. - С. 5-15.

31. Левнер Е.В. Сетевой подход к задачам теории расписаний. Исследования по дискретной математике. М.:Наука, 1973. С.135-150.

32. Марыкина М.В. Сервах В.В., Алгоритм решения задачи выбора инвестиционных проектов // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2006. -С.110.

33. Межецкая М.А. Сервах В.В., О задаче обработки партий однотипных деталей // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2006. С.111.

34. Межецкая М.А., Сервах В.В. О задаче минимизации общего времени выпуска партии однотипных деталей // Материалы 14 Байкальской международной школы-семинара "Методы оптимизации и их приложения", Северобайкальск, 2008. Т.1. - С.468-474.

35. Межецкая М.А., Сервах B.B. О задаче обработки партии однотипных деталей со сложным технологическим маршрутом // Третья Международная научная конференция "Танаевские чтения", Минск, 2007. -С.119-121.

36. Меньшиков И.С. Финансовый анализ ценных бумаг. Москва: Финансы и статистика, 1998. 360 с.

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

38. Павлов В.Н. Межотраслевые системы. Математические модели и методы. Новосибирск, Наука, 1986. 221 с.

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

40. Первозванский A.A., Первозванская Т.Н. Финансовый рынок: расчет и риск. Москва: Инфра-М, 1994. 192 с.

41. Подчасова Т.П., Португал В.М., Татаров В.А., Шкурба В.В. Эвристические методы календарного планирования. Киев: Техника, 1980.

42. Попков В.К. Математические модели связности. Новосибирск: ИВМиМГ СО РАН, 2006. 490с.

43. Романова A.A., Сервах В.В. О структуре оптимальных расписаний в задаче с нефиксированными маршрутами размерномти 3x3 // Препринт, Омский государственный университет, Омск, 2002. 40с.

44. Романова A.A., Сервах В.В. О структуре оптимальных расписаний в задаче с нефиксированными маршрутами // Материалы Российской конференция "Дискретный анализ и исследование операций", Новосибирск, 2002. С.221.

45. Романова A.A., Сервах B.B. О построении циклических расписаний для задачи обработки однотипных деталей // Материалы Российской конференции "Дискретный анализ и исследование операций", Новосибирск, 2004. С.175.

46. Романова A.A., Сервах В.В. Алгоритмы решения одной задачи построения циклических расписаний // Труды 13 Байкальской международной школы-семинара "Методы оптимизации и их приложения", Иркутск, 2005. Т.5. - С.131-135.

47. Романова А. А. Сервах В.В., Планирование выпуска партии однотипных деталей со сложным маршрутом обработки // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2006. С.52.

48. Романова A.A., Сервах В.В. Оптимизация выпуска однотипных деталей на основе циклических расписаний // Дискретный анализ и исследование операций, 2008. Т. 15, N5. - С.47-60.

49. Романова A.A., Сервах В.В. Об одной задаче построения циклического расписания // Информационный бюллетень Ассоциации мат. программирования №11, Екатеринбург, УрО РАН, 2007. С.206.

50. Сервах В.В. О задаче Акерса-Фридмана // Материалы 15 Всесоюзной студенческой конференции Новосибирск,1977. С.54-63.

51. Сервах В.В. О задаче Акерса-Фридмана //В кн. Управляемые системы, Новосибирск, 1983. вып.23. - С.70-81.

52. Сервах В.В. Алгоритм решения задачи Акерса- Фридмана // Материалы научно-технической конференции "Методы математического программирования и программное обеспечение", Свердловск, 1984. С.99.

53. Сервах В.В. Некоторые свойства трехстаночной задачи Джонсона //В кн. Дискретная оптимизация и численные методы решения прикладных задач, Новосибирск, ВЦ СО АН СССР, 1986. С.99-115.

54. Сервах В.В. Задача коммивояжера на ленточных графах // Тезисы докладов 3 Всесоюзной школы "Дискретная оптимизация и компьютеры", М.ДЭМИ, 1987. С.58.

55. Сервах В.В. Задача коммивояжера на ленточных графах //В кн. Управляемые системы, Новосибирск, 1988. вып.28. - С.45-55.

56. Сервах В.В. Календарное планирование с работами единичной длительности // Материалы Межреспубликанского семинара по дискретной оптимизации, Киев, 1990. С.66.

57. Сервах В.В. Алгоритм решения задачи календарного планирования с единичными длительностями работ // В кн. Дискретная оптимизация и анализ сложных систем, ВЦ СО АН СССР, Новосибирск, 1989. С.99-107.

58. Сервах В.В. Задача сетевого планирования с ограниченными ресурсами ¡1 Тезисы докладов 4 Всесоюзного совещания "Методы и программы решения оптимизационных задач на графах и сетях", Новосибирск, 1989, 4.2.-С.100.

59. Сервах В.В. О линейном размещении ориентированного взвешенного графа // Материалы 4 Всесоюзной школы-семинара "Статистический и дискретный анализ данных и экспертное оценивание", Одесса, 1991. С.113.

60. Сервах В.В. Эффективные алгоритмы для некоторых задач календарного планирования // В кн. Методы решения и анализа задач дискретной оптимизации. Сб.научных трудов под ред. A.A. Колоколова, Омск, ОмГУ, 1992. С.94-106.

61. Сервах В.В. Задачи календарного планирования со штрафами за превышение директивных сроков // Инф. бюллетень N4 Ассоциации математического программирования. Тез. докл. конференции "Математическое программирования и приложения", Екатеринбург, 1993. С.76.

62. Сервах В.В. Моделирование и оптимизация на транспортной сети города // Тезисы докладов Международной конференции "Проблемы оптимизации и экономические приложения", Омск, 1997. С. 140.

63. Сервах В.В. Схема динамического программирования для некоторых задач теории расписаний // Материалы Международной сибирской конференции по исследованию операций, Новосибирск, 1998. С.91.

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

65. Сервах В.В., О задаче оптимального выбора инвестиционных проектов // Тезисы Всеросийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2003. С.109.

66. Сервах В.В. Полиномиально разрешимый случай трехстаночной задачи Джонсона // Дискретный анализ и исследование операций, Сер. 2, 2006. -Т.13, N.2. С.44-55.

67. Сервах В.В. Некоторые задачи календарного планирования инвестиционных проектов // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2009.-С.87.

68. Сервах В.В. О сложности задачи построения расписаний с фиксированным числом однотипных деталей // Материалы Международной конференции "Дискретная математика, алгебра и их приложения", Минск 2009. С.111.

69. Сервах В.В., Сергунов А.В. Анализ сложности задачи выбора инвестиционных проектов // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2009. -С.162

70. Сервах В.В., Сухих С.Л. Гибридный алгоритм для задачи календарного планирования проектов с учетом реинвестирования прибыли // Автоматика и телемеханика, 2004. N.3. - С. 100-107.

71. Сервах В.В., Щербинина Т. А. О задаче календарного планирования проекта с различными критериями и складируемыми ресурсами // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2006. С.93.'

72. Сервах В.В., Щербинина Т. А. Гибридные алгоритмы для некоторых задач календарного планирования проектов // XIII Всероссийская конференция "Математическое программирование и приложения", Екатеринбург, 2007. С.213-214.

73. Сервах В.В., Щербинина Т. А. Алгоритмы решения задач календарного планирования с различными критериями // Материалы 14 Байкальской международной школы-семинара "Методы оптимизации и их приложения", Северобайкальск, 2008. Т.1 - С.506-513.

74. Сервах В.В., Щербинина Т. А. О сложности задачи календарного планирования проектов // Вестник НГУ. Серия: математика, механика, информатика, 2008. Т.8, вып.З. - С.105-111.

75. Сервах В.В., Щербинина Т.А. Алгоритм решения задачи календарного планирования с критерием средневзвешенного времени завершения работ // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2009.

76. Сердюков А.И. О задаче коммивояжера при наличии запретов // Сб.Управляемые системы, Новосибирск, 1978. N.17 - С.80-86.

77. Сотсков Ю.Н. Оптимальное обслуживание двух требований при регулярном критерии // Автоматизация процессов проектирования, Минск:ИТК АН БССР, 1985. С.52-62.

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

79. Танаев B.C., Гордон B.C., Шафранский В.В. Теория расписаний. Одностадийные системы. М.: Наука, 1987.

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

81. Теория расписаний и вычислительные машины /под ред. Э.Г. Кофф-мана. М.: Наука, 1984.

82. Тимковский В.Г. Приближенное решение задачи составления расписания циклической системы)/ Экономика и математические методы, АН СССР, 1986. N 1. - С. 171-174.

83. Шкурба В.В. Задача трех станков. М:Наука, 1976. 96 стр.

84. Achugbue J.О., Chin F.Y. Complexity and solutions of some three-stage shop scheduling problems. Math. Oper. Res. 1982. V.l, N.4. - P.532-544.

85. Akers S.B., Friedman J. A non-numerical approach to production scheduling problems // Oper.Res., 1955. Vol.3. - P.429-442.

86. Akers S.B. A graphical approach to production scheduling problems// Oper.Res., 1956. Vol.4, N 2. - P.244-245.

87. Aldakhilallah K.A., Ramesh R. Cyclic scheduling heuristics for a reentrant job shop manufacturing environment // International Journal of Production Research, 2001. V.39(12). - P. 2635-2675.

88. Bandelloni M., Tucci M., and Rinaldi R. Optimal Resource Leveling using Non-Serial Dynamic Programming // European Journal of Operational Research, 1994. V.78. - P. 162-177.

89. Baroum S.M. and Patterson J.H. The Development of Cash Flow Weight Procedure for Maximizing the Net Present Value of a Project // Journal of Operations Management, 1996. V.14(3). - P.209-227.

90. Bigelow C.G. Bibliography on Project Planning and Control by Network Analysis // Operations Res., 1962. V.10. - P.728-731.

91. Blazewicz J., Lenstra J.K., and Rinnoy Kan A.H.G. Scheduling subject to resource constraints: Classfication and complexity // Discrete ^Applied Mathematics, 1983. V.5, N.l. - P. 11-24.

92. Blazewicz J., Cellary W., Slowinski R., Weglarz J. Scheduling under Resource Constraints -Deterministic Models. Baltzer, Basel, 1986.

93. Böttcher J., Drexl A., Kolisch R., and Salewski F. Project scheduling under partially renewable resource constraints // Technical Report 398, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel, 1996.

94. Böttcher J., Drexl A., and Salewski F. Project scheduling under partially renewable resource constraints // Management Science, 1999. V.45(4). -P.543-559.

95. Boudoukh T. Algorithms for solving job shop problems with idntical and similar jobs, based on fluid approximation (Hebrew with English synopsis)// MSc Thesis, Technion, Haifa, Israel, 1999.

96. Boudoukh T., Penn M., Weiss G. Scheduling job shops with some identical or similar jobs // Journal of Scheduling, 2001. V.4. - P.177-199.

97. Brucker P., Drexl A., Mohring R., Neumann K. and Pesch E. Resource-constrained project scheduling: Notation, classification, models, and methods // European Journal of Operational Research, 1999. V.112. - P.3-41.

98. Brucker P., Knust S., Schoo A., and Thiele O. A branch and, bound algorithm for the resource-constrained project scheduling problem // European Journal of Operational Research, 1998. V.107. - P.272-288.

99. Brucker P., Kampmeyer T. Tabu search algorithms for cyclic machine scheduling problems. Osnabrueck, Preprint, 2002, P. 24.

100. Brucker P., Kravchenko S.A., Sotskov Y.N. On the complexity of two machine job-shop scheduling with regular objective. functions. OR Spektrum, 1997. V.19(l). - P.5-10.

101. Brucker P., Kramer A. Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems. European J. Oper. Res., 1996.- V.90. P.214-226.

102. Bubnova E. Servakh V.V. Combination of branch and bound algorithm and programming for project management problem // International, Conference on Operations Research, Abstract. Klagenfurt, Austria, 2002.- P. 135

103. Burns F., Rooker J. Three-Stage Flow-Shops with Recessive Second Stage. Oper.Res. 1978. N.26. - P.207-208.

104. Chauhan S.S., Eremeev A.V., Kolokolov A.A., Servakh V.V. Concave cost supply management problem with single manufacturing unit. //In A. Dolgui, J. Soldek, O. Zaikin (Eds.) Supply chain optimisation. Kluwer. Acad. Pbs. 2004. P.167-174.

105. Chauhan S.S., Eremeev A.V., Romanova A.A., Servakh V.V., Woeginger G. J. Approximation of the supply scheduling problem // Operations Research Letters, 2005. V.33(3) - P.249-254.

106. Chen B., Potts C.N., Woeginger G.J. A review of machine sceduling: complexity, algorithms and approximability // Handbook of Combinatorial Optimization. Boston, MA:I<luwer Acad. Publ., 1998. V.3. - P.21-169.

107. Coffman E.G., Graham Jr, and R.L. Optimal scheduling for twoprocessor systems. Acta Informal. P.200-213.

108. Dantzig G.B. Liscrete-variable extremum problems // Operation Research, 1957. V.5. - P.266-277.

109. Demeulemeester E. and Herroelen W. A Branch-and-Bound Procedure for the Multiple Resource-Constrained Project Scheduling Problem // Management Science, 1992. V.38. - P.1803-1818.

110. Demeulemeester E., Herroelen W., Van Dommelen P. An optimal recursive search procedure for the deterministic unconstrained max-npv project scheduling problem // Technical Report, Departement of Applied Economics, Katholieke Universiteit Leuven, 1996.

111. Doersch R.H., Patterson J.H. Scheduling a Project to Maximize Its Net Present Value: A Zero-One Programming Approach // Management Science, 1977. V.23. - P.882-889.

112. Doersch R.H., Patterson J.H. Scheduling a project to maximize its present value: a zero-one programming approach // Management Sciences, 1977. -V. 23, N 8. P.882-889.

113. Drexl A., Kimms A. Optimization Guided Lower and Upper Bounds for the Resource Investment Problem // Journal of the Operational Research Society, 2001. V.52. - P.340-351.

114. Easa S.M. Resource leveling in construction by optimization // Journal of Construction Engineering and Management, 1989. V.115. - P.302-316.

115. Elmaghraby S.E., Herroelen W.S. The Scheduling of Activities to Maximize the Net Present Value // European Journal of Operational Research, 1990. V.49. - P.35-49.

116. Elmaghraby S.E. Activity networks: project planning and control by network models. New York: Wiley, 1977.

117. Eremeev A.V., Romanova A.A., Chauhan S.S., Servakh V.V. Approximate Solution of the Supply Management Problem // Journal of Applied and Industrial Mathematics, 2007. V.I., N.4. - P.l-9.

118. Fazar W. The Origin of PERT // The controller, 1962. P.598-621.

119. Garey M.R., Johnson D.S., Sethi R. The complexity of flowshop and jobshop scheduling. Math. Oper. Res., 1976. V.l, N.2. - P.117-129.

120. Garey M.R., Johnson D.S. Strong NP-completeness results: Motivation, examples, and implications. // Journal of the ACM, 1978. V. 25. - P. 499508.

121. Garey M.R., Johnson D.S. Complexity result for multiprocessor scheduling under resource constraints // SIAM J. Comput. 1975. V.4. - N.4. - P.397-411.

122. Garfinkel R.S. Vinimizing wallpaper waste. Part I: a class of traveling salesman problems // Operation Research. 1977. V.25. - P.741-751.

123. Gilmore P.C., Gomory R.E. Sequencing a one state-variable machine: a solvable case of the traveling salesmanv problem // Operation Research, 1964. V. 12. - P.655-679.

124. Gimadi E., Sevastianov S. On Solvability of the Project Scheduling Problem with Accumulative Resorces of an Arbitrary Sign // Operations Research Proceedings, Springer, 2002 P.241-246.

125. Gonzalez T., Sahni S. Flowshop and jobshop schedules: complexity and approximation. Oper. Res., 1978. V.26, N.l. - P.36-52.

126. Gordon V.S., Strusevich V.A. Farliness penalties on a single machine subject to precedence constraints: SLK due date assignment // Comput. Oper. Res., 1999. V.26. - P.157-177.

127. Gordon V.S., Potts C.N., Strusevich V.A., Whitehead J.D. Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation // Journal of Scheduling,2008. V.ll, N.5. - P.357-370.

128. Gordon V.S., Strusevich V.A. Single machine scheduling and due date assignment with positionally dependent processing times // European Journal of Operational Research, 2009. V.198, N.l. - P.57-62.

129. Grinold R.C. The payment scheduling problem // Naval Research Logistics Quarterly, 1972. V. 19. - P.123-136.

130. Hall N.G., Lee T.B., Posner M.E. The complexity of cyclic shop scheduling problems. //Journal of Scheduling, 2002. V.5. - P.307-327.

131. Hanen C. Study of a NP-hard cyclic scheduling problem: The recurrent job-shop // European Journal of Operational Research, 1994. V.72. -P.82-101.

132. Hardgrave W.W., Nemhauser G. A Geometric Model and Graphical Algorithm for a Sequencing Problem. Operation Research, 1963, V.ll, N.6. - P.889-900.

133. Herroelen W.S., De Reyck B., DemeulemeesterE.L. Resource-Constrained Project Scheduling: A Survey of Recent Developments // Computers and Operations Research, 1998. V.25. - P.279-302.

134. Herroelen W.S., Gallens E. Computational Experience with an Optimal Procedure for the Scheduling of Activities to to Maximize the Net Present Value of projects // European Journal of Operational Research, 1993. -V. 65. P. 274-277.

135. Herroelen W.S., Van Dommelen P., Demeulemeester E.L. Project network models with discounted cash flows a guided tour through recent developments // European Journal of Operational Research, 1997. -V.100. - P. 97-121.

136. Herroelen W., Demeulemeester E., Bert De Reyck A classification scheme for project scheduling // Project schedling: recent models, algorithms, and applications (edited by Jan Weglarz,) USA, 1999,- P. 1-26.

137. Hu T.C. Parallel sequencing and assembly line problems // Operations Res, 1961. V.9. - P.841-848.

138. Ibarra O., Kim C.E. Fast approximation algorithms for the knapsack and sum of subset problems // Journ. of the ACM, 1975. V.22. - P.463-468.

139. Icmeli O., Erenguc S.S. A tabu search procedure for the resource constrained project scheduling problem with discounted cash Cows // Computers and Operations Research, 1994,- V. 21, N 8. P.841-853.

140. Icmeli 0., Erenguc S.S. A branch and bound procedure for the resource constrained project scheduling problem with discounted cash Cows // Management Science, 1996. V. 42, N 10.- P.1395-1408.

141. Jansen K., Solis-Oba R., Sviridenko M. Makespan minimization in job shops: A linear time approximation scheme // SIAM Journal on Discrete Mathematics, 2003,- V.16, N.2. P.288-300.

142. Johnson S.M. Optimal Two and Three Stage Production Schedules with Setup Times Included. Naval.Res.Logist.Quart., 1954. N.l. - P.61-68.

143. Kamoun H., Sriskandarajah C. The complexity of scheduling jobs in repetitive manufacruring systems // European Journal of Operational Research, 1993. V.70. - P.350-364.

144. Karp R.M. Reducibility among combinatorial problems // In: Miller R.E. and Thatcher J.W. Complexity of Computer Computations. Plenum Press, New York, 1972. P.85-104.

145. Kelley J.E. Critical-Path Planning and Scheduling: Mathematical Basis // Operations Res., 1961.- V.9. P.296-320.

146. Kelley J.E., Walker M.R. Critical Path Planning and Scheduling: An Introduction. Mauchly Associates, Ambler, PA, 1959.

147. Kolish R., Padman R. An Integrated Survey of Deterministic Project Scheduling // OMEGA Journal of Scheduling, 2001. V. 29.- P. 249-272.

148. Kolisch R., Sprecher A., Drexl A. Characterization and Generation of a General Class of Resource Constrained Project Scheduling Problem // Management Science, 1995. V.41. - P.1693-1703.

149. Kononov A., Sevastianov S. and Tchernykh I. When difference in machine loads leads to efficient scheduling in open shops // Annals of Oper. Res., 1999. V.92. - P.211-239.

150. Kovalyov M. Improving the complexities of approximation algorithm for optimization problems. // Operations Research Letters, 1995.- V.17. -P.85-87.

151. Kravchenko S.A. Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem. Discrete Appl. Math., 1999. -98(3)- P.209-217.

152. Kubiak W., Timkovsky V.G. A polynomial-time algorithm for total completion time minimization in two-machine job-shop with unit-time operations. European J. Oper. Res., 1996. 94. - P.310-320.

153. Lawner E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. Sequencing and scheduling: Algorithms and complexity. /j Handbook in Operations Research and Management Science (Graves S.C., Rinnooy Kan A.H.G., Zipkin P., Eds.) NorthHolland, 1993. Vol. 4.

154. Lee T., Posner M. Performance measure and schedules in periodic job shop // Operations Research, 1997. V.45. - P.72-91.

155. LenstraJ.K., Rinnooy Kan A.H.G. Computational complexity of discrete optimization problems. Ann. Discrete Math., 1979. 4. - P.121-140

156. Lerda-Olberg S. Bibliography on Network-Based Project Planning and Control Techniques: 1962-1965 // Operations Res, 1966.- V.15 P.925-931.

157. Markowitz H. Portfolio selection.// The journal of finance, 1952. V.7, N1. - P.77-91.

158. McGormick S.T., Rao U.S. Some complexity results in cyclic scheduling // Mathematical and Computer Modeling, 1994. V.20. - P.107-122.

159. McCormick S.T., Pinedo M.L., Shenker S., Wolf B. Sequencing in an assembly line with blocking to minimize cycle time // Operation Research, 1989. V.37. - P.925-935.

160. Middendorf M., Timkovsky V.G. Transversal graphs for partially ordered sets: Sequencing, Merging and Scheduling problems // Journal of Combinatorial Optimization, 1999.- V.3, N.4.- P.417-435.

161. Mohring R.H. Minimizing Costs of Resource Requirements in Project Networks Subject to a Fixed Completion Time // Operations Research, 1984. V.32. - P.89-120.

162. Neumann K., Schwindt C. and Zimmermann J. Project Scheduling with Time Windows and Scarce Resources: Temporal and Resource-Constrained Project Scheduling with Regular and Nonregular Objective Funsctions. Springer-Verlag, 2002.

163. Neumann K., Zimmermann J. Resource Levelling for Project with Schedule-Dependent Time Windows // European Journal of Operational Research, 1999. V.117. - P.591-605.

164. Neumann K., Zimmermann J. Procedures for Resource Levelling and Net Present Value Problems in Project Scheduling with General Temporal and

165. Resource Constraints // European Journal of Operational Research, 2000. V.127. - P.425-443.

166. Padman R., Smith-Daniels D.E. Early-Tardy Cost Trade-Offs in Resource Constrained Projects with Cash Flows: An Optimization Guided Heuristic Approach // European Journal of Operational Research, 1993. V.64. -P.295-311.

167. Padman R., Smith-Daniels D.E., Smith-Daniels V.L. Heuristics Scheduling of Resource-Constrained Projects with Cash Flows // Naval Research Logistics, 1997. V.44. - P.364-381.

168. Patterson J.H. A Comparison of Exact Procedures for Solving the Multiple-Constrained Resource Project Scheduling Problem // Management Science, 1984. V.20. - P.767-784.

169. Patterson J.H., Slowiñski R., Talbot F.B., W§glarz J. An Algorithm for a General Class of Precedence and Resource Constrained Scheduling Problems // Slowiñski R., W§glarz J. (Eds.). Advances in Project Scheduling. Elsevir, 1989. P.3-28.

170. Project scheduling: recent model, algorithm and applications // edt. by Jan Weglarz. Kluwer Academic Publishers. 1999.

171. Rao U., Jackson P. Identical Jobs Cyclic Scheduling: Subproblems, Properties, Complexity and Solution Aproaches (Ithaca, NY: Cornell University Press), 1993.

172. Romanova A.A., Servakh V.V. On some cyclic machine scheduling problem // Abstracts of International Conference of the European Chapter on Combinatorial Optimization, Minsk, 2005. P.58-59.

173. Romanova A.A., Servakh V.V. On the Cyclic Schedules for Shop Scheduling Problem with Identical Jobs // International Conference on Operations Research, Abstract Guide. Karlsruhe (Germany), 2006. -P.231.

174. Roundy R. Cyclic schedules for job shops with identical jobs // Mathematics of Operations Research, 1992, V.17, N.4, - P.842-865.

175. Russell R.A. A Comparison of Heuristics for Scheduling Projects with Cash Flows and Resource Restrictions // Management Science, 1986. -V.32. P.1291-1300.

176. Russell A.H. Cash Cows in networks. Management Science, 1970 16(5)— P. 357-373.

177. Schirmer F., Drexl A. Partially Renewable Resources -A Generalization of Resource-Constrained Project Scheduling Problem // IFORS Triennial Meeting, Vancouver, 1996.

178. Schuurman P. Woeginger G.J. Approximation Schemes. A Tutorial, 2007 P.33-36.

179. Sepil C. Comment on Elmaghraby and Herroelen's "The Scheduling of Activities to Maximize the Net Present Value" // European Journal of Operational Research, 1994. V.73. - P. 185-187.

180. Servakh V.V. Dynamic programming algorithms for somescheduling problems // ECCO VIII, Conf. of European Chapter of Combinatorial

181. Optimization, Poznan, May 1995: Abstracts. Poznan,1995. P.80.

182. Servakh V.V. Scheduling under Resourse Constraints and DueDates // Fifth Czech-Slovak Internationzl Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague,July 1998, Abstracts, P.89.

183. Servakh V.V. Polynomially solvable case of the three-stage flow-shop problem // Fourth Workshop on Models and Algorithms for Planning and Scheduling Problems, The Netherlands, 1999, Abstracts, P.46.

184. Servakh V.V. A dynamic programming algorithm for some project management problems // Proceedings of the International Workshop "Discrete optimization methods in scheduling and computer-aided design", Minsk, 2000. P.90-92.

185. Servakh V.V. A dynamic programming algorithm for scheduling under resource constraints // Firth Workshop on Models and Algorithms for Planning and Scheduling Problems, 2001. C.99.

186. Servakh V.V. A polynomially solvable case of the three machine johnson problem. Journal of Applied and Industrial Mathematics, Springer Science, 2008. V.2, N.3. - P.397-405.

187. Servakh V.V., Shcherbinina T.A. On some approximation of solution of resource constrained project scheduling problem // Abstracts of1.ternational Conference of the European Chapter on Combinatorial Optimization, Minsk, 2005. P.64.

188. Servakh V.V., Shcherbinina T.A. A fully polynomial time approximation scheme for two project scheduling problem // Preprints of 12th IFAC Symposium on Information Control Problems in Manufacturing, France, Vol.3. 2006,- P.419-424.

189. Servakh V.V., Shcherbinina T.A. Complexity of project scheduling problem with nonrenewable resources // Abstract of International Conference of Operations Research in the Service Industry, Germany, 2007,- P.167.

190. Servakh V.V., Soukhikh S.L. Some cases of the Project Management Problem with profit reinvestment // International Conference on Operations Research: Book of Abstracts. Duisburg, 2001. P.74.

191. Servakh V.V., Soukhikh S.L. The Reinvestment of Profit for the Project Management Problem // Eighth International Workshop on Project Management and Scheduling (PMS 2002), Abstract Valencia, Spain, 2002.- P.318-321.

192. Sevast'janov S.V. Vector summation in Banach space and polynomial algorithms for flow shops and open shops // Math.Oper.Res., 1995. V.20, N.l. - P.90-103.

193. Sevastianov S.V., Woeginger G.J. Makes-pan minimization in open shops: A polynomial time approximation scheme // Math. Programming, 1998. -V.82, N. 1-2. P.191-198.

194. Skutella M. Approximation algorithms for the discrete time-cost tradeoff problem // Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, 1997. P.501-508.

195. Smith-Daniels D.E., Aquilano N.J. Using a Late-Start Resource-Constrained Project Schedule to Improve Project Net Present Value // Decision Sciences, 1987. V.18. - P.617-630.

196. Smith-Daniels D.E., Smith-Daniels V.L. Maximizing the Net Present Value of a Project Subject to Materials and Capital Constraints/ j Journal of Operations Management, 1987. V.7. - P.33-45.

197. Sotskov Y.N., Shakhlevich N.V. NP-hardness of shop-scheduling problems with three jobs. Discrete Appl. Math., 1995. 59(3) - P.37-266.

198. Sotskov Y.N. The complexity of shop-scheduling problems with two or three jobs. European J. Oper. Res., 1991. 53(3) - P.326-336.

199. Syslo M.M. A new solvable case of the traveling salesman problems // Math. Programming, 1973. V.4. - P.347-348.

200. Talbot F.B. Resource-constrained project scheduling with time-resource tradeoffs: The non preemptive case // Management science, 1982. V. 28(10). - P.1197-1210.

201. Talbot F.B., Patterson J.H. An Integer Programming Algorithm with Network Cuts for Solving Resource-Constrained Project Scheduling Problems // Management science, 1978. V.24. - P.1163-1164.

202. Tavares L.V. Multicriteria Scheduling of a Railway Renewal Program // European Journal of Operational Research, 1986. V.25. - P.395-405.

203. Timkovsky V.G. On the complexity of scheduling an arbitrary system. Soviet J. Comput. Systems Sci., 1985 23(5). - P.46-52.

204. Timkovsky V.G. A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem. Discrete Appl. Math., 1197. 77(2) - P. 185-200.

205. Timkovsky V.G. Is a unit-time job shop not easier than identical parallelmachines? Discrete Appl. Math., 1998. 85(2) - P.149-162.

206. Ullman 3.D.NP-complete scheduling problems // J.Comput. System Sci., 1975. V.10. - P.384-393.

207. Vanhoucke M., Demeulemeester E., Herroelen W. On Maximizing the Net Present Value of a Project Under Renewable Resource Constraints // Management Science, 2001. V.47, N.8. - P.1113-1121.

208. Williamson D.P., Hall L.A., Hoogeveen J.A., Hurkens C.A.J., Lenstra J.K., Sevastianov S.V., Shmoys D.B. Short shop schedules // Oper. Res., 1997. V.45, N.2. - P.288-294.

209. Woeginger G. J. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? // INFORMS J. on Computing, 2000. V.12, N.l. - P.57-74.

210. Yang K.K., Talbot F.B., Patterson J.H. Scheduling a Project to Maximize Its Net Present Value: An Integer Programming Approach // European Journal of Operational Research, 1992. V.64. - P. 188-198.

211. Yang K.K., Talbot F.B., Patterson J.H. Scheduling a Project to Maximize Its Net Present Value: An Integer Programming Approach // European Journal of Operational Research, 1992. V.64. - P. 188-198.

212. Younis M.A., Saad B. Optimal Resource leveling of multi-resource projects // Computers and Industrial Engineering, 1996. V.31. - P. 1-4.

213. Zhu D., Padman R. Tabu Search for Scheduling Resource-Constrained Projects with Cash Flows // Working Paper, The Heinz School, Carnegie Mellon University, Pittsburgh, 1996.

214. Zhu D., Padman R. A Multiheuristic Combination Model for Scheduling Resource-Constrained Projects with Cash Flows // Working Paper, The Heinz School, Carnegie Mellon University, Pittsburgh, 1997.