авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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


с.н.с. Лаборатории №68

Гафаров Евгений Рашидович

Графический метод

решения задач

комбинаторной оптимизации

Диссертационная работа на соискание

ученой степени

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

Специальность: 01.01.09

«Дискретная математика и математическая кибернетика»

Научный консультант: д.ф.-м.н., профессор Лазарев Александр

Алексеевич

Содержание презентации

Часть 1. Графический метод: точное решение.

Модификация метода динамического программирования.

Кусочно-линейные функции Беллмана.

Часть 2. Графический метод: приближенное решение.

Нахождение решения с заданной погрешностью.

Часть 3. Графические алгоритмы решения задач теории расписаний Исследование сложности задач.

Точные и приближенные алгоритмы решения.

Часть 4. Графические алгоритмы решения классических задач комбинаторной оптимизации Точные и приближенные алгоритмы решения.

Часть 5. Прочие результаты Сложность задач теории расписаний.

Программные продукты.

2 из Цель работы Разработка эффективных методов и алгоритмов решения задач комбинаторной оптимизации.

Задачи • исследование задач теории расписаний, выявлении их сложности (NP трудности, полиномиальности);

• нахождение свойств оптимальных решений исследуемых задач;

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

3 из Задачи комбинаторной оптимизации Выбрать лучшее (оптимальное) решение среди множества допустимых решений.

Множество слишком большое – полный перебор за разумное время невозможен.

Задача об одномерном ранце pjxj max Для n=80 порядка 280 решений!

n предметов, W – вместимость рюкзака;

230 опер/секунду -- быстрейший wj – вес предмета;

wjxj W;

pj – cтоимость предмета. xj = 0 или 1. компьютер.

Необходимо: сократить область перебора, не исключив оптимальное решение.

Алгоритмическая (временная) сложность решения задач комб. оптимизации Класс P – задачи, решаемые за полиномиальное время («несложные»);

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

Известная математическая проблема: P = NP?

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

Хачиян Леонид Генрихович, ВЦ РАН, метод эллипсоидов, премия Фалкерсона.

Необходимо:

1. Определить, к какому классу (P или NP-трудные) относится задача.

2. Построить быстрый точный или приближенный алгоритм решения.

4 из Основные направления исследований в дис.работе Задачи Комбинаторная оптимизация Теория расписаний Задачи с кусочно- Задачи с кусочно линейными линейными функциями Беллмана функциями Беллмана Графический метод Динамическое программирование Метод решения 5 из Часть 1. Графический метод: точное решение Некоторые сведения о трудоемкости алгоритмов M.A. Posypkin, I. Kh. Sigal, Speedup estimates for some variants of the parallel implementations of the branch-and-bound method, Computational Mathematics and Mathematical Physics, 46, N 12 (2006), 2189 –2 202.

Для задачи о ранце, ВСЕ алгоритмы ветвей и границ с полиномиальными алгоритмами расчета верхних/нижних оценок имеют трудоемкость не меньше () операций, где x – длина входа.

3 2+3/ операций, т.е. 2 (+1) Thomas E. O’Neil and Scott Kerlin, A Simple 2( ) Algorithm for PARTITION and SUBSET SUM, 2010,4 pages (работа не опубликована).

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

Простая идея: сокращать интервал рассмотрения состояний.

7 из Графический метод Функциональные уравнения Беллмана.

На стадии l, l = 1,2,…,n рассматриваются все целые точки (состояния) t из [0,A] (t) – функция Беллмана, Если = (например, = + ) на некотором интервале, +1, то можно построить графический алгоритм.

8из Графический алгоритм решения задачи максимизации суммарного запаздывания Ф1 = max 0, + + 1 +, = 0, = 1,2, …, ;

= Ф = max 0, + + 1, = 1, = 1,2, …,.

= 0 = 0,.

0 оптимальное значение целевой функции, [0, ] состояние системы, = (t) – функция Беллмана, стадия (шаг), размерность задачи (количество требований), числовой параметр продолжительность обслуживания, числовой параметр директивный срок.

График функции Беллмана в алгоритме динамич.

программирования 10 из Вычисления в алгоритме динамического программирования Вычисления в графическом алгоритме 9 из Графический алгоритм решения задачи максимизации суммарного запаздывания Ф1 = max 0, + + 1 +, = 0, = 1,2, …, ;

= Ф = max 0, + + 1, = 1, = 1,2, …,.

