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

Введение

1 Свойства оптимальных расписаний задачи минимизации максимального временного смещения

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

1.2 Свойства оптимальных расписаний общего случая задачи

1.3 Свойства оптимальных расписаний частных случаев задачи 1| r3\Lmaz

2 Эффективные алгоритмы решения задачи минимизации максимального временного смещения

2.1 Процедура построения приближенного расписания для задачи 1|r.[ < Tj,di > dj\Lmax. Оценка абсолютной погрешности

2.2 Процедура построения допустимого расписания для задачи 1 < rj,di > dj\Lmax.

2.3 Алгоритм решения задачи 1|гг < rj,dt > dj\Lmax

2.4 Полиномиальные алгоритмы решения частных случаев задачи 1|г.; < rj,di > dj\Lmax.

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

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

Первые публикации по решению задач теории расписаний появились в начале 1950 - х годов [73], [98]. Следует отметить, что уже на начальной стадии развития теории расписаний стало ясно, что задачи оптимального упорядочения трудоемки. Для их решения привлекались известные результаты прикладной математики, а также разрабатывались новые подходы и методы. Значительная часть результатов в области теории расписаний касается выявления сложности проблемы. Вопросы сложности задач теории расписаний рассматривались, например, в работах [17], [20], [56], [62].

Вследствие NP - трудности многих задач теории расписаний специалистами в этой области уделялось внимание разработке приближенных методов решения, а также построению алгоритмов для частных случаев задач. Предложены разнообразные приближенные методы, основанные на различных эвристических соображениях, В. К. Леонтьевым [35] для болыперазмерных задач, Ньюджентом [90] для задач небольшой размерности. М. Я. Ковалевым [23] разработаны £ - приближенные эффективные алгоритмы решения некоторых задач теории расписаний. Достаточно полное описание методов решения задач упорядочения содержится в обзорных статьях В. Н. Буркова, С. Е. Ловецкого [3, 4], В. Я. Бурдюка, В. В. Шкурбы [2], Е. Лоулера, Я. Ленстры, А. Ринной Кана, Д. Шмойса [81], Р. Грэхема, Е. Лоулера, Я. Ленстры, А. Ринной Кана [69], в книгах В. С. Танаева, В. С. Гордона, Я. М. Шафранско-го [42] и В. С. Танаева, Ю. Н. Сотскова, В. А. Струсевича [43].

Интерпретация задач теории расписаний в терминах смешанных графов проведена в работах Л. П. Матюшкова и В. С. Танаева [37], Е. Ба-лаша [52], Б. Сассмана [100]. Применению матричных методов к решению этих вопросов посвящена работа [91]. Цикл работ по минимизации линейных форм на различных подмножествах множества перестановок проведен Д. А. Супруненко, В. С. Айзенштатом, Н. А. Лепешинским, И. М. Кунцевичем, Д. Н. Кравчуком, Н. Н. Метельским. Обзор этих работ приведен в [40]. Систематическое исследование функций, рекку-рентно заданных на множестве перестановок, проведено Г. М. Левиным и В. С. Танаевым [34, 44]. Алгоритмы оптимальной машинной реализации подстановок предложены Ю. В. Голунковым [9, 10, 11]. Формулировка и исследование общей задачи теории расписаний, как задачи целочисленного программирования, были приведены Боуманом [53], Вагнером [101], Манне [85]. Результат применения метода целочисленного программирования для задачи конвейерного типа был опубликован в работах Стори и Вагнера [99], Гиглио и Вагнера [70]. Использование метода ветвей и границ в решении задач теории расписаний предложили Брукс и Уайт [55]. Различные схемы организации процесса ветвления для решения многостадийных задач на быстродействие рассматривались в [39, 50, 52, 55, 59, 60, 66, 89]. Для вычисления оценки снизу оптимального значения целевой функции в [54] было предложено использовать решение задачи минимизации максимального временного смещения для одного прибора. В [76] было отмечено, что болыниство известных оценок снизу значения целевой функции оптимального расписания для многостадийных задач на быстродействие получены в результате решения задачи минимизации максимального временного смещения для одного прибора.

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

В диссертационной работе исследуются NP - трудные задачи теории расписаний для одного прибора — задача минимизации максимального временного смещения и задача минимизации суммарного запаздывания. Для этих задач получены новые свойства оптимальных расписаний и предлагаются приближенные и точные алгоритмы решения. Основная часть полученных результатов относится к первой задаче. Результаты, изложенные в диссертации, опубликованы в работах [1], [28] - [31], [47] - [49], [83], [93], [94].

Задача минимизации максимального временного смещения для одного прибора при запрещении прерываний процесса обслуживания требований является NP - трудной в сильном смысле [17, 84]. Это означает, что не существует псевдополиномиального алгоритма решения задачи в предположении, что классы Р и NP не совпадают. Известен NP -трудный частный случай задачи [42], для которого в диссертационной работе предлагается псевдополиномиальный алгоритм решения. Обзор методов решения задачи минимизации максимального временного смещения для одного прибора приведен в [42, 75, 84, 86]. При разрешении прерываний в обслуживании требований задача разрешима за полиномиальное время [32, 72, 75]. Алгоритмы трудоемкости 0(п log п) решения задачи в случае одновременно поступающих требований и одинаковых директивных сроков были предложены Д. Джексоном [73] и Б. Лаге-вегом, Я. Ленстрой и А. Ринной Каном [75]. При частично упорядоченном множестве требований и их одновременном поступлении решение было получено Е. Лоулером и Д. Муром [79, 82]. В. Хорн [72] получил решение задачи в случае единичных продолжительностей обслуживания требований обобщенным алгоритмом Джексона, а Фредериксон [67] предложил алгоритм решения этого случая трудоемкости 0(п) операций. В [97] получено решение этой задачи в случае одинаковых продолжительностей обслуживания требований. А. А. Лазаревым [25, 26] были предложены подходы к построению приближенных алгоритмов решения задачи и получении оценки абсолютной погрешности оптимального значения целевой функции, основанные на применении алгоритмов решения частных случаев. Частные случаи задачи рассмотрены в работах [32, 25, 28, 29, 31, 47, 49, 83, 72, 75]

Вопросы построения допустимых расписаний, при которых максимальный штраф не превышает заданной величины и разрешены прерывания в обслуживании требований, исследовались в [5, 14, 24]. В случае одинаковых продолжительностей обслуживания требований допустимое относительно заданного значения максимального временного смещения расписание, являющееся оптимальным по быстродействию среди всех допустимых расписаний, может быть построено за O(nlogn) операций [68]. Результаты по построению допустимых относительно директивных сроков расписаний получены в [5, 6, 16, 92].

В. С. Гордон [12, 13] предложил алгоритм решения задачи минимизации максимального штрафа при разрешении прерываний. Алгоритм сложности 0{п2) решения этой задачи для частично упорядоченного множества требований разработан B.C. Гордоном и В. С. Танаевым [16] (см. также [33, 51]). В случае одновременного поступления требований и наличия отношений предшествования решение может быть найдено за число операций, не превышающее 0(п2) [79]. В [87] задача минимизации максимального штрафа рассматривается в предположении, что продолжительности обслуживания требований могут быть отрицательными, а в [77, 96] - в предположении, что штраф назначается как за отклонение от директивных сроков, так и за начало обслуживания требований ранее моментов поступления. Двухкритериальные задачи с критериями на быстродействие и минимизацию максимального временного смещения исследовались в [45, 46].

NP - трудность задачи минимизации суммарного запаздывания для одного прибора в случае одновременного поступления требований была установлена Я. Ду и Я. Ленгом [62]. Е. Лоулером [80] для решения этой задачи в предположении, что продолжительности обслуживания р-п j = 1 , п, - целые положительные числа, построены псевдополиномил. 71 альный алгоритм трудоемкости 0(п Е Pj), основанный на идее метоj=i да динамического программирования, а также вполне полиномиальный алгоритм с оценкой сложности 0(п7/е). М. Я. Ковалеву [74] удалось на порядок понизить эти оценки. Простые методы решения задачи были предложены В. Хорном [72]. В [63, 64] для решения задачи минимизации суммарного запаздывания был применен метод множителей Лагранжа.

В случае единичных продолжительностей и одновременном поступлении требований задача минимизации суммарного штрафа была сведена Е. Лоулером [78] к задаче о назначении, которую можно решить за 0(п3) операций [18]. Применению метода динамического программирования для решения задачи минимизации суммарного штрафа посвящены работы [7, 36, 38, 58, 71], а использованию методов последовательного анализа вариантов — работы [21, 41, 57, 61, 65, 88, 95]. Задача минимизации суммарного штрафа при дополнительном условии обслуживания требований без нарушения директивных сроков рассмотрена в [8, 15, 19].

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

Работа состоит из введения, трех глав, заключения и списка литературы.

В первой главе предлагаются новые свойства оптимальных расписаний задачи минимизации максимального временного смещения. Свойства для общего случая можно разделить на три группы. Первая группа свойств дает возможность определять требования, на которых достигается значение целевой функции любого расписания, в том числе и оптимального [31, 47]. Установлено, что при любом расписании 7г £ U(N,t), где П(ЛГ, t) - множество всех расписаний обслуживания требований множества N с момента времени £, значение целевой функции F{7г) = Lj(7r) - временное смещение требования j, достигается на определенных требованиях, следующих после требования с минимальным директивным сроком jdmt1,(N)

Вторая группа свойств устанавливает существование оптимального расписания с определенным порядком следования специальным образом выбранных требований. Доказано, что существует оптимальное расписание, при котором требования с не меньшим моментом поступления, чем у требования jd„liu{N), следуют после jdmin(N).

Третья группа свойств описывает порядок обслуживания требований в частичных расписаниях, из которых состоит оптимальное [28, 31, 47]. Показано, что найдутся такие подмножества TV1, А7"2 С TV, что будет оптимальным расписание, при котором требования, предшествующие требованию j(imi„(Ar), упорядочены по неубыванию моментов поступления, а следующие за ним - оптимальным образом. Далее доказывается, что найдутся такие целое число га, подмножества 7V1,., Nm С N, и требования что будет оптимальным расписание (7г*, j,*, .,7г"\ j'/'), где 7г?'., i = 1, .,m, — расписание обслуживания требований множества

