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

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

САДЫКОВ Руслан Равильевич

АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ ДЛЯ ОДНОГО ПРИБОРА С КРИТЕРИЯМИ IИ 5>/0

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

АВТОРЕФЕРАТ

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

Москва 2006

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

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

наук, доцент А. А. Лазарев

Официальные оппоненты: доктор технических наук, профессор И. X. Сигал,

кандидат физико-математических наук, в.н.с. Я. М. Шафран скип

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

0 та г, в

зета Д.002.017.02 при Вычислите?;

Защита диссертации состоится в ' часов

на заседании диссертационного совета Д.002.017.02 при Вычислительном Центре имени A.A. Дородницина Российской академии наук (119991, г. Москва, ул. Вавилова, 40, конф.зал).

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

' l/>JIK-tllW.VJЦ 1 LJWI О KJKlVJlMVi.^

г.

Учены П секретарь // jgrfj

диссертационного совета, д.ф.-м.и. " Cs В. В. Рязанов

Общая характеристика работы Актуальность темы

Диссертационная работа посвящена исследованию классических задач теории расписаний для одного прибора.

* Теория расписаний берет свое начало в 50-е годы 20-го века с par бот Джексона1 и Джонсона2. В связи с бурным развитием автоматизации производства данное направление прикладной математики приобре-

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

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

Рассмотрим постановку одноприборной задачи теории расписаний. Множество требований N = {1,2,... ,п} должно быть обслужено без прерываний на одном приборе, который может обслуживать не более одного требования в каждый момент времени. Время обслуживания требования j € N обозначается как pj. Момент, когда требование j становится доступным для обслуживания, задается временем поступления rj. Требование j также может иметь директивный срок dj (время, до которого желательно завершить обслуживание требования), вес wj (значимость требования).

В любой приборной задаче теории расписаний целью является построение оптимального расписания по определенному критерию. Для представления различных критериев нам необходимы следующие определения. Времена начала и окончания обслуживания требования j в рас, писанин 7г обозначаются как, соответственно, Sj(7r) и сДтг). Определим ¿Дтг) = Cj(tt) — dj как временное смещение требования j в расписании тг, a Tj(n) — как его запаздывание. Uj(ir) обозначает запаздывает

t 1jAcksou J.R. Scheduling & production line ta minimize maximum tardiness// Los Angeles, CA:

University of California, 1955.- Manag. Sei, Res. Project. Research Report N 43.

3Johnson S.M. Optimal two- Uixj three-stage production schedules with setup times included// Naval Res. Logistics Qua!.- 1954- V. 1. P. 61-68.

ли требование j в расписании тг или нет. Uj{ir) = 1 если j запаздывает (Cj(tt) > dj), иначе Уу(тг) = 0 (требование j обслуживается вовремя).

Классическими критериями в приборных задачах теории расписаний являются: CmiBt — минимизация максимального времени окончания обслуживания, Lxt&x — минимизация максимального временного смещения, — минимизация (взвешенного) суммарного времени окончания обслуживания, — минимизация (взвешенного) суммарного за-

паздывания, 2(tt>j)tfj — минимизация (взвешенного) числа запаздывающих требований.

Заметим, что классические критерии являются регулярными, то есть данные функции являются неубывающими по отношений к временам обслуживания требований. При наличии регулярного критерия мы можем ограничиться рассмотрением только ранних расписаний. Каждое раннее расписание я> однозначно определяется перестановкой т требований множества N. Если т = (ju ..., ja), тогда яу = (s^.Sj,,... ,sja), где

sji = *V„ Sj, = maxfi,,., +Pjt_„rh}, к ... ,n.

Множество всевозможных расписаний обслуживания требований множества JV обозначается как П(ЛГ).

В работе Грэхэма и др.® была введена классификация для приборных задач теории расписаний. В данной классификации каждой задаче соответствует обозначение а | ¡3 | 7, где а обозначает число и тип доступных приборов, jв описывает дополнительные ограничения задачи (например, обозначение г,- указывает на наличие неодинаковых времен поступления требований), 7 представляет собой критерий задачи.

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

^Grah&m R.L., Lawler E.L., Lenstra J К , Rinnooy Kan A.H.G. Optimisation and approximation in deterministic sequencing end icheduling: a survey// Ann. Discrete Math.- 1979,- V, 5.- P. 287 - 326.

Многие задачи теории расписаний являются JVP-трудными4. Для решения таких задач существуют три основных класса алгоритмов: эвристические, приближенные и алгоритмы сокращения перебора. Эвристические алгоритмы позволяют получить "хорошее"решение за небольшое время, однако они не могут дать оценок качества полученного решения. Приближенные алгоритмы5 гарантируют оценку качества полученного решения (погрешность), которое будет ими найдено за полиномиальное время. Приближенные алгоритмы для задач теории расписании разработаны, например, в работах Ковалева®, Севастьянова7. Однако, во многих случаях гарантируемая погрешность не является достаточной. Более того, для некоторых ^VP-трудных задач вообще нельзя постоить приближенные алгоритмы. Алгоритмы сокращения перебора используются для оптимального решения NP-трудной задачи. Однако, получение оптимального решения может занять длительное время. Поэтому, если за некоторое приемлемое время оптимальное решение не было найдено, исполнение алгоритма прекращается. В этом случае пользователю доступно некоторое приближенное решекие задачи и оценка его качества. Подчеркнем, что оценка полученного решения здесь известна после решения, тогда как при использовании приближенного алгоритма оценка качества известна до начала решения. Обычно, алгоритм сокращения перебора дат ет лучшее решение поставленной задачи, чем приближенный алгоритм, но за более длительное время. Наиболее распространенным подклассом алгоритмов сокращения перебора являются алгоритмы, построенные по методу ветвей и границ8.

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

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

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

