Оптимизация мультизадачного графика по временному критерию

Актуальность проблемы. В работе исследован ряд взаимосвязанных задач, важнейшими из которых являются следующие: а) комбинаторная задача непрерывного расположения ненулевых элементов в каждой строке матрицы с сохранением множеств элементов в каждой линииб) полиномиальная подзадача известной 1МР-полной задачи «Целочисленный поток в сети с гомологичными дугами» — в) задача о равномерной реберной раскрашиваемости двудольных графовг) задача об оптимизации 0−1 матрицы без ограничения допустимых операций только перестановками столбцовд) поиск кратчайших полупериодических путейе) разрешимость задачи устранения пробелов для разреженных матриц.

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

Приведенные в Главе 1 формулировки задач позволяют оценить их разброс по предметным областям, степени формализуемости и вычислительной сложности. В качестве модели, объединяющей в себе характерные черты упомянутых и близких к ним задач, сформулированных в последующих главах данной работы, рассматривается задача оптимизации графика работы нескольких исполнителей по временному критерию. Для определенности в Главе 1 формулировка модели приведена в понятиях и терминах задачи Оптимизации учебного расписания (сокращенно ОУР) по одному из критериев.

— уменьшению окон преподавателей. Приведем формулировку в сокращенном виде.

Задача. Дана матрица М тхк, каждый столбец которого содержит некоторую перестановку чисел 1, 2, ., п, т>п и т-п нулей. Ячейку Му с нулевым значением будем называть «пробелом», если найдутся 5 и / такие, что 7 М^гЮ, Ми? Ю. Требуется найти необходимые и достаточные условия существования преобразования матрицы М к беспробельному виду (где ненулевые элементы в каждой строке располагаются рядом) с сохранением множества элементов в каждом столбце и каждой строке матрицы. В случае существования такого преобразования разработать схему его реализации на ЭВМ.

Для случаев к<6 задача рассматривалась в работах [23] - [32].