N\ составленное в порядке неубывания моментов поступления. Доказано, что добавление к исходному множеству определенных требований влечет за собой существование оптимального расписания некоторого специального вида [29, 31, 47]. Приведенные свойства используются для получения достаточных условий построения оптимального расписания, а также для получения свойств оптимальных расписаний частных случаев задачи.

Далее, в первой главе предлагается схема решения общей задачи минимизации максимального временного смещения при предположении, что для любого подмножества N' исходного множества известна процедура отыскания множества N* С N', состоящего из требований, обслуживаемых в оптимальном расписании после jdmin(N) и имеющих меньший момент поступления, чем у требования jdmin{N). Трудоемкость этой схемы составляет 0(п2 + пх) операций, где О(х) - трудоемкость отыскания N*. Приводятся примеры построения подмножеств N*.

На основе свойств оптимальных расписаний общего случая задачи получены свойства оптимальных расписаний для случая, когда на параметры требований накладываются ограничения riKrj^diZdjViJCN, (1) где dj - директивный срок требования j, rj - момент поступления требования j [47]. В работе ([42], с. 293) показана NP - трудность задачи 1|г(; < rndi > dj\Lmax путем полиномиального сведения известной NP - полной задачи о разбиении к соответствующей ей задаче распознавания. В диссертационной работе для задачи 1|тг < r-n dt > dj\Lmax доказано, что существует оптимальное расписание, при котором требование с минимальным моментом поступления обслуживается на первом либо на последнем месте. В конце главы предлагаются свойства оптимальных расписаний частных случаев задачи 1|г* < rj,di > dj\LmaX [31, 29, 83], которые во второй главе используются для обоснования точных алгоритмов их решения.

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

Для задачи 1|г; < г, dt > d.j\Lmax предлагаются и обосновываются псевдополиномиальные процедура /iy [47, 49] построения приближенного расписания 7r/t0 и процедура h [48, 93] построения допустимого расписания 7T/t, а также псевдополиномиальный алгоритм построения оптимального расписания [47, 94].

Значение целевой функции расписания 7Г/1о отличается от оптимального значения не более, чем на величину pmax{N) максимальной продолжительности обслуживания требований. Кроме того, момент завершения обслуживания всех требований расписания 7г^0 отличается от момента завершения обслуживания всех требований расписания, оптимального по быстродействию, также не более, чем на ртаX(N). Процедура ho состоит из п итераций. Внутри итерации для каждого целочисленного момента времени, число которых не превосходит Р, где Р — max{rmux(N),t} + £ - тах{rmm(N), £}, rmax(N) = max г-, rmm (N) =

7 = 1 j<EN minr.;-, следующее приближенное расписание получается добавлением j&N ' требования из множества неупорядоченных с максимальным моментом поступления и минимальным директивным сроком к уже построенному расписанию. Трудоемкость процедуры ho составляет 0(п2Р) операций.

Процедура h строит расписание со значением целевой функции, не превышающим заданного вещественного числа у либо устанавливает, что такого расписания не существует. Процедура состоит из п итераций. Внутри итерации для каждого целочисленного момента времени, количество которых не превосходит Р, строится допустимое расписание путем добавления к уже построенному требования из множества неупорядоченных с максимальным моментом поступления и минимальным директивным сроком. Построеннное этой процедурой расписание 7T/J является оптимальным по быстродействию среди всех расписаний допустимых относительно значения у. Если процедурой h построено непустое расписание, то Т(тг)1) = min{T(7r)|7r £ n(iV, t), F(ir) < у}, где Т(тт) - момент завершения обслуживания всех требований расписания 7г. В противном случае F(ж) > у для всех 7г £ П(N,t). Трудоемкость процедуры h составляет 0(nlogn + пР) операций.