= Сдвинуть график функции влево на Ф1 = max 0, + + 1 +, = 0, = 1,2, …, ;

= Ф = max 0, + + 1, = 1, = 1,2, …,.

= Решить уравнение + = 0, и увеличить наклон графика функции на 1 после точки t’ – корень уравнения.

Ф1 = max 0, + + 1 +, = 0, = 1,2, …, ;

= Ф = max 0, + + 1, = 1, = 1,2, …,.

= Решить уравнение + =1 = 0, и увеличить наклон графика функции на 1 после точки t’’ – корень уравнения.

11 из 12 из Графический алгоритм решения задачи максимизации суммарного запаздывания Функция F1(t) Функция Fl-1(t) 13 из Пример 14 из Пример 15 из Пример 16 из Пример 17 из Пример 18 из Графический алгоритм решения задачи максимизации суммарного запаздывания Трудоемкость алгоритма динамического программирования O(npj ).

Трудоемкость графического алгоритма O(n2).

Трудоемкость графического алгоритма для других задач Трудоемкость графического алгоритма (в т.ч. для других задач) зависит от количества точек излома ml+1 на стадии l.

Пусть M – суммарное количество точек излома на всех стадиях.

Если трудоемкость дин.прогр. равна O(nA), то трудоемкость графического алгоритма O(min{nA,M}) Количество точек излома равно количеству различных значений bk в таблице.

19 из Часть 2. Графический метод:

приближенное решение Аппроксимация основанная на графическом алгоритме Количество точек излома равно количеству различных значений bk в таблице.

Трудоемкость каждого шага зависит линейно от количества точек излома.

Нужно сократить количество изломов.

21 из FPTAS основанная на графическом алгоритме Fully polinomial time approximation schema (полная полиномиальная аппрокс. схема) Относительная погрешность не боле. Трудоемкость полиномиально зависит только от размерности задачи и 1/.

Функция Беллмана в графическом алгоритме В таблице, 0bl1 bl2 … т.к. функция Fl(t) неубывающая.

Сократить количество изломов = Сократить количество колонок.

22 из FPTAS основанная на графическом алгоритме Чтобы сократить трудоемкость, мы можем округлить значения blkUB, чтобы в таблице было полиномиальное число различных значений blk Пусть решается задача минимизации и UB – верхняя оценка.

Пусть F(*) – оптимальное значение целевой функции и UB/ F(*) 2.

Пусть трудоемкость графического алгоритма равна O(n min{UB,А}).

. Округлим blk до ближайшего множителя Пусть.

Тогда… 23 из FPTAS основанная на графическом алгоритме Не более чем UB/ = 2n/ различных модифицированных blk.

Тогда не более чем 4n/ колонок в таблице задающей функцию.

Суммарная относительная погрешность не более чем n F(*).

, если трудоемкость графического алгоритма () Трудоемкость FPTAS равна 24 из Сравнение графического алгоритма и алгоритмов динам. программирования для одноприборных задач теории расписаний 25 из Экспериментальное сравнение графического алгоритма и алгоритмов динам.

программирования для задачи о ранце.

Время работы, сек Алгоритм динамического программирования Графический алгоритм Количество предметов pi = random(100);

wi = random(100).

Графический алгоритм эффективно решает примеры с миллионом предметов.

26 из Преимущества графических алгоритмов Графический алгоритм работает не в режиме «калькулятора», а принимает во внимание аналитический вид целевой функции.

• возможность решать нецелочисленные примеры;

• легче строить FPTAS;

• теоретическая трудоемкость для многих задач меньше;

• можно решать примеры большого масштаба;

• находит решение для всех возможных точек старта обслуживания t [-,+];

• согласно результатам экспериментальных исследований, для большинства рассмотренных примеров трудоемкость графического алгоритма не превышает O(n3).

Задачи с переменным временем начала обслуживания требований:

Hoogeveen, H., and T’Kindt, V., 2010. Minimizing the Number of Late Jobs When the Starting Time of the Machine is Variable. Proceedings PMS, 235 – 238.

27 из Публикации по графическому алгоритму для задач теории расписаний E.R. Gafarov, A.A. Lazarev and F. Werner (2012), Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one. Annals of Operations Research, 196 (1), 247-261.

E.R. Gafarov, A.A. Lazarev and F. Werner. (2012), A note on a single machine scheduling problem with generalized total tardiness objective function. Information Processing Letters, 112 (3), 72 – 76.