5Корбут A.A.. Фмнкелыцтейн Ю.Ю. Прн&лнженные методы дискретного програттрования// Иэв. AK СССР. Техн. кнбернет- 1933-N 1,- С. 165- 176.

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

7Севастьянов C.B. Геометрические методы н эффективные алгоритмы в теории расписаний// Дне. док. фиа.-мат. наук.- Новосибирск: 2000.- 280 с.

'Снгач I1X , Иванова А.П. Введение в прикладное дискретное программирование// М : Фнэ-матлит, 2002,- 2 40 с.

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

Цель работы

Целью работы является разработка новых алгоритмов, как приближенных так и алгоритмов сокращения перебора, для решения двух ЛГР-трудных одноприборных задач теории расписаний: 11 г^ | Ьтах и

Методы исследования

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

Научная новизна

Результаты работы являются новыми. Основными являются следующие.

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

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

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

4. Для задачи 1 | r$ \ Lmix предложен новый точный алгоритм ветвей и границ, включающей в себя элементы существующих алгоритмов для данной задачи, а также алгоритмы метода программирования в ограничениях. Экспериментальное исследования на множестве тестовых примеров показало преимущество предложенного алгоритма над алгоритмами, существующими в литературе.

5. Для модифицированного варианта разрешимости проблемы 1 | r^ j Lmax разработан алгоритм, который определяет допустимо ли заданное множество требований и в случае недопустимости находит некоторое недопустимое подмножество. Разработанный алгоритм используется для решения задачи с критерием минимизации взвешенного

. числа запаздывающих требований.

6. Для задачи 1 | г,-1 ^ WjUj предложен точный алгоритм ветвей и отсечений. Преимущество предложенного алгоритма над наилучшим алгоритмом для данной задачи, представленном в литературе, на множестве общедоступных тестовых примеров подтверждено численными экспериментами.

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

Исследуемые в диссертации задачи являются схематичными теоретическими моделями практических задач. Однако алгоритмы для решения этих задач используются как вспомогательные для решения более сложных задач теории расписаний, более приближенных к практике. Предложенные методы также могут быть использованы для разработки алгоритмов решения других похожих теоретических задач теории расписаний. Результаты работы могут быть полезны специалистам Вычислительного центра им. A.A. Дородницина РАН, Казанского Государ-

ственного Университета, Новосибирского Государственного Университета, Омского Государственного Университета, Минского Государственного Университета.

Апробация результатов

Результаты диссертации докладывались и обсуждались на VII Международном семинаре "Дискретная математика и ее приложения" (Москва, 2001 г.), XL Международной научной студенческой конференции "Студент и научно-технический прогресс" (Москва, 2002 г.), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004 гг.), X Международной конференции по оптимизации FGI-2000 (Монтпелье, Франция, 2000 г.), I Международной конференции по интеграции методов исследования операций и искусственного интеллекта в программировании в ограничениях для решения комбинаторных задач CP-AI-OR'04 (Ницца, Франция, 2004 г.), VII Международном семинаре по методам и алгоритмам для задач календарного планирования и теории расписаний MAPSP'05 (Сиена, Италия, 2005 г.).

Публикации

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

Структура и объем работы

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

Содержание работы

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

В первой главе предлагаются полиномиальные алгоритмы приближенного решения задачи 1 | tj | ¿max- Данные алгоритмы основаны на доказанной нами теореме об абсолютной погрешности.

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

В разделе 1,3 доказывается теорема об абсолютной погрешности (Теорема 1). Для формулировки теоремы требуется следующие определение и обозначение. Пусть задан пример А на множестве требований N. Будем говорить, что пример В на том же множестве требований наследует у примера А параметр х, если xf = xf, V j € N. Будем обозначать через L!(n) максимальное временное смещение расписания тг для примера I с параметрами требований dj}.

Теорема 1 Пусть пример С наследует у примера А длительности обслуживания требований (pf = pf, j € N) и пусть жА чиР — оптимальные расписания для этих примеров. Тогда

О < ЬА(ъ€) ~ La(ka) < р(Л, С),

