О сложности задач теории расписаний с длительностями, зависящими от времени тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

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

1.1. Основные обозначения и определения

1.2. Линейные функции

1.3. Выпуклые и вогнутые функции

1.4. Ступенчатые функции.

Глава 2. Задачи теории расписаний на одной машине с длительностями, линейно или кусочно-линейно зависящими от времени.

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

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

2.3. Полиномиальные и псевдополиномиальные алгоритмы для задач с общим директивным сроком.

2.4. Сложность задач с общим директивным сроком

Глава 3. Задачи теории расписаний на параллельных машинах и в многооперационных системах с линейно ра стущими длительностями.

3.1. Основные обозначения и определения.

3.2. Вспомогательный результат.

3.3. Параллельные машины. NР-трудность.

3.4. Многооперационные системы.

3.5. Полиномиально-разрешимые случаи.

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

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

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

В многооперационных (многостадийных) системах работа состоит из набора операций. В дальнейшем будут рассматриваться следующие типы многооперационных задач. Если каждая работа состоит из последовательных операций и порядок выполнения операций одинаков для всех работ и определяется последовательностью машин, то такая обслуживающая система называется системой поточного типа. В случае. если порядок выполнения операций не фиксирован и может быть различным для каждой работы, то такая обслуживающая система называется системой открытого типа. Подробно с различными постановками и результатами для задач с одной или несколькими параллельными машинами можно ознакомиться в монографии [11]. а для задач с многооперационными системами в монографии [12].

Будем предполагать, что в каждый момент времени на любой машине выполняется не более одной работы и в каждый момент времени любая работа обслуживается не более одной машиной.

Для того чтобы задать расписание требуется установить какие работы или операции выполняются машинами в каждый момент времени. Например, при сделанных выше предположениях расписание можно рассматривать как указание для каждой операции номера машины. на которой она выполняется и момента начала ее выполнения. Другие различные способы задания расписаний описаны в монографиях [11, 12. 13]. Расписание, которое удовлетворяет всем условиям и ограничениям, вытекающим из постановки рассматриваемой задачи. называется допустимым. Отметим, что построение допустимого расписания и даже проверка того факта, существует ли оно вообще, часто оказывается нетривиальной задачей. Допустимое расписание задает для каждой работы момент ее завершения. В качестве критерия качества полученного расписания выступает значение некоторой действительной функции, называемой целевой. Расписание с наименьшим значением целевой функции среди всех допустимых расписаний, называется оптимальным. В качестве целевой функции наиболее часто рассматриваются функции, выражающие следующие понятия: длина расписания, сумма моментов завершения работ, взвешенная сумма моментов завершения работ, число запаздывающих работ, максимальное запаздывание работы относительно директивного срока и некоторые другие.

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

Первый шаг в этом направлении был сделан Мельниковым и Ша-франским [8]. Они рассмотрели задачи, в которых длительность каждой работы Ji в момент времени t задается функцией,

Pi = а; + Т(£), где а,- > 0 и Y(i) >0 — функция, определенная для всех t > 0. В случае одной машины в [8] установлено, что если Т(t) монотонно возрастает при t > 0, то перестановка работ по неубыванию величин а, минимизирует длину расписания; если Y(i) — монотонно убывающая дифференцируемая функция и | | < 1 при t > 0, то перестановка

Но работ по невозрастанию величин аг- минимизирует длину расписания. В этой же работе изучались задачи построения оптимального по длине расписания для системы потокового типа (flow shop) на т машинах. Авторы рассмотрели две возможные ситуации. В первом случае длительность операции зависит от времени начала выполнения работы. Во втором случае длительность операции зависит от времени начала выполнения самой операции. В первом случае задача формулировалась следующим образом. Пусть длительность операции г работы Jj определяется как

Pij = ач + T(5i)> где a,ij — фиксированные числа, Sj — начало выполнения работы Jj Л dT(t), первой машинои, T(t) >0 — дифференцируемая функция и |—— | >

С66

Л > 0 при t > 0. В [8] построен полиномиальный алгоритм, находящий точное решение задачи при условии, что число работ п > N, где N — конечное число, независящее от функции Y(i). Во втором случае рассматривалась задача на двух машинах. Длительность операции i работы Jj определяется как р^ — a,j + T(sjj), где T(t) > 0 — монотонно возрастающая функция при t > 0, ац > ац > 0. Для этой задачи в [8] построен алгоритм с абсолютной оценкой точности.