E.R. Gafarov, A.A. Lazarev and F. Werner (2010), Single machine total tardiness maximization problems: complexity and algorithms. Annals of Operation Research 3 статьи находятся на рецензии 28 из Часть 3. Графические алгоритмы решения задач теории расписаний Классические задачи Теории расписаний 1 прибор (нет простоев, не более 1го требования в каждый момент времени) n требований (прерывания в обслуживании запрещены) pj продолжительность обслуживания требования j dj директивный срок wj вес (значимость) Sj() время начала обслуживания требования j при расписании Сj() = Sj()+ pj время окончания обслуживания требования j при расписании Tj() = max{0, Сj() - dj } запаздывание wj Tj() = wj max{0, Сj() - dj } взвешенное запаздывание GTj() = max{0, min{pj, Сj() - dj }} обобщенное запаздывание Uj() = 1, если Сj() - dj 0 иначе Uj() = Bellman R. Mathematical aspects of scheduling theory // Journal of the Society of Industrial and Applied Mathematics. – 1956. – Vol. 4. –P. 168–205.

Танаев В.С., Шкурба В.В., Введение в теорию расписаний.

М.: Наука, 1975.

30 из Классические задачи Теории расписаний Sj() время начала обслуживания требования j при расписании Сj() = Sj()+ pj время окончания обслуживания требования j при расписании Tj() = max{0, Сj() - dj } запаздывание wj Tj() = wj max{0, Сj() - dj } взвешенное запаздывание GTj() = max{0, min{pj, Сj() - dj }} обобщенное запаздывание Uj() = 1, если Сj() - dj 0 иначе Uj() = dj pj Tj() Sj() Сj() Задачи 1||Tj минимизация суммарного запаздывания Частный случай B-1G: dmax-dmin pmin Док-во NP-трудности Частный случай B-1: p1… pn, d1… dn, dn-d1 pn Док-во NP-трудности 1| dj =d| wjTj 1||GTj Док-во NP-трудности 1|| wj Uj 1| d‘j =dj +T |Uj 31 из Задачи с обратными критериями оптимизации Максимизировать Tj, wjTj, Uj и т.п.

Допустимые расписания:

– обслуживание начинается в момент времени 0;

-- нет простоев прибора (no-idle).

Теоретическая значимость:

- для оценки худшего возможного решения;

- для отсечения плохих частичных решений;

- для решения би-критериальных задач.

Собственные практические интерпретации.

n заказов на монтаж ветряных турбин;

dj дата схода снега в локации заказа j.

После схода снега – меньше затраты, но все заказы выполнить к определенному времени.

32 из Задачи с обратными критериями оптимизации Сведение задачи разбиения к частному случаю.

Дано множество чисел = 1, 2, …,, _ = 2.

= Существует ли подмножество, что = B?

Лемма 1.5. Для частного случая (1.1)-(1.9) в любом допустимом расписании запаздывающих требований.

Лемма 1.6. Для любых двух канонических расписаний 1 и 2 выполняется |F(1 ) – F(2)| A Лемма 1.7. Для частного случая (1.1)-(1.9) все оптимальные расписания – канонические или могут быть преобразованы в них, применением правила SPT (упорядочить по возрастанию продолжительностей обслуживания) к первым требованиям.

Теорема 1.8. Задача 1(no-idle)||max wj Tj является NP-трудной в обычном смысле.

Доказательство: E.R. Gafarov, A.A. Lazarev and F. Werner (2013), Single machine total tardiness maximization problems: complexity and algorithms.// Annals of Operation Research, doi:10.1007/s10479-012-1288-x 33 из Задачи с обратными критериями оптимизации Полученные результаты:

1(no-idle)||max wj Tj - док-во NP-трудности в обычном смысле, графич. алгоритм.

1(no-idle)| rj | max Tj - док-во NP-трудности.

1(no-idle)|| max Tj - полиномиальный графический алгоритм решения.

