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

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

003062647

КВАРАЦХЕЛИЯ Александр Гонерович

МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ МИНИМИЗАЦИИ СУММАРНОГО ЗАПАЗДЫВАНИЯ ДЛЯ ОДНОГО ПРИБОРА И ЗАДАЧИ РАЗБИЕНИЯ

01 01 09 дискретная математика и математическая кибернетика

Автореферат

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

Москва - 2007

003062647

Работа выполнена на кафедре экономической кибернетики Казанского государственного университета им В И Ульянова-Ленина

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

доцент А А Лазарев

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

профессор И X Сигал,

кандидат физико-математических наук М А Посыпкин

Ведущая организация Институт проблем управления РАН г Москва

Защита диссертации состоится " ^ " & 2007 г в часов на заседании диссертационного совета Д 002 017.02 при Вычислительном центре им А А Дородницина Российской академии наук (119991 г Москва ул Вавилова 40, конф зал)

С диссертацией можно ознакомиться в библиотеке ВЦ РАН Автореферат разослан " ^ " ¿^ь^еля 2007 г

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

В В Рязанов

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

Актуальность темы Диссертационная работа посвящена исследованию классической ЫР-трудной (в обычном смысле) задачи теории расписаний -- минимизации суммарного запаздывания для одного прибора (далее - задача 1 11 ^ Т,) — с целью отыскания новых свойств оптимальных расписаний общего и некоторых частных случаев задачи, построения на их основе новых алгоритмов решения этой задачи и применения полученных результатов для построения алгоритма решения ЫР полной (в обычном смысле) задачи РАЗБИЕНИЕ1.

Изучаемые в теории расписаний задачи выбора очередности обслуживания имеют самый общий характер и возникают при различных видах целенаправленной деятельности, например при календарном планировании производства транспортных перевозок обучения, информационно-вычислительных процессов исследовании структуры молекулы ДНК2

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

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

Цель работы заключается в исследовании задачи 1 '[ | ^ Т3 для отыс-

1 Гэри М , Джонсон Л Вычислительные машины и труднорешаемые задачи Пер с англ - М Мир, 1982 - 416 с

2В зарубежной читературе данное направление известно как ОМА-ищитслщ

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

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

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

Апробация работы Результаты диссертационной работы докладыва-

лись и обсуждались на VII Международном семинаре «Дискретная математика и ее приложения» (Москва, МГУ 29 января - 2 февраля 2001 г ), на XXIII Конференции молодых ученых мехмата МГУ (Москва, 9-14 апреля 2001 г) на Международной конференции «MAPSP'01 Models and Algorithms in Planning and Scheduling Problems» (Ассуа Франция, 17-22 июня 2001 г), на XL Международной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, НГУ, 16-18 апреля 2002 г), на XIII Международной конференции «Проблемы теоретической кибернетики» (Казань, КГУ, 27-31 мая 2002 г), на Международной конференции «DAOR'2002 Дискретный анализ и исследование операций» (Новосибирск 24-28 июня 2002 г ) на Международной конференции «MAPSP'03 Models and Algorithms foi Planning and Scheduling Problems» (Ассуа, Франция, 30 марта-4 апреля 2003 г ), на Международной летней школе «Doctoral Courses m Discrete Systems and Optimization» (Гренобль Франция, 22 июня-4 июля 2003 г ), на VIII Международном семинаре «Дискретная математика и ее приложения» (Москва, МГУ 2-6 февраля 2004 г), на III Международной конференции «PSC'04 Parallel Computing Systems» (Колима, Мексика, 19-22 сентября 2004 г), на VI Международной конференции «Дискретные модели в теории управляющих систем» (Москва, МГУ 7-11 декабря 2004 г), на XVIII Между-

народной конференции «ЕССО'Об European Chaptei on Combinatorial Optimization» (Минск, Беларусь, 26-28 мая 2005 г), на итоговых научных конференциях Казанского государственного университета и научных семинарах кафедры экономической кибернетики Казанского государственного университета

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

Структура и объем работы Диссертационная работа состоит из введения, трех глав заключения, указателя основных обозначений и списка литературы (86 наименований) Общий объем диссертации -126 страниц

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

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

В первой главе рассматриваются комбинаторные свойства задачи минимизации суммарного запаздывания для одного прибора 1 | | Т3 Получены свойства оптимальных расписаний, на основе которых построены алгоритмы решения задачи Даны некоторые оценки оптимального значения целевой функции

В параграфе 1 1 приводится постановка рассматриваемой задачи, вводятся необходимые понятия и обозначения

Необходимо обслужить п требований на одном приборе Прерывания требований, искусственные простои прибора при обслуживании и обслуживание более одного требования в любой момент времени запрещены Требования пронумерованы числами 1,2, , п Множество индексов N = {1,2, , п} назовем множеством требований

Для требования j G JV заданы следующие параметры продолжительность обслуживания р3 > 0, pj £ Z+, и директивный срок окончания обслуживания d3 Задан момент начала обслуживания ¿о, с которого прибор готов начать обслуживание требований Все требования поступают на обслуживание одновременно в момент времени to

Расписание обслуживания требований множества N задается кусочно-постоянной непрерывной слева функцией s Ж —> {0,1,2, , п} Если s(f) = 0, то в момент времени t прибор простаивает, если s{t) — j, j 6 N, то в момент времени t прибор обслуживает требование j Поскольку в рассматриваемой задаче требования поступают на обслуживание одновременно, обслуживаются без прерываний и искусственных простоев прибора, то расписание однозначно задается перестановкой тг элементов множества N Далее понятия расписания и перестановки элементов множества требований будем отождествлять и называть перестановку тг расписанием

Для обозначения индивидуального примера I задачи с заданными множеством требований N, продолжительностями обслуживания директивными сроками dj и моментом начала обслуживания t0 будем использовать запись / = ({Pj, dj}](:j4, to) Краткая форма этой записи I —

— {N, ¿о} применяется в случав, когда параметры требований р}, d3 фиксированы (однозначно определены контекстом) Пусть П(1) — множество всех возможных та' расписаний для примера I

Через (г —» jбудем обозначать взаимный порядок обслуживания двух требований inj при расписании 7г, данная запись означает то что требование г обслуживается ранее требования j Основной характеристикой обслуживания требования j G N при расписании 7г является момент окончания обслуживания Cj (тт): равный to -f + Pj

Величину Ту (тг) = тах{0, с,(7г) — d0} называют запаздыванием, требования j при расписании -?г а величину F(ir) = Х^ел'^-Д77) " суммарным запаздыванием требований при расписании 7г

Задача минимизации суммарного запаздывания для одного прибора заключается в построении оптимального расписания тг*, при котором выполняет,ся неравенство F{ir*) < F(tt) для всех тг G П(7)

Пусть П*(/) — множество оптимальных расписаний для примера I Сформулированная задача является NP-трудной в обычном смысле3

В параграфе 1 2 рассматриваются алгоритмы решения примеров рассматриваемой задачи, основанные на декомпозиционных свойствах задачи Такие свойства позволяют рассматривать процесс нахождения оптимального расписания как процесс разбиения примера на подпримеры,

3Du J , Leung J Y-T Minimizing total tardiness on one processor is NP-hard // Math Oper Res

- 1990 - N 15 - P 483-495

которые могут быть решены независимо друг от друга Одно из первых декомпозационных свойств задачи было получено Лаулером, который предложил алгоритм решения примеров задачи с оценкой трудоемкости 0(п4 Y^Pj) операций4

Перенумеруем требования множества N в порядке неубывания директивных сроков d\ < < dn (при этом, если d3 — d]+\, то р} < pJ+i, J = 1,2, , п — 1) Пусть ]* будет требованием с максимальной продолжительностью (если таких требований несколько, то выберем требование с наибольшим номером), те j* = max{j £ N р3 — тахрг} Пусть

