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

ВВЕДЕНИЕ.

ГЛАВА I. ЛЕКСИКОГРАФИЧЕСКАЯ МИНИМИЗАЦИЯ НА ПЕРЕСТАНОВКАХ

§ I. Основные понятия. 1*

§ 2. Постановка задачи. Векторные приоритето-порождающие функционалы.

§ 3. Минимизация векторных приоритето-порождающих функционалов.

§ 4. Минимизация векторных функционалов специального вида.

ГЛАВА П. ОПИСАНИЕ МНОЖЕСТВА ВСЕХ ОПТИМАЛЬНЫХ ПЕРЕСТАНОВОК.

§ I. Описание множества -Я* при заданном группировании элементов.

§ 2. ^-допустимые графы.5?

§ 3. Преобразование ориентированных графов.

§ 4. Описание множества -Я* при древовидных и последовательно-параллельных ограничениях предшествования.

§ 5. Общий случай. Построение множества . . . . 82.

§ 6. Минимизация максимального штрафа на -Я

ГЛАВА Ш. РЕШЕНИЕ НЕКОТОРЫХ КЛАССОВ ДВУХКРИТЕРИАЛЬНЫХ

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

§ I. Постановка задачи. Схема решения.

§ 2. Задачи на перестановках.10Z

§ 3. Сведение к задаче о назначении.

§ 4. Минимизация максимального штрафа.

§ 5. Нефиксированные длительности обслуживания

Многие практические задачи оптимального планирования, проектирования и управления приводят к необходимости рассмотрения многокритериальных оптимизационных задач в той или иной постановке. Несмотря на то, что к настоящему времени общая теория многокритериальной оптимизации достаточно развита [5У36, 39,^45,49,60,95], по-прежнему актуальны вопросы разработки практически приемлемых методов решения многих классов многокритериальных задач с учетом их специфических особенностей.

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