Процедуры /iy и h используются в алгоритме решения задачи 1|г« rjidt > dj\Lmax. Идея алгоритма заключается в следующем. В качестве начального значения у выбирается значение целевой функции расписания, построенного процедурой кц. Далее, уменьшая значение у на единицу, не более, чем за pma.x{N) применений процедуры h, получаем оптимальное расписание. Трудоемкость алгоритма -0(п2Р + npmax(N)P) операций.

Для частных случаев задачи 1|г; < r.j,di > dj\Lmax построены алгоритмы решения трудоемкости, не превышающей 0(п2) операций [29,

31].

Отметим, что приведенные алгоритмы дают также способ построения N* в общей схеме, описанной выше.

Для общего случая задачи минимизации максимального временного смещения предлагается следующий приближенный алгоритм трудоемкости 0(п2Р + npmax(N)P) операций [47]. Директивные сроки требований изменяются так, чтобы новые параметры требований удовлетворяли ограничениям (1), и для этой задачи строится оптимальное расписание. Полученное расписание является приближенным расписанием для исходной задачи с минимальным значением границы абсолютной погрешности оптимального значения целевой функции на множестве оптимальных расписаний частного случая (1). Минимизация значения границы абсолютной погрешности обеспечивается алгоритмом изменения директивных сроков. Аналогичный подход для построения приближенных алгоритмов решения общей задачи с использованием алгоритмов решения других частных случаев был предложен в работе ([25], с. 36).