В [11, 16, 25, 29] рассматривалась задача построения оптимального по длине расписания п работ на одной машине с длительностями, равными р{ = а^; + Ьг.

В этих работах показано, что оптимальное расписание строится упорядочением работ по неубыванию величин Ъ{/аКроме того, в [29] рассматривались задачи, когда время выполнения работы </г- описывается полиномом общего вида а{пхп + щп+1Хп+1 + . + ацх + а,-0.

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

В [44] рассмотрены задачи на одной машине с различными критериями оптимальности, в которых длительность работы Ji прямо пропорциональна моменту начала ее выполнения и равна

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

В [45] рассмотрена следующая задача. Множество из п работ должно быть выполнено на одной машине. Все работы готовы к выполнению в момент времени 0. Длительность работы /г- задается формулой Рг = 1 + аг-5г-. Требуется минимизировать суммарное время завершения всех работ. Показано, что среди оптимальных расписаний существует расписание, обладающее следующими свойствами. Первой выполняется работа с наибольшим аг\ Работа с наименьшим щ не выполняется ни второй, ни последней. Работы в оптимальной последовательности упорядочены в порядке убывания, если они выполняются до работы с наименьшим оц. и упорядочены в порядке возрастания, если они выполняются после работы с наименьшим аг-.

В [39] рассмотрена следующая задача. Множество из п работ должно быть выполнено на одной машине. Все работы готовы к выполнению в момент времени 0. Для каждой работы определено директивное время на начало выполнения. Длительность каждой работы определяется суммой фиксированной части и некоторой штрафной добавки за нарушение директивного срока. Величина штрафной добавки прямо пропорциональна разности между моментом начала выполнения работы и директивным сроком. Требуется построить расписание минимальной длины. Для решения этой задачи предложены точные экспонепиальные алгоритмы, основанные на методе ветвей и границ и динамическом программировании, а также ряд эвристических полиномиальных алгоритмов. В [40] показана КР-трудность этой задачи при условии, что все работы имеют общий директивный срок. Там же рассмотрена задача, в которой рост штрафной добавки ограничен другим директивным сроком также одинаковым для всех работ. Для обоих задач построены псевдополиномиальные алгоритмы. В [38] для задач, рассмотренных в [40], построены полные полиномиальные ап-проксимационные схемы.

Модели, в которых длительность работы является убывающей линейной или кусочно-линейной функцией, рассматривались в [17, 30, 48]. В [30] изучалась задача нахождения допустимого относительно директивных сроков расписания, когда длительность работы «7г- задается формулой Рг = — аг-5г- + где 0 < &г- < 1 и ЬД- < аг- < Авторы установили, что задача является МР-полной уже в том случае когда у работ существует только два различных директивных срока. Этот результат влечет ТУР-трудность и соответствующих оптимизационных задач, в частности, задачи минимизации числа запаздывающих работ. В [48] был построен точный полиномиальный алгоритм решения этой задачи в предположении, что все работы имеют общий директивный срок.

В [18, 19] изучались задача минимизации суммы времен завершения всех работ в системе с несколькими параллельными машинами, когда длительность работы задается формулой рг- = а^-. Установлено, что если число параллельных машин является частью входа индивидуальной задачи, то при условии Р ^ NP для ее решения не существует полиномиального алгоритма, находящего расписание, длина которого не более чем в фиксированное число раз хуже длины оптимального расписания. Для случая когда система состоит из двух параллельных машин установлена Л^Р-трудность рассматриваемой задачи.

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

Первая глава посвящена исследованию сложности и построению эффективных алгоритмов для задач на одной машине с длительностями работ, пропорциональными функции от времени. Время выполнения работы 3{ равно р{ = где Т(£) — некоторая функция от времени, одинаковая для всех работ.

В разделе 1.1 даются основные определения теории дискретной оптимизации и теории расписаний, приведятся эталонные ТУР-трудные задачи и вводятся обозначения для рассматриваемых задач теории расписаний.

В разделе 1.2 рассматриваются задачи, в которых функция Т(£) имеет вид Тй = а* + Ь. Устанавлено, что если работы выполняются без простоев, то суммарное время обработки не зависит от последовательности выполнения этих работ. Использование этого факта позволяет построить точные полиномиальные алгоритмы для задач со следующими критериями оптимальности:

- минимизация максимального запаздывания;

- минимизация взвешенного суммарного времени завершения выполнения всех работ;

- минимизация числа запаздывающих работ;

- минимизация максимального временного смещения.

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

В разделе 1.4 исследуются задачи минимизации длины расписания, когда длительности работ пропорциональны ступенчатой функции. Для всех рассмотренных в этом разделе задач устанавлена их ТУР-трудность и построены "псевдополиномиальные"алгоритмы.

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

В разделе 2.1 устанавливается ]УР-трудность задачи минимизации максимального временного смещения на одной машине с линейными функциями длительности.

В разделе 2.2 рассматриваются задачи минимизации длины расписания, в которых длительность работ определяется суммой фиксированной части и некоторой штрафной добавки. Каждая работа Ji имеет директивный срок <1{ на начало выполнения. Штраф равен нулю, если работа начинает выполняться до этого директивного срока, и прямо пропорционален количеству времени, прошедшему с момента наступления директивного срока, то есть длительность работы вычисляется по формуле р{ = аДйг — + Ъ{. Устанавливается А^Р-трудность в сильном смысле данной задачи.

В разделах 2.3 и 2.4 изучается задача с общим директивным сроком на начало выполнения всех работ, ои = V. В разделе 2.3 строится псевдополиномиальный алгоритм для этой задачи, а в разделе 2.4 устанавливается ее АГР-трудность. Аналогичные результаты получены независимо в [40]. В этих же разделах рассматриваются три частных случая данной задачи. Для одной из них удается построить полиномиальный алгоритм, а для остальных задач установлена их ]УР-трудность и построены "псевдополиномиальные"алгоритмы.

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

В разделе 3.1 приводятся основные определения и обозначения для задач теории расписаний при наличии нескольких машин.

В разделе 3.2 формулируется вспомогательная задача 4-ПРОИЗВЕ-ДЕНИЕ. Устанавливается ее принадлежность к классу А^Р-полных задач. В дальнейшем этот результат используется для доказательства КР-трудности некоторых задач теории расписаний.

В разделе 3.3 изучаются задачи теории расписаний, когда каждая работа может быть выполнена на одной из двух идентичных машин. Рассматриваются критерии минимизации длины расписания и минимизации суммарного времени завершения всех работ. Для обоих критериев устанавливается Л^Р-трудность построения оптимального расписания. Аналогичный результат для критерия минимизации суммарного времени завершения всех работ получен независимо в [18, 19].

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

- минимизация максимального временного смещения в системе поточного типа из двух машин;

- минимизация длины расписания в системе открытого типа из трех машин;

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

Показывается ]УР-трудность рассматриваемых задач.

В разделе 3.5 строятся точные полиномиальные алгоритмы для задач минимизации длины расписания в системах поточного и открытого типа из двух машин.

Основные результаты диссертации опубликованы в работах [3 - 7, 34 - 37] и докладывались на Втором сибирском конгрессе по прикладной и индустриальной математике (г. Новосибирск, Россия, 1996), на Симпозиуме по исследованию операций 1996 (г. Брауншвейг, Германия, 1996), на Третьем рабочем семинаре по моделям и алгоритмам в планировании и теории расписаний (г.Кембридж, Великобритания,

1997), на Международной конференции проблемы оптимизации и экономические приложения (г. Омск, Россия 1997), на Международном симпозиуме по комбинаторной оптимизации (г. Брюссель, Бельгия,

1998), на семинарах в Институте математики СО РАН. Непринадлежащие автору результаты будем формулировать в виде утверждений".

Заключение

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

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

1. Для случая, когда длительность каждой работы пропорциональна линейной функции изучена взаимосвязь получающихся задач с классическими задачами теории расписаний, в частности: а) для задач с одной машиной и различными критериями оптимальности построены точные полиномиальные алгоритмы, обобщающие известные алгоритмы для задач с фиксированными длительностями; б) разработан метод, позволяющий по известным полиномиальным алгоритмам для задач с фиксированными длительностями строить полиномиальные алгортимы для задач с длительностями пропорциональными линейной функции, и с его помощью построены точные полиномиальные алгоритмы для задач минимизации длины расписания в системах поточного и открытого типа на двух машинах; в) установлена ]УР-трудность в сильном смысле задачи минимизации длины расписания в системе поточного типа из трех машин; г) показано, что задача минимизации суммарного времени завершения выполнения всех работ на двух идентичных машинах является Л^Р-трудной, в то время, как в случае фиксированных длительностей задача является полиномиально разрешимой.