Как самостоятельный раздел исследования операций, теория расписаний интенсивно развивается на протяжении последних 30 лет. Состояние этой теории достаточно полно отражено в монографиях [Z3,5*1, 48,50] . Рассмотрению многокритериальных задач теории расписаний уделялось явно недостаточное внимание. Лишь в последнее время многокритериальные задачи начали привлекать внимание специалистов, что объясняется с одной стороны возросшими потребностями решения практических задач, а с другой - значительными успехами в области решения однокритериальных задач теории расписаний. Задачи с несколькими упорядоченными по важности критериями рассматривались в [22>231,65,66,7^,92,99, iOZ], а с неупорядоченными - в [76, 78, 30, 98, Юъ , 1052,

Поскольку большинство задач теории расписаний являются дискретными экстремальными задачами [ 31 ], то для их решения можно использовать универсальные методы (метод динамического программирования [3,4 ] , метод ветвей и границ [SO], метод последовательного анализа вариантов /33,35"J, метод построения последовательности решений[1S,19]и т.п.). Применение этих методов, как правило, не дает желаемого эффекта, т.к. за практически приемлемое время удается решать задачи небольшой размерности. Поэтому особый интерес представляет выделение классов задач, допускающих построение эффективных алгоритмов решения, и построение таких алгоритмов.

Установить принципиальную сложность различных дискретных экстремальных задач (в том числе и теории расписаний) позволила развитая в начале семидесятых годов теория полиномиальной сводимости [1, 15,27, 50]. Как отмечалось в работе [79] , из 4536 задач теории расписаний 3688 являются NT -трудными, для 416 известны эффективные (с полиномиальными оценками временной сложности) алгоритмы, а для остальных пока не установлено являются ли они А/Р-трудными и не известно эффективных алгоритмов решения (списки ЛАЯ-трудных задач теории расписаний приведены также в [15,85,87]).

Отметим, что некоторые важные классы задач теории расписаний могут быть сформулированы в терминах минимизации функционалов на множестве перестановок элементов конечного множества, и для их решения могут быть использованы результаты по исследованию экстремальных задач на перестановках, полученные, в частности, белорусскими математиками [ 16,S0} 32, 43, 46 J.

В диссертации рассматриваются задачи лексикографической минимизации на перестановках и двухкритериальные задачи теории расписаний (о задачах лексикографической оптимизации см., например, [Z9Z1,26,38,51,53,54] ).

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

1. Ахо А., Хопкрофт Да., Ульман Ддс. Построение и анализ вычислительных алгоритмов,- М.: Мир, 1979.- 536 с.

2. Бабинцев B.C., Подиновский В.В., Шорин В.Г. Выбор решений по многим критериям, упорядоченным по важности.- М.: ИУНХ, 1977.44 с.

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

4. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования.- М.: Наука, 1965.- 455 с.

5. Березовский Б.А., Борзенко В.И., Кемпнер JI.M. Бинарные отношения в многокритериальной оптимизации.- М.: Наука, 1981.- 149 с.

6. Визинг В.Г. 0 расписаниях, соблюдающих директивные сроки выполнения работ.- Кибернетика, 1981, №1, с.128-135.

7. Визинг В.Г., Кяипкер И.А. Полиномиальный алгоритм решения задачи Гэри-Джонсона о составлении расписания.- Сообщ. АН Гр.ССР, 1981, т.102, ЖЕ, с.29-32.

8. Вилкас Э.И., Майминас Е.З. Решения: теория, информация, моделирование.- М.: Радио и связь, 1981.- 328 с.

9. Гермейер Ю.Б. Введение в теорию исследования операций.- М. : Наука, 1971.- 383 с.

10. Гольдгабер Е.М. Задача минимизации времени исполнения проекта работ, заданного деревом.- Кибернетика, 1977, №2, с.102-107.

11. Гордон А.Я. Один алгоритм решения минимаксной задачи о назначении.- В кн.: Исследования по дискретной оптимизации. М.: Наука, 1976, с.327-333.

12. Гордон B.C. Некоторые свойства последовательно-параллельных графов.- Изв. АН БССР. Сер. физ.-мат. наук, 1981, №1, с.18-23.

13. Гордон B.C., Шафранский Я.М. Оптимальное упорядочение при последовательно-параллельных ограничениях предшествования.- ДАН БССР, 1978, т.22, №3, с.244-247.

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

15. Демиденко В.М. Специальные случаи задачи о бродячем торговце с симметрической матрицей.- ДАН БССР, 1980, т.24, №2, с.105-108.

16. Диниц Е.А. О решении двух задач о назначении.- В кн.: Исследования по дискретной оптимизации. М.: Наука, 1976, с.333-348.

17. Емеличев В.А. Дискретная оптимизация. Последовательные схемы решения. X.- Кибернетика, 1971, №6, с.109-121.

18. Емеличев В.А. Дискретная оптимизация. Последовательные схемы решения. П.- Кибернетика, 1972, №2, с.92-103.

19. Емеличев В.А., Супруненко Д.А., Танаев B.C. О работах белорусских математиков в области дискретной оптимизации.- Изв. АН СССР. Техническая кибернетика, 1982, Л6, с.25-45.

20. Еремин И.И. О задачах последовательного программирования.-Сибирский матем. журнал, 1973, т.Х1У, II, с.53-63.

21. Зиндер Я.А. Оптимизация обслуживания требований в детерминированной системе обслуживания с одинаковыми обслуживающими приборами.- В кн.: Математическое обеспечение АСЛ1. Москва-Горький, 1978, с.45-47.

22. Зиндер Я.А., Подчасова Т.П. Минимизация упорядоченных критериев в одностадийных детерминированных системах обслуживания.- В кн.: Автоматизированные системы управления и обработки данных. Киев, 1976, с.20-25.

23. Иоффе Э.Г. Алгоритм для определения всех оптимальных расписаний в двухоперационной задаче Ддонсона.- Автоматика и телемеханика, 1973, №7, с.95-101.

24. Калашников В.В. Некоторые задачи лексикографической минимизации.- В кн.: Оптимизация. Новосибирск, 1978, Л21 (38), с.109-120.

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

26. Ковалев М.Я. Область сходимости одного алгоритма минимизации приоритето-порождающих функционалов.- В кн.: Алгоритмы и программы решения задач оптимизации. Минск, ИЖ АН БССР, 1983, с.21-35.

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

28. Кук С.А. Сложность процедур вывода теорем.- В кн.: Кибернетический сборник. Новая серия, вып.12, М.: Мир, 1975, с.5-15.

29. Леонтьев В.К. Дискретные экстремальные задачи.- В кн.: Итоги4науки и техники. Теор. вероятн. Матем. стат. Теор. киберн. М.: ВИНИТИ АН СССР, 1979, т.16, с.39-101.

30. Метельский Н.Н., Демиденко В.М. О квадратичной задаче выбора. Изв. АН БССР. Сер. физ.-мат. наук, 1975, №5, с.25-29.

31. Михалевич B.C. Последовательные алгоритмы минимизации и ихприменение.- Кибернетика, 1965, №1, с.45-55; №2, с.85-89.

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

33. Михалевич B.C., Шор Н.З. Метод последовательного анализа вариантов при решении вариационных задач управления, планирования и проектирования.- В кн.: Докл. на 1У Всесоюзн. матем. съезде. Л., 1961, с.91.

34. Многокритериальные задачи принятия решений. Под ред. Гвишиа-ни Д.М., Емельянова С.В.- М.: Машиностроение, 1978.

35. Овсянкин Б.П. Об одной задаче организации обработки данных в многопроцессорных вычислительных системах.- ЖВМ и МФ, 1983, №5, с.1262-1266.

36. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям.- М.: Сов. радио, 1975.- 192 с.

37. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач.- М.: Наука, 1982.- 256 с.

38. Рева В.Н. Об одном алгоритме оптимизации функционала на перестановках частично упорядоченного множества.- В кн.: Актуальные проблемы ЭВМ и программирование. Днепропетровск, ДГУ, 1979, с.92-95.

39. Санникова А.К. О построении оптимальных расписаний для систем поточного типа с переменной структурой.- Дне. канд. физ.-мат. наук. Минск, 1982.- 113 с.

40. Санникова А.К., Танаев B.C. Об одном классе экстремальных задач на перестановках.- ДАН БССР, 1979, т.23, №9, с.784-786.

41. Сарванов В.И. К оптимизации на подстановках.- Изв. АН БССР. Сер. физ.-мат. наук, 1979, №4, с.9-11.

42. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров взадачах со многими критериями.- М.: Наука, 1981.- ПО с.

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

44. Супруненко Д.А. К задаче о бродячем торговце.- Кибернетика, 1975, №5, с.64-68.

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

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

47. Теория выбора и принятия решений.- М.: Наука, 1982.- 328 с.

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

49. Федоров В.В. Численные методы максимина.- М.: Наука, 1979.280 с.

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

51. Червак Ю.Ю. Об условиях существования решений задач лексикографической оптимизации.- Изв. АН СССР. Техн. кибернетика, 1982, №6, с.65-71.

52. Червак Ю.Ю. Поиск лексикографически максимальной дискретно определенной точки выпуклого множества.- В кн.: Математические методы решения экономических задач. Сб. 8, Наука, 1979, с.69-75.

53. Шафранский Я.М. Оптимизация детерминированных систем обслуживания с древовидным частичным порядком.- Изв. АН БССР. Сер. физ.-мат. наук, 1978, №2, с.119.

54. Шафранский Я.М. Об оптимальном упорядочении в детерминированных системах с древовидным частичным порядком обслуживания.-Изв. АН БССР. Сер. физ.-мат. наук, 1978, №2, с.120.

55. Шафранский Я.М. О задаче минимизации функций на множестве перестановок частично упорядоченных элементов. I.- Изв. АН БССР. Сер. физ.-мат. наук, 1980, №5, с.132.

56. Шафранский Я.М. О задаче минимизации функций на множестве перестановок частично упорядоченных элементов. П.- Изв. АН БССР. Сер. физ.-мат. наук, 1981, №1, с.113.

57. Bansal S.P. Single machine scheduling to minimize weighted sum of completion times with secondary criterion.- A branch and hound approach.- Europ. J. Oper. Res., 1980, v. 5, N3, p.177-181.

58. Brucker P., Garey M.R., Johnson D.S. Scheduling equal-lengtht tasks under tree-like precedence constraints to minimize maximum lateness.- Math. Oper. Res., 1977, v.2, N3, p.275-284.

59. Bruno J., Downey P. Complexity of task sequencing with deadlines, set-up times and changeover costs.- SIAM J. Comput.,1975, v.7, N4, p.393-404.

60. Bruno J., Sethi R. Task sequencing in a batch environment with set-up times.- "Found. Contr. Eng." (PEL), 1978, v.3, N3,p.105-117.

61. Burns R.N. Scheduling to minimize the weighted sum of completion times with secondary criteria.- Nav. Res. Log. Quart.,1976, v.23, N1, p.125-129.

62. Emmons H. A note on a scheduling problem with dual criteria. Nav. Res. Log. Quart., 1975, v.22, N3, p.615-616.

63. Erschler J., Roubellat F., Vernhes J.P. Characterizing the set of feasible sequences for N jobs to be carried out on a single machine.- Europ. J. Oper. Res., 1980, v.4, p.189-194.

64. Frederickson G.N. Scheduling unit-time tasks with integer release times and deadlines.- Inform. Process. Lett., 1983, N16, p.171-173.

65. Garey M.R., Johnson D.S. Scheduling tasks with nonuniform deadlines on two processors.- J. Assoc. Comput. Mach., 1976, v.23, N3, p.461-467.

66. Garey M.R., Johnson D.S. Two-processor scheduling with start-time and deadlines.- SIAM J. Comput., 1977, v.6, N3, p.416-426.

67. Garey M.R., Johnson D.S., Simons B.B., Tarjan R.E. Scheduling unit-time tasks with arbitrary release times and deadlines.-SIAM J. Comput., 1981, v.10, N2, p.256-259.

68. Heck H., Roberts S. A note of the extention of a result on scheduling with secondary criteria.- Nav. Res. Log. Quart., 1972, v.19, N2, p.403-405.75» Horn W.A. Some simple scheduling algorithms.- Nav. Res. Log. Quart., 1974, v.21, N1, p.177-185.

69. Land A.H., Doig A.G. An automatic method of solving discrete programming problems.- Econometrica, 1960, v.28, ITJ, p.497-520.

70. Lawler E.L. Optimal sequencing of a single machine subject to precedence constraints.- Manag. Sci., 1973» v.19, p.544-546.

71. Lawler E.L. Optimal sequencing of jobs subject to series parallel precedence constraints.- Math. Cent. Afd. Math. Bes-lisk. BW, 1975, N54, p.1-15.

72. Lawler E.L. Preemptive scheduling of precedence-constrained jobs on parallel machines.- Math. Cent. Afd. Math. Beslisk. BW, 1981, N132, p.1-23.

73. Lawler E.L., Labetoulle J. On preemptive scheduling of unrelated parallel processors by linear programming.- J. Assoc. Comput. Mach., 1978, vol.25, p.612-619.

74. Lenstra J.K., Rinnooy Kan A.H.G. Complexity of scheduling under precedence constraints.- Oper. Res., 1978, v.26, N1, P.22-35.

75. Ligtenberg E. Minimal cost sequencing of n grouped and ordered jobs on m machine.- J. Industr. Enging., 1966, v.17,p.217-223.

76. Lin K.S. Hybrid algorithm for sequencing with bicriteria.- J. Optim. Theory and Appl., 1983, v.39, N1, p.105-124.

77. Martel C. Preemptive scheduling with release times, deadlines and due times.- J. Assoc. Comput. Mach., 1982, v.29, N5,p.812-829.

78. Miyazaki S. One machine scheduling problem with dual criteria. J. Oper. Re. Soc. Japan, 1981, v.24, N1, p.37-50.93» Monma C.L., Sidney J.B. Sequencing with series-parallel pre-crdence constraints.- Math, of Oper. Res., 1979, v.4, N3, p.215-224.

79. Ran L.G. Minimizing a function of permutations of n integers. Oper. Res., 1971, v.19, N1, p.237-240.97» Salmi S., Cho Y. Scheduling independent tasks with due times on a uniform processor system.- J. Assoc. Comput. Mach., 1980, v.27, N3, p.550-563.

80. Simons B.B. A fast algorithm for multiprocessor scheduling.-21st Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc., 1980, p.50-53.

81. Simons B.B. On scheduling with release times and deadlines In: Deterministic and Stochastic Scheduling. Proc. Nato Adv. Study and Res. Inst. Theor. Approaches Scheduling Probl. Durham, July 6-7, 1981.- Dordrecht e.a. 1982, p.75-88.

82. Smith W.E. "Various optimizers for single stage production.-Nav. Res. Log. Quart., 1956, v.3, N1, p.59-66.

83. Vickson E.G. Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine.- Oper. Res., 1980, v.28, 1*5, p.1155-1167.

84. Van Wassenhove L.N., Baker K.R. A bicriterion approach to time/cost trade-offs in sequencing.- Europ. J. Oper. Res.,1982, v.11, К1, р.48-54.

85. Van Wassenhove L.H., Gelders L.P. Solving a bicriterion scheduling problem.- Europ. J. Oper. Res., 1980, v.4, N1, p.42-48.

86. Тузиков A.B. Об одном классе задач векторной оптимизации на перестановках.- В кн.: Алгоритмы и программы решения экстремальных задач и смежные вопросы. Минск, ШК АН БССР, 1982, с.62-70.

87. Тузиков А.В., Шафранский Я.М. О задаче лексикографической минимизации на множестве перестановок.- Редколлегия ж."Известия АН БССР. Сер. физ.-мат. наук", Минск, 1983, 14 с. (Рукопись депонирована в ВИНИТИ II.7.83, per. № 3820-83 Деп.).

88. Тузиков А.В. Минимизация максимального штрафа и решение некоторых двухкритериальных задач теории расписаний.- ДАН БССР,1983, т.27, №10, с.907-910.

89. Тузиков А.В. О двухкритериальных задачах теории расписаний.-В кн.: Оптимизация и управление в кибернетических системах. Тез. докл. Ж Болгаро-Польского симпозиума. София, 1983, октябрь 17-21, с.26-28.

90. Тузиков A.B. Задача лексикографической минимизации на множестве перестановок с заданным группированием элементов.-В кн.: Алгоритмы и программы решения задач оптимизации. Минск, ИТК АН БССР, 1983, с.36-43.

91. Тузиков А.В. О двухкритериальной задаче составления расписаний.- В кн.: Материалы 8 всесоюзного семинара-совещания: Управление большими системами. Алма-Ата, 1983, с.98-99.

92. Тузиков А.В. О двухкритериальной задаче теории расписаний с учетом изменения длительностей обслуживания.- ЖВМ и Ш, 1984, J§ 10, с. 1585-1590.