Отметим множественность точек соприкосновения задачи ОУР с классическими труднорешаемыми задачами. В связи с этим становится актуальной проблема поиска частных случаев, допускающих решение исходной задачи за полиномиальное время. Так, требуемое в ОУР непрерывное размещение ненулевых элементов в строках исходной матрицы предполагает в качестве необходимого условия возможность аналогичного размещения единиц в строках матрицы, полученной заменой ненулевых элементов на единицы (обозначим соответствующую задачу как «(ЭУР-01»). В работе указывается на полиномиальную сводимость ИР-полной задачи «Разбиение» к задаче ОУР-01, что доказывает М5- полноту последней.

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

Многочисленные задачи, сформулированные в Главах 1−5, рассматриваются в качестве различных аспектов задачи оптимизации расписания, чем и обусловлен интерес к задаче ОУР. Разработке и обоснованию методов ее решения и посвящена диссертационная работа.

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

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

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

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

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

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

Научные положения, выносимые на защиту:

1. Доказана теорема о необходимых и достаточных условиях разрешимости задачи ОУР с четным количеством (2, 4 или 6) ненулевых элементов в каждой строкеразработан полиномиальный алгоритм решения задачи.

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

3. Сформулированы и обоснованы результаты о равномерной реберной рас-крашиваемости двудольных графов.

4. Доказана теорема о разбиении объединения семейств из 2-х и 4-х элементных множеств.

5. Установлена ТУР-полнота задачи о связности 0−1 — матрицы расписания.

6. Разработан и обоснован метод вычисления бездефектного потока в транспортной сети.

7. Оптимизация расположения резидентных программ в блоках памяти.

Публикации и апробация работы. По теме диссертации опубликованы 5 работ. Основные результаты диссертации докладывались на годичных итоговых конференциях Дагестанского госуниверситета, а также на Всероссийской н/п конференции «Внедрение информационных технологий в преподавание общетехнических и гуманитарных дисциплин» (Ин-т мировой экономики, 2−3июля 1998 г, г. Махачкала).

Структура и объем работы. Работа состоит из введения, пяти глав, заключения, списка использованной литературы, содержащего 73 наименований, и приложения. Содержание работы изложено на 115 страницах.

1. Альрашайда А. Об оптимизации матрицы. Вестник ДГУ.- Выпуск 4. — Махачкала, 1999 г. -С.2.

2. Асанов М. О. Дискретная оптимизация. Екатеринбург. Ур О АН СССР, 1998 г. -205С.

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

4. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, Физматгиз, 1974.-366С.

5. Басангова Е. С. Нахождение эйлерова цикла в смешанном графе. в сб. Модели и дискретные структуры. -Элиста: Калмыц. гос. ун-т, 1996. — С.58−61.

6. Белов В. В. и др. Теория графов. М.: Высшая школа, 1976. -392С.

7. Березин Е. А. Оптимальное распределение ресурсов и элементы синтеза систем. М.: Советское радио, 1974. — 304С.

8. Блох А. Ш. Граф схемы и алгоритмы. — Минск: Высшая школа, 1987. 141 С.

9. Турина JI.T. Оптизация: теория и алгоритмы. М.: Наука, 1973.-244С.

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

11. Дж.Просиз. Управление памятью в DOS 5: М.: Мир, 1994. 240С.

12. Е. А. Зуев. Turbo Pascal. Практическое программирование. -М.: «Издательство ПРИОР», 1998, 336 С.

13. Евстигнеев В. А., Касьянов В. Н. Толковый словарь по теорииграфов в информатике и программировании. Новосибирск: Наука, 1999.-288С.

14. Емеличев В. А., Мельников О. И., Сарванова В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. — 384С.

15. Зыков A.A. Основы теории графов. М.: Наука, 1987, — 384С.

16. Иванова В. В., Березовский В. К. Методы алгоритмизации непрерывных производственных процессов. М.: Наука, 1975. -400С.

17. Камерон П. Линт Дж. Теория графов, теория кодирования и блок-схемы. М.: Наука, 1980 — 139С.

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

19. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложения, М.: Мир, 1965. — 302С.

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

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

22. Магомедов A.M. Аналог теоремы Холла. Деп. в ВИНИТИ № 447−85, 1985.-7С.

23. Магомедов A.M. Выделение двух множеств непересекающихся двудольных паросочетаний. Деп. в ВИНИТИ № 7332, 1986. 9С.

24. Магомедов A.M. К вопросу минимизации разделяющих нулей в строках матрицы. Деп. в ВИНИТИ № 7224, 1984. 8С.

25. Магомедов A.M. Минимизация простоев. Тезисы Всесо-юзн.семинара «Системное моделирование производства, распределения и потребления», ч.2. Воронеж, 1986. С. 2.

26. Магомедов A.M. Нахождение кратчайших периодических путей в графе. Деп. в ВИНИТИ № 6759−1389, 1989. -8С.

27. Магомедов A.M. Псевдополиномиальный алгоритм решения задачи уплотнения матрицы для одного частного случая. Деп. в ВИНИТИ № 6762−1389, 1989. 5С.

28. Магомедов A.M. Раскраска графа с непрерывным спектром. Деп. в ВИНИТИ № 478, 1985. ЗС.

29. Магомедов A.M. Сдвиг по полупустому циклу для уплотнения графика работы нескольких исполнителей. Деп. в ВИНИТИ № 7225, 1984.-9С.

30. Магомедов A.M. Сильные NP-полные задачи о матрице со свойством псевдосвязности. Деп. в ВИНИТИ № 6761−1389, 1989.-6С.

31. Магомедов A.M. Теорема о п.н.п. с ограничениями. Деп. в ВИНИТИ № 7155В-85, 1989. 1С.

32. Магомедов A.M. Условия и алгоритм уплотнения матрицы из 4 столбцов. Деп. в ВИНИТИ, 1991.-7С.

33. Магомедов A.M., Альрашайда А. Матрица расписания с двумя ненулевыми элементами в строке. Вестник ДГУ. Выпуск 4. -Махачкала, 1999.-4С.

34. Магомедов A.M., Альрашайда А. Необходимые условия уп-лотнимости матрицы перестановок из 5 столбцов. Вестник ДГУ. Выпуск 1. — Махачкала, 1998. — С. 130−131.

35. Магомедов A.M., Альрашайда А., Якубов А. З. Оптимальное размещение TSR-программ. Вестник ДГУ. Выпуск 4. — Махачкала, 1997.-С. 133−138.

36. Новиков O.A., Петухов С. И. Прикладные вопросы теории массового обслуживания. М.: Советское радио, 1969. — 399С.

37. Овчаров A.A. Прикладные задачи теории массового обслуживания. М.: Машиностроение, 1969. — 323С.

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

39. Данкан Р. Профессиональная работа в MS DOS: пер. с англ. -М.: Мир, 1993.-509с.

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

41. Романовский И. В. Алгоритмы решения экстремальных задач. -М.: Наука, 1977. -352С.

42. Саульев В. К. Математические модели теории массового обслуживания. М.: Статистика, 1979. — 96С.

43. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.-455С. S.

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

45. Танаев В. С., Шкурба В. В.

Введение

в теорию расписаний. -М.: Наука, 1975.-256С.

46. Тат Ульям Т. Теория графов. М.: Мир, 1988. — 424С.

47. Фаронов В. В. Турбо Паскаль 7.0. Практика программирования. Учебное пособие. М.: «Нолидж», 1997 — 432С.

48. Федоров А. Г. Delphi 3.0 для всех. КомпьютерПресс, 1998. -544 С.

49. Финогенов К. Г. Самоучитель по системным функциям MS/DOS. M.: МП «МАЛИП», 1993 — 262С.

50. Форд JI.P., Фалкерсон Д. Р. Потоки в сетях. М.: Мир, 1963.

51. Ху Т. Целочисленное программирование и потоки в сетях. -М.: Мир, 1974. 520С.

52. Anstee R.P., Caccetta L. Orthogonal matchings. Discrete Math. -1998. 179, № 1−3.-P.37−47.

53. Antee R.P., Nam Yunsum. More sufficient conditions for graph to have factors. Discrete Math. — 1998. — 184, № 1−3. — P.15−24.

54. Armstrong Ronald D., Chenwei, Goldfard Donald. Strongly polynomial dual simplex methods for the maximum flow problem. Math. Programm. A. — 1998. — 80, № 1. P.17−33.

55. Balinski Michel, Ralier Gujiaume. Graphs and marriages. Amer. Math. Mon. — 1998. — 105, № 5. — P.430−445.

56. Burkhard R.E., He Y., Kellerer H. A linear compound algorithm for uniform machine scheduling. Computing. — 1998. — 61, № 1. -P.1−9.

57. Daniels Richard 1., Hua Stella Y. Heuristics for parallel-machine flexible scheduling problems with unspecified job assignment. -Webster Scott Comput. and Oper. Res. — 1999. — 26, № 2 — P. 143 155.

58. Dantzig G.B., W.O.Blattner, and M.R.Rao, «All shortest routes from a fixed origin in a graph», in Theory of Graphs: International Symposium, Gordon and Breach, NY, 85−90 (1967).

59. Gnan D.J., Zhu Xuding. Multiple capacity vehicle routing on paths. Discrete Math. — 1998. — 11, № 4. — P.590−602.

60. Goldberg Andrew V., Rao Satish. Flows in undirected unit capacity networks. Discrete Math. 1999. — 1999. 12, № 1 — P. 1−5.

61. Hind Hugh, Zhao Yue. Edge colorings of graphs embeddable in surface of low genus. Discrete Math. 1998 — 190, № 1−3. — P. 107 114.

62. Itai A., and M. Rodeh, «Some matching problems» in Automata, languages and programming, Lecture Notes in Computer Science, Vol. 52, Spring, Berlin, 258−268 (1979).

63. Jonson D.S. Near-Opimal Bin Packing Algorithms, Doctoral Thesis, Dept. of Mathematics, Massachusetts Institute of Technology, Cambridge, 1973.

64. Lu Changhong, Yao Tianxing. The strong edge colouring of cycles and complete graphs. Math. Biguartely. — 1998. — 15, № 2. -P. 186−190.

65. OPE О. Теория графов. М., Физматгиз, 1968. — 352С.

66. Rios Mercado Roger Z., Bard Jonathan F. Computational experience with setups. — Comput. and Oper. Res. — 1998. — 25, № 5. — P.351−366.

67. Sahni S. Approximate algorithms for the u/i knapsack problem. J. assoc: Comput. Mach. 22, 115−124 (1975).

68. Sahni, S., «Computationally related problems», SIAM J. Comput. 3,262−279(1974).

69. Shiraishi shuji. A remark on maximum matching of line graphs. -Discrete Math. 1998. — 179, № 1−3. — P.289−291.

70. Tuza Zsolt. Graph coloring with local constraints. -Discuss. Math. Graph Theory. 1997. — 17, № 2. — P.161−228.

71. Y. Edmonds and R.M. Karp, Teoretical Improvements in Algorithmic Efficiency for Network Flow Problems. -Y. ACM.-1972. -Vol.19.-P.248−264.

72. Yuan jinjiang. Induced matching extendable graphs. J. Graph Thery. — 1998. 28, № 4. -P.203−213.