1. Е.Р. Гафаров, А.А. Лазарев и Ф. Вернер. Алгоритмы решения задач максимизации суммарного запаздывания и максимизации количества запаздывающих требований для одного прибора // Автоматика и телемеханика, № 10, 2010, С. 2070- 2. E.R. Gafarov, A.A. Lazarev and F.Werner. Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one// Annals of Operations Research, 2012, Volume 196, Issue 1, C. 247- 3. E.R. Gafarov, A.A. Lazarev and F. Werner (2013), Single machine total tardiness maximization problems: complexity and algorithms.// Annals of Operation Research, doi:10.1007/s10479 012-1288-x 32 из Задачи с одним невозобновимым ресурсом (деньги, энергия) Требования, которые должны быть обслужены Требование j 1 2 Потребление ресурса при начале обслуживания $100 $250 $ требования gj Продолжительность обслуживания pj 25 15 График поступления ресурса Времена поступления ресурса ti 0 20 30 Объемы поступления G(ti) $50 $50 $200 $ 2 ti 20 30 G(0)+G(20)+G(30) = $300 $250 = g 33 из Задачи с одним невозобновимым ресурсом (деньги, энергия) Рассмотренные задачи и частные случаи 1|NR|Uj - минимизация количества запаздывающих требований.

1|NR|Cj - минимизация сумм моментов завершения обслуживания.

1|NR|Tj - минимизация суммарного запаздывания.

Частные случаи:

dj =d - равные директивные сроки, gj = g - равные требования к ресурсу, p j = p - равные продолжительности обслуживания.

dj =d, gj =g - равные директивные сроки и требования к ресурсам.

Полученные результаты:

Доказательства NP трудности в обычном или сильном смыслах E.R. Gafarov, A.A. Lazarev and F.Werner. Single Machine Scheduling Problems with Financial Resource Constraints:

Some Complexity Results and Properties// Mathematical Social Sciences, 2011, 62, C. 7- 34 из Доказательство NP-трудности 1|NR, pj=p|Tj Сведение задачи разбиения к частному случаю.

Дано множество чисел = 1, 2, …,, _ = 2.

=, что Существует ли подмножество = B?

n – количество требований Множество запаздывающих требований = ti M Множество незападывающих требований 35 из Доказательство NP-трудности 1|NR, dj=d|Tj Сведение задачи разбиения к частному случаю.

Дано множество чисел = 1, 2, …,, _ = 2.

=, что Существует ли подмножество = B?

2n+ требований Только если N‘ существует ti d 36 из Задачи одноколейной железной дороги с двумя станциями Задача оперативного планирования.

Двухпутные железные дороги:

Ремонтные работы.

Однопутные железные дороги: США, Австралия, Иран и т.д.

Одноколейный участок. Q сегментов, разделенных светофорами.

n поездов. N1 -- множество поездов со ст.1 на ст.2. N2 – со ст.2 на ст.1.

Поезда поступают НЕОДНОВРЕМЕННО! rj – время поступления на ст. отправления поезда j.

pq -- время прохождения поездом сегмента q. Скорость поездов одинаковая.

Ст.1 Ст. 1 2 3 Q-1 Q N1 N Целевые функции: минимизация общего времени прохождения всех поездов Cmax;

минимизация количества запаздывающих поездов Uj;

минимизация суммарного взвешенного запаздывания wjTj ;

И ДРУГИЕ!

В каком порядке пропускать поезда? 37 из Дополнительные интерпретации.

1) Речной канал с цепочкой шлюзов. Пропускная способность каждого шлюза – не более одного судна в каждый момент времени;

2) Сборочно-разборочный конвейер.

Полученные результаты:

• сведение к «одноприборной» задаче теории расписаний с переналадками;

• полиномиальные алгоритмы решения O(n6)—O(n15), n – количество поездов.

E.R. Gafarov, A. Dolgui, A.A. Lazarev (2013), Two-Station Single Track Railway Scheduling Problem With Equal Speed of Trains. Computers & Industrial Engineering.

38 из Часть 4. Графические алгоритмы решения классических задач комбинаторной оптимизации Графический алгоритм для задачи об инвестициях n возможных инвестиционных проектов.

А – сумма доступных инвестиций (для всех A из промежутка [A’,A’’]).

fj(t) – функция прибыль для проекта j, если в него «проинвестировать» t денег.

Определить объем инвестиций в каждый проект для максимизации прибыли.

40 из Графический алгоритм для задачи об инвестициях Классический алгоритм динамического программирования: O(nA2) операций.

Альтернативный алгоритм дин. программирования: O(kjA) операций.

В графическом алгоритме функции fj(t) и функции Беллмана Fj(t) хранятся в виде:

