автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Задачи распределения ресурсов и упорядочения работ в сетевых канонических структурах

ВВЕДЕНИЕ.

ГЛАВА 1. ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ И УПОРЯДОЧЕНИЯ РАБОТ.

1.1 Классические задачи распределения ресурсов и упорядочения работ.

1.2 Математические модели и методы решения задач распределения ресурсов и упорядочения работ.

1.2.1 Задачи распределения ресурсов.

1.2.2 Задачи упорядочения.

1.3 Задача распределения ресурсов и упорядочения работ в сетевых канонических структурах.

ВЫВОДЫ ПО ГЛАВЕ 1.

ГЛАВА 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И ПОСТАНОВКИ ОПТИМИЗАЦИОННЫХ ЗАДАЧ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ И УПОРЯДОЧЕНИЯ РАБОТ В СЕТЕВЫХ КАНОНИЧЕСКИХ СТРУКТУРАХ.

2.1 Общая математическая .модель распределения ресурсов и упорядочения работ.

2.2 Исследование математической модели.

2.3 Постановки оптимизационных задач.

Выводы по главе 2.

ГЛАВА 3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ И УПОРЯДОЧЕНИЯ РАБОТ.

3.1 Взаимно однозначное соответствие между множеством допустимых решений задачи упорядочения и множеством решений задачи о назначениях.

3.1.1 Установление взаимно однозначного соответствия.,.

3.1.2Построение множества всех решений задачи о назначениях.

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

3.3. Перестановочные процедуры решения задач распределения ресурсов и упорядочения работ.

Выводы по главе 3.

ГЛАВА 4. ДИАЛОГОВЫЕ ПРОГРАММНЫЕ СРЕДСТВА ПРИНЯТИЯ РЕШЕНИЙ ДЛЯ ЗАДАЧ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ И УПОРЯДОЧЕНИЯ РАБОТ.

4.1. Архитектура диалоговой системы.

4.2. Типовые сценарии.

4.3. Составление план графиков работы подразделений.

4.4 Планирование сборочных операций консольно-фрезерных станков (узловая и генеральная сборка).

Выводы по главе 4.

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

В различных моделях природа ресурсов может быть различна. Это и ресурсы типа «материалы», и энергетические ресурсы, и трудовые ресурсы, и время. В производственных системах в качестве ресурсов могут выступать обслуживающие приборы. Экстремальные задачи распределения ресурсов возникают в связи с тем, что объемы ресурсов являются ограниченными. При распределении ограниченных ресурсов возникают конфликтные ситуации. Сложность составления расписаний определяется еще и тем, что необходимо не только обеспечить необходимые условия проведения всего множества операций, но и согласовать их во времени. Основной целью планирования является создание такого расписания, которое обеспечит выполнение всего комплекса работ с минимальными затратами.

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

Основными методами управления в этих моделях являются метод критического пути (при заданных фиксированных длительностях работ) и метод оценки и пересмотра проектов (при неопределенности в длительностях работ).

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

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

Развитием этой научной области занимались такие ученые как Шкурба В.В., Подчасова Т.П., Бурдюк В.Я., Танаев B.C., Гордон B.C., Михалевич B.C., Шор Н.З., Мироносецкий Н.Б., Поругал В.М. и многие другие. Из зарубежных ученых это Конвей Р., Джонсон Б., Максвелл У., Гиффлер Б., Томпсон Ж. И другие. Следует отметить школу нижегородского университета и ученых Батищева Д.И., Прилуцкого М.Х., Когана Д.И., Федосенко Ю.С., которые рассматривали подобные проблемы.

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

• целевые разработки сложных систем (проектирование, опытное производство, испытания и т.д.);

• планирование деятельности предприятий типа НИИ, ОКБ, проектных институтов;

• строительство и монтаж промышленных и гражданских объектов;

• реконструкция и ремонт;

• подготовка и освоение производства новых видов продукции;