В третьей главе исследуется NP - трудная задача [62] теории расписаний для одного прибора — задача минимизации суммарного запаздывания. Описываются свойства задачи. Выделен [1] полиномиально разрешимый частный случай задачи, когда на параметры требований накладываются ограничения

Рг < Pj Рг + d, < Pj + d3 V ij j. (2)

Предлагаются новые свойства оптимальных расписаний для случая (2) и полиномиальный алгоритм построения оптимального расписания на множестве допустимых (см. [27]) расписаний. Для случая (2) доказаны новые свойства допустимых расписаний, касающиеся порядка следования определенных требований в оптимальном расписании, а также условия существования оптимального расписания с некоторыми свойствами. На основе этих свойств разработан алгоритм решения задачи

15 при условиях (2), который заключается в следующем. На первом этапе по определенному правилу исходное множество требований разбивается

Г) не более, чем на п подмножеств. На втором этапе алгоритма строятся оптимальные расписания для всех полученных на первом этапе множеств, в том числе и исходного. Трудоемкость алгоритма составляет 0(п3) операций.

Автор выражает благодарность научному руководителю доценту А. А. Лазареву, а также сотрудникам кафедры экономической кибернетики Казанского государственного университета за полезное обсуждение результатов.

Заключение

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

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

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

3. Для NP - трудного частного случая 1|г.; < rj,di > dj\Lmax предложены и обоснованы процедура h$ построения приближенного расписания с величиной абсолютной погрешности оптимального значения целевой функции, не превышающей величины максимальной продолжительности обслуживания требований, и процедура /г,, которая строит допустимое расписание со значением целевой функции, не превосходящим заданного числа у, либо устанавливает отсутствие допустимого относительно у расписания. Трудоемкость процедур ho и h. составляет 0(п2Р) и 0(nlogn + пР) операций соответственно.

4. Разработан и обоснован алгоритм трудоемкости О (п2Р+пртах(N)P) операций для решения NP - трудного частного случая 1 < г3, d.L > dj\Lmax'

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