Трудоемкость графического алгоритма: O(kjA) Трудоемкость графической FPTAS: O(n(loglog n)k/) 41 из Графический алгоритм для задачи об инвестициях 42 из Графический алгоритм для задачи об инвестициях Пример 43 из Графический алгоритм для задачи об инвестициях Пример 44 из Части 1--4. Основные результаты Основные результаты 46 из Основные результаты 47 из Основные результаты 48 из Основные результаты • Предложен графический метод решения задач комбинаторной оптимизации. Графический метод эффективно применен для решения некоторых задач комбинаторной оптимизации, для которых существует псевдо-полиномиальный алгоритм решения, основанный на принципе оптимальности Беллмана. Для многих одноприборных задач теории расписаний, а также известных комбинаторных задач (задача о ранце, задача об инвестициях) графический метод позволяет существенно сократить трудоемкость по сравнению с классическими алгоритмами динамического программирования.

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

• Найдены доказательства NP-трудности для 7 задач теории расписаний, связанных с запаздыванием.

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

• Построены графические алгоритмы для 9 задач комбинаторной оптимизации.

• Предложены FPTAS, основанные на графическом методе для 7 задач комбинаторной оптимизации.

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

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

Вывод: графический метод является более эффективной заменой метода динамического программирования для многих задач комбинаторной оптимизации, в частности, для задач с кусочно-линейными функциями Беллмана.

49 из Часть 5. Прочие результаты Прочие результаты • Результаты о «сложности» частного случая задачи RCPSP (минимизация времени выполнения работ проекта с учетом ограничения на ресурсы и отношений предшествования).

• Результаты о «сложности» для задачи SALBP-1 (балансировка производственной линии).

• Результаты о «сложности» для задачи о мастере и подмастерье (два прибора).

1. E.R. Gafarov, A. Dolgui (2013), Two Dedicated Machines Scheduling Problem in Two-Sided Assembly Lines.

Optimization Letters, Vol. 7. DOI 10.1007/s11590-013-0671-0.

2. E.R. Gafarov, A.A. Lazarev and F. Werner (2012), Approximability Results for the Resource-Constrained Project Scheduling Problem with a Single Type of Resources. Annals of Operations Research, doi:10.1007/s10479 012-1106- 3. A.A. Lazarev and E.R. Gafarov (2009), Transformation of the Network Graph of Scheduling Problems with Precedence Constraints to a Planar Graph. Doklady Mathematics, 79 (1), 1-3.

4. T. C. E. Cheng, A. A. Lazarev, E. R. Gafarov (2009), A Hybrid Algorithm for the Single Machine Total Tardiness Problem. Computers & Operations Research, 36 (2), 308-315.

51 из И другие статьи… Публикации Опубликовано 5 монографий Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Теория расписаний. Задачи управления транспортными системами. Учебное пособие. М.: Физический факультет МГУ им. М. В. Ломоносова, 2012. – 159 с.

Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. Учебное пособие. М.:

МГУ, 2011. – 224 с.

13 статей в рецензируемых журналах (список ВАК) (из них 7 – в зарубежной печати, 6 -- в отечественной печати).

17 тезисов международных научных конференций (после защиты кандидатской).

12 препринтов в университетах России, Германии, Франции.

1 свидетельство о регистрации программы для ЭВМ (№2013660198).

52 из Спасибо за внимание!

Алгоритм динамического программирования для задачи 1(no-idle)|| max Tj Утверждение. Существует оптимальная последовательность обслуживания требований (перестановка) вида (G,H).

Все требования из G не запаздывают и обслуживаются по неубыванию pj Все требования из H запаздывают и обслуживаются по невозрастанию pj Классическая реализация алгоритма дин. программирования Перенумеруем требования согласно p1… pn Стадии l=1,2,…,n. Все состояния t из [0,pj]. t– время старта частичного расписания l-1(t+pl) l t l-1(t) l t Стадии l=n,n-1,…, Альтернативная реализация l pj Только возможные состояния t из [0,pj]. t– суммарная продолжительность требований обслуживаемых вначале 16 из Монографии 1. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Минимизация суммарного запаздывания для одного прибора. // Научное издание, М.: Вычислительный центр им. А.А. Дородницына РАН,2006.- 134 c.

2. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Исследование задач с отношениями предшествования и ресурсными ограничениями. // Научное издание, М.: Вычислительный центр им. А.А. Дородницына РАН, 2007. -- 80 c.

3. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы // Учебное пособие М:Издательство МГУ, 2011, 223 с.

4. Лазарев А.А., Мусатова Е.Г., Гафаров Е.Р., Кварацхелия А.Г. Теория расписаний. Задачи железнодорожного планирования//Научное издание, М:ИПУ РАН, 2012, 92 с.