где р{АуС) — — (^} + тах-,-6лг{о£' — df} + тах.,6;у{г^ - rf) +•

maxie„{rf-т*}.

Заметим, что функция р(А, С) удовлетворяет свойствам псевдометрики в пространстве примеров задачи с одинаковыми временами обслуживания, и ее можно рассматривать, как расстояние между примерами А к С.

На основе Теоремы 1 в разделе 1,4 предлагается схема приближенного решения задачи. Идея схемы состоит в построении по заданному примеру А такого примера С с такими же временами обслуживания требований, который бы, во-первых, принадлежал некоторому известному полиномиально разрешимому классу примеров, и во-вторых, отличался от примера А минимальным образом (в псевдометрике р(А, С)). Применив полиномиальный алгоритм-для решения примера С, мы найдем оптимальную перестановку его требований и применим ее в качестве приближенного

решения примера А. Из теоремы 1 следует, что абсолютная погрешность полученного решения не будет превосходить р(А, С).

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

где Af = df ~ rf ~ pf обозначает временной запас требования j. Затем доказывается Теорема 2, которая дает аналитическую формулу для абсолютной погрешности р{А, С) для первого варианта схемы.

Теорема 2 Для любого примера А задачи 1 | r¿ | Lm>x, не принадлежа-гцего классу Лазарева, и для любого примера С, наследующего длительности обслуживания примера А и принадлежащего классу Лазареве?, справедлива оценка расстояния между А и С:

р(А, С) > pL{A) = max min{df - d¡\ Af - A?}. (1)

Оценка (1) достигается на некотором примере С, который может быть найден за время 0(п log п).

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

r} е [dj - Pj - ß, dj -ß\ Vj € N, ß-const.

Затем доказывается Теорема 3, которая дает аналитическую формулу для абсолютной погрешности р{А, С) для второго варианта схемы.

'Лп&рев A.A. Эффективные алгоритмы решения некоторых задач теории расписаний для одного прибора с директивными сроками обслуживания требований// Дне. канд. фвэ.-м&Т- каук,-Казань: 1939,- 10S с.

iúHoogeveen J. A. Minimizing maximum promptness and maximum lateness on a single machine// Math, Oper, Res.- 1998.- V. 2].- P. 100 - 114.

Теорема 3 Для любого примера А задачи l|rj|Lmutl не принадлежащего классу Хогевена, и для любого примера С, наследующего длительности обслуживания примера А и принадлежащего классу Хогевена, справедлива оценка расстояния между А и С:

Р(А, С) > рИ{А) = max(df - rf-pf-d? + г?}. (2)

Оценка (2) достигается «а некотором примере С, который может быть найден за время 0(п).

D разделе 1.5 построена процедура равномерной генерации примеров из ограниченного множества содержащего всевозможные примеры задачи 1 | Tj | ¿т|Ц[. С помощью данной процедуры проведено экспериментальное исследование полиномиальных алгоритмов Лазарева и Хогевена для решения соответствующих специальных случаев задачи. Исследование показало число оптимально решенных данными алгоритмами примеров стремится к 100% при увеличении размерности. Также экспериментально было оценена фактическая погрешность решения, полученного с помощью предложенных вариантов схемы приближенного решения задачи. Показано, что среднее отношение фактической погрешности к гарантированной теоретической погрешности возрастает.при увеличении размерности и стремится к некоторому значению, не превышащему 1/2.

Вторая глава диссертации посвящена алгоритмам оптимального решения задачи 1 | Tj | ¿max-

В разделе 2,1 рассмотрены существующие подходы к решению задачи, такие как алгоритм Карлье11 н метод программирования в ограничениях12 {ПвО). Данный метод близок к методу ветвей п границ. Отличие заключается в том, что для сокращения перебора в ПвО используется пропагацня ограничения, которая удаляет несовместимые значения из множеств допустимых значений переменных. Алгоритм Карлье и программирование в ограничениях служат основой для алгоритмов решения задачи, предложенных далее во второй главе диссертации.

"Carlier J, The one-machine sequencing problem// European J. of Oper. fits.- 1902.- V, 11, N 1.-P. 42 - 47. j

J" ПартЛм-о Ph., Le P&pe C., Nuijten W. Constraint-based scheduling: applying constraint programming to scheduling problems// Kluwer Academic Publishers) 2001.- 198 p.

В разделе 2.2 предлагаются два алгоритма оптимального решения задачи 1 | | ¿msx- Первый алгоритм построен по методу программирования в ограничениях. На каждом шаге алгоритма для исходной задачи решается задача распознавания с помощью метода ПвО, в котором используется предложенная нами правило ветвления, основанное на следующей теореме.

Теорема 4 Пусть построено расписание Шража13 € П(ЛГ) для данного примера задачи, и требования пронумерованы, в там порядке, в котором они упорядочены в Пусть также Ь € N — наименьший номер, для которого 1>ь{щ) = immW, и а € N — наибольший такой номер, что а < Ь и

— min г,- < Ьь(fff) — UВ,

a<j<b

где UB < UB — верхняя оценка оптимального решения. При-

мем S — {а,..., Ь}, тогда:

• если не существует такого требования с е S, что dc > tfj, то для данного примера не существует расписания с максимальны** временным смещением, меньшим, чем UB;

• иначе, если с € S - последнее требования с директивным сроком de > dt, то в любом таком расписании тг', что Lmax(iv') < UB, требование с выполняется или до, иди после всех требований ш множества J = {с + 1,... ,р}.

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

lJSchr&ge. L Solving Resource-Constrained Network Problems by Implicit Enumeration: Noft-Preemptive Case// Oper. Res.- 1970.- У, 18.- P. 563 - 275.

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

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

В разделе 2.4 рассматривает вариант распознавания задачи 1 | т^ | Ьтах. Назовем расписание тг допустимым по отношению к константе Ь\ если ЬщахМ 5 Множество требований 3 допустимо по отношению к константе V, если существует допустимое расписание тг 6 П(5), и недопустилю, если не существует такого расписания. В рассматриваемом здесь варианте задачи требуется определить допустимо ли заданное множество требований N по отношению к заданной константе V. Бели ТУ допустимо, то необходимо найти допустимое расписание. Если же N недопустимо, то требуется найти как можно меньшее недопустимое по отношению к той же константе подмножество требований из множества N. Для данного варианта задачи предлагается алгоритм, который является эвристическим в том смысле, что он находит некоторое недопустимое подмножество требований 3 С .ЛГ, не обязательно минимальное, когда множество требование N недопустимо. В тоже время, алгоритм точно определяет, допустимо ли множество требование ЛЛ Правило ветвления алгоритма основано на следующей теореме.

Теорема 5 Пусть дано недопустимое по отношению к констпанте V расписание Шража е П(ЛГ) ы требования пронумерованы в том порядке, в котором они упорядочены е т:„. Пусть также Ь е N — наименьший номер, для которого Ьь{жа) > V, и а & N — наибольший такой камер, что а <Ь и '

- ттг, < Ьь(-ка) - Ь\

где, 3 = {а,... ,6}. Тогда:

1. если не существует такого требования с £ 5, что дс > то множество требований недопустимо по отношению к V;

2. иначе, если с 6 5 - последнее требования с директивным сроком ¿с > <1ь, и существует допустимое расписание ж' е П(ЛГ), то в данном расписании тг1 требование с выполняется или до, или после всех требований из множества 3 = {с + 1,.,., р}.

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

Теорема 6 Пусть в текущей задаче в любом допустимом расписании гг1 £ П(Л^) требование с € N может быть обслужено только до ил« после всех требований из множества 3 С N. Пусть также С N - недопустимое множество требований для задачи с дополнительным ограничением, согласно которому с обслуживается перед всеми требованиями из множества 3, о С N - недопустимое подмножество для задачи, где с выполняется после всех требований из 3. Тогда:

1. если с £ За> то множество недопустимо для текущей задачи;

2. если с $ то множество Зь недопустимо для.текущей задачи;

3. если с 6 и с € Эь, то множество 5' = 3 и Эа и 8ь недопустимо для текущей задачи. .

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

алгоритм решения задачи 11 rj [ ^uijUj. Алгоритм построен по"гибрид-ному" методу14 ветвей и отсечений15, который представлен в разделе 3.1. В этом же разделе сделан обзор работ, внесших вклад в развитие данного метода. Предложенный алгоритм' ветвей и отсечений заключается в следующим. Релаксация задачи формулируется как задача целочисленного линейного программирования (ЦЛП) и решается методом ветвей и отсечений, который является производным от метода ветвей и границ (метода Лэнд и Дойг). Каждое полученное целочисленное решение формулировки проверяется на допустимость с помощью специально разработанных комбинаторных алгоритмов. В случае недопустимости решения генерируются дополнительные ограничения, добавляемые в формулировку задачи — отсечения. j

В разделе 3.2 приведена постановка задачи, сделан обзор литературы по существующим методам ее решения.

В разделе 3.3 задача 1 | r^ j формулируется как задача

ЦЛП. Пусть булева переменная Xj принимает значение 1, если требование j € N обслуживается вовремя и 0 - если требование jeJV запаздывает. Тогда в компактном виде формулировка записывается следующим образом.

mm ^Wjtl-ij) (3)

Яод (4)

disjunctive^) (5)