6. Для задачи минимизации максимального временного смещения разработан и обоснован псевдополиномиальный алгоритм построения приближенного расписания с минимальным значением границы абсолютной погрешности оптимального значения целевой функции на множестве оптимальных расписаний NP - трудного частного случая. Трудоемкость алгоритма - 0(п2Р + npmax(N)P) операций.

7. Для задачи минимизации суммарного запаздывания найден новый полиномиально разрешимый частный случай, разработан и обоснован алгоритм построения оптимального расписания для этого случая трудоемкости 0(п3) операций.

1. Беркута О. Н., Лазарев А. А. Алгоритм сложности 0(п3) решения задачи минимизации суммарного запаздывания// Иссл. по прикл. мат.- Выпуск 22.- Казань, 1995.- С. 67 78.

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

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

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

5. Визит В. Г. О расписаниях , соблюдающих директивные сроки выполнения работ// Кибернетика.- 1981- N 1.- С. 128 135.

6. Визит В. Г., Клипкер И. А. Полиномиальный алгоритм решения задачи Гэри Джонсона о составлении расписания// Сообщ. АН Груз. ССР.- 1981,- N 1.- С. 29 - 32.

7. Власюк Б. А. Задача оптимального расписания при наличии переналадок// Экономика и матем. методы,- 1967 N 3 - С. 79 - 84.

8. Гик Е. Я., Левнер Е. В. Решение некоторых задач календарного планирования для одного станка// В кн.: Вопросы матем. теории управл. систем и ее применнен. в металлургии.- 1974.- С. 22 25.

9. Голунков Ю. В. О сложности представления подстановок симметрической полугруппы через элементы систем образующих// Журн. Кибернетика.- 1971.- N 1- С. 43 44.

10. Голунков Ю. В. Программно-автоматная реализация подстановок симметрической полугруппы. Часть 1// Журн. Кибернетика.-1971.- N 5.- С. 5 12.

11. Голунков Ю. В. Программно-автоматная реализация подстановок симметрической полугруппы. Часть 2// Журн. Кибернетика.-1975.- N 5.- С. 35 42.

12. Гордон В. С. Об оптимальных расписаниях с прерываниями процесса обслуживания// Изв. АН БССР. Сер. физ.- матем. н.- 1974.-N 5.- С. 129 130.

13. Гордон В. С. Детерминированная система обслуживания с минимаксным критерием оптимальности и частично упорядоченным множеством требований// Автоматиз. техн. подготовки пр-ва.-1977.- N 4.- С. 70 75.

14. Гордон В. С. Детерминированные одностадийные системы обслуживания с прерываниями// В кн.: Вычислит, техн. в машиностроении.- Минск.- 1973.- С. 30 38.

15. Гордон В. С. Допустимые относительно директивных сроков расписания с наименьшим суммарным штрафом// Труды 8-го Болг.

16. Польск. симпозиума "Оптимизация, принятие решений, микропроцессорные системы", 17 21 октября 1983 г.- София.- С. 153 - 156.

17. Гордон В. С., Танаев В. С. О минимаксных задачах теории расписаний с одним прибором// Изв. АН БССР. Сер. физ.- матем-1983.- N 3.- С. 3 9.

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

19. Диниц Е. А., Кронрод М. А. Один алгоритм решения задачи о назначении// ДАН СССР 189.- 1969.- N 1,- С. 23 25.

20. Зиндер Я. А. Об алгоритмах решения некоторых задач упорядочения/ / В кн.: Алгоритмы и программы Горький, 1977.- вып 1.- С. 114 - 123.

21. Карп Р. М. Сводимость комбинаторных проблем// В кн.: Кибер-нет. сб.- М.: Мир, 1975.- Вып. 12.- С. 16 38.

22. Китик М. Г. К вопросу "сужения" ветвления в задаче одного станка// Кибернетика,- 1972.- N 1.- С. 145 147.

23. Кнут Д. Искусство программирования для ЭВМ. т. 3: Сортировка и поиск,- М.: Мир,- 1973.- 348 с.

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

25. Копылов Г. Н. Точное решение задачи одного станка// Весн. Яро-славск. ун-та, 1975,- Вып. 9 С. 52 - 60.

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

27. Лазарев А. А. Исследование задач теории расписаний с помощью преобразований// Иссл. по прикл. мат.- Вып. 12.- Казань, 1984-С. 63 74.