i€N

Sk ~ t0 + р, (к = 1,2, ,n)

Через L(I) обозначим множество всех таких индексов к > j* что выполнены неравенства dj + Pj < Sk (j = j* + 1, . , к) и Sk < ¿4+ъ доопределив dn+\ = +оо Множество L{I) будем называть множеством подходящих позиций для требования j*

Теорема 1 Для любого примера I множество подходящих позигщй Ь{1) для требования j* не пусто

Декомпозиционные свойства задачи выражены следующей теоремой

Теорема 2 э Для любого примера I существует оптимальное расписание 7Г* Е П*(1), при котором требование j* обслуживается па месте к € Ь{1) При этом для подходящего места к выполняется

О Лтт* для j <Е {1,2, ,k}\{f} « 0* -» З)*' для j G {fc+1, ,n}

Приведем схему решения произвольного примера задачи 1 j | Ту на основе приведенных декомпозиционных свойств

Рассмотрим пример I = {N, ¿о} Для него найдем требование j* и построим множество подходящих позиций L(I) Пусть m = |L(/)| Разобьем пример I на 2т подпримеров следующим образом Для каждого к G L(/) построим два подпримера Ik = {N'k,t'k} и Ik — {Nk,tk}, где N'k = {1,2, ,fc} \ {/}, ffc = i0 и N£ = {к + 1, ,n}, tl = Решим построенные примеры, т е построим оптимальные расписания тг'к и

4Lawler EL A pseudopolynomial algorithm for sequencmg jobs to minimize total tardiness // Ann Discrete Math - 1977 - No 1 - P 331-342

5Лазарев А А Алгоритмы декомпозиционного типа решения задачи минимизации суммарного запаздывания // Исследования по прикладной математике - Казань Изд-во Казан гос ун-та, 1990 - Вьш 17 - С 71-78

7гЧ для примеров Гк и (к € Ь(1)) Пусть ттк = е М-0)

Тогда, согласно теореме 2 расписание ттк-, где к* = а^тт^д/) Р(ттк), будет оптимальным расписанием для примера I Построение примеров Гк и I')' и нахождение для них оптимальных расписаний будем называть декомпозицией примера I по подходящей позиции к

Идея алгоритма решения произвольного примера задачи с помощью декомпозиционных свойств (далее, алгоритм А) основана на обходе дерева подпримеров "в глубину" с использованием рекурсивного вызова описанной выше процедуры декомпозиции примеров на подримеры Данная процедура принимает в качестве параметров множество требований и момент начала обслуживания и результатом ее работы является построение оптимального расписания для данного примера (подпримера)

Отметим, что если в двух различных вершинах дерева подпримеров будет находиться один и тот же подример (одинаковы множества требований и моменты начала обслуживания) то алгоритм А построит оптимальное расписание для данного подпримера дважды Чтобы избежать данного недостатка, предлагается использовать алгоритм БВА процесс выполнения которого разбивается на два этапа На первом этапе осуществляется декомпозиция исходного примера в список всех его подпримеров вплоть до получения подпримеров из одного требования Список подпримеров организован как хэш-таблица Значение хэш-функции, соответствующее подпримеру вычисляется с использованием момента начала обслуживания требований данного примера При формировании данного списка подпример включается в список только в том случае, если в списке нет аналогичного примера На втором этапе осуществляется "сборка" оптимального расписания на основе построенного списка подпримеров

В заключение параграфа приводятся результаты экспериментального сравнения времени выполнения алгоритмов А и БВА на некотором классе тестовых примеров

В параграфе 1 3 рассматриваются свойства оптимальных расписаний и предлагается алгоритм решения примеров / в случае, когда при любом расписании тг £ П(/) запаздывает одно и то же количество требований т (О < т < п) При этом запаздывающие требования упорядочены в конце расписания 7г (т е расписание 7Г можно представить в виде тг = (я-!, 7Гг) где подрасписание тг2 содержит все т запаздывающих требований)

Через D(7г) обозначим множество запаздывающих расписаний при расписании тг В рассматриваемом случае верны следующие утверждения

Лемма 1 При любом, оптимальном расписании тг* требования множества D(ir*) обслуживаются в SPT порядке6

Далее, перенумеруем требования примера I в порядке невозрастания продолжительностей обслуживания р\ > р2 > > р„, при этом, если Pj = Pj+i 0 = 1» ,п- 1), то dj > dJ+1

Лемма 2 Существует оптимальное расписание тх* такое, чт,о если для некоторого k Е N выполняется к Е D(ir*), то (j —> для всех требований j Е {к + 1, , п}

Свойства оптимальных расписаний в рассматриваемом случае выраженные в леммах 1 и 2, позволяют построить алгоритм нахождения оптимального расписания за 0(п3) операций (далее, алгоритм FA) Построение оптимального расписания алгоритмом FA сводится к обходу дерева, каждая ветка которого соответствует некоторому порядку обслуживания запаздывающих требований Количество вершин этого дерева экспоненциально зависит от величин тип однако полученные свойства позволяют выполнить определенную "склейку" вершин дерева так, что в нем остается только полиномиальное количество вершин

В параграфе 1 4 приводятся две оценки оптимального значения суммарного запаздывания, основанные на свойствах SPT-расписаний При этом полученные оценки позволяют получить абсолютную погрешность значения суммарного запаздывания при SPT-расписании7

Перенумеруем требования множества N в порядке неубывания продолжительностей обслуживания, то есть р\ < щ < < Рп SPT-расписание (1,2, , п) будем обозначать через 7rspi Рассмотрим произвольный пример задачи I = ({pj, dj}jep?, ¿о) с оптимальным значением целевой функции F*(I) Пусть dmm = mmjeAr d} и (imax = тах^дг d3

6SPT - Shortest Processing Time Расписание ж называется SPT-расписанием если требования упорядочены при расписании 7г в порядке неубывания продолжительностей обслуживания

Относительная погрешность значения суммарного запаздывания при EDD-расписанип (расписании, требования при котором > порядо зены в порядке невозрастания значений директивных сроков) установлена Лаутером в 197Т г

Выберем величины С и 5 такими, что

¿nun < с < firnax и 5 = max{draax - С, С - dmin}

Пусть S = to + J2]l=i Pv и рассмотрим пример I' = {{р2, d'3 — C}jejy, i0) Справедлива следующая теорема

