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

ВВЕДЕНИЕ

1. ПОСТАНОВКА ОБОБЩЕННОЙ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ II

1.1. Основные понятия

1.2. Решение вспомогательной задачи теории расписаний

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

2. ДВОЙСТВЕННАЯ ОБОБЩЕННАЯ ЗАДАЧА ТЕОРИИ РАСПИСАНИЙ

2.1. Методы негладкой оптимизации при решении дискретных задач математического программирования

2.2. Промежуточная двойственная задача теории расписаний. Аддитивная целевая функция

2.3. Промежуточная двойственная задача теории . расписаний. Минимизация общего времени выполнения системы работ

3. АЛГОРИТМИЧЕСКАЯ И ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДОВ

РЕШЕНИЯ РЯДА ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ

3.1. Задача определения очередности выполнения работ на одной машине

3.2. Динамическая задача выполнения ^ работ с помощью М/ машин

3.3. Экспериментальное исследование эффективности алгоритмов

4. ЗАДАЧА ПЕРСПЕКТИВНОГО КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ СТРОИТЕНЬНО-МОНТАШЗЫХ РАБОТ ДОМОСТРОИТЕЛЬНОГО

КОМБИНАТА

4.1. Описание и постановка

4.2. Алгоритмы решения

Во всей системе народнохозяйственного планирования СССР важное место занимает календарное и объемно-календарное планирование, оперативное управление. Задачи календарного планирования (КП) входят в состав, как определяющая часть, многих АСУ.

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

Предав том исследования задач КП, их математической природы является зародившаяся недавно теория расписаний. Дальнейшее развитие теория расписаний и календарное планирование в нашей стране получили благодаря работам Михалевича B.C., Танаева B.C., Шкур -бы В.В., Подчасовой Т.П., Гордона B.C., Шафранского Я.М., Кук -сы А.И., Мироносецкого Н.Б., Португала В.М. и др. [48,52,62,63, 69,71J . Известны и зарубежные публикации [31,64,79,80] .

Кроме КП существуют многие другие сферы применения ТР. К задачам TP относят распараллеливание алгоритмов на множестве элементарных операторов [4,5] , планирование работы вычислительной системы в мультипрограммном режиме [5,40] и т.п.

При решении задач TP нашли применение различные методы [7,31, 42,62,63,69,70] . Задачи TP сводились к линейным и линейным целочисленным задачам. Для некоторых из постановок был использован аппарат динамического программирования. Большое распространение по-, лучил подход определения точных решений методом последовательного конструирования, анализа и отсеивания вариантов и его частным случаем - методом ветвей и границ. Некоторые задачи решались алгоритмами, максимально использующими юс собственные свойства.

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

Отметим наметившиеся в последнее время новые подходы к решению задач теории расписаний:

- симультативные методы [41,61^ - формирование (с помощью датчика случайных чисел) на каждой симуляции (при каждом испытании) технологически-допустимых расписаний с проверкой на ресурсную допустимость;

- вероятностно-приближенные методы [ 72 ] , основанные на имитационном моделировании программируемых систем и в которых определяются оценки стратегий ситуационного управления,*

- метод ветвей и границ с динамической оценкой на промежуточных множествах ветвления [15,16,48,79] ;

- £ - эффективный алгоритм, дающий приближенное решение с гарантированной точностью [12,13] ;

Как бы в стороне от общей массы задач КП и оперативного управления стоят задачи КП в строительстве, дяя решения которых применялись многие методы,характерные для задач ТР вообще [п,57,58^.

Решение задач КП в строительстве сопряжено со многими трудностями:

- это, прежде всего, использование различных типов ресурсов;

- сложность учитываемых связей между работами;

- необходимость рассматривать различного рода неформализуе-мые ситуации;

- многокритериальное^.

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

И как следствие, несмотря на достигнутые определенные успехи в области автоматизации календарного планирования в строительстве [ 11,35,58,65] , все же методы и модели КП достаточно широкого распространения в отрасли еще не получили, что объясняется не только причинами организационного характера, но и несовершенством предлагаемых методов, алгоритмов, математического обеспечения.

Для задач КП в строительстве, как и вообще для задач КП, оказались неприменимы искусственно привнесенные из математического программирования точные методы решения. Не дали желаемого эффекта и сетевые методы [ 54] .

Целью работы является:

- постановка обобщенной многоресурсной многосетевой задачи теории расписаний ("задачи ОМС ТР);

- исследование возможности решения задачи ОМС ТР путем перехода от дискретной задачи СМС ТР к двойственной непрерывной с последующим решением ее методами негладкой оптимизации,*

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

Методика исследований основана на теории расписаний, теории дискретного и динамического программирования, выпуклом анализе, численных методах негладкой оптимизации. При постановке и обосновании методов решения практических задач привлекались результаты из опыта создания АСУ в строительстве.

Научная новизна. Первым идею перехода от прямой дискретной задачи ТР к двойственной непрерывной предложил Фишер МЛ. [ 79].

В отечественных исследованиях этот подход получил дальнейшее развитие в работах Демина В.К. и Чеботарева A.C. (МФТИ) [15,1б] ,Ми-хале вича B.C., Куксы А.И. и Лаптина Ю.П. (ИК АН УССР) [ 34,48] . Решение линейных целочисленных задач методом ветвей и границ с вычислением оценок на вершинах предложил Лебедев С.С. (ЦЭМЙ) [l,36,37] . Характерные особенности этих исследований для задач TP: I. Используется только один тип ресурсов - нескладируемый не-возобновляемый при постоянной интенсивности его потребления. 2. В качестве целевых функционалов выступают: взвешенное и общее время (только у Демина В.К. и Чеботарева B.C.) выполнения системы работ, причем двойственная задача для второго функционала решается уже с увеличением размерности пространства двойственных переменных. 3. Задача TP представляется как специальная задача целочисленного линейного программирования с булевыми переменными. 4. Решение двойственной задачи служит оценкой снизу (на подмножествах допустимых расписаний) для решения прямой задачи TP в методе ветвей и границ. 5. Подход эффективен на задачах сравнительно незначительной размерности.

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

I. Для задачи ОМС TP задана система работ, выполняемая в определенный период времени, который разбит на равнозначные элементарные интервалы. На каждой работе, состоящей из частично упорядоченного множества операций, любая из которых выполняется непрерывно, используются ресурсы пяти типов: I) возобновляемые типа мощностей (ВТМ); 2) нескладируемые невозобновляемые; 3) складируемые невозобновляемые; 4) нескладируемые невозобновляемые финансовые; 5) складируемые невозобновляемые материальные. На начало и конец работы могут быть наложены директивные сроки начала и окончания. Допускается переменная интенсивность выполнения операций. Необходимо указать расписание (тройку векторовх- моментов начал операций, интенсивностей ведения операций, видов применяемых ресурсов ВТМ), при котором достигается минимум взвешенного или общего времени выполнения системы работ.

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