2. Для случая, когда длительность каждой работы пропорциональна произвольной функции выделены новые широкие классы полиномиально разрешимых задач, а именно: а) построены точные полиномиальные алгоритмы для задачи минимизации длины расписания на одной машине для выпуклой (или вогнутой) функции; б) построен точный полиномиальный алгоритм для задачи минимизации суммарного времени завершения выполнения всех работ на одной машине для выпуклой функции; в) при дополнительных ограничениях на исходные данные задач построены точные полиномиальные алгоритмы для задач минимизации максимального запаздывания и взвешенного суммарного времени завершения выполнения всех работ на одной машине для выпуклой (или вогнутой) функции;

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

4. Установлена NР-трудность задачи минимизации длины расписания, в которых длительность каждой работы определяется произвольной выпуклой неубывающей кусочно-линейной функцией.

1. Бухштаб A.A. Теория чисел.- М.: Учпедгиз, i960.

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

3. Кононов A.B. О расписаниях работ на одной машине с длительностями, нелинейно зависящими от времени // Дискретный анализ и исследование операций Т.2, N 1. 1995. С. 21-35.

4. Кононов A.B. Комбинаторная сложность составления расписаний для работ с простым линейным ростом длительностей // Дискретный анализ и исследование операций Т.З, N 2. 1996. С. 15-32.