5. Лазарев А.А., Мусатова Е.Г., Гафаров Е.Р., Кварацхелия А.Г. Теория расписаний. Управление транспортными системами// Учебное пособие М:Издательство МГУ, 2012, 159 с.

Публикации из списка ВАК 6. E.R. Gafarov, A.Dolgui. Two Dedicated Machines Scheduling Problem in Two-Sided Assembly Lines//Optimization Letters, 2013, doi:10.1007/s11590-013-0671-0.

7. Гафаров Е.Р., Лазарев А.А.Доказательство NP-трудности частного случая задачи минимизация суммарного запаздывания для одного прибора // Известия РАН: Теория и системы управления. -- 2006. -- №.3. -- С. 120--128.

8. Лазарев А.А., Кварацхелия А.Г., Гафаров Е.Р. Алгоритмы решения NP-трудной проблемы минимизации суммарного запаздывания для одного прибора. // Доклады Академии Наук, 2007. -- Том 412, № 6. -- С. 739--742.

9. Е.Р. Гафаров, А.А. Лазарев и Ф. Вернер. Алгоритмы решения задач максимизации суммарного запаздывания и максимизации количества запаздывающих требований для одного прибора//Автоматика и телемеханика, № 10, 2010, С. 63-79.

10. А. А. Лазарев, Е. Р. Гафаров. Преобразование сетевого графика задач теории расписаний с ограничениями предшествований // Доклады Академии Наук, 2009. Т. 424. № 1. С. 7-9.

11. Лазарев А.А., Гафаров Е.Р. К решению задачи построения расписания выполнения проекта // Автоматика и телемеханика, 2008. № 12.С. 86-104.

12. T. C. E. Cheng, A. A. Lazarev, E. R. Gafarov. A Hybrid Algorithm for the Single Machine Total Tardiness Problem // Computers \& Operations Research, 2009. Volume 36, Issue 2. C. 308-315.

13. E.R. Gafarov, A.A. Lazarev and F.Werner. Single Machine Scheduling Problems with Financial Resource Constraints: Some Complexity Results and Properties// Mathematical Social Sciences, 2011, 62, C. 7-13.

14. E.R. Gafarov, A.A. Lazarev and F.Werner. A note on a single machine scheduling problem with generalized total tardiness objective function// Information Processing Letters, 2012, vol. 112, No. 3, C. 72 -- 76.

15. E.R. Gafarov, A.A. Lazarev and F.Werner. Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one// Annals of Operations Research, 2012, Volume 196, Issue 1, C. 247-261.

16. E.R. Gafarov, A.A. Lazarev and F.Werner. Approximability results for the resource-constrained project scheduling problem with a single type of resources//Annals of Operations Research, 2012, 13 March 2012, C. 1-16. doi:10.1007/s10479-012- 17. Гафаров Е.Р. Гибридный алгоритм решения задачи минимизации суммарного запаздывания для одного прибора // Информационные технологии, 2007, -- №1 -- С. 30—37.

18. E.R. Gafarov, A.A. Lazarev and F.Werner. Single machine total tardiness maximization problems: complexity and algorithms.// Annals of Operation Research, 2013, 207, 121-136, doi:10.1007/s10479-012-1288-x.

Статьи на рецензии 19. E.R. Gafarov, A.Dolgui, F. Werner. A Graphical Approach for Solving Single Machine Scheduling Problems Approximately// International Journal of Production Research, 2012 (на рецензии).

20. E.R. Gafarov, A.Dolgui, A.A. Lazarev. Two-Station Single Track Railway Scheduling Problem With Equal Speed of Trains// Computers \& Industrial Engineering, 2012 (на рецензии).

21. E.R. Gafarov, A.Dolgui. Notes on Complexity of the Simple Assembly Line Balancing Problem//Optimization Letters, (на рецензии).

22. E.R. Gafarov, A.Dolgui, A.A. Lazarev and F.Werner. A Graphical Approach to Solve Investments Optimization Problem// Journal of Mathematical Modelling and Algorithms in Operations Research, 2012 (на рецензии).

23. E.R. Gafarov, A.Dolgui, A.A. Lazarev and F.Werner. Two Graphical Algorithms to Solve an Investment Optimization Problem Effectively: An Exact Algorithm and an FPTAS// Annals of Operation Research, 2012 (на рецензии) 24. Е.Р. Гафаров. Графический метод решения задач комбинаторной оптимизации // Известия РАН: Теория и системы управления. 2013 (на рецензии).

