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

• Кварацхелия, Александр Гонерович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Кварацхелия, Александр Гонерович

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Методы решения задачи минимизации суммарного запаздывания для одного прибора и задачи разбиения»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Кварацхелия, Александр Гонерович

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Кварацхелия, Александр Гонерович, 2007 год

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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