2. Задача СМС ТР, учитывая характер использования ресурсов В1М, распадается на две последовательно решаемые задачи: основ -ную - собственно построение расписаний и вспомогательную - рас -пределение единиц ресурсов ВТМ по операциям.

3. Дня реализации двойственной задачи ОМС ТР предлагается воспользваться разработанным Шором Н.З. [46,75"] Ъ- алгоритмом -обобщенным градиентным спуском с растяжением пространства в направлении разности двух последовательных градиентов. Цромежуточная двойственная задача, возникающая на каждой итерации ъ- алгоритма решается алгоритмами последовательной оптимизации. Причем при минимизации функционала общего времени - без увеличения размерности пространства двойственных переменных, что очень существенно в условиях применения ъ- алгоритма.

4. Разработаны оригинальные алгоритмы приближенного решения двух частных - по отношению к задаче СМС ТР - задач ТР, простых по содержанию, но представляющих несомненнй научный и практический интерес. Основу алгоритмов составляют использование накопленной статистики о встречаемых значениях возможных решений, получаемых в результате многократного (на каждой итерации ъ-алгоритма) решения промежуточных двойственных; задач.

5. Задача ОМС ТР с некоторыми дополнениями является задачей оптимального календарного планирования строительно-монтажных работ (СМР) домостроительного комбината (ДСК). Предлагается, учитывая противоречивость ограничений (как правило на практике), ре -шать ее в диалоге человек-ЭВМ для разрешения компромиссных нефор-мализуемых ситуаций планирования. Причем на этапе построения оптимизационных расписаний, называемом генерацией расписаний, применяются выявленные в ходе многочисленных экспериментов на ЭВМ свойств методов обобщенного градиентного спуска (ОГС), большей степени ъ-алгоритма, по сбалансированности наличного и планируемого уровней потребления ресурсов. Впервые задача TP такой степени обобщения программно реализована в сочетании с ^алгоритмом.

Практическая ценность. Основная область применения - календарное планирование в строительном производстве. Результаты работы также могут быть использованы в программно-целевых методах планирования и управления научно-техническими программами, при планировании процесса прохождения заданий как на одно - так и многопроцессорных ЭВМ.

Реализация результатов исследования. Диссертационная работа выполнена в НИИ АСС Госстроя УССР в период с 1976 по 1984 гг. в соответствии с планами научно-исследовательских работ по темам, содержащим результаты: а) анализа математических моделей планирования СМР, б) постановки и алгоритмов решения комплексов задач календарного планирования СМР, в) разработки соответствующих пакетов прикладных программ.