5. Кононов A.B. Задачи теории расписаний на одной машине с длительностями работ, пропорциональными произвольной функции // Дискретный анализ и исследование операций Т.5, N 3. 1998. С. 17-37.

6. Кононов A.B. Задачи теории расписаний с длительностями, зависящими от времени. Алгоритмы и сложность // Тезисы докладов. Второй Сибирский Конгресс по Прикладной и Индустриальной Математике (ИНПРИМ-96). , Новосибирск 1996. С. 137.

7. Кононов A.B. Задачи теории расписаний с увеличением длительности работ за нарушение нормативных сроков // Тезисы докладов.

8. Международная конференция Проблемы оптимизации и экономические приложения. , Омск 1997. С. 97.

9. Мельников О.Н. Шафранский Я.М. Параметрическая задача теории расписаний // Кибернетика. N 3. 1979. С. 53-57.

10. Пападимтриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М: Мир, 1985.

11. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М: Мир, 1980.

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

13. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М: Наука, Москва. 1989.

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

15. Alidaee В. A Heuristic Solution Procedure to Minimize Makespan on a Single Machine with Non-linear Cost Functions // «/. Opnl. Res. Soc. V. 41. 1990. P. 1065-1068.

16. Alidaee В., Landram F. Scheduling Deteriorating Jobs on a single Processor // Opns. Res. Letts. V. 17. 1996. P.507-510.

17. Browne S. Yechiali U. Scheduling deterioration jobs on a single processor // Oper. Res. V. 38. 1990. P. 495-498.

18. Chen Z-L. A note on single-processor scheduling with time-dependent execution times // Operations research letters, V. 17, N 3. 1995. P. 127-129.

19. Chen Z-L. Parallel machine scheduling with time dependent processing times // Discrete Applied Mathematics, V. 70. 1996. P. 81-93.

20. Chen Z-L. Erratum to Parallel machine scheduling with time dependent processing times // Discrete Applied Mathematics, V. 75. 1997. P. 103.

21. Cheng, T.C., Ding Q. The complexity of scheduling starting time dependent tasks with release times // Information Processing Letters V. 65. 1998. 75-79.

22. Conway R.W., Maxwell W.L., Miller L.W. Theory of scheduling. Addis on-Wesley, Reading, MA.

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

24. Garey M.R. Johnson D.S. Computers and Intractability: a Guide to the Theory of NP-Completness. Freeman, San Francisco.