28. Лазарев А. А. Алгоритм решения задачи минимизации максимального временного смещения для одного прибора// Иссл. операций и оптимальное упр.- Деп в ВИНИТИ N 3795 85ДЕП - С. 21 - 30.

29. Лазарев А. А., Шульгина О. Н. К решению задачи планирования производственно-экономической деятельности предприятия// Иссл. по прикл. мат.- Выпуск 21.- Казань, 1999.- С. 155 169.

30. Лазарев А. А., Шульгина О. Н. Полиномиально разрешимые частные случаи задачи минимизации максимального временного смещения/ / Ред. Журн. "Изв. Вузов. Математика".- Казан, ун-т.- Казань, 2000.- 11 е.- Библ. 8 назв.- Деп в ВИНИТИ 28.11.00, N 3019-В00.

31. Лебединская Н. Б. Минимизация максимального отклонения в случае прерывания работ// Зап. науч. семинаров. Ленингр. отд. Матем. ин-та АН СССР, 1978.- С. 117 124.

32. Лебединская Н. Б. Минимизация максимального штрафа в случае прерывания работ// Зап. науч. семинаров. Ленингр. отд. Матем. ин-та АН СССР, 1980.- С. 61 67.

33. Левин Г. М., Танаев В. С. Об одном классе комбинаторных задач оптимизации// Изв. АН БССР, сер. физ.- мат. наук.- 1968.- С 30 -35.

34. Леонтьев В. К. Построение на заданном множестве точек гамиль-тонова цикла, близкого по длине к найкратчайшему// Сб. "Акту-альн. вопр. техн. кибернетики".- М: "Наука".- 1972.- С. 244 248.

35. Лобановский Н. М. Об оптимальном планировании последовательности выполнения работ на одной или двух машинах// Сб "Кибернетика и управление".- М.: Наука, 1967.- С. 85 92.

36. Матюшков Л. П., Танаев В. С. Программные генераторы допустимых расписаний// Сб. "Вычислительная техника в машиностроении".- Минск, 1967.- С. 35 48.

37. Прокофьев О. Н. Выбор оптимальной очередности обслуживания// Изв. АН СССР, Техн. кибернетика,- 1972,- С. 104 107.

38. Сотсков Ю. Н. Оптимальное расписание множества работ заданное смешанным графом// Изв. АН БССР. Сер. физ.- мат. наук.-1977.- N 47,- С. 133.

39. Супруненко Д. А., Айзенштат В. С., Лепешинский Н. А. Экстремальные значения функций на множествах перестановок// Тезисы докл. 1 Всес. конф. по исслед. операций.- Минск, 1972.- С. 61 64.

40. Танаев В. С. Некоторые оптимизируемые функции одностадийного производства// ДАН БССР 9.- 1965.- N 1.- С. 11 14.

41. Танаев В. С., Гордон В. С., Шафранский Я. М. Теория расписаний. Одностадийные системы.- М.: Наука. Главная редакция физико-математической литературы, 1984,- 384 с.

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

43. Танаев В. С., Левин Г. М. Об оптимальном поведении систем с частично ограниченной памятью// Изв. АН БССР, сер. физ.- мат. наук.- 1967.- N 3.- С. 82 88.

44. Тузиков А. В. Об одном классе векторной оптимизации на перестановках/ / В кн.: Алгоритмы и программы решения экстремальных задач и смежные вопросы,- Минск, 1982.- С. 62 70.

45. Тузиков А. В. О двухкритериальных задачах теории расписаний/ / Оптимизация, принятие решений, микропроцессорные системы. Труды 8-й Болг,- Польск. симпозиума, 17 21 окт. 1983 г.София,- С. 163 - 168.

46. Шульгина О. Н. Исследование задачи минимизации максимального временного смещения для одного прибора// Казан, ун-т.- Казань, 2000.- 21 е.- Библ. 3 назв.- Деп в ВИНИТИ 28.06.00, N 1809-В00.

47. Шульгина О. Н. Построение допустимого расписания относительно заданной оценки значения целевой функции// Материалы международной конференции "Дискретный анализ и исследование операций", 26 июня 1 июля - Новосибирск, 2000 - С. 179.

48. Шульгина О. Н. Алгоритм решения частного случая задачи минимизации максимального временного смещения// Тез. докл. Всероссийской науч. конф. "Алгоритмический анализ неустойчивых задач".- Екатеринбург, 26 февраля 2 марта 2001 года.- С. 316.