Методика решения задачи перспективного календарного планирования СМР предложена для внедрения на Харьковском ДСК-I, а задача расчета оптимизационных календарных планов внедрена на Сургутском ДСК. Применение результатов подтверждено актами внедрения.

Апробация работы. Основные результаты работы докладывались и обсуждались на конференции молодых ученых НИИ АСС "Применение экономико-математических методов и ЭВМ в планировании и управлении строительством" (Киев, 1977), П-й Республиканской конференции "Вычислительная математика и современный научно-технический прогресс" (Киев, 1978), П-й Всесоюзной конференции "Црименение экономико-математических методов и ЭВМ в народном хозяйстве" (Москва, 1983), семинарах научного совета по проблеме "Кибернетика" АН УССР (Ж АН УССР, НИИ АСС Госстроя УССР, 1979 - 1984).

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

ЗАКЛЮЧЕНИЕ

В диссертации получены следующие результаты:

1. Осуществлена постановка и построена экономико-математическая модель обобщенной многоресурсной многосетевой задачи теории расписаний с переменной интенсивностью выполнения работ.

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

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

4. Исследованы и решены две простые по содержанию, но пред -ставляющие определенный научный и практический интерес, задачи ТР.

5. Используя идею перехода от дискретных задач к двойственным непрерывным, разработаны алгоритмы решения комплекса задач КП СМР ДСК с противоречивыми ограничениями в сочетании с методами ОГС и Т-алгоритмом.

6. Разработанные алгоритмы реализованы в виде двух комплексов программ.

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

1. Азарян Л.Л., Лебедев С.С., Местецкий Л.й. Решение целочисленных задач транспортного типа с использованием обобщенных множителей Лагранжа. - Экономика и мат.методы, 1974, т.ХШ, вып.4.

2. Алексеев О.Г., Григорьев В.Ф. Некоторые алгоритмы решения задач о покрытии и их экспериментальные исследования на ЭВМ. %р-нал вычислит.матем. и матем.физики, 1984, т.24, №10, с. 1565-1570.

3. Алексеев О.Г., Мержанов В.Ю. Алгоритм распределения по минимальному критерию. УСиМ, 1977, Ш, с.36-41.

4. Барский А. Б. Метод оптимального распределения работ в однородной вычислительной системе. Известия АН СССР. Технич.кибер-нет., 1974, JS5, с.133-138.

5. Барский А.Б. Планирование параллельных вычислительных процессов. М.: Машиностроение, 1980, 192 с.

6. Бурков В.Н. и др. Сетевые модели и задачи управоения. М. : Советское радио, 1967, 163 с.

7. Бушуев С.Д., Михайлов B.C. Разработка алгоритмов управления строительством. Киев: Буд!вельник, 1980, 135 с.

8. Визинг В.Т. О расписаниях, соблюдающих директивные сроки выполнения работ. Кибернетика, 1981, JH, с. 128-135.

9. Воропаев В.И. Модели и методы календарного планирования в автоматизированных системах управления строительством. М.: Строй-издат, 1975, 232 с.

10. Гене Г.В., Левнер Е.В. Дискретные оптимизационные задачи и эффективные приближенные решения. Известия АН СССР. Технич. кибернет., 1979, J£6, с.9-10.

11. Гене Г.В., Левнер Е.В. Приближенные алгоритмы некоторых универсальных задач теории расписаний. Известия АН СССР. Технич. кибернетика, 1978, Я6, с.38-43.

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

13. Демин В.К., Чеботарев A.C. Оптимизация обслуживания детерминированного потока требований. I Известия АН СССР. Технич.кибернет., 1976, М, с.193-197.

14. Демин В.К., Чеботарев A.C. Оптимизация обслуживания детерминированного потока требования. П Известия АН СССР. Технич. кибернет., 1976, Jfö, с.65-70.