25. Gawiejnowicz S. Brief survey of continuous models of scheduling // Foundations of Computing and Decision Sciences, V. 21, N. 2. 1996. 81-100.

26. Gawiejnowicz S., Pankowska L. Scheduling jobs with varying processing times // Information Processing Letters V. 54. 1995. P. 175-178.

27. Glazebrook K.D. Single-Machine Scheduling of stochastic Jobs Subject to Deterioration or Delay // Nav.Res.Logist. Quart. V. 39. 1992. P. 613-633.

28. Gonzalez T., Sahni S. Open shop scheduling to minimize finish time // J. Assoc. Comput. Mach. V. 23. 1976. P. 665-679.

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

30. Gupta J.N.D. Gupta S.K. Single facility scheduling with nonlinear processing times // Computers ind. Engng. V. 14, N 4. 1988. P. 387-393.

31. K.I.-J.Ho, J.Y.-T.Leung, W.D.Wei, Complexity of scheduling tasks with time-dependent execution times // Information Processing Letters V. 48. 1993. 315-320.

32. Jackson J.R. Scheduling a production line to minimize maximum tardiness // Res.rep. Management Science Research Project, University of California, Los-Angeles.

33. Jonson S.M. Optimal two and three stage production schedules with set up times included // Naval.Res.Logist. Quart. V .1, N 1. 1954. P. 61-68.

34. Karp R.M. Reducibility among combinatorial problems // R.E.Miller, J. W. Thatcher (eds.) Complexity of Computer Computations, Plenum Press, New York 1972. P. 85-103.

35. Kononov A.V. On schedules of a single machine jobs with processing times nonlinear in time // Operations Research and Discrete Analysis. Mathematics and Rs Applications, Kluwer Academic Publishers, Dordrecht. 1997. P. 109-123.

36. Kononov A.V. Scheduling Problems with Linear Increasing Processing Times // Operations Research Proceedings 1996, Springer 1997. P. 208-212.

37. Kononov A.V. Complexity of Scheduling Problems with the Time-Dependent Processing Times // Third Workshop on Models and Algorithms for Planning and Scheduling Problems. Abstracts, Cambridge, 1997. P. 29.

38. Kononov A.V. Exact polynomial algorithms and complexity of some parametric scheduling problems on a single machine // International Symposium on Combinatorial Optimization. Abstracts, Brussel, 1998. P. 96.

39. Kovalyov M.Y., Kubiak W. A fully polynopmial Approximation Scheme for Minimizing Makespan of Deteriorating Jobs // Journal of Heuristics V. 3. 1998. P. 287-297.

40. Kunnarthur A.S., Gupta S.K. Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem // Europian J. Oper. Res. V. 47, N 1. 1990. P. 56-64.

41. Kubiak W., van de Velde S.L. Scheduling deteriorating jobs to minimize makespan // Report LPOM-94-12, Laboratory of Production and Operations Management, Department of Mechanical Engineering, Univercity of Twente, 1994.

42. Lawler E.L. A "pseudopolynomial"algorithm for sequencing jobs to minimize total tardiness // Ann. of Discrete Math. Amsterdam:North-Holland V. 1. 1977. P. 331-342.

43. Lawler E.L. Optimal sequensing of a single machine subject to precedence constraints // Management Sci. V. 19, 1973, P. 544-546.

44. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, Sequensing and scheduling: Algorithms and complexity, in Handbooks in Operation Research and Management Science, Vol 4, North Holland, 1993. P. 445-522.

45. Mosheiov G. Scheduling jobs under simple linear deterioration // Computers Operations Research. V. 21, N 6. 1994. P. 653-659.

46. Mosheiov G. V-shaped policies for scheduling deteriorating jobs // Oper. Res. V. 39, N 6. 1991. P. 979-991.

47. Moore J.M. An n job, one machine sequensing algorithm for minimizing the number of late jobs // Management Set. V. 15. 1955. P. 102-109.

48. Pilliboothamgudi, Sundararaghavan S., Kunnathur A.S. Single machine scheduling with start time dependent processing times: Some solvable cases // European Journal of Operational Research, V. 78, N. 3. 1994. P. 394-403.

49. Woeginger G.J. Scheduling with time-dependent execution times // Information Processing Letters, V. 54. 1995. P. 155-156.