Препринты и научные отчеты 25. E.R. Gafarov, A.A. Lazarev and F. Werner (2009), Algorithms for Some Maximization Scheduling Problems on a Single Machine// Preprint 38/09, FMA, Otto-von-Guericke-Universitaet Magdeburg, 29 pages 26. E.R. Gafarov, A. Dolgui, F. Werner (2012), Dynamic Programming Approach to Design FPTAS for Single Machine Scheduling Problems// Report n° RR-12-02, LIMOS, CNRS UMR 6158, March 3rd, 26 pages.

27. E.R. Gafarov, A. Dolgui (2012), Two-Station Single Track Railway Scheduling Problem With Equal Speed of Trains// Report n° RR-12-09, LIMOS, CNRS UMR 6158, April 7th, 14 pages.

28. E.R. Gafarov, A. Dolgui (2012), Two Customized Parallel Machines Scheduling Problem with Precedence Relations// Report n° RR-12-10, LIMOS, CNRS UMR 6158, April 7th, 9 pages.

29. E.R. Gafarov, A. Dolgui (2012), Hard Special Case and Other Complexity Results for SALBP-1// Report n° RR-12-08, LIMOS, CNRS UMR 6158, April 7th, 13 pages.

30. E.R. Gafarov, A.A. Lazarev, A. Dolgui, F. Werner, A Graphical Approach to Solve an Investment Optimization Problem// Preprint 15/13, FMA, Otto-von-Guericke-Universitaet Magdeburg, 27 pages.

31. E.R. Gafarov, A.A. Lazarev and F. Werner (2010), Single Machine Scheduling with a Non-Renewable Financial Resource// Preprint 07/10, FMA, Otto-von-Guericke-Universitaet Magdeburg, 19 pages.

32. E.R. Gafarov, A.A. Lazarev and F. Werner (2010), "Single Machine Scheduling with Generalized Total Tardiness Objective Function// Preprint 10/10, FMA, Otto-von-Guericke-Universitaet Magdeburg, 8 pages.

33. E.R. Gafarov, A.A. Lazarev and F. Werner (2010), A Polynomial Time Graphical Algorithm for Maximizing Total Tardiness on a Single Machine// Preprint 12/10, FMA, Otto-von-Guericke-Universitaet Magdeburg, 15 pages.

34. E.R. Gafarov, A.A. Lazarev and F. Werner (2010), On Lower and Upper Bounds for the Resource-Constrained Project Scheduling Problem// Preprint 8/10, FMA, Otto-von-Guericke-Universitaet Magdeburg, 27 pages.

35. E.R. Gafarov, A.A. Lazarev and F. Werner (2010), Classical Combinatorial and Single Machine Scheduling Problems with Opposite Optimality Criteria// Preprint 11/10, FMA, Otto-von-Guericke-Universit?t Magdeburg, 15 pages.

36. E.R. Gafarov, A.A. Lazarev and F. Werner (2010), A Modification of Dynamic Programming Algorithms to Reduce the Time Complexity// Preprint 20/10, FMA, Otto-von-Guericke-Universitaet Magdeburg, 24 pages.

Тезисы конференций 37. E. R. Gafarov, A. Dolgui, A. Lazarev (2012), Notes on Complexity of the Simple Assembly Line Balancing Problem// Proceedings of the Conference UKI 2012, Institute of Control Sciences of the Russian Academy of Sciences, Moscow, Russia, 16-19 April, pp. 259-266.

38. E.R. Gafarov, A. Dolgui, A.A. Lazarev (2012), Some Complexity Results for the Simple Assembly Line Balancing Problem// Proceedings of the 3rd International Conference Optimization and Applications (OPTIMA 2012), Costa da Caparica, Portugal, 23- September 23-30, Edited by V.I. Zubov, Moscow, Russian Academy of Sciences, 2012, ISBN 978-5-91601-051-0, pp. 81-85.

39. E.R. Gafarov, A. Dolgui (2012), Algorithms for the two-station single track railway scheduling problem// Book of abstracts of the International Conference "Information Technologies in Industry" (ITI 2012), Minsk, Belarus, 30 October -1 November, ISBN 978 985-6744-78-8, pp. 111-112.

40. E.R. Gafarov, A.A. Lazarev, F. Werner (2012), Graphical Approach to Solve Combinatorial Problems: Algorithms and Some Computational Results// Proceedings of the 14th IFAC Symposium on Information Control Problems in Manufacturing (INCOM 2012), Bucharest, Romania, 23-25 May, Editors: N. Bakhtadze, A. Dolgui, Elsevier IFAC-PapersOnLine, ISSN 1474-6670, vol. 14, part 1, pp. 127 132.