15. Демин В.К. Метод отсечения для решения задач оптимального распределения ресурсов. Известия АН СССР. Технич.кибернет.,1973, №5, с.37-39.

16. Демин В.К., Малашенко Ю.Е. Получение оценочных решений дня задач оптимального резервирования. Известия АН СССР. Технич.кибернет., 1974, Ш, с. II2-II7.

17. Еремин И.И., Мазуров В.Д., Астафьев H.H. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983,336 с.

18. Зак Ю.А. Некоторые свойства задач теории расписаний. -Автоматика и телемеханика, 1978, Ш, с.123-132.

19. Зангвилл У.И. Нелинейное программирование. М.: Советское радио, 1973, 312 с.

20. Ильницкий А.Л. Многосетевая дискретная задача теории расписаний и метод ее оптимального решения. В кн.: Вычислительнаяматематика в современном научно-техническом прогрессе. П^я Республиканская конференция. Тезисы докладов. Киев, 1978, с.192.

21. Ильницкий А.Л. Исследование и разработка методов решения одного класса задач теории расписаний. В кн.¡Вторая конференция по оптимальному планированию и управлению народным хозяйством. Секция 6. - М.: 1983, с.68-69.

22. Ильницкий А.Л. Задача оптимального календарного планирования работы специализированной строительной организации. В кн.: Управление строительством. Экономика строительства, М.: ЦИНИС Госстроя СССР, 1978, с.15-17.

23. Ильницкий А.Л. Двойственность в целочисленном программировании при решении задач календарного планирования. В кн.: Исследование операций и АСУ, Киев*. КГУ, 1978, вып.II, с.75-81.

24. Ильницкий А.Л. Об одном подходе к решению задачи календарного планирования в строительстве. В кн.: Исследование операций и АСУ, Киев*. КГУ, 1976, вып.8, с.25-30.

25. Ильницкий А.Л. Универсальность и условия существования решений одного класса задач теории расписаний. В кн.: Исследование операций и АСУ, Киев: КГУ, 1980, вып.10, с.38-46.

26. Ильницкий А.Л. Оценка целевой функции одной дискретной задачи теории расписаний. В кн.: Исследование операций и АСУ, Киев: К1У, 1979, еыпЛЗ, с.54-59.

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

28. Кибалов Е.В., Хуторецкий A.B. Задача объемно-календарного планирования строительного производства. Экономика и мат. методы, 1976, т.12, вып.6, с.1092-1100.

29. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука, 1975, 359 с.

30. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969, 368 с.

31. Кристофидес Н. Теория графов: Алгоритмический подход. -М.: Мир, 1978, с.

32. Кукса А.И., Лаптин Ю.П. Использование динамического программирования при двойственном подходе к решению задачи календарного планирования. Известия АН СССР. Технич. кибернет., 1981, М, с.79-85.

33. Куликов Ю.Я. Имитационные модели и их применение в управлении строительством. Л.: Стройиздат, Ленинградское отделение, 1983, 224 с.

34. Лебедев С.С. Целочисленное программирование и множители Лагранжа. Экономика и мат.методы, 1974, т.10, вып.З, с.592-609.

35. Лебедев С.С., Шейнкман O.K. Двойственный подход в целочисленном программировании. Известия АН СССР. Технич. кибернет., 1983, Ш, с.181-187.

36. Левин М.Ш. Детерминированные задачи планирования при идентичных процессорах и одновременном поступлении заявок. -Известия АН СССР. Технич. кибернет., 1982, М, с.51-57.

37. Левин М.Ш. Об эффективном решении некоторых задач теории расписаний на сетях. Кибернетика, 1980, Ш, с.131-135.

38. Липаев В.В. Распределение ресурсов в вычислительных системах. -М.: Статистика, 1979, 247 с.

39. Лихтенштейн В.Е. Дискретность и случайность в экономико-математических задачах. М.: Наука, 1973, 375 с.

40. Лурье А.Л. О некоторых задачах календарного планирования.-В сб.: Цроблемы кибернетики, М.: Наука, 1962, вып.7, с.201-208.

41. Михалевич B.C. и др. Пакет прикладных программ ДИСПРО, предназначенный для решения задач дискретного программирования.

42. Кибернетика, I981, Ш, с.117-137.

43. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. I-Кибернетика, 1965, Ж, с.45-56.

44. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. П-Кибернетика, 1965, Ш, с.85-88.

45. Михалевич B.C. и др. Вычислительные методы выбора оптимальных проектных решений. Киев*. Наукова думка, 1977, 177 с.