Теорема 3 (первая оценка) Для выбранных значений С и 5 верно неравенство

\F\I)-F*(I')\<n5 (2-2| + £)-М,

Отметим, что SPT-расписание nspt является оптимальным расписанием для любого примера директивные сроки которого равны некоторой константе Следовательно величина F*(I') равна суммарному запаздыванию требований примера I' при расписании Trspt

Для формулировки второй оценки рассмотрим функцию

п J

fit) = max{°' *о+X) p* - *>

r~l 1=1

Значение этой функции в точке t равно оптимальному значению суммарного запаздывания для параметрического примера 7(f) = jv,io) при котором директивные сроки всех требований одновременно равны t Данное утверждение справедливо потому, что оптимальным расписанием для данного примера ири любом значении t будет SPT-расписание Kspt Функция / является кусочно-линейной невозрастающей непрерывной и неотрицательной функцией принимающей значения 0 для всех t > to + T,j€NPj

Теорема 4 (вторая оценка) Для любого примера I справедливо неравенство f{d max ) < F*{I) < f{dmm)

В заключение параграфа приводится схема построения такого примера задачи 1 11 Yl^и ПРИ котором оптимальное значение целевой функции равняется заранее заданному значению Схема построения такого примера основана на свойствах функции /

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

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

{ Р1>Р2> >Рп, т

\ < ¿2 < < <1п 1 }

Предлагается подход к решению задачи в случае (1), при котором исходное множество требований N разбивается на к таких непересекающихся подмножеств М.\,М.2, ,-М^, что N = М.1\)М.2\} и^ь и шахи6^1/1(1г — ¿3\ < тш(у — 1> ,к), а затем на основе этого разбиения строится оптимальное расписание

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

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

Лемма 3 Существует оптимальное расписание -к* при котором выполняется либо (к —>■ г)плибо (_7 —)■ к)ж» для любой, тлкой тройки требований г,],к € М, что \с1г — | < тш{р„р;}, к < тт{г,_7} и (г 7)тг*

Лемма 4 Существует оптимальное расписание гг* при котором выполняется либо (к —> либо ((к + 1) —> к)ж> для любой такой пары требований & N, что к < у

На основе полученных свойств оптимальных расписаний в параграфе 2 2 приводится описание подхода к решению примеров задачи в случае (1)

На первом этапе производится разбиение множества требований N на непересекающиеся подмножества Л4-2, ,-Мь, такие, что разность

8 Лазарев А А, Гафаров Е Р Доказательство 1ЧР-трудности частного случая задачи минимизации суммарного запаздывания//Известия РАН Теория и системы управления - 2006 - №3 - С 120128 А также [8]

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

Определим параметрический пример /¿(i) = {{Pjj 0), где

N)с — {k,k +1, ,n} ndj(i) = dj—dn+t~tQ Ik(t) - это индивидуальный пример исследуемой задачи обслуживания требований множества с моментом начала обслуживания, равным нулю, и директивными сроками dj(t), линейно зависящими от параметра t Исходный пример I равен параметрическому примеру Ii(t) при t = dn, те множества оптимальных расписаний для примеров I и I\(dn) совпадают

Идея предлагаемого подхода к решению примеров в случае (1) основана на методе динамического программирования и заключается в построении оптимальных расписаний \{t) для примеров Ik{t) в порядке к = п, п — 1, , 1 для всех целочисленных точек t € [¿о, dn) Расписания 7r£(i) строятся на основе построенных на предыдущих шагах расписаний 7tf(i'), I > к, t' Е [io,rfn] Оптимальные расписания для примеров /„(i), множество требований которых включает в себя только одно требование с номером п, равны расписанию (п)

Согласно леммам 3 и 4, при построении оптимального расписания для исходного примера I можно исключить из рассмотрения все расписания 7г, при которых

(a) существуют такие требования г,у,к G N, что к < min{z,j}, требования г, j принадлежат некоторому подмножеству М„, требование к принадлежит подмножеству с меньшим чем f, номером, и выполняется (г —» к —t j)^

или

(b) существуют такие требования j, к € N. что к < j, и выполняется

При построении оптимальных расписаний для примеров h{t), отталкиваясь от структуры полученных на ранних шагах оптимальных расписаний примеров Ii(t'), I > к, можно определить позиции для требования к, на которых оно может быть обслужено при некотором оптимальном расписании Показано, что таких позиций может быть не больше, чем

9Такое разбиение множества требований может быть выполнено за 0(п) операций

количество подмножеств Л4 Накапливая информацию об оптимальных значениях целевой функции в ходе работы алгоритма, можно найти оптимальное расписание для исходного примера I за 0(кп ^Рз) операций

В параграфе 2 3 рассматривается случай к = 1, то есть, параметры требований удовлетворяют условиям

В этом случае при построении оптимального расписания 7гГ(¿) с помощью описанного выше подхода для каждой точки £ требуется просмотреть только две позиции для требования к до всех требований множества и после всех требований этого множества При постановке требования к на обслуживание до всех требований множества N¡¡.+1 получаем расписание (к, 7г£+1(< — рк)) после всех требований - расписание (7г^ч_1 , к) Расписание с наименьшим значением суммарного запаздывания среди двух полученных расписаний будет оптимальным расписанием для примера Алгоритм, реализующий данный подход к построению расписания в случае (2), назовем алгоритмом В-1

Теорема 5 Алгоритм В-1 находит оптимальное расписание для случая (2) за 0(п£р,) операций

В заключение параграфа приводится схема нахождения полиномиально разрешимых подслучаев случая (2), для которых алгоритм FA (параграф 1 3) находит решение за 0(п3) операций

В параграфе 2 4 рассматривается с л .у чай для произвольного значения к Приводится формальное описание алгоритма В-к нахождения оптимального расписания в случае (1) Необходимо отметить, что в случае к = 1 шаги алгоритма -В-к совпадают с шагами алгоритма В-1 Трудоемкость нахождения решения с помощью алгоритма В-к равна операций

Далее, в параграфах 2 5 и 2 6 формулируются и доказываются свойства оптимальных расписаний для двух частных случаев задачи позволяющие построить алгоритмы нахождения решения примеров данных случаев с трудоемкостью 0(п2) операций

В параграфе 2 5 рассматриваются примеры, параметры требований которых удовлетворяют условиям

¿1 < ¿2 < . < в,п,

¿п ~ ¿1 < 1, (3)

На основе полученных свойств оптимальных расписаний в случае (3) построен алгоритм С-1, который находит решение за 0(п2) операций Идея данного алгоритма основана на построении расписания "с конца" Процесс работы алгоритма разбит на 3 этапа

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

Алгоритм С-1 находит оптимальное расписание для случая (3) за 0(п2) операций Отметим, что данный алгоритм можно использовать для решения примеров в случае, когда в условиях (3) второе неравенство заменено на ¿п — < НОД (рх, ,рп)

В параграфе 2 6 рассматриваются примеры параметры требований которых удовлетворяют условиям

й3 -с^-х > р3, з = 2,3, ,п (4)

Поскольку р} > 0, з 6 N, то выполняется < < (1п Отметим, что случай (4) является "предельным" подслучаем случая (1), когда количество подмножеств к равно количеству требований, те каждое подмножество Л4и {у = 1, , к) состоит ровно из одного требования

Показано, что для примеров в случае (4) существует оптимальное расписание 7г* £ П*(/), при котором требование ]* обслуживается на первой позиции из множества Ь{1) Данное свойство позволяет построить

алгоритм В-п решения примеров рассматриваемого случая за 0(тг2) операций Этот алгоритм представляет собой модификацию алгоритма А в которой перебираются не все возможные позиции для требования ]*, а только первая из них

В третьей главе диссертации исследуются свойства алгоритма В-1 показано, что данный алгоритм может быть использован для нахождения решения следующих ИР-полных задач разбиения РАЗБИЕНИЕ ЧЕТНО-НЕЧЕТНОЕ РАЗБИЕНИЕ ЧЕТНО-НЕЧЕТНОЕ РАЗБИЕНИЕ С ОГРАНИЧЕНИЯМИ Предложены модификации алгоритма В-1 и показано, что процесс построения расписания этим алгоритмом можно свести к процессу построения кусочно-линейной функции специального вида

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

Расписание 7г назовем расписанием обладающим свойством В-1, если для всех требований к £ {1,2, ., п — 1} при расписании 7г выполняется либо (к —>• либо (_7 —>■ к)л- для всех о & {к 1, ., п}

Множество всех расписаний, обладающих свойством В-1 для примера I, будем обозначать через Пв-^/) Пусть П^_1(/) = Пв_!(/) р) П*(/) Таким образом множество П|3_1(/) является множеством всех оптимальных расписаний обладающих свойством В-1 Получено следующее необходимое и достаточное условие того, что алгоритмом В-1 для некоторого примера I будет построено оптимальное расписание (даже если параметры требований примера I не удовлетворяют условиям (2))

Теорема 6 Алгоритм В-1 ■находит оптимальное расписание для некоторого примера I тогда и только тогда,, когда П^_1(/) ф 0

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

Параграф 3 2 посвящен классической МР-полной (в обычном смысле) задаче РАЗБИЕНИЕ, рассматривается схема полиномиального сведения

примеров этой задачи к примерам задачи теории расписаний 1 11 J2 Т} Приводится алгоритм решения задачи РАЗБИЕНИЕ

В подпараграфе 3 2 1 приводится постановка задачи РАЗБИЕНИЕ и указывается схема полиномиального сведения данной задачи к двум NP-полным в обычном смысле задачам ЧЕТНО-НЕЧЕТНОЕ РАЗБИЕНИЕ (далее, ЧНР) и ЧЕТНО-НЕЧЕТНОЕ РАЗБИЕНИЕ С ОГРАНИЧЕНИЯМИ (далее, ОЧНР)

В классической задаче РАЗБИЕНИЕ требуется определить, существует ли такое разбиение множества m целых положительных чисел на два подмножества, что суммы чисел в обоих подмножествах равны Задача ЧНР представляет собой модификацию задачи разбиения, когда на разбиение множества накладывается ограничение, что соседние числа (первое и второе, третье и четвертое и т д ) должны оказаться в разных подмножествах Задача ОЧНР представляет собой задачу ЧНР с дополнительными ограничениями на значения чисел исходного множества

Известна10 схема полиномиального сведения примеров задачи ОЧНР к задаче 1 11 Т3 (таким образом устанавливается NP-трудность задачи 1 | | J2 У)) Основная идея схемы сведения заключается в построении по заданному примеру задачи ОЧНР примера задачи 1 | | (такие

примеры задачи суммарного запаздывания называются каноническими) При этом доказывается что для полученных примеров задачи 1 11 Y2 Т3 существует оптимальное расписание специального вида называемое каноническим Исходный пример задачи ОЧНР имеет искомое разбиение на два подмножества тогда и только тогда когда соответствующий канонический пример задачи 1 11 имеет оптимальное значения суммарного запаздывания, равное определенной величине

В подпараграфе 3 2 2 показано, что любое (в том числе, и оптимальное) расписание канонического вида обладает свойством В-1 Таким образом, мы можем использовать алгоритм В-1 для нахождения решения канонических примеров задачи 1 | | ^ Т3 и, соответственно, задач РАЗБИЕНИЕ ЧНР, ОЧНР, хотя канонические примеры не принадлежат случаю (2) С учетом особенностей канонических примеров предложен алгоритм B-1-канонический, трудоемкость которого не хуже известного алгоритма Гэри и Джонсона11 для задачи РАЗБИЕНИЕ Алгоритм В-

10Du J , Leung I Y -Т Minimizing total tardiness on one processor is NP-haxd // Math Oper Res - 1990 - N 15 - P 483-495

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

1 -канонический отличается от алгоритма В-1 тем, что на каждом шаге алгоритма просматриваются не все точки t из интервала t £ [to,dn], а лишь некоторые из них

В параграфе 3 3 приводится модификация алгоритма В-1, которая позволяет снизить трудоемкость решения примеров в случае (2) Идея алгоритма ВЛ-людифицированный заключается в том, что процесс построения оптимального расписания сведен к процессу построения кусочно-линейной функции специального вида Рассматривается функция fit) кусочно-линейная непрерывная монотонно-невозрастающая функция, обращающаяся в нуль для всех t больших или равных некоторой величины i', и строго убывающая для всех t < t! При этом коэффициент наклона функции fit) по модулю не превышает значения п Рассматриваются три операции над функциями такого вида сдвиг функции, сложение двух функций и нахождение функции минимума двух функций

Полученные свойства рассматриваемых функций использованы для построения алгоритма B-1-модифицированный Преимущество этого алгоритма заключается в том, что при построении решения для примеров случая (2) нет необходимости рассматривать все целочисленные точки интервала t е [i0> dn] Трудоемкость решения полиномиально зависит от максимального количества точек изменения наклона функций, рассматриваемых в ходе решения Преимуществом Алгоритма B-1-модифициро-ванный является то что при умножении одновременно всех параметров примера в константное количество раз трудоемкость решения не меняется Также данный алгоритм может быть использован для решения задач 1 | | Y,T3 (в случае (2)), РАЗБИЕНИЕ, ЧНР и ОЧНР с нецелочисленными параметрами примеров

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ

РАБОТЫ

• Найдены новые свойства задачи 1 | | ]Г]Т-, использование которых позволяет сократить перебор при построении решения с помощью одного известного алгоритма декомпозиционного типа На основе полученных свойств предложен полиномиальный алгоритм решения примеров в случае, когда при любом возможном расписании количество запаздывающих требований является константой, Мир, 1982 - 416 с

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

• Доказаны новые свойства оптимальных расписаний NP-т рудного частного случая, когда параметры требований удовлетворяют условиям pi > р2 > > рп, d\ < ¿2 < < dn, и предложен алгоритм решения примеров этого случая за 0(n2 Y^Pj)) операций Выделен один псевдополиномиально разрешимый (0(n Y^Pj) операций) и два полиномиально (0(п2) операций) разрешимых подслучая этого случая,

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

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

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ

[1] Кварацхелия А Г К исследованию NP-сложной задачи теории расписаний минимизации суммарного запаздывания для одного прибора / А Г Кварацхелия // Материалы XL Международной научной студенческой конференции «Студент и на>чно-технический прогресс» Математика - Новосиб гос ун-т Новосибирск, 2002 - С 124-125

[2] Лазарев А А Стохастическое исследование методов ветвей и границ для NP-трудной задачи теории расписаний минимизации суммарного запаздывания для одного прибора / А А Лазарев, А Г Кварацхелия // Материалы VII Международного семинара «Дискретная математика и ее приложения» (29 января - 2 февраля 2001 г) Часть III - M Изд-во центра прикладных исследований при мех -мат фак>льтете МГУ, 2001 г - С 379-381

[3] Лазарев А А Иссчедование проблемы теории расписаний 1 || ]T)Tj / А А Лазарев, А Г Кварацхелия // Проблемы теоретической кибернетики Тезисы докладов XIII Международной конференции (Казань, 27-31 мая 2002 г) Часть II - M Изд-во

центра прикладных исследований при механико-математическом факультете МГУ 2002 - С 107

[4] Лазарев А А Исследование проблемы теории расписаний 1 11 Т} / А А Лазарев А Г Кварацхелия // Материалы Российской конференции «Дискретный анализ и исследование операций», 24-28 июня, 2002 г - Новосибирск, 2002 - С 218

[5] Лазарев А А Теоретическое и экспериментальное исследование NP-трудной проблемы теории расписаний минимизации суммарного запаздывания на одном приборе / А А Лазарев А Г Кварацхелия // Исследования по прикладной математике и информатике - Казань Изд-во Казан гос з'н-та, 2003 - Вып 24 - С 90-106

[6] Лазарев А А Алгоритм 0(n2£]pj) решения NP-трудной проблемы теории расписаний 1 11 Т] / А А Лазарев, А Г Кварацхелия // Материалы VIII Международного семинара «Дискретная математика и ее приложения» (2-6 февраля 2004 г) - Изд-во механико-математического факультета МГУ, 2004 - С 211-213

[7] Лазарев А А Алгоритм решения проблем 1 || и четно-нечетного разбиения / А А Лазарев А Г Кварацхелия // Труды VI ¡Международной конференции «Дискретные модели в теории управляющих систем» (7-11 декабря 2004 г) М Изд-во факультета вычислительной математики и кибернетики МГУ 2004 - С 184-187

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

[9] Lazarev A Methods to research problem of scheduling theory minimizing total tardiness on a single machine / A Lazarev, A Kvaratskhelia // Abstracts of VI Workshop «Models an Algorithms for Planning and Scheduling Problems» (Aussois, Prance 30 III - 4 IV 2003)

- P 143-144

[10] Lazarev A Solution Algorithms foi the Total Tardiness Scheduling Problem on a Single Machine / A Lazart\, A Kvaratskhelia, A Tchernykh // Proceedings of XV International Conference ENC'04 (Colima, Mexico, 20 - 24 X 2004) - P 474-480

[11] Lazarev A Algorithms for solving problems 1 || and Even-Odd Partition / A Lazarev, A Kvaratskhelia // Abstracts of XVIII International Conference «European Chapters on Combinatorial Optimization» (26-28 May Minsk Belarus) Minsk United Institute of Informatics Problems on the National Academy of Sciences of Belarus 2005

- P 32-33

Отпечатано с готового оригинал-макета в типографии Издательского центра Казанского государственного университета им В И Ульянова-Ленина Тираж 100 экз Заказ 4/10

420008, ул Профессора Нужина, 1/37 тел 231-53-59,292-65-60

Введение

1 Исследование комбинаторных свойств задачи 1 11 ^ 7}

1.1 Постановка задачи суммарного запаздывания для одного прибора

1.2 Алгоритмы построения оптимальных расписаний, основанные на декомпозиционных свойствах задачи

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

1.4 Оценки ЯРТ расписаний.

1.4.1 Первая оценка.

1.4.2 Вторая оценка

1.4.3 Задача построения набора требований с заданным оптимальным значением целевой функции.

1.5 Результаты экспериментальных исследований

2 Полиномиально и псевдо- полиномиально разрешимые случаи задачи 1 11 ^ 7)

2.1 Свойства оптимальных расписаний.

2.2 Описание похода к решению примеров задачи.

2.3 Алгоритм В А.

2.4 Алгоритм В-к.

2.5 Алгоритм С-1.

2.6 Алгоритм В-п.

3 Исследование свойств и приложения Алгоритма В

3.1 Свойство В-1.

3.2 Алгоритм решения задач разбиения.

3.2.1 Постановка и полиномиальная сводимость задач о разбиении

3.2.2 Алгоритм В-1 -канонический.

3.3 Алгоритм B-1-модифицироваиный.

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

Принято считать, что исследование задач теории расписаний началось с публикации С. Джонсоном своей работы [49], в которой рассматривалась задача выбора очередности обслуживания множества деталей, каждая из которых должна пройти последовательную обработку на нескольких станках с целью минимизации момента окончания обслуживания всех деталей. Начиная с первых публикация по теории расписаний [48, 78, 72] выяснилось, что большинство рассматриваемых задач являются трудоемкими для решения. Поэтому, значительная часть работ в этой области посвящена исследованию и выявлению сложности задач1. Обзоры по задачам теории хНа данный момент наиболее полная и постоянно обновляемая классификация М-*-трудных и открытых задач теории расписаний приведена на сайтах http://www.mathematik.uni-osnabrueck.de/research/OR/class/ и http://www.lix.polytechnique.fr/ <1игг^иегу/. расписаний и их сложности представлены в работах Гэри и Джонсона [5], Карпа [6], Лоулера [60], Ленстры и др. [61], Танаева и др. [27, 28], Брукера [37, 38]

Большинство задач теории расписаний являются ^-трудными, поэтому важным направлением исследований является разработка подходов к их решению. Задачи теории расписаний принадлежат классу экстремальных комбинаторных задач и допускают формулировку в терминах математического программирования. Поэтому при разработке алгоритмов их решения применяются идеи метода ветвей и границ [9, 25], динамического программирования [1, 50], методов нахождения приближенного решения [10, И, 30]. В последнее время динамически развивается направление разработки алгоритмов параллельных вычислений для решения таких задач [23]. Среди работ, посвященных методам решения задач дискретной оптимизации в целом и теории расписаний в частности, можно выделить статьи [2, 3, 4, 47] и книги [24, 25, 26, 27, 28, 29, 31, 33, 36, 37, 41, 66].

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

Диссертационная работа посвящена исследованию классической трудной (в обычном смысле) задачи теории расписаний минимизации суммарного запаздывания для одного прибора (далее2 - задача 1 11 ^ 7)) с целью отыскания новых свойств оптимальных расписаний общего и некоторых частных случаев задачи, построения на их основе новых алгоритмов решения данной задачи и применения полученных результатов для построения алгоритма решения МР-полных задачи РАЗБИЕНИЕ.

Задача 1 11 впервые была сформулирована в статье [62]. Приведем краткую постановку задачи. Необходимо обслужить п требований на одном приборе. Прерывания при обслуживании, обслуживание более одного требования в каждый момент времени запрещены. Требования поступают на обслуживание одновременно в момент времени ¿о- Требования пронумерованы числами 1,2,., 7г, множество N — {1,2,., гг} называют множеством требований. Расписание обслуживания требований однозначно задается перестановкой 7Г элементов множества N. Основной характеристикой обслуживания требования ^ £ N при расписании 7г является момент окончания обслуживания ц(тг). Величину 7)(7г) = тах{0, с^(7г) — называют запаздыванием требования ^ при расписании 7Г. Задача 1 | | 7) заключается в построении такого расписания 7Г, при котором достигается минимум целевой функции Г(тг) = ^¿ем^^)

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

Первые свойства оптимальных расписаний рассматриваемой задачи представлены в работе Эммонса [45]. Им, в частности, было установлено существование такого оптимального расписания 7г*, что если для требований е N выполняется р{ < р^ и с^ < а^-, то обслуживание требова

2В теории расписаний принята следующая нотация для обозначения задач. Каждой задаче соответствует запись а | /5 | 7, где а обозначает количество и тип доступных приборов, /3 описывает дополнительные ог раничения задачи (например, наличие отношения предшествования между требованиями),

7 представляет собой критерий задачи. ния i предшествует обслуживанию требования j при расписании 7Г*, т.е. {i > j)тг*- В соответствии с этим условием, если dj = const (j G N), то SPT расписание является оптимальным, и если pj = const (j G N), то EDD расписание является оптимальным. Некоторые улучшения результатов Эммонса приведены в работах [46, 71]. Разработке алгоритмов построения оптимальных расписаний для рассматриваемой задачи, основанных на идее метода ветвей и границ, посвящены работы [12, 40, 44, 46, 65, 68, 71, 73, 74, 77, 81, 82, 83, 85]. Применение метода динамического программирования для построения алгоритмов решения рассматривалось в работах [35, 52, 57, 58, 67, 69, 76, 79]. Для решения примеров рассматриваемой задачи Б. Лоулером [58, 59] построены псевдополиномиальный алгоритм трудоемкости 0(n4J2Pj), а также вполне полиномиальный е- приближенный алгоритм с оценкой трудоемкости 0(п7/е). Последняя оценка была понижена М.Я. Ковалевым [8] на порядок.

Построению приближенных (в т.ч. эвристических) алгоритмов для задачи 1 || ^Tj посвящены работы [32, 34, 39, 51, 63, 64, 70, 86]. В статье

42] исследовались нижние оценки относительной погрешности суммарного запаздывания для расписаний, построенных с помощью всех известных для рассматриваемой задачи эвристических алгоритмов AU [63], MDD [34], PSK [64], WI [86], COVERT [39], NBR [51], и DEC/MDD, DEC/PSK, DEC/WI [70]. В этой статье были построены примеры, для которых данные эвристические алгоритмы имеют неограниченно большое значение относительной погрешности значения суммарного запаздывания.

NP-трудность рассматриваемой задачи минимизации суммарного запаздывания для одного прибора была установлена в 1990 году [43]. В работе

43] предложена схема полиномиального сведения задачи четно-нечетного разбиения к исследуемой задаче. Поскольку задача четно-нечетного разбиения является КР-полной в обычном смысле [5], то задача 1 || является КР-трудной в обычном смысле.

Среди обзорных статей, посвященных задаче минимизации суммарного запаздывания для одного прибора и смежных ей задачах, следует выделить работы [53, 75, 80, 84].

С задачей 1 тесно связана задача минимизации суммарного опережения для одного прибора. Эта задача заключается в построении расписания, при котором достигается минимальное значение целевой функции гпах{0, £¿7 — су(7г)}. Данные задачи эквивалентны с той точки зрения, что алгоритм решения одной задачи может быть использован для получения решения второй задачи. Пусть I = ({Pj,dj}jeN^to) является примером задачи суммарного запаздывания. Построим пример задачи суммарного опережения Г = (^^'^з^^о), где ^ = (£0 + Е»елгР») ~ ^ + Рз> 3 € N. Пусть 7Г* = {з\,32,---ч3п) является оптимальным расписанием для примера I задачи суммарного запаздывания. Тогда расписание -к'* — {ЗпчЗп-ъ • • • > л) является оптимальным расписанием для примера V задачи суммарного опережения, и наоборот [43]. Поэтому, результаты, представленные в диссертации, непосредственным образом могут быть использованы для задачи минимизации суммарного опережения для одного прибора.

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

Заключение

Сформулируем основные результаты диссертационной работы:

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

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

• Доказаны новые свойства оптимальных расписаний ИР-трудного случая, когда параметры требований удовлетворяют условиям р\ > р2 > > . > рп, 4 < (¿2 < . < (1п, и предложен алгоритм решения примеров этого случая за 0(п2 ХРзУ) операций. Выделен один псевдополи-номиально разрешимый (О(пЕ^) операций) и два полиномиально (0(п2) операций) разрешимых подслучая этого случая;

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

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

Указатель обозначений

В диссертационной работе приняты следующие обозначения.

N ■ множество требований, N = {1,2,., п};

Рз ■ продолжительность обслуживания требования 3 € ./V; dj • директивный срок окончания обслуживания требования ] € И) о • момент начала обслуживания требований множества

I ■ индивидуальный пример исследуемой задачи, / = ({р]. ¿о);

7г • расписание обслуживания требований множества требований N (перестановка элементов множества Ы), п = (71,72, • • •,Зп), Зк - требование, обслуживаемое к-ым по порядку при расписании 7г; ж} ■ множество требований, упорядоченных при расписании ж; расписание ж называется частичным, если {7т} С ./V; расписание ж называется полным, если {7г} = ЛГ;

7Г0 • пустое расписание, то есть, {ж0} = 0;

П(/) • множество всех расписаний для примера /, |П(/)| = п\;

С](ж) • момент окончания обслуживания требования 3 при расписании 7г; г —> • обслуживание требования г предшествует обслуживанию требования з при расписании 7г, то есть, с*(ж) < ц(ж);

SPT (Shortest Processing Time) • расписание, при котором обслуживание требования с меньшей продолжительностью предшествует обслуживанию требования с большей продолжительностью, то есть, если pi < pj, то (i —> j)n, где тг - SPT расписание;

EDD (Earliest Due Date) • расписание, при котором обслуживание требования с меньшим директивным сроком предшествует обслуживанию требования с большим директивным сроком, то есть, если di < dj, то (z —»■ где тг - EDD расписание;

Tj (тг) - запаздывание требования j при расписании тт, вычисляется по формуле Tj (тг) = max{0,Cj(7r) — dj}\

F(tt) • суммарное запаздывание требований при расписании 7Г, вычисляется по формуле F(tt) = YjeN

D(tt) • множество запаздывающих при расписании тг требований, то есть, D(тг) = {j £ {тг} : ф) > dj}; тг* • оптимальное расписание, то есть, F(tt*) < F(tt) для всех тг 6 П(7);

П*(7) • множество оптимальных расписаний для примера 7;

F*(I) • оптимальное значение суммарного запаздывания для примера 7, то есть, F*(I) = F(tt*) для некоторого тг* G П*(7);

Запись (г —> j)n при необходимости будет расширена до (г —> j —> к)п для обозначения отношения предшествования более чем двух требований при некотором расписании 7Г, а также, эта нотация будет расширена до (j —» Ат% или (N' —j)n для обозначения того, что требование j предшествует всем требованиям или следует за всеми требованиям множества N' при расписании тг.

Для обозначения структуры некоторого расписания 7Г будем использовать запись 7г = (7г1,7г2,., 7гт), где расписание щ, г = 1 ,.,т, является частичным расписанием. Для частичных расписаний тг{ выполняется М = ЦЦМ' М ПК'} = 0 для г ^ ({ттх} -> {тг2} {тгт})„, и отношение предшествования между любыми двумя требованиями при любом частичном расписании щ совпадает с отношением предшествования между этими требованиями при расписании 7Г. Также, для обозначения структуры расписания 7Г относительно некоторого требования ] б {7г} будем использовать запись 7г = (7Гх, тга).

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

2. Бурдюк В.Я., Шкурба В.В. Теория расписаний. Задачи и методы решений // Кибернетика.- 1971. № 1. - С. 89 -102.

3. Бурков В.Н., Ловецкий С.Е. Методы решения экстремальных комбинаторных задач (обзор) // Известия АН СССР, Техническая кибернетика. 1968. - № 4. - С. 82-93.

4. Бурков В.Н., Ловецкий С.Е. Методы решения экстремальных задач комбинаторного типа (обзор) // Автоматика и телемеханика. 1968. - № 11. - С. 68-93.

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

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

7. Ковалев М.Я. Интервальные е приближенные алгоритмы решения дискретных экстремальных задач // Дисс. канд. физ.-мат. наук. -Минск, 1986. - 110 с.

8. Корбут А.А., Сигал И.Х., Финкелъштейн Ю.Ю. Методы ветвей и границ. Обзор теорий, алгоритмов, программ и приложений // Operations Forsch. Statist., Ser. Optimiz. — 1977. — V.8, N.2. — P. 253-280.

9. Корбут А.А., Сигал И.Х., Финкелъштейн Ю.Ю. Гибридные методы в дискретном программировании // Изв. АН СССР. Техн. кибернет.- 1988. № 1. - С. 65-77.

10. Корбут А. А., Финкелъштейн Ю.Ю. Приближенные методы дискретного программирования // Изв. АН СССР. Техн. кибернет. — 1983.1. С. 165-176.

11. Лазарев А.А. Алгоритмы в теории расписаний, основанные на необходимых условиях оптимальности // Исследования по прикладной математике. Казань: Изд-во Казан, гос. ун-та, 1984. - Вып. 10. - С. 102-110.

12. Лазарев А.А. Алгоритмы декомпозиционного типа решения задачи минимизации суммарного запаздывания // Исследования по прикладной математике. Казань: Изд-во Казан, гос. ун-та, 1990. - Вып. 17. - С. 71-78.

13. Лазарев А.А. Эффективные алгоритмы решения некоторых задач теории расписаний для одного прибора с директивными сроками обслуживания требований // Дис. канд. физ.-мат. наук. Казань, 1989.- 108 с.

14. Лазарев A.A., Гафаров Е.Р. Теория расписаний. Минимизация суммарного запаздывания для одного прибора. // М.: Вычислительный центр им. A.A. Дороницина РАН, 2006. 134 с.

15. Лазарев A.A., Кварацхелия А.Г. Алгоритм 0(n2Y^Vj) решения NP- трудной проблемы теории расписаний 1 || // Материалы

16. VIII Межд. семинара «Дискретная математика и ее приложения» (26 февраля 2004 г.). М: Изд. механико-математического факультета МГУ, 2004. - С. 211-213.

17. Посыпкин M.A., Сигал И.Х., Галимъянова H.H. Алгоритмы параллельных вычислений для решения некоторых классов задач дискретной оптимизации. // М.: Вычислительный центр им. A.A. Дороници-на РАН, 2005. 44 с.

18. Современное состояние теории исследования операций // Под ред. Н.Н.Моисеева. М.: Наука, 1979. — 464 с.

19. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: теория и вычислительные алгоритмы. // М.: Физ-матлит, 2002. 240 с.

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

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

22. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. // М.: Наука. Гл. ред. физ.-мат. лит., 1989.- 328 с.

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

24. Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования // М.: Наука, 1976.

25. Хачатуров В.Р., Веселовский В.Е., Злотов A.B. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности // М.: Наука. 2000.

26. Alidaee В., Gopalan S. A note of the equivalence of two heuristics to minimize total tardiness // European Journal of Operation Research. -1997.-V.96.-P. 514-517.

27. Baker K.R. Introduction to sequencing and scheduling. // Wiley, New York. 1974.

28. Baker K.R., Bertrand W.M. A dynamic priority rule for scheduling against due dates // Journal of Operation Management. 1982. V.3. -P. 37-42.

29. Baker K.R., Schräge L. Finding am optimal sequence by dynamic programming: an extension to precedence-related tasks // Operations Research. 1978. - V. 26. - P. 111-120.

30. Blazewicz J., Ecker K., Pesch E., Schmidt G., Weglarz J. Scheduling Computer and Manufactoring Processes. // Springer Berlin. 1996.

31. Brucker P. Scheduling Algorithms. // Springer-Verlag, 2001. 365 p.

32. Brucker P., Lenstra J.K., Rinnoy Kan A.N.G. Complexity of machine scheduling problems // Math. Cent. Afd. Math Beslisk. Amsterdam, 1975. - BW 43. - 29 pp.

33. Carroll D. C. Heuristic sequencing of single and multiple components // PhD Thesis, Massachusets Institute of Technology. 1965.

34. Chang S., Lu Q., Tang G., Yu W. On decomposition of the total tardiness problem, // Oper. Res. Lett. 1995. - V.17. - P. 221-229.

35. Conway R.W., Maxwell W.L., Miller L.W. Theory of Scheduling // Addison-Wesley, Reading, MA. 1967.

36. Delia Croce F., Grosso A., Paschos V. Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem 11 Journal of Scheduling. 2004. - V.7. - P. 85-91.

37. Du J., Leung J. Y.-T. Minimizing total tardiness on one processor is NP-hard // Math. Operation Research. 1990. - V.15. - P. 483-495.

38. Elmaghraby S.E. The one machine scheduling ptoblem with delay costs // Journal of Industrial Engineering. 1968. - V.19. - P. 105-108.

39. Emmons H. One machine sequencing to minimizing certain function of job tardiness // Operations Research. 1969. - V.17. - P. 701-715.

40. Fisher M.L. A dual problem for the one machine scheduling problem // Mathematics Programming. 1976. - V.ll. - P. 229-251.

41. Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G Optimization and approximation in determenistic sequencing and scheduling: a servey. // Ann. Descrete Optimization. 1979. - V.2. -P. 287-325.

42. Jackson J.R. Scheduling a production line to minimize maximum tardiness // Res. Report 43 Sci. Res.Project. UCLA, 1955.

43. Johnson S.M. Optimal two- and three-stage production schedules with setup times included. // Naval Research Logistics Quarterly. 1954. -V.l. - P. 61-68.

44. Held M., Karp R.M. A dynamic programming approach to sequencing problems // SIAM Journal. 1962. - Y.10. - P. 196-210.

45. Holsenback J.E., Russell R.M. A heuristic algorithm for sequencing on one machine to minimize total tardiness // Journal of Operation Research Society. 1992. - V.43. - P. 53-62.

46. Kao E.P.C., Queyranne M. On dynamic programming methods for assembly line balancing // Operations Research. 1982. - V.30. - P. 375-390.

47. Koulamas C.P. The total tardiness problem: Review and extensions // Operations Research. 1994. - V.42. - P. 1025-1041.

48. Lazarev A., Kvaratskhelia A., Tchernykh A. Solution algorithms for the total tardiness scheduling problem on a single machine. // Workshop Proceedings of the ENC'04 Mexican International Conference in Computer Science. Mexico, 2004. - P. 474-480.

49. Lazarev A., Kvaratskhelia A. Algorithms for solving problems 1 11 Yl^i and Even-Odd Partition. //In Book of Abstracts of XVIII Internationa Conference «European Chapters on Combinatorial Optimization». -Minsk, 26-28.V.2005. P. 32-33.

50. Lawler E.L. On scheduling problems with deferral costs // Management Science. 1964. - V.U.- P. 280-288.

51. Lawler E.L. A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness // Ann. Discrete Math. 1977. - V.l. - P.331.342.

52. Lawler E.L. A fully polynomial approximation scheme for the total tardiness problem // Oper. Res. Lett. 1982. - V.l. - P. 207-208.

53. Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shrnoys D.B. Sequencing and Schedling: Algorithms and Complexity // Elsevier Science Publishers B.V. 1993. - V.4. - P. 445-520.

54. Lenstra J.K., Rinnooy Kan A.H.G., Brucker P. Complexity of machine scheduling problems // European Journal of Operational Research. -1980. V.4. - P. 270-275.

55. McNaughton R. Scheduling with deadlines and loss functions // Management Science. 1959. - V.6. - P. 1-12.

56. Morton T.E., Rachamadugu R.M., Vepsalainen A. Accurate myopic heuristics for tardiness scheduling // GSIA Working Paper 36-83-84, Carnegie Mellon University. 1984.

57. Panwalkar S.S., Smith M.L., Koulamas C.P. A heuristic for the single machine tardiness problem // European Journal of Operation Research.- 1993. V.70. - p. 304-310.

58. Picard J., Queyranne M. The time-dependent travelling salesman problem and its application to the tardiness problem in one machine // Operations Research. 1978. - V.26. - P. 86-110.

59. Pinedo M. Scheduling: Theory, Algorithms, and Systems. Prentice-Hall? Englewood Cliffs, New Jersey. - 1995.

60. Potts C.N., Van Wassenhove L.N. A decomposition algorithm for the single machine total tardiness problem // Oper. Res. Lett. 1982. - V.5.- P. 177-182.

61. Potts C.N., Van Wassenhove L.N. A branch-and-bound algorithm for the weighted tardiness problem // Operations Research. 1985. - V.33. - P. 363-377.

62. Potts C.N., Van Wassenhove L.N. Dynamic programming and decomposition approaches for the single machine total tardiness problem European Journal of Operational Research. 1987. - V.32. - P. 405-414.

63. Potts C.N., Van Wassenhove L.N. Single machine tardiness sequencing heuristics //IIE Transactions. 1991. - V.23. - P. 93-108.

64. Rinnooy Kan A.H.G., Lageweg B.J., Lenstra J.K. Minimizing total cost in one machine scheduling // Operations Research. 1975. - V.23. - P. 908-927.

65. Schild L., Fredman K.R. Scheduling tasks with linear loss function // Management Science. 1961. - V.7. - P. 280-285.

66. Sen T., Austin L.M., Ghandforoush P. An algorithm for the single machine sequencing problem to minimize total tardiness // HE Transactions. 1983. - V.15. - P. 363-366.

67. Sen T., Borah B.N. On the single machine sheduling problem with tardiness penalties // Journal of Operational Research Society. — 1991. — V.42. P. 695-702.

68. Sen T., Sulek J.M., Dileepan P. Static scheduling research to minimize weighted and unweighted tardiness: A state-of-the-art survey. // International Jornal of Production Economics. 2003. - V.83. - P. 112.

69. Schräge L., Baker K.R. Dynamic programming solution of sequencing problems with precedence constraints // Operations Research. 1978. -V.26. - P. 444-449.

70. Shwimer J. On the n-job one machine sequence-independent scheduling problem with tardiness penalties 11 Management Science. 1972. - V.18. - p. 301-313.

71. Smith W.E. Various optimizers for single stage production // Naval Research Logistics Quarterly. 1956. - V.3. - P. 59-66.

72. Srinivasan V. A hybrid algorithm for the one machine sequencing problem to minimize total tardiness // Naval Research Logistics Quaterly. 1971. -V.18. - P. 317-327.

73. Szwarc W. Single machine total tardiness problem revised // Creative and Innovate Approaches to the Science of Management, Quorum Books.- 1993. P. 407-419.

74. Szwarc W., Delia Croce F., Grosso A. Solution of the single machine total tardiness problem // Journal of Scheduling. 1999. - V.2. - P. 55-71.

75. Szwarc W., Grosso A., Delia Croce F. Algorithmic paradoxes of the single machine total tardiness problem // Journal of Scheduling. 2001. - V.4.- P. 93-104.

76. Szwarc W.; Mikhopadhyay S. Decomposition of the single machine total tardiness problem //Oper. Res. Lett. 1996. - V.19. - P. 243-250.

77. Tansel B.C., Sabuncuoglu I. New insights on the single machine total tardiness problem // Operations Research Letters. 1997. - V.48. - P. 82-89.

78. Tansel B.C., Kara B.Y., Sabuncuoglu I. An efficient algorithm for the single machine total tardiness problem // IIE Transactions. 2001. -V.33. - P. 661-674.

79. Wilkerson L.J., Irvine J.D. An improved algorithm for scheduling independent tasks // AIIE Transactions. 1971. - V.3. - P. 239-245.