• материально-техническое снабжение крупных промышленных и гражданских объектов;

• ремонт промышленного оборудования;

• подготовка и проведение крупномасштабных мероприятий.

Цели и задачи исследования.

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

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

• проведена классификация моделей распределения ресурсов;

• проведена классификация и сравнительный анализ методов сетевого планирования;

• построена общая математическая модель и поставлены оптимизационные задачи распределения ресурсов и упорядочения работ в сетевых канонических структурах;

• разработаны методы решения задач рассматриваемого класса;

• создана диалоговая система решения задач сетевого планирования.

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

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

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

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

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

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

Практическая ценность.

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

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

Разработанная диалоговая система прошла апробацию на станкостроительном заводе «ЗеФС» г. Н.Новгород при планирование сборочных операций консольно-фрезерных станков и в ГУП ОКБМ им. Африкантова И.И. г. Н.Новгород при составлении план-графиков деятельности отделов предприятия.

Результаты диссертационной работы используются в учебном процессе Нижегородского государственного университета им. Н.И. Лобачевского на факультете вычислительной математики и кибернетики (курс «Математические основы информатики» раздел «Дискретные оптимизационные модели») и на радиофизическом факультете (курс «Моделирование сложных систем»).[124]

Научные результаты были изложены и опубликованы в 9 работах, обсуждались на Всероссийском совещании-семинаре «Математическое обеспечение информационных технологий в технике, образовании и медицине» (Воронеж, 1996г., 1997г.), на XII Международной конференции «Проблемы теоретической кибернетики» (Н. Новгород, 1999г.), на Всероссийской конференции «Интеллектуальные информационные системы» (Воронеж 1999), на конференции, посвященной 80-летию Ю.И.Неймарка (Н.Новгород, 2000), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.

Структура и содержание работы.

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

Основные результаты диссертационной работы заключаются в следующем:

• проведена классификация моделей распределения ресурсов и упорядочения работ;

• проведена классификация и сравнительный анализ методов сетевого планирования;

• исследованы методы решения задач упорядочения работ в конвейерных системах;

• построена общая модель распределения ресурсов и упорядочения работ в сетевых канонических структурах;

• модель исследована на существование допустимых решений;

• показано, что рассматриваемая проблема распределения ресурсов и упорядочения работ в сетевых канонических структурах относится к классу NP-трудных;

• предложен подход исследования и решения задач упорядочения основанный на установлении взаимно-однозначного соответствия между множеством допустимых решений конвейерной задачи Беллмана-Джонсона и множеством бистохастических булевых квадратных матриц;

• предложены алгоритмы переборного типа для решения задач упорядочения;

• рассмотрена возможность использования идеологии двойственности к решению поставленных задач;

96

Заключение

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

1. Ленина А.Я., Чернышева Г.Д. Об одном алгоритме решения задачи Джонсона // Тр. 4-й Межд. конф. женщин-матем. Волгоград, 27-31 мая, Т.4, Вып.1, Н.Новгород, 1997.- с. 82-86.

2. Ахьюджа Х.Н. Сетевые методы в проектировании и производстве.-М.: Мир. 1979.-63 8с.

3. Батищев Д.И., Громницкий B.C. Распределение ограниченных ресурсов по принципу гарантированного результата // В кн. Кибернетика и ВУЗ. Вып. 17. Томск. 1982.

4. Батищев Д.И., Гудман Э.Д., Норенков И.П., Прилуцкий М.Х. Метод декомпозиций для решения комбинаторных задач упоядочения и распределения ресурсов. Информационные технологии 1997 №1.

5. Батищев Д.И., Гудман Э.Д., Норенков И.П., Прилуцкий М.Х. Метод комбинированных эвристик для решения комбинаторных задач упорядочения и распределения ресурсов. Информационные технологии 1997 №2.