х € {0,1}" (6)

Здесь ограничение disjunctive (я) выполняется тогда и только тогда, когда множество требований J = {j : Xj = 1} может быть обслужено на одном приборе без прерываний и с соблюдением времен поступления и директивных сроков, (4) — релаксация ограничения disjunctive. Ограничение {5) моделируется линейными ограничениями достаточно громоздко и неэффективно, что делает невозможным решение задачи ЦЛП достаточно большой размерности за приемлемое время. Поэтому в предлагаемом алгоритме ветвей и отсечений ограничение (5) исключается из

"Корбут А.А., Сигал H.X., ФннкелыцтеАн Ю.Ю. Гибридные методы в дискретном программировании// Изв. АН СССР, Техн. кибернет.- 1Э88.- N 1.- С. 65 - 77.

1*Фннкелы1ггеПн Ю.Ю. Метел отсечения и ветвления для решения ЭАДлч далочмелеиного линейного программирования// Изв. АН СССР. Техм. кнбернет.- 1971,- N 4.- С, 34 - 38,

формулировки,

В разделе 3.4 рассматриваются различные варианты релаксации (4). Существующие в литературе варианты не являются достаточно эффективными, поэтому в качестве ограничений (4) предлагаются следующие неравенства. Обозначим ajf = (n — rj)+ и ¡3^ = (dj — dj)+.

Утверждение 1 Пусть для двух требований i,j g N выполняется г; < dj. Если вектор х удовлетворяет ограничению disjunctive, тогда х также удовлетворяет ограничению