46. Михалевич B.C., Волкович В.Я. Вычислительные методы исследований и проектирования сложных систем. М.: Наука, 1982, 287 с.

47. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. -М.: Наука, 1983 , 208 с.

48. Нейлор Т. Машинные имитационные эксперименты с моделями экономических систем. М.: Мир, 1975,

49. Основы теории вычислительных систем. М.: Высшая школа, 1978, 408 с.

50. Пирьянович В.А. Машинные эксперименты по решению задач ЦЯП с помощью локально-стохастических алгоритмов. .й&грнал вычис-лительн.матем. и матем.физики, т.19, Й2, 1979, с.79-87.

51. Подчасова Т.П., Португал В.М. и др. Эвристические методы календарного планирования. Киев*. Техника, 1980, 140 с.

52. Раков Ю.В. и др. Методические рекомендации по использованию системы программ, расширяющих возможности языка Фортран. -Киев: НИИ АСС Госстроя УССР, 1979, 23 с.

53. Рекомендации по применению в строительстве разработанных в странах членах СЭВ методов алгоритмов и программ решения многосетевых и многоцелевых задач с учетом рационального использования ресурсов. - Киев: НИИ АСС Госстроя УССР, 1970, с. 270.

54. Романовский И.В. Алгоритм решения экстремальных задач.1. М.: 1977, 325 с.

55. Рощин В.А., Сергиенко И.В. Об одном подходе к решению задач о покрытии. Кибернетика, 1984, JK3, с.65-69.

56. Рыбальский В.И. Автоматизированные системы управления строительством. Киев: Вища школа, 1979, с.497.

57. Рыбальский В.И. Кибернетика в строительстве. Киев: Бу-Д1вельник, 1975, 232 с.

58. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. Киев: Наукова думка, 1980, 274 с.

59. Сергиенко И.В., Кастпицкая М.Ф. Модели и методы решения на ЭЕМ комбинаторных задач оптимизации. Киев: Наукова думка, 1981, с.287.

60. Сытник В.Ф. АСУП и оптимальное планирование. Киев: Вища школа, 1977, 312 с.

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

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

63. Теория расписаний и вычислительные машины. М.: Наука, 1984, 335 с.

64. Ушацкий С.А. Выбор оптимальных решений в управлении строительным производством. Киев: Буд1вельник, 1974, 168 с.

65. Фридаан H.A., Вотяков A.A. Дискретные задачи и методы ветвей и границ. Экономика и мат. методы, 1974, т.Х, вып.З, с.611-620.

66. Хедли Дж. Нелинейное и динамическое программирование. -М.: Мир, 1967, 506 с.

67. Чеботарев A.C. Последовательная оптимизация в одной задаче календарного планирования. Известия АН СССР, Технич.кибер-нет., 1975, Ш, с.32-38.

68. Шкурба В.В. и др. Задачи календарного планирования и методы их решения. Киев: Наукова думка, 1966, 155 с.

69. Шкурба В.В. Вычислительные схемы решения задач теории расписаний. Кибернетика, 1965, ЖЗ, с.72-76.

70. Шкурба В.В. и др. Планирование дискретного производства в условиях АСУ. Киев: Техника, 1975, 295 с.

71. Шкурба В.В., Селивончик В.М. Расписания. Имитационное моделирование и оптимизация. Кибернетика, 1981, №1, с.91-96.

72. Шор Н.З. Црименение метода градиентного спуска для решения сетевой транспортной задачи. В кн.: Материалы научного семинара по теорет. и прикл. вопросам кибернетики и исслед. операций: Науч. совет по кибернетике АН УССР, Киев, 1962, вып.1, с.9-17.

73. Шор Н.З. Применение обобщенного градиентного спуска в блочном программировании. Кибернетика, 1967, ЛВ, с.53-55.

74. Шор Н.З. Методы минимизации недеференцированннх функций и их приложения. Киев: Наукова думка, 1979, 200 с.

75. Fisher M.L. Optimal solution of scheduling problems using Lagnrange multipliers. Part 11* Lect. Notes Econ.and Math. Syst., 1973, 86, p.294-318.

76. Held M., Wolfe P., Crowder H. Validation of subgradient optimization. Math. Program., 1974, 6, No.1, p. 62-88.

77. Lawler S.L., Moore <J«M. A functional equation and itsapplication to resource allocation and sequencing problems. Management Science, 1969, 16, No«1, p. 77-84.