6. Батищев Д.И., Прилуцкий М.Х. Многокритериальное распределение разнородных ресурсов на совокупности канонических сетевых моделей// 33 Intern. Wiss. Koll. ТН Ilmenau, 1988.

7. Булгак А.С. Многокритериальная задача теории расписаний с ресурсами складируемого типа // АиТ.- 1987. №12.- С.143-146.

8. Вахания Н.Н. Построение сокращенного дерева вариантов для общей задачи теории расписаний//Дискр. Матем. Т.2.- Вып.З. 1990, с. 10-20.

9. Вахания Н.Н., Шафранский В .В. Алгоритмы решения обобщенных задач теории расписаний// Сообщения по прикладной матем. М.: ВЦ РАН, 1991, с. 1-46.11 .Витковский Я.Я. Основы сетевого планирования и управления // Рига, 1966.

10. Волчкова Г.П. Один метод построения допустимых расписаний. //Тез. докл. Гродн. гос. ун-т. Гродно, 1992.

11. Гейл Д. Теория линейных экономических моделей М.: Иностранная литература, 1963. 415с.

12. Гимади Э.Х. О некоторых моделях и методах планирования крупномасштабных проектов // Тр. Ин-та Новосиб. 1988. Т.10, с. 89-115.

13. Голенко Д.И. Статистическое моделирование в технико-экономических системах Л.: Изд-во Лен. ун-та. 1977. 264с.

14. Гревцов О.И. Нахождение оптимального решения многокритериальных задач//Вестн. Самарск. гос. тех. у-та,- 1998.-№6.-с.135-136.

15. Турин Л.С., Дымарский Я.С., Меркулов А.Д. Задачи и методы оптимального распределения ресурсов.- М.:Сов. радио,1968.

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

17. Давыдов Э.Г. Игры, графы, ресурсы.- М.: Радио и связь, 1981.

18. Давыдов Э.Г. Исследование операций. М.: Высш. шк., 1981.- 383с.

19. Давыдов Э.Г. О распределении ресурсов на сетях./Сб. Системы распределения ресурсов на графах.-М.: ВЦ АН СССР, 1970.

20. Давыдов Э.Г., Большаков С.Ю. Теоретико-групповые методы агрегирования в сетевых задачах.- М.: ВЦ АН СССР, 1986.

21. Давыдов Э.Г., Злобина С.В. Применение геометрического программирования к сетевому планированию.- М.: ВЦ АН СССР, 1981.

22. Давыдов Э.Г., Исиченко И.В. Некоторые дискретные задачи теории управления.- ВЦ АН СССР, 1988.

23. Дегтярев Ю.И. Исследование операций. М.: Высшая школа, 1986.

24. Исследование операций. Под ред. Дж. Моудера, С. Эдмаграби- М.: Мир, 1981.

25. Калачев В.Н., Кривоноженко В.Е., Немчинов Б.В. Задачи планирования в гибких производственных системах // АиТ. 1995. №6, с. 155-164.

26. Козлов М.К., Шафранский В.В. Календарное планирование выполнения комплексов работ при заданной динамике поступления складируемых ресурсов.- Известия АН СССР. Технич. кибернетика, 1977,№4, с. 75-81; 1977, №51, с. 38-43.

27. Компьютер и задачи выбора. М.:Наука,1989.

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

29. Кривцов A.M., Шеховцев В.В. Сетевое планирование и управление -М.: Экономика. 1978. 191с.

30. Кропачев С.В., Наумов Е.А. Программно-целевое управление решением научно-технических проблем / АН СССР Сиб. Отд. Ин-т эконом.и орг. пром. пр-ва. Новосибирск.: Наука Сиб. отд. 1989.

31. Кумагина Е.А. Задачи распределения ресурсов и упорядочения работ // Вычислительная математика и кибернетика 2000: Конференция, посвященная 80-летию Ю.И.Неймарка/ Тезисы докладов. Нижний Новгород: Изд-во ННГУ, 2000. С.49.