41. E.R. Gafarov, A.A. Lazarev, F. Werner (2011), Scheduling Problems with Financial Resource Constraints// Proceedings of the 2nd International conference "Optimization and Applications" (Optima 2011), Petrovac, Montenegro, 25 September - 2 October, pp.

82-85.

42. A.A. Lazarev, E.R. Gafarov (2009), Lower Bounds and Flat Graphs of Precedence Relations for the Resource-Constrained Project Scheduling Problem// Proceedings of 13th IFAC Symposium on Information Control Problems in Manufacturing (INCOM 2009), Moscow, Russia, 3-5 June, Editors: N. Bakhtadze, A. Dolgui, Elsevier IFAC-PapersOnLine, ISSN 1474-6670, vol. 13, part 1, pp. 536-539.

43. A.A. Lazarev, E.R. Gafarov (2007), Estimation of Lower Bounds for the Resource Constrained Project Scheduling Problem// Proceedings of V Moscow International Conference on Operation Research (ORM 2007), Moscow, Russia, 10-14 April, pp. 236-238.

44. A.A. Lazarev, E.R. Gafarov (2006), Special case of the single machine total tardiness problem is NP-hard// In: Information Control Problems in Manufacturing 2006, A Proceedings volume from the 12th IFAC/IFIP/IFORS International Symposium (INCOM 2006, St Etienne, France, May 17-19), Elsevier Science, Vol. III, Operational Research, Editors: A. Dolgui, G. Morel, C. Pereira, ISBN: 978-0-08 044654-7, pp. 153-155. (Available also on IFAC-PapersOnLine, ISSN 1474-6670, vol. 12, part 1, pp. 155-157).

45. E.R. Gafarov, A. Dolgui, F. Grimaud (2012), Two Dedicated Machines Scheduling Problem in Two-Sided Assembly Lines// Conference Guide Abstracts Book of the conference Operations Research 2012, Hannover, Germany, 4-7 September, p. 174. (to appear in Operations Research Proceedings 2012).

Тезисы конференций 46. E.R. Gafarov, A.A. Lazarev and F. Werner (2010), Properties of Lower Bounds for the RCPSP// Booklet of Abstracts of the 12th International Workshop on Project Management and Scheduling (PMS 2010), Tours, France, 26-28 April, pp. 191-194.

47. E.R. Gafarov, A.A. Lazarev and F. Werner (2010), Single Machine Scheduling with a Non-renewable Financial Resource// Conference Program of EURO 2010, Lisboa, Portugal, 11-14 July, p. 69.

48. A.A. Lazarev, F. Werner and E.R. Gafarov (2010), On Single Machine Scheduling and Knapsack Problems with Opposite Optimization Criteria// Booklet of Abstracts of the European Chapter on Combinatorial Optimization (ECCO 2010), Malaga, Spain, 27- May, p.1.

37. A.A. Lazarev, E.R. Gafarov (2009), Estimation of Absolute Error for the Resources-Constrained Project Scheduling Problem// Booklet of Abstracts of the Multidisciplinary International Conference on Scheduling: Theory and Application (MISTA 2009), Booklet of Abstracts, Paris, France, 28-31 August. p. 8.

49. A.A. Lazarev, E.R. Gafarov (2009), Graphical Approach for Solving Combinatorial Problems//

Abstract

Guide of International Conference on Operation Research (OR 2006), Karlsruhe, Germany, 6-8 September, p. 59.

50. A.A. Lazarev, E.R. Gafarov (2006), Algorithms for the Single Machine Total Tardiness Problem// Abstract Guide of International Conference on Operation Research (OR 2006), Karlsruhe, Germany, 6-8 September, p. 285.

51. A.A. Lazarev, A.G. Kvaratskhelia, E.R. Gafarov (2005), Algorithms for Solving Problems $1||\sum T_j$ and Even-Odd Partition// Book of Abstracts of XVIII International Conference European Chapters on Combinatorial Optimization (ECCO XVIII), Minsk, Belarus, 26-28 May, pp. 32-33.

Основные результаты (сжато) • графический метод решения задач комбинаторной оптимизации;

• 10 точных графических алгоритмов;

• 7 графических FPTAS;

• более 10 доказательств NP-трудности;

• точные не графические алгоритмы.

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

40 из

 


 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.