- П, (pi - тах{аи, < dj - г*. (7)

ietf

Раздел 3.5 посвящен вопросу проверки на допустимость решения £ задачи ЦЛП (3), (7), (6), а также вопросу построения отсечений в случае недопустимости Предлагаются два семейства отсечений. Отсечение первого семейства может быть построено при помощи алгоритма, предложенного в разделе 2.4. Алгоритм выполняется для множества требований J = {j : xj = 1}, и в случае его недопустимости находится недопустимое подмножество S С J, для которого строится ограничение

2>j<|S|-l. (8)

jes

Следующее утверждение представляет отсечения второго вида.

Утверждение 2 Пусть заданы такие множество требований П С N и требование k € N \ П, что к может быть обслужено только с момента времени г^, г" > г*, если все требования из fi выполняются вовремя. Положим также а," = (rjt — Тогда вектор х, удовлетворяющий ограничению disjtmctive, удовлетворяет неравенству

£ min [dj - if, (pi - max{a^,/Jj(})+] xt+ (Pk - 0jk)+2k <dj- rf + - г*)(| n I - E ж-).

oSii

для каждого требования j € N\U, dj> r{?.

В работе предлагается алгоритм сложности 0(п3), который проверяет существование отсечения вида (9), которое нарушается заданным вектором X.

В разделе 3,6 рассматриваются различные варианты предложенного алгоритма ветвей и отсечений. В заключительном разделе 3.7 представляются результаты экспериментального исследования предложенного алгоритма на множестве общедоступных тестовых примеров. Пока-занно, что разработанный алгоритм для задачи 1 | r¡ \ ^ щ Uj является более эффективным, чем лучший алгоритм для данной задачи, существующий в литературе16.

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

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

1. Лазарев A.A., Садыков P.P. Эффективность полиномиального алгоритма 0(n3 log п) для решения NP-трудноЙ проблемы минимизации максимального временного смещения 1 | r¿ | Lmsx// Материалы VII Международного семинара "Дискретная математика и ее приложения", 29 января - 2 февраля,- М.: Изд-во центра прикладных исследований при мех.-мат. факультете МГУ, 2001.- С. 381 - 383.

2. Лазарев A.A., Садыков P.P. К исследованию проблемы теории расписаний 1 I Tj I Lmix// Материалы российской конференции "Дискретный анализ и исследование операций", 24 июня - 28 июня.— Новосибирск: Изд-во Ин-та математики, 2002,- С. 219.

3. Лазарев A.A., Садыков P.P. Схема приближенного решения проблемы 1 I Tj I ¿mai// Материалы российской конференции "Дискретный анализ и исследование операций", 28 нюня - 2 июля,- Новосибирск: Изд-во Ин-та математики, 2004.- С. 173.

4. Лазарев A.A., Садыков P.P., Севастьянов C.B. Схема приближенного решения проблемы 1 | r-j | ¿max// Дискретный анализ и исследование операций.- 2006 - Сер. 2,- Т. 13, N 1.- С. 57 - 76.

iePerMy, L., Pinson е., Rivreau D. Using short-term memory to minimi« the weighted number of late jobs on a single machine// European J. Oper. Res.- £003.- V. 14S. P. 591 - 603.

5. Садыков P.P. Экспериментальное исследование проблемы теории расписаний для одного прибора минимизации максимального временного смещения// Материалы XL Международной научной студенческой конференции "Студент и научно-технический прогресс", 16 апреля - 18 апреля,- Новосибирск: Изд-во НГУ, 2002.- С. 126 -127.

6. Lazarev А.А., Sadykov R.R. A polynomial approximation scheme for the 11 fj I ¿max scheduling problem with guaranteed absolute error// Arias Estrada M., Gelbukh A. (eds.) Avances en ía Ciencia de la Computación: Proceedings of Fifth Mexican International Conference ENC'04, 20 - 24 September.- Colima, Mexico: 2004,- P. 465 - 473.

7. Sadykov R. A hybrid branch-and-cut algorithm for the one-machine ¡scheduling problem // Régin, J.-C., Rueher M. (eds.) Proceedings of the First International Conference CPAIOR'04,20 - 22 april.- SpringerVerlag, LNCS, V. 3011, 2004.- P. 409 - 414.

8. Sadykov R.R., Lazarev A.A. Experimental comparison of branch-and-bound algorithms for the 1 | rj \ Lmax problem// Proceedings of the Seventh International Workshop MAPSP'05, 6-10 june - Siena, Italy: 2005,- P. 239 - 241.

9. Sadykov R.R., Lazarev A.A., Kvaratskhelia A.G. Research of absolute error for NP-hard scheduling problem minimizing maximum lateness// Proceedings of the Tenth FVanch-German-Italian Conference on Optimization FGI'00, 4-8 September.- Montpelier, France: 2000.-P. 56 - 57.

Садыков Руслан Равильевич

Алгоритмы решения задач теории расписаний для одного прибора с критериями и *£¡wJ V}

Подписано в печать 17.10.2006 Уч.-изд.л. 0,9. Усл.-печ. л. 1 Тираж 100 экз. Заказ 53

Отпечатано на ротапринтах в Вычислительном центре им. A.A. Дородницына Российской академии наук 119991, Москва, ул. Вавилова, 40

Введение

1 Полиномиальные алгоритмы решения задачи 1 | r3 \ Lrnax

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

1.2 Обозначения и определения основных понятий.

1.3 Абсолютная погрешность приближенного решения.

1.4 Схема нахождения приближенного решения.

1.4.1 Вариант схемы на основе случая Лазарева.

1.4.2 Вариант схемы на основе случая Хогевена.

1.5 Экспериментальное исследование полиномиальных алгоритмов решения задачи 1 | Tj | Lmax.

1.5.1 Способ генерации примеров.

1.5.2 Оценка практического значения абсолютной погрешности.

1.5.3 Эффективность применения полиномиальных алгоритмов для общего случая задачи.

2 Алгоритмы оптимального решения задачи 1 | гj \ Lmax

2.1 Существующие методы решения задачи 1 | г, | Lmax

2.1.1 Алгоритм Карлье.

2.1.2 Метод программирования в ограничениях.

2.2 Алгоритмы решения задачи 1 | rj | Lmax

2.3 Экспериментальное сравнение алгоритмов решения задачи 1 | rj | Lmax.

2,4 Модифицированный алгоритм Карлье.

3 Алгоритм ветвей и отсечений для решения задачи 1 | r:/ [

3.1 "Гибридная" схема решения одного класса задач целочисленного линейного программирования.

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

3.3 Формулировка задачи 1 | г,- | как задачи ЧЦЛП.

3.4 Дополнительные ограничения.

3.5 Генерация отсечений.

3.6 "Гибридный" алгоритм ветвей и отсечений.

3.7 Экспериментальная оценка эффективности.

Общее направление исследований

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

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

Данное направление в науке, получившее название "теория расписанийберет свое начало в 50-е годы 20-го века. Одними из первых работ по теории расписаний считаются труды Джонсона (Johnson [53]), Джексона (Jackson [50]) и Смита (Smith [79]).

Изначально одними из главных вопросов нового направления были классификация задач и установление их сложности. Считающаяся стандартной и по нынешний день классификация задач теории расписаний была предложена Грэхэмом и др. (Graham at al. [45]). Относительно быстро была установлена сложность большого числа задач. Достаточно полные обзоры по задачам теории расписаний и их сложности представлены в работах Гэри и Джонсона (Garey, Johnson [1]), Ленстры и др. (Lenstra et al. [62]), Лоулера и др. (Lawler et al. [59]), Танаева и др. [17, 18], Брукера (Brucker [36]).

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

Первым подходом является разработка полиномиальных эвристических алгоритмов. Для многих эвристических алгоритмов были найдены оценки погрешности получаемого решения. Такие алгоритмы называются приближенными [6, 16]. Существуют приближенные алгоритмы, гарантирующие как относительную погрешность [2, 76], так и абсолютную погрешность [14]. Некоторые Л'Р-трудные задачи допускают существование так называемой аппроксимационной схемы. В рамках данной схемы можно найти решение с относительной погрешностью не более любого заданного значения е > 0 за время, полиномиально зависящее от 1/е. Для задач теории расписаний такие схемы разработали, например, Ковалев [3], Алон и др. (Alon et al. [23]), Мастролилли (Mastrolilli [64]), Севастьянов и Вёгин-гер (Sevastianov,Woeginger [77]. Для задач, не имеющих аппроксимационной схемы, большое значение имеет установление предельного значения е, для которого возможно нахождения ^-приближенного алгоритма за полиномиальное время.

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

Точным методам решения iVP-сложных задач также уделено немалое внимание в работах по теории расписаний. Наибольшее распространение получили методы сокращения перебора, также называемые методами ветвей и границ [4,15, 35, 37, 54]. Для сокращения перебора здесь вычисляются нижние оценки целевой функции (в случае ее минимизации), а также используются комбинаторные свойства задач, например, свойства оптимальных расписаний.

Часто задачи теории расписаний могут быть сформулированы как задачи целочисленного линейного программирования. Решению таких задач посвящены, например, работы [21, 22, 70, 80].

В последнее время широкое распространение получил метод программирования в ограничениях. Одной из областей его успешного применения является теория расписаний [29].

Некоторые сложные задачи теории расписаний могут быть оптимально решены с помощью алгоритмов, использующих элементы сразу нескольких методов. Одно из их названий — "гибридные алгоритмы" [5, 51]. На данный момент данное направление является одним из перспективных.

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

Диссертационная работа посвящена исследованию iVP-трудных задач теории расписаний для одного прибора с неодновременным поступлением требований с критериями минимизации максимального временного смещения (1 | rj | Ь1ШХ) и минимизации взвешенного числа запаздывающих требований (1 | Tj | J^WjUj). Для первой задачи предложена схема нахождения приближенного решения с гарантированной абсолютной погрешностью. В диссертации рассмотрены два варианта данной схемы, основанные на двух полиномиально разрешимых классов примеров задачи. Для данной задачи также предложены два точных алгоритма решения общего случая. Алгоритмы хорошо показали себя в численных экспериментах при их сравнении с лучшими существующими в литературе алгоритмами решения задачи 1 | fj | Lmax. Для решения второй задачи предложен точный алгоритм, работающей по схеме метода ветвей и отсечений. Последний является расширением метода ветвей и границ для решения задач целочисленного линейного программирования (ЦЛП). В алгоритме задача формулируется как задача ЦЛП. Из последней исключаются некоторые ограничения, то есть мы получаем релаксацию изначальной задачи. Затем "усеченная" задача ЦЛП решается методом ветвей и границ. При этом в процессе решения недопустимые решения для исходной задачи исключаются с помощью добавления в формулировку дополнительных ограничений — отсечений. При проведении сравнительного экспериментального исследования предложенный алгоритм показал хорошие результаты.

Структура и обзор результатов диссертации

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

Заключение

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

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

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

• Экспериментально показано, что процент оптимально решенных примеров задачи 1 | r?- | Ьшах полиномиальными алгоритмами стремится к 100% при увеличении размерности. Также экспериментально установлено, что фактическое значение абсолютной погрешности решения, полученного при помощи обоих вариантов предложенной схемы нахождения приближенного решения, в среднем не превосходит половины теоретического значения абсолютной погрешности.

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

• Для модифицированного варианта распознавания проблемы

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

• Для задачи 1 | г7- | J2wjUj предложен точный алгоритм ветвей и отсечений. Преимущество предложенного алгоритма над наилучшим алгоритмом для данной задачи, представленном в литературе, на множестве общедоступных тестовых примеров подтверждено численными экспериментами.

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

2. Каширских К.Н., Поттс К.Н., Севастьянов С.В. Улучшенный алгоритм решения двухмашинной задачи flow shop с неодновременным поступлением работ// Дискретный анализ и исследование операций-1997.- Т. 4, N 1 С. 13 - 32.

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

4. Корбут А.А., Сигал И.Х., Финекельштейн Ю.Ю. Метод ветвей и границ. Обзор теорий, алгоритмов, программ и приложений// Math. Operation Forsch. Statist. Ser. Optimization.- 1977.- V. 8, N 2. C. 253 -280.

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

6. Корбут А.А., Финкелыцтейн Ю.Ю. Приближенные методы дискретного программирования// Изв. АН СССР. Техн. кибернет- 1983-N 1.- С. 165 176.

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

8. Лазарев А.А., Садыков P.P. К исследованию проблемы теории расписаний 1 | г j ) Lmax// Материалы российской конференции "Дискретный анализ и исследование операций", 24 июня 28 июня - Новосибирск: Изд-во Ин-та математики, 2002 - С. 219.

9. Лазарев А.А., Садыков P.P. Схема приближенного решения проблемы 1 I fi I -^тах// Материалы российской конференции "Дискретный анализ и исследование операций", 28 июня 2 июля - Новосибирск: Изд-во Ин-та математики, 2004 - С. 173.

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

11. Лазарев А.А., Садыков P.P., Севастьянов С.В. Схема приближенного решения проблемы 1 | гj | Lmax// Дискретный анализ и исследование операций,- 2006.- Сер. 2,- Т. 13, N 1,- С. 57 76.

12. Севастьянов С.В. Геометрические методы и эффективные алгоритмы в теории расписаний// Дис. док. физ.-мат. наук Новосибирск: 2000280 с.

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

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

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

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

17. Финкельщтейн Ю.Ю. Метод отсечения и ветвления для решения задач целочисленного линейного программирования// Изв. АН СССР. Техн. кибернет,- 1971,- N 4,- С. 34 38.

18. Alon N., Woeginger G. J., Yadid T. Approximation schemes for scheduling on parallel machines// J. of Scheduling 1998.- V. I - P. 55 - 66.

19. Apt K. Principles of Constraint Programming// Cambridge University Press, 2003,- 420 p.

20. Baker K.R., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. Preemtive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints// Oper. Res.-1983-V. 31, N 2-P. 381 386.

21. Baker K.R., Su Z.-S. Sequencing with due-dates and early start times to minimize maximum tardiness// Naval Res. Logist. Quart 1974-V. 21-P. 171 - 176.

22. Baptiste Ph. An 0(n4) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs// Oper. Res. Letters -1999-V. 24,- P. 175 180.

23. Baptiste Ph., Jouglet A., Le Pape C., Nuijten W. A constraint-based approach to minimize the weighted number of late jobs on parallel machines// University of Technology of Compiegne, 2000,- Research Report N 2000/288,- 45 p.

24. Baptiste Ph., Le Pape C., Nuijten W. Constraint-based scheduling: applying constraint programming to scheduling problems/ / Kluwer Academic Publishers, 2001 198 p.

25. Baptiste Ph., Peridy, L., Pinson E. A branch and bound to minimize the number of late jobs on a single machine with release time constraints// European J. of Oper. Res.- 2003. V. 144, N 1. P. 1 11.

26. Benders J.F. Partitioning procedures for solving mixed-variables programming prolems// Numerische Mathematik 1962 - V. 4. P. 238 -252.

27. Bockmayr A., Pisaruk N. 2003. Detecting infeasibility and generating cuts for MIP using CP // Proceedings of the Fifth International Workshop CPAIOR'03, 8-10 may.- Montreal: 2003.- P. 16 30.

28. Bockmayr A., Kasper Th. Branch-and-Infer: A unifying framework for integer and finite domain constraint programming// INFORMS J. Computing.- 1998.- V. 10.- P. 287 300.

29. Bratley P., Florian M., Pobillard P. On sequencing with earliest starts and due dates with application to computing bounds for the (n/ra/G/Fmax) problem// Naval Res. Logist. Quart.- 1973,- V. 20,- P. 57 67.

30. Brooks G.N., White C.R. An algorithm for finding optimal or near -optimal solutions to the production scheduling problem// J. Ind. Eng-1965,- V. 16, N 1- P. 34 40.

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

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

33. Carlier J., Pinson E. A practical use of Jackson's preemptive schedulefor solving the job-shop problem// Annals of Oper. Res 1990 - V. 26-P. 269 - 287.

34. Carlier J., Pinson E. Adjustment of heads and tails for the job-shop problem// European J. of Oper. Res.- 1994.- V. 78,- P. 146 161.

35. Chen Z-L., Powell W.B. Solving parallel machine scheduling problems by column generation// INFORMS J. Computing.- 1999 V. 11- P. 78 - 94.

36. Colombani Y., Heipcke T. Mosel: an extensible environment for modelling and programming solutions// Proceedings of the Fourth International Workshop CPAIOR'02, 25 27 march.- Le Croisic, France: 2002,- P. 277 -290.

37. Dauzere-Peres S., Lasserre J.B. A note on Carlier's algorithm for the one-machine sequencing problem// Toulouse: CNRS, 1990 Rapport LA AS N 90370,- 4 p.

38. Dauzere-Peres S., Sevaux M. Using Lagrangean relaxation to minimize the weighted number of late jobs on a single machine// Naval Res. Logistics.-2003,- V. 50, N 3.- P. 273 288.

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

40. 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- V. 5 - P. 287 - 326.

41. Gueret C., Prins C., Sevaux M., Heipcke S. Applications of Optimization with XpressMP// Dash Optimization Ltd., 2002,- 264 p.

42. Hall L.A., Shmoys D.B. Jackson's rule for one-machine schedulings: Making a good heuristic better// Math. Oper. Res -1992 V. 17.- P. 22 -35.

43. Hoogeveen J. A. Minimizing maximum promptness and maximum lateness on a single machine// Math. Oper. Res.- 1996 V. 21- P. 100 -114.

44. Hooker J.N., Ottosson G. Logic-based Benders decomposition// Math. Prog.- 2003,- V. 96.- P. 33 60.

45. Jackson J.R. Scheduling a production line to minimize maximum tardiness// Los Angeles, С A: University of California, 1955 Manag. Sci. Res. Project. Research Report N 43.

46. Jain V., Grossmann I.E. Algorithms for hybrid MILP/CLP models for a class of optimization problems// INFORMS J. Computing 2001-V. 13,- P. 258 - 276.

47. Kise H., Ibaraki Т., Mine H. A solvable case of the one machine scheduling problem with ready and due times// Oper. Res 1978 - V. 26, N 1-P. 121 - 126.

48. Johnson S.M. Optimal two- and three-stage production schedules with setup times included// Naval Res. Logistics Quat- 1954 V. 1- P. 61 -68.

49. Lageweg B.J., Lenstra J.K., Rinnooy Kan A.H.G. Minimizing maximum lateness on one machine: computational experience and applications// Statistica Neerlandica.- 1976,- V. 30.- P. 25 41.

50. Land A.H., Doig A.G. An automatic method for solving discrete programming problems// Econometrica I960 - V. 28 - P. 497 - 520.

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

52. Lawler E.L. A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs// Annals of Oper. Res.- 1990,- V. 26,- P. 125 133.

53. Lawler E.L. Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the "tower od sets" property// Math. Сотр. Modelling-1994,- V. 20, N 2.- P. 91 106.

54. Lawler E.L., Moore J.M. A functional equation and its application to resource allocation and sequencing problems// Manag. Sci 1969-V. 16.- P. 77 - 84.

55. Lenstra J.K., Rinnooy Kan A.H.G., Brucker P. Complexity of machine scheduling problems// Annals of Discrete Math 1977 - V. 1- P. 343 -362.

56. Marriott K., Stuckey P.J. Programming with Constraints: An Introduction// The MIT Press, 1998,- 476 p.

57. Mastrolilli M. Efficient Approximation Schemes for Scheduling Problems with Release Dates and Delivery Times// J. of Scheduling 2003 - V. 6, N 6.- P. 521 - 531.

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

59. Moore J.M. An n job, one machine sequencing algorithm for minimizing the number of late jobs// Manag. Sci 1968.- V. 15, N 1,- P. 102 - 109.

60. Nowicki E., Zdrzalka S. A note on minimizing maximum lateness in a one-machine sequencing problem with release dates// European J. of Oper. Res.- 1986.- V. 23.- P. 266 267.

61. Peridy, L., Pinson E., Rivreau D. Using short-term memory to minimize the weighted number of late jobs on a single machine// European J. Oper. Res.- 2003 V. 148. P. 591 - 603.

62. Potts C.N. Analysis of a heuristic for one machine sequencing with release dates and delivery times// Oper. Res.- 1980.- V. 28. P. 1436 1441.

63. Queyranne M., Schultz A.S. Polyhedral approaches to machine scheduling// Preprint N 408/1994 Berlin: Technical University of Berlin, Department of Mathematics, 1994 - 61 p.

64. Sadykov R. A hybrid branch-and-cut algorithm for the one-machine scheduling problem // Regin, J.-C., Rueher M. (eds.) Proceedings of the First International Conference CPAIOR'04, 20 22 april - Springer-Verlag, LNCS, V. 3011, 2004.- P. 409 - 414.

65. Sadykov R.R., Lazarev A.A. Experimental comparison of branch-and-bound algorithms for the 1 | r?- | Lmax problem// Proceedings of the Seventh International Workshop MAPSP'05, 6-10 june Siena, Italy: 2005.- P. 239 - 241.

66. Schrage, L. Solving Resource-Constrained Network Problems by Implicit Enumeration: Non Preemptive Case// Oper. Res -1970 V. 18 - P. 263 -278.

67. Sevaux M., Dauzere-Peres S. Genetic algorithms to minimize the weighted number of late jobs on a single machine// European J. of Oper. Res-2003.- V. 151.- P. 296 306.

68. Sevastianov S.V., Woeginger G.J. Makespan minimization in open shops: A polynomial time approximation scheme / / Math. Prog 1998 - V. 82-P. 191 - 198.

69. Simons B.B. A fast algorithm for single processor scheduling// Proceedings of the 19th IEEE Annual Symposium on Foundations of Computer Science New York: Ann. Arbor. Mich., 1978 - P. 246 - 252.

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

71. Sousa J.P., Wolsey L.A. A time-indexed formulation of non-preemptive single-machine scheduling problems// Math. Prog.- 1992.- V. 54.-P. 353 367.