32. Кумагина Е.А. Об одном подходе к решению задач упорядочения. // Труды Всероссийской конференции "Интеллектуальные информационные системы" Воронеж 23-25 июля 1999. С.61-63

33. Курицкий Б .Я. Методы оптимизации сетевых планов.-Л.:ЛДНТП, 1976. 31с.

34. Левнер Е.В., Немировский А.С. Задача севого планирования в постановке «точно вовремя» и потоковые алгоритмы ее решения.// Численные методы оптимизации и анализа. Новосибирск: Сиб. энерг. ин-т, 1992, с. 18-35.

35. Липский В. Комбинаторика для программистов М.:Мир, 1988.

36. Майзер X., Эйджин Н., Тролл Р. Исследование операций / в 2-х томах. Пер. с англ. М.: Мир,1981.

37. Максимов Ю.И. Сетевые модели в перспективном планировании отраслевых систем- Новосиб.: Наука Сиб. Отд. 1979. 143с.

38. Мироносецкий Н.Б. Экономико-математические методы календарного планирования.- Новосибирск: Наука, 1973.

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

40. Мищенко А.В. Устойчивость решений задачи оптимального распределения ресурсов при динамичеком изменении структуры сети-М.: ВЦ АН СССР 1980. 12 с.

41. Мищенко А.В., Сушков Б.Г. Минимизация времени выполнения работ, представленных сетевой моделью, при нефиксированных параметрах сети- М.: ВЦ АН СССР 1980. 25 с.

42. Новицкий Н.И. Сетевое планирование и управление производством -Минск: Беларусь 1976. 80с.

43. Палов А.А., Мисюра Е.Б., Михайлов В.В. Исследование задачи минимизации суммарного взвешенного момента окончания выполнения множества заданий с директивными сроками. // Киевский политехи, инт. Киев, 1993.

44. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация М.: Мир, 1985.

45. Попова Е.В. Исследование мощности множества альтернатив двукритериальной задачи инвестора. // Карачаево-Черкесский Тех. Ин-т.-Черкесск, 1996.16с.

46. Португал В.М., Семенов А.И. Модели планирования на предприятии-М.: Наука 1978. 269с.

47. Поспелов Г.С., Гейман А.И. Автоматизация процессов управления разработками больших систем или сложных комплексов.- М.: Известия АН СССР. Техническая кибернетика. 1963.

48. Поспелов Г.С., Ириков В.А., Курилов А.Е. Процедуры и алгоритмы формирования комплексных программ.- М.: Наука. 1985. 424с.

49. Прилуцкий М.Х. Математическая модель многокритериального распределения ресурсов на сетях и условие ее разрешимости // Сб. Принятие оптимальных решений в экономических системах. Горький, 1985, с. 62-65.

50. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах // Автоматика и телемеханика. 1996, №2. С. 24-29.

51. Прилуцкий М.Х., Кумагина Е.А. Задача упорядочения работ как задача о назначениях // Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. Изд-во ННГУ, 1999. Вып.2(21). С.270-275.

52. Прилуцкий М.Х., Кумагина Е.А. Перестановочные процедуры решения задач распределения ресурсов. Межвузовский сборник научных трудов «Прикладные задачи моделирования и оптимизации» ч.П, Воронеж, 2000. С.81-90.

53. Прилуцкий М.Х., Кумагина Е.А., Попов Д.В. Многостадийные задачи распределения и упорядочения // Тезисы докладов XII Международной конференции "Проблемы теоретической кибернетики", часть II М.: Изд-во механико-математического ф-та МГУ, 1999. С. 193

54. Прилуцкий М.Х., Тарбеев А.Ф. Годовое и оперативное планирование и управление НИОКР в условиях НПО // Сб. Анализ и моделирование экономических процессов. Горький, 1984, с. 68-73.

55. Протасов В.Н., Жердзинский И.Ю. Оптимизация функционирования конвейерной производственной системы. Систем, моделир. 1991 №18.

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

57. Севастьянов С.В. Эффективное построение расписаний в системах открытого типа. Сиб. ж. иссл. операций 1991-1 №1.

58. Сетевое планирование и управление опытным производством . Сб статей-М.: Экономика, 1979. 151с.

59. Сетевое планирование при ограниченных нескладируемых ресурсах. Сб. статей под ред. Л.Я. Лефмана.- Новосибирск 1971.

60. Смоляр Л.И Оперативно-календарное планирование. М.: Экономика, 1979.

61. Смоляр Л.И. Теория расписаний и управление. М.: Знание, 1977.

62. Сорокин С.В. Разностные алгоритмы распределения неоднородных целочисленных ресурсов.// Изв. РАН Теория и системы управления .-1995.-№6.-с. 218-222.

63. Танаев B.C. Теория расписаний. М.:Мир,1988.

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

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

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

67. Теория расписаний и вычислительные машины. Под ред. Э.Г. Коффмана.- М.:Наука, 1984.

68. Топка В.В. вероятностная модель планирования исследований и разработок с линейными ограничениями.// АиТ. 1997. №4 с.232.

69. Черенков А.П. Задачи распределения разнотипных ресурсов с насыщением //Журнал вычисл.мат. и мат. физ. 1988. Т. 28, №7, с. 11021107.

70. Шахлевич Н.В. Оптимальное обслуживание двух требований в неоднородных системах с прерываниями // 6 Конф. Мат. Беларуси Тез докл. 4.4/ Гродн. Гос. Ун-т . Гродно, 1992. С 105.

71. Шмелев В.В. Динамические задачи календарного планирования // АиТ.-1997.-№1.-с.121-126.

72. Шмелев В.В. Точные штрафные функционалы в задачах календарного планирования // АиТ.- 1999.-№9.-с. 107-114.

73. Экономико-математические модели и методы // Сборник научных трудов. Воронеж ВГТУ 1989

74. Юдин Д.Б., Гольдштейн Е.Г. Линейное программирование (теория, методы, приложения).- М.: Наука, 1969.

75. Abdul-Razaq T.S., Potts C.N. Dynamic Programming State-Spase Relaxation Method For Single-Machine Scheduling // J. Oper. Res. Soc.- 1988.- Vol. 39.-p.l41-152.

76. Antill J.M., Woodhead R.W. Critical Path Methods in Construction Practice, Wiley, New York, 1970.

77. Archibald R.D., Villoria R.L. Network-Based Management Systems (PERT/CPM), Wiley, New York, 1968.

78. Artentano Vinicius A., Ronconi Debora P. Taby-search for total tardiness minimization in flowshop problems // Сотр. and Oper. Res.- 1999.- 26, №3, p.219-235.

79. Bar-Ilean, Peleg D. Scheduling job using common resources // Inf. And Сотр. 1996.-№1, p. 52-61.

80. Bellman R. Mathematical Aspects of Scheduling Theory I I J. Soc. Indust. and Appl. Math. 1956. V.4 №3. p. 168-205.

81. Bellman R., Gross O. Some Combinatorial Problems Arising in the Theory of Multistage Processes // J. Soc. Indust. and Appl. Math. 1945. V.2 №3. p. 175-183.

82. Biskup Dirk, Cheng T.C. Edwin, Multi-machine scheduling with earliness, tardiness and complexion time penalties // Сотр. and Oper. Res.- 1999.- 26, №1, p.45-57.

83. Chun Y., Moskowitz H., Plante R. Sequencing a set of alternatives under time constraints // J. Oper. Res. Soe. 1995.- №6, p. 1133-1144.

84. Daniel Richard L., Hua Stella Y., Webster Scott. Heuristics for parallel-machine flexible-resource scheduling problems with unspecified job assignment // Сотр. and Oper. Res.- 1999.-26, №2, p. 143-155.

85. Emmons H. One-Machine Sequencing to Minimize Certain Functions of Job Tardiness // Oper. Res. 1969. V.17 №4. p. 701-716.

86. Hariri A.M.A., Potts C.N. Single-machine scheduling with deadlines to minimize the weigthed number of tardy jobs // Man. Sci.- 1994.- Vol.40.-№12.-p.l712-1719.

87. Healy Thomas L. Activity subdivision and PERT probability statements // Oper. Res. 1961. V.9№3.

88. Hoogeveen J.A. Oosterhout M., VeldeS.L. A new lower bounds approach for single-machine multicriteria scheduling // Rept/ Cent. Math, and Сотр.Sci.- 1990.-№BS-R9026.- p. 1-8.

89. Hoogeveen J.A. Oosterhout M., VeldeS.L. New lower and upper bounds for scheduling aroound small common due date // Rept/ Cent. Math, and Comp.Sci.- 1990.- №BS-R9030.- p. 1-11.

90. Janiak A., Kobylaski P. Генетический алгоритм решения перестановочной задачи теории расписаний с ресурсами // Zesz. Nauk. Mech. PSL- 1993.-№4, p. 99-114.

91. Johnson S.M. Optimal Two- and Three-Stage Production Schedules with Setup Times Included // Nav. Res. Log. Quart. 1954 V.l №1. p. 61-68.

92. Khachaturov V.R. Multiextremal allocation problems (models and solutions) // Stud. sci. math, hung.- 1992.- № 3, p. 243-260.

93. Lambourn S. Resource allocation and multi-project scheduling. A new tool in planning and control // Comp.J. 1963. № 3.

94. Man Sungsu , Ishii Hiroaki Lexicographical scheduling problem on three machine open shop // Math. Jap.-1991.- 36- №6. p.1001-1014.

95. Manne A.S. On the Job-Shop Scheduling Problem // Oper. Res.- 1960.-V.8 №2. p. 219-233.

96. Michael David J., Kamburowski J., Stallmann M On the minimum dummy-arc problem // Rech. oper.-1993.- №2, p. 153-168.

97. Nowicki Eugeniusz Задачи теории расписаний с учетом изменения моментов поступления задач // Arch Autom: Rob 1991.- 36, №2, р.303-312.

98. Potts C.N., L.N. Van Wassenhove Algoritm For Scheduling a Single Machine To Mminimize the Weigthed Number of Late Jobs // Man. Sci.-1988.- Vol.34.-p.843-858.

99. Rinnooy Kan A.H., Lageweg B.J., Lenstra J.K. Minimizing Total Costs in One-Machine Scheduling // Rech. oper.-1975. vol 23 №5, p. 908-925.

100. Rogers V.R., White K.P. Algebraic, Mathematical Programming and Network Models of the Deterministic Job-Shop Scheduling Problem // IEEE Trans. On Systems, Man, 1991, №3, p. 693-697.

101. Sharage L. Solving resource-constrained network problem by implicit enumeration: nonpreemptive case // Op. Res.- 1970,- №2, p. 263-278.

102. Velde S.L. & de. Dual composition of a single-machine scheduling problem // Math. Programming A. -1995-69, №3, p.413-428.

103. Volegant A., Teerhuis E. Improved heuristics for the n-job single-machine weighted tardiness problem// Сотр. and Oper. Res.- 1999.- 26, №1, p.35-44.

104. Yu Chang Sok, Zimmermann Karol Optimal choice of parametrs in machine-time scheduling problem with penaltized earliness in start and tardiness in completing the operations // Acta Univ. Carol. Math, and Phys.-1992.-33, №l.-p.53-61.

105. Yu G. Min-max optimization of several classical discrete optimization problems // J. Optimize. Theory and App.- 1998.- №l.-p.221-242.