49. Ashour S, Hiremath S. R. A branch-and-bound approach to the job-shop scheduling problem// Int. J. Prod. Res 1973 - V. 11, N 1- P. 47 - 58.

50. Baker K. R., Lawler E. L., Lenstra J. K., Rinnoy Kan A. N. G. Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints// Oper. Res.-1983.- n 2.- P. 381 386.

51. В alas E. Mashine Scheduling via Disjunctive Graphs: An Implicit Enumeration Algorithm// Oper. Res.- 1969,- V. 17, N 6.- P. 941 -957.

52. Bowman E. N. The Schedule Sequencing Problem// Oper. Res. 7.1959.- N 5.

53. Bratley P., Florian M., Robillard, P. On sequencing with earliest starts and due dates with application to computing bounds for the (n\m\G\Fmux) problem// Nav. Res. Log. Quart.- 1973.- V. 20.- P. 57 67.

54. Brooks G. N. and White C. R. An Algorithm for Finding Optimal or Near Optimal Solutions to the Production Scheduling Problem// J. Ind. Eng. 16.- 1965.-V 16, N 1.- P. 34 - 40.

55. 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.

56. Burstall R. M. A heuristic method for a jobscheduling problem// Oper. Res. Quart. 17.- 1966.- N 3 P. 291 - 304.

57. Buzacott J. A., Dutta S. K. Sequencing many jobs on a multipurpose facility// Nav. Res. Log. Quart. 18.- 1971.- N 1- P. 75 82.

58. Charlton J. M., Death С. C. A method of solution for general machine scheduling problems// Oper. Res.- 1970.- V. 18, N 4.- P. 689 707.

59. Carlier J. The one machine sequencing problem// Eur. J. Oper. Res.-1982,- V. 11, N 1,- P. 42 - 47.

60. Dessouky M. I., Margenthaler C. R. The one machine sequencing problem with early starts and dates// AIIE Trans 4.- 1972 - N 3.- P. 214 - 222.

61. Du J., Leung J. Y-T. Minimizing total tardiness on one machine is NP-hard// Math. Oper. Res. 15,- 1990.- P. 483 495.

62. Fisher M. L. Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part 1// Oper. Res.- 1973,- V. 21, N 5.- P. 1114 1127.

63. Fisher M. L. A dual algorithm for the one machine scheduling problem// Mathem. Program.- 1976.- N 11- P. 229 - 251.

64. Elmagraby S. E. The one machine sequencing problem with delay costs// J. Industr. Engng 19.- 1968 N 2.- P. 105 - 108.

65. Florian M., Trepart P., McMahon G. An implicit enumeration algorithm for the machine sequencing problem// Manag. Sci.(B).-1971.- V. 17, N 12.- P. 782 792.

66. Frederickson G. N. Sheduling unit-time tasks with integer release times and deadlines// Inform. Process. Lett. 16.- 1983.- P. 171 173.

67. Garey M. R., Jonson D. S., Simons В. В., Tarjan R. E. Scheduling unite time tasks with arbitrary release times and deadline// SI AM J. Comput.- 1981.- V. 10, N 2.- P.256 - 269.

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

69. GigUo R. J. and Wagner H. M. Approximate Solutions to the Three -Machine Scheduling Problem// Oper. Res. 12,- 1964,- N 2.

70. Held M., Karp R. M. A dynamic programming approach to sequencing problem// J. Soc. Industr. and Appl. Math. 10.- 1962.- N 1.- P. 196 210.

71. Horn W. A. Some simple scheduling algorithms// Nav. Res. Log. Quart. 21 1974,- N 1.- P. 177 - 185.

72. Jackson J. R. Scheduling a production line to minimize maximum tardiness// Res. Report 43, Manag. Sci. Res Project, USLA, Jan, 1955.

73. Kovalev M. Y. One one machine scheduling to minimize the namber of late items and the total tardiness// Minsk, 1991.(Preprint// Institute of Enginering Cybernetics of the BSSR Academy of Sciences, N4)

74. Lageweg B. JLenstra J. K., Rinnooy Kan A. H. G. Minimizing maximum lateness on one machine: computational experience and some applications// Statist, neer.- 1976.- N 1- P. 25 41.

75. Lageweg B. J., Lenstra J. K., Rinnooy Kan A. H. G. Job shop scheduling by implicit enumeration// Manag. Sci.- 1977.- V. 24, N 4.- P. 441 - 450.

