Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

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

Диссертация: Анализ сложности и разработка алгоритмов решения задач календарного планирования и теории расписаний
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • Введение <
  • 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. И.С. Финансовый анализ ценных бумаг. Москва: Финансы и статистика, 1998. 360 с.
  36. B.C., Кукса А. И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983.
  37. В.Н. Межотраслевые системы. Математические модели и методы. Новосибирск, Наука, 1986. 221 с.
  38. X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. 512 с.
  39. A.A., Первозванская Т. Н. Финансовый рынок: расчет и риск. Москва: Инфра-М, 1994. 192 с.
  40. Т.П., Португал В. М., Татаров В. А., Шкурба В. В. Эвристические методы календарного планирования. Киев: Техника, 1980.
  41. В.К. Математические модели связности. Новосибирск: ИВМиМГ СО РАН, 2006. 490с.
  42. A.A., Сервах В. В. О структуре оптимальных расписаний в задаче с нефиксированными маршрутами размерномти 3×3 // Препринт, Омский государственный университет, Омск, 2002. 40с.
  43. A.A., Сервах В. В. О структуре оптимальных расписаний в задаче с нефиксированными маршрутами // Материалы Российской конференция «Дискретный анализ и исследование операций», Новосибирск, 2002. С. 221.
  44. A.A., Сервах B.B. О построении циклических расписаний для задачи обработки однотипных деталей // Материалы Российской конференции «Дискретный анализ и исследование операций», Новосибирск, 2004. С. 175.
  45. A.A., Сервах В. В. Алгоритмы решения одной задачи построения циклических расписаний // Труды 13 Байкальской международной школы-семинара «Методы оптимизации и их приложения», Иркутск, 2005. Т.5. — С.131−135.
  46. А. А. Сервах В.В., Планирование выпуска партии однотипных деталей со сложным маршрутом обработки // Материалы Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2006. С. 52.
  47. A.A., Сервах В. В. Оптимизация выпуска однотипных деталей на основе циклических расписаний // Дискретный анализ и исследование операций, 2008. Т. 15, N5. — С.47−60.
  48. A.A., Сервах В. В. Об одной задаче построения циклического расписания // Информационный бюллетень Ассоциации мат. программирования № 11, Екатеринбург, УрО РАН, 2007. С. 206.
  49. В.В. О задаче Акерса-Фридмана // Материалы 15 Всесоюзной студенческой конференции Новосибирск, 1977. С.54−63.
  50. В.В. О задаче Акерса-Фридмана //В кн. Управляемые системы, Новосибирск, 1983. вып.23. — С.70−81.
  51. В.В. Алгоритм решения задачи Акерса- Фридмана // Материалы научно-технической конференции «Методы математического программирования и программное обеспечение», Свердловск, 1984. С. 99.
  52. В.В. Некоторые свойства трехстаночной задачи Джонсона //В кн. Дискретная оптимизация и численные методы решения прикладных задач, Новосибирск, ВЦ СО АН СССР, 1986. С.99−115.
  53. В.В. Задача коммивояжера на ленточных графах // Тезисы докладов 3 Всесоюзной школы «Дискретная оптимизация и компьютеры», М. ДЭМИ, 1987. С. 58.
  54. В.В. Задача коммивояжера на ленточных графах //В кн. Управляемые системы, Новосибирск, 1988. вып.28. — С.45−55.
  55. В.В. Календарное планирование с работами единичной длительности // Материалы Межреспубликанского семинара по дискретной оптимизации, Киев, 1990. С. 66.
  56. В.В. Алгоритм решения задачи календарного планирования с единичными длительностями работ // В кн. Дискретная оптимизация и анализ сложных систем, ВЦ СО АН СССР, Новосибирск, 1989. С.99−107.
  57. В.В. Задача сетевого планирования с ограниченными ресурсами ?1 Тезисы докладов 4 Всесоюзного совещания «Методы и программы решения оптимизационных задач на графах и сетях», Новосибирск, 1989, 4.2.-С.100.
  58. В.В. О линейном размещении ориентированного взвешенного графа // Материалы 4 Всесоюзной школы-семинара «Статистический и дискретный анализ данных и экспертное оценивание», Одесса, 1991. С. 113.
  59. В.В. Эффективные алгоритмы для некоторых задач календарного планирования // В кн. Методы решения и анализа задач дискретной оптимизации. Сб. научных трудов под ред. A.A. Колоколова, Омск, ОмГУ, 1992. С.94−106.
  60. В.В. Задачи календарного планирования со штрафами за превышение директивных сроков // Инф. бюллетень N4 Ассоциации математического программирования. Тез. докл. конференции «Математическое программирования и приложения», Екатеринбург, 1993. С. 76.
  61. В.В. Моделирование и оптимизация на транспортной сети города // Тезисы докладов Международной конференции «Проблемы оптимизации и экономические приложения», Омск, 1997. С. 140.
  62. В.В. Схема динамического программирования для некоторых задач теории расписаний // Материалы Международной сибирской конференции по исследованию операций, Новосибирск, 1998. С. 91.
  63. В.В. Эффективно разрешимый случай задачи календарного планирования с возобновимыми ресурсами // Дискретный анализ и исследование операций, Сер.2, 2000. Т.7, N 1. — С.75−82.
  64. В.В., О задаче оптимального выбора инвестиционных проектов // Тезисы Всеросийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2003. С. 109.
  65. В.В. Полиномиально разрешимый случай трехстаночной задачи Джонсона // Дискретный анализ и исследование операций, Сер. 2, 2006. -Т.13, N.2. С.44−55.
  66. В.В. Некоторые задачи календарного планирования инвестиционных проектов // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2009.-С.87.
  67. В.В. О сложности задачи построения расписаний с фиксированным числом однотипных деталей // Материалы Международной конференции «Дискретная математика, алгебра и их приложения», Минск 2009. С. 111.
  68. В.В., Сергунов А. В. Анализ сложности задачи выбора инвестиционных проектов // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2009. -С.162
  69. В.В., Сухих С. Л. Гибридный алгоритм для задачи календарного планирования проектов с учетом реинвестирования прибыли // Автоматика и телемеханика, 2004. N.3. — С. 100−107.
  70. В.В., Щербинина Т. А. О задаче календарного планирования проекта с различными критериями и складируемыми ресурсами // Материалы Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2006. С. 93.'
  71. В.В., Щербинина Т. А. Гибридные алгоритмы для некоторых задач календарного планирования проектов // XIII Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, 2007. С.213−214.
  72. В.В., Щербинина Т. А. Алгоритмы решения задач календарного планирования с различными критериями // Материалы 14 Байкальской международной школы-семинара «Методы оптимизации и их приложения», Северобайкальск, 2008. Т.1 — С.506−513.
  73. В.В., Щербинина Т. А. О сложности задачи календарного планирования проектов // Вестник НГУ. Серия: математика, механика, информатика, 2008. Т.8, вып.З. — С.105−111.
  74. В.В., Щербинина Т. А. Алгоритм решения задачи календарного планирования с критерием средневзвешенного времени завершения работ // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2009.
  75. А.И. О задаче коммивояжера при наличии запретов // Сб. Управляемые системы, Новосибирск, 1978. N.17 — С.80−86.
  76. Ю.Н. Оптимальное обслуживание двух требований при регулярном критерии // Автоматизация процессов проектирования, Минск: ИТК АН БССР, 1985. С.52−62.
  77. B.C., Шкурба В. В. Введение в теорию расписаний М.: Наука, 1975. 256с.
  78. B.C., Гордон B.C., Шафранский В. В. Теория расписаний. Одностадийные системы. М.: Наука, 1987.
  79. B.C., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы. М.: Наука, 1989.
  80. Теория расписаний и вычислительные машины /под ред. Э.Г. Кофф-мана. М.: Наука, 1984.
  81. В.Г. Приближенное решение задачи составления расписания циклической системы)/ Экономика и математические методы, АН СССР, 1986. N 1. — С. 171−174.
  82. В.В. Задача трех станков. М: Наука, 1976. 96 стр.
  83. 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.
  84. Akers S.B., Friedman J. A non-numerical approach to production scheduling problems // Oper.Res., 1955. Vol.3. — P.429−442.
  85. Akers S.B. A graphical approach to production scheduling problems// Oper.Res., 1956. Vol.4, N 2. — P.244−245.
  86. 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.
  87. 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.
  88. 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.
  89. Bigelow C.G. Bibliography on Project Planning and Control by Network Analysis // Operations Res., 1962. V.10. — P.728−731.
  90. Blazewicz J., Lenstra J.K., and Rinnoy Kan A.H.G. Scheduling subject to resource constraints: Classfication and complexity // DiscreteApplied Mathematics, 1983. V.5, N.l. — P. 11−24.
  91. Blazewicz J., Cellary W., Slowinski R., Weglarz J. Scheduling under Resource Constraints -Deterministic Models. Baltzer, Basel, 1986.
  92. Bottcher J., Drexl A., Kolisch R., and Salewski F. Project scheduling under partially renewable resource constraints // Technical Report 398, Manuskripte aus den Instituten fur Betriebswirtschaftslehre der Universitat Kiel, 1996.
  93. Bottcher J., Drexl A., and Salewski F. Project scheduling under partially renewable resource constraints // Management Science, 1999. V.45(4). -P.543−559.
  94. 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.
  95. Boudoukh T., Penn M., Weiss G. Scheduling job shops with some identical or similar jobs // Journal of Scheduling, 2001. V.4. — P.177−199.
  96. 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.
  97. 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.
  98. Brucker P., Kampmeyer T. Tabu search algorithms for cyclic machine scheduling problems. Osnabrueck, Preprint, 2002, P. 24.
  99. 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.
  100. Brucker P., Kramer A. Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems. European J. Oper. Res., 1996.- V.90. P.214−226.
  101. 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
  102. Burns F., Rooker J. Three-Stage Flow-Shops with Recessive Second Stage. Oper.Res. 1978. N.26. — P.207−208.
  103. 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.
  104. 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.
  105. Chen B., Potts C.N., Woeginger G.J. A review of machine sceduling: complexity, algorithms and approximability // Handbook of Combinatorial Optimization. Boston, MA: I
  106. Coffman E.G., Graham Jr, and R.L. Optimal scheduling for twoprocessor systems. Acta Informal. P.200−213.
  107. Dantzig G.B. Liscrete-variable extremum problems // Operation Research, 1957. V.5. — P.266−277.
  108. 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.
  109. 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.
  110. 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.
  111. 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.
  112. 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.
  113. Easa S.M. Resource leveling in construction by optimization // Journal of Construction Engineering and Management, 1989. V.115. — P.302−316.
  114. 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.
  115. Elmaghraby S.E. Activity networks: project planning and control by network models. New York: Wiley, 1977.
  116. 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.
  117. Fazar W. The Origin of PERT // The controller, 1962. P.598−621.
  118. 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.
  119. Garey M.R., Johnson D.S. Strong NP-completeness results: Motivation, examples, and implications. // Journal of the ACM, 1978. V. 25. — P. 499 508.
  120. 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.
  121. Garfinkel R.S. Vinimizing wallpaper waste. Part I: a class of traveling salesman problems // Operation Research. 1977. V.25. — P.741−751.
  122. 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.
  123. 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.
  124. Gonzalez T., Sahni S. Flowshop and jobshop schedules: complexity and approximation. Oper. Res., 1978. V.26, N.l. — P.36−52.
  125. 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.
  126. 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.
  127. 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.
  128. Grinold R.C. The payment scheduling problem // Naval Research Logistics Quarterly, 1972. V. 19. — P.123−136.
  129. 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.
  130. 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.
  131. 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.
  132. 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.
  133. 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.
  134. 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.
  135. 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.
  136. Hu T.C. Parallel sequencing and assembly line problems // Operations Res, 1961. V.9. — P.841−848.
  137. 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.
  138. 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.
  139. 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.
  140. 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.
  141. Johnson S.M. Optimal Two and Three Stage Production Schedules with Setup Times Included. Naval.Res.Logist.Quart., 1954. N.l. — P.61−68.
  142. Kamoun H., Sriskandarajah C. The complexity of scheduling jobs in repetitive manufacruring systems // European Journal of Operational Research, 1993. V.70. — P.350−364.
  143. 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.
  144. Kelley J.E. Critical-Path Planning and Scheduling: Mathematical Basis // Operations Res., 1961.- V.9. P.296−320.
  145. Kelley J.E., Walker M.R. Critical Path Planning and Scheduling: An Introduction. Mauchly Associates, Ambler, PA, 1959.
  146. Kolish R., Padman R. An Integrated Survey of Deterministic Project Scheduling // OMEGA Journal of Scheduling, 2001. V. 29.- P. 249−272.
  147. 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.
  148. 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.
  149. Kovalyov M. Improving the complexities of approximation algorithm for optimization problems. // Operations Research Letters, 1995.- V.17. -P.85−87.
  150. 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.
  151. 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.
  152. 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.
  153. Lee T., Posner M. Performance measure and schedules in periodic job shop // Operations Research, 1997. V.45. — P.72−91.
  154. LenstraJ.K., Rinnooy Kan A.H.G. Computational complexity of discrete optimization problems. Ann. Discrete Math., 1979. 4. — P.121−140
  155. Lerda-Olberg S. Bibliography on Network-Based Project Planning and Control Techniques: 1962−1965 // Operations Res, 1966.- V.15 P.925−931.
  156. Markowitz H. Portfolio selection.// The journal of finance, 1952. V.7, N1. — P.77−91.
  157. McGormick S.T., Rao U.S. Some complexity results in cyclic scheduling // Mathematical and Computer Modeling, 1994. V.20. — P.107−122.
  158. 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.
  159. 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.
  160. 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.
  161. 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.
  162. Neumann K., Zimmermann J. Resource Levelling for Project with Schedule-Dependent Time Windows // European Journal of Operational Research, 1999. V.117. — P.591−605.
  163. Neumann K., Zimmermann J. Procedures for Resource Levelling and Net Present Value Problems in Project Scheduling with General Temporal and
  164. Resource Constraints // European Journal of Operational Research, 2000. V.127. — P.425−443.
  165. 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.
  166. 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.
  167. 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.
  168. Patterson J.H., Slowinski R., Talbot F.B., W§ glarz J. An Algorithm for a General Class of Precedence and Resource Constrained Scheduling Problems // Slowinski R., W§ glarz J. (Eds.). Advances in Project Scheduling. Elsevir, 1989. P.3−28.
  169. Project scheduling: recent model, algorithm and applications // edt. by Jan Weglarz. Kluwer Academic Publishers. 1999.
  170. Rao U., Jackson P. Identical Jobs Cyclic Scheduling: Subproblems, Properties, Complexity and Solution Aproaches (Ithaca, NY: Cornell University Press), 1993.
  171. 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.
  172. 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.
  173. Roundy R. Cyclic schedules for job shops with identical jobs // Mathematics of Operations Research, 1992, V.17, N.4, — P.842−865.
  174. Russell R.A. A Comparison of Heuristics for Scheduling Projects with Cash Flows and Resource Restrictions // Management Science, 1986. -V.32. P.1291−1300.
  175. Russell A.H. Cash Cows in networks. Management Science, 1970 16(5) — P. 357−373.
  176. Schirmer F., Drexl A. Partially Renewable Resources -A Generalization of Resource-Constrained Project Scheduling Problem // IFORS Triennial Meeting, Vancouver, 1996.
  177. Schuurman P. Woeginger G.J. Approximation Schemes. A Tutorial, 2007 P.33−36.
  178. 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.
  179. Servakh V.V. Dynamic programming algorithms for somescheduling problems // ECCO VIII, Conf. of European Chapter of Combinatorial
  180. Optimization, Poznan, May 1995: Abstracts. Poznan, 1995. P.80.
  181. 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.
  182. 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.
  183. 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.
  184. 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.
  185. 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.
  186. 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.
  187. 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.
  188. 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.
  189. 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.
  190. 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.
  191. 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.
  192. 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.
  193. 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.
  194. 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.
  195. 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.
  196. Sotskov Y.N., Shakhlevich N.V. NP-hardness of shop-scheduling problems with three jobs. Discrete Appl. Math., 1995. 59(3) — P.37−266.
  197. Sotskov Y.N. The complexity of shop-scheduling problems with two or three jobs. European J. Oper. Res., 1991. 53(3) — P.326−336.
  198. Syslo M.M. A new solvable case of the traveling salesman problems // Math. Programming, 1973. V.4. — P.347−348.
  199. Talbot F.B. Resource-constrained project scheduling with time-resource tradeoffs: The non preemptive case // Management science, 1982. V. 28(10). — P.1197−1210.
  200. 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.
  201. Tavares L.V. Multicriteria Scheduling of a Railway Renewal Program // European Journal of Operational Research, 1986. V.25. — P.395−405.
  202. Timkovsky V.G. On the complexity of scheduling an arbitrary system. Soviet J. Comput. Systems Sci., 1985 23(5). — P.46−52.
  203. 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.
  204. Timkovsky V.G. Is a unit-time job shop not easier than identical parallelmachines? Discrete Appl. Math., 1998. 85(2) — P.149−162.
  205. Ullman 3.D.NP-complete scheduling problems // J.Comput. System Sci., 1975. V.10. — P.384−393.
  206. 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.
  207. 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.
  208. 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.
  209. 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.
  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. Younis M.A., Saad B. Optimal Resource leveling of multi-resource projects // Computers and Industrial Engineering, 1996. V.31. — P. 1−4.
  212. Zhu D., Padman R. Tabu Search for Scheduling Resource-Constrained Projects with Cash Flows // Working Paper, The Heinz School, Carnegie Mellon University, Pittsburgh, 1996.
  213. 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.
Заполнить форму текущей работой

На отлично!