76. Lakshminarayan S., Lakshmanan R., Papineau R. L, Rochette R. Optimal single machine scheduling with earliness and tardiness penalties// Oper. Res.- 1978.- V. 26, N 6.- P. 1079 - 1082.

77. Lawler E. R. On scheduling problems with deferral costs// Manag. Sci.- 1964.- V. 11, N 2.- P. 280 288.

78. Lawler E. R. Optimal sequencing of a single machine subject to precedence constraints// Manag. Sci.- 1973.- V. 19, N 5.- P. 544 -546.

79. Lawler E. R. A "pseudopolynomial" algorithm for sequencing jobs to minimize total tardiness// Ann. Discrete Math.- 1977.- N 1.- P. 331 342.

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

81. Lawler E. R., Moore J. M. A functional eguation and its application to resource allocation and sequencing problems// Manag. Sci.- 1969.-V. 16, N 1.- P. 77 84.

82. Lazarev A., Schul'gina 0. Problem minimizing maximum lateness for single machine: properties, procedures, algorithms// 9-th Belgian-French-German Conference on Optimization, Namur, September 7-11.-Namur, 1998.- P. 45.

83. Lenstra J. K., Rinnooy Kan A. H. G., Bruker P. Complexity of machine scheduling problems// Ann. Descrete Math.- 1977.- N 1.-P. 343 362.

84. Manne A. S. On the Job Shop Scheduling Problem// Oper. Res.-1960.- V. 8, N 2.

85. McMahon G. В., Florian M. On sequencing with ready times and due dates to minimize maximum lateness// Oper. Res.- 1975.- V. 23.- P. 475 482.

86. Monma C. L. Sequencing to minimize the maximum job cost// Oper. Res.- 1980.- V. 28, N 4,- P. 942 951.

87. Nabeshima I. Unified treatment on single machine schedulig problems// Repts. Univ. Electro Communs.-1971.- V. 22, N 2.- P. 29 - 38.

88. Nabeshima I. General scheduling algorithms with applications to parallel scheduling and multiprogramming scheduling// J. Oper. Res. Soc. Japan.- 1971.- V. 14, N 2,- P. 72 99.

89. Nugent С. E. On Sampling Approaches to the Solution of the n by- m Static Sequencing Problem// Ph. D. thesis, Cornell University. -1964.

90. Okamura K., Yamashina H. Eastablishment of linear sequences// Mem. Fas. Engng. Kyorto Univ. 31.- 1969.- N 3.- P. 307 331.

91. Schindler S. Sheduling general monitor systems// In Proc. 9-th Haw. Int. Conf. Syst. Sci. Honolulu.- 1976.- P. 122 124.

92. SchuVgina Oksana N. Construction of feasible schedule with designated evaluation of criterion function// French- German- Italian Conference on Optimization, Montpellier, September 04-08-2000.- P. 61.

93. SchuVgina Oksana Pseudopolynomial algoritm for the problem of minimizing maximum lateness// Scan2000, Karlsruhe, September 19- 22, 2000.

94. Shwimer J. On the n-job, one-machine, sequence-indepent scheduling problem with tardiness penalties. A branch-bound solution// Manag. Sci.- 1979.- V. 18, N 6.- P. 301 313.

95. Sidney J. B. Optimal singlemachine scheduling with earlines and tardiness penalties// Oper. Res.- 1977,- V. 25, N 1.- P. 62 - 69.

96. Simons B. A. A fast algorithm for single processor scheduling// In: 19th Annu. Symp. Found. Comput. Sci., Ann. Arbor, Mich.- New York, 1978.- P. 246 252.

97. Smith W. E. Various optimizers for single stage production// Nav. Res. Log. Quart.- 1956.- V. 3, N 1.- P. 59 66.

98. Story A. E. and Wagner H. M. Computational Experience with Integer Programming for Job Shop Scheduling// Industrial Scheduling, J. E.103

99. Muth and G. L. Thompson eds. Englewood Cliffs, N. J., Prentice -Hall.- 1963.- Ch. 14.

100. Sussmann B. Scheduling problems with interval disjunctions// Z. Operat. Res. Ser. A16.- 1972.- N 5.- P. 165 178.

101. Wagner H. M. An Integer Linear Programming Model for Machine Scheduling// Nav. Res. Log. Quart.- 1959.- V. 6, N 2.