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

• Красовский, Дмитрий Владимирович
• кандидат физико-математических наук
• 2007

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

Введение

Глава 1. Основные понятия и формальная постановка задачи

1.1. Модель

1.2. Оценка погрешности и времени составления расписания

1.3. Задачи большой размерности

Глава 2. Характеристика задачи и существующие методы ее решения

2.1. Результаты для задач минимизации длины расписания

2.2. Оценки характеристик алгоритмов составления расписаний

2.3. Анализ существующих точных и приближенных алгоритмов

2.4. Анализ существующих параллельных стратегий

Глава 3. Алгоритмы составления расписания без прерываний

3.1. Алгоритм «Процессор с ранним окончанием первым»

3.2. Вероятностный алгоритм

3.3. Псевдополиномиальные алгоритмы

3.3.1. Различные интерпретации псевдополиномиальных алгоритмов

3.3.2. Псевдополиномиальный алгоритм с поиском в ширину

3.3.3. Псевдополиномиальный алгоритм с поиском в глубину

3.4. Метод агрегирования

3.4.1. Формальное описание

3.4.2. Задача составления расписания п работ на ш идентичных процессорах

3.4.3. Вспомогательные алгоритмы

3.4.4. Агрегирующие алгоритмы

3.5. Анализ возможности совместного использования методики агрегирования с другими алгоритмами

Глава 4. Алгоритмы с гарантированной точностью

4.1. Псевдополиномиальный алгоритм с поиском в глубину

4.2. Вероятностный алгоритм

4.3. Алгоритм «Процессор с ранним окончанием первым»

4.4. Алгоритм «Самая длинная работа первой»

Глава 5. Результаты для некоторых частных случаев

5.1. Длительности работ, заданные арифметической прогрессией

5.2. Длительности работ, близкие к арифметической прогрессии

5.3. Фиксированное число процессоров

Глава 6. Параллельное выполнение вычислений

6.1. Комбинированный псевдополиномиальный алгоритм

6.2. Параллельное построение дерева решения

Глава 7. Результаты экспериментов

7.1. Экспериментальная система78

7.2. Таблицы и графики

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

Актуальность и характеристики задачи

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

Для иллюстрации большой практической значимости рассматриваемых задач и важности эффективных алгоритмов их решения можно привести следующие примеры: системы противоракетной обороны; системы управления ядерными реакторами на АЭС; бортовые системы при испытаниях и управлении летательными аппаратами и космическими кораблями; организация расписаний в современных аэропортах и многие другие.

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

Исторически появлению дискретных методов оптимизации предшествовало развитие методов линейного программирования. Высокая вычислительная производительность этих методов позволила предполагать, что на их основе могут быть разработаны эффективные методы решения дискретных задач оптимизации. Однако вычислительные эксперименты не подтвердили это предположение. Принципиальные трудности решения дискретных задач показала и теория вычислительной сложности алгоритмов [1, 2, 3, 4]. В соответствии с этой теорией оценка эффективности производится по наихудшему случаю. Так как для большинства дискретных задач оптимизации в наихудшем случае не известен точный алгоритм кроме перебора всех или почти всех вариантов, то полученные оценки являются неудовлетворительными с точки зрения практического использования.

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

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

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

Понижение размерности системы приводит также к уменьшению накладных расходов на организацию обслуживания, которые, например, согласно некоторым исследованиям [5] в вычислительных системах реального времени достигают 70% (в отдельных случаях и выше) времени работы центрального процессора.

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

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

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

Цели и новизна работы

Целями настоящей диссертационной работы являются:

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

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

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

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

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

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

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

Методы исследований

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

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

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

Разработанные в диссертации алгоритмы построения оптимальных и ¿■-приближенных расписаний могут быть рекомендованы к использованию при проектировании, анализе и эксплуатации аппаратно-программных комплексов систем реального времени, применяемых при разработке, испытаниях и эксплуатации сложных технических объектов, а также в системах оперативного мониторинга.

Апробация работы

Результаты диссертации и материалы исследований докладывались, обсуждались и получили одобрение специалистов на:

- ХЬУ, ХЬУИ и 1Ь научных конференциях Московского физикотехнического института (государственного университета),

Долгопрудный, 2002,2004,2006);

- X, XI и XII международных конференциях "Проблемы управления безопасностью сложных систем" (Москва, 2002, 2003,2004);

- IV международной конференции по исследованию операций (Москва, 2004);

- II Всероссийской научной конференции «Методы и средства обработки информации» (Москва, 2005);

- научных семинарах кафедры математических основ управления Московского физико-технического института (государственного университета);

- научных семинарах сектора проектирования систем реального времени Вычислительного центра им. А.А. Дородницына Российской Академии Наук.

По материалам диссертации опубликовано 12 печатных работ. Структура работы

Работа состоит из данного введения, семи глав и заключения. В главе 1 вводится формальная постановка и описание задачи. Формализуются термины, которые используются далее в работе. В главе 2 приводится анализ исследований рассматриваемого и смежных классов задач, проведенные другими учеными. Проводится исследование описанных в литературе алгоритмов, которые могут использоваться для рассматриваемого класса задач, приводятся их сильные и слабые стороны. Выделен ряд наиболее перспективных алгоритмов и методик, которые были использованы для сравнения с разработанными в рамках данной работы алгоритмами. Глава 3 посвящена алгоритмам, разработанным в рамках данной работы: их формальному описанию, определению алгоритмической сложности. В главе 4 для разработанных ¿--приближенных алгоритмов определяется и доказывается их гарантированная точность. Глава 5 посвящена некоторым интересным математическим фактам, относящимся к разработанным алгоритмам, которые были определены в процессе этой диссертационной работы. В главе 6 исследуется параллельный процесс построения расписания. В главе 7 собраны и структурированы все полученные вычислительные результаты, приводится описание системы, которая использовалась для проведения экспериментов.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Красовский, Дмитрий Владимирович

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

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

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

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

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

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

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

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

По результатам работы состоялись 12 публикаций [60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71].

Наиболее перспективным представляется развитие предложенных в данной работе методов и подходов по следующим направлениям:

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

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

• определение зависимости погрешности и алгоритмической сложности агрегирующих алгоритмов от параметров исходной системы и декомпозиции.

Заключение

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

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

1. Ульман Дж. Полиномиально полные задачи составления расписаний // Operating Systems Review, 1973.

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

3. Танаев В. С., Гордон В. С., Шафранский Я.М. Теория расписания. Одностадийные системы // М.: Наука, 1984.

4. Brucker P. Scheduling algorithms, 2nd edition // Springer, Heidelberg, 1998.

5. Bondy J. L., Freeman D. N. Putting supervisory routines into hardware // North-Holland Publ. Co., 1977.

6. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование // ФИЗМАТЛИТ. 2002.

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

8. Сигал ИХ. Параметризация и исследование некоторых задач дискретного программирования большой размерности // М.: Известия академии наук. Теория и системы управления, 2001, №2, С. 60-69.

9. Сигал ИХ. Параметризация ¿"-приближенных алгоритмов решения некоторых классов задач дискретной оптимизации большой размерности // М.: Известия академии наук. Теория и системы управления, 2002, №6, С. 63-72.

10. Сигал ИХ. Оценки параметров алгоритмов ветвей и границ для задач дискретной оптимизации большой размерности // М.: Известия академии наук. Теория и системы управления, 2005, №4, С. 96-101.

11. Baker К. R. Introduction to Sequencing and Scheduling // John Wiley and Sons, Inc., 1974.

12. Conway R., Maxwell W., Miller L. Theory of Scheduling // Addison Wesley Publishing Company, 1967.

13. Giffler В., Thompson G. Algorithms for solving production scheduling problems // Operations Research, 8(4):487-503,1960.

14. Растригин JI.A. Статистические методы поиска // M.: Наука, 1968.

15. Гончаров Е.Н., Кочетов Ю.А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискрет, анализ и исслед. операций Сер. 2,2002. Т. 9, №2. С. 13-30.

16. Кочетов Ю, Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет, анализ и исслед. операций Сер. 2,2003. Т. 10, № 1,С. 11-44.

17. Кочетов Ю.А., Столяр А.А. Использование чередующихся окрестностей для приближенного решения задачи календарного планирования с ограниченными ресурсами // Дискрет, анализ и исслед. операций Сер. 2,2003. Т. 10, № 2, С. 29-56

18. Tripathy A. School timetabling a case in large binary integer linear programming //Management Science, 30(2): 1473-1480, 1984.

19. Ciriani Т., Leachman R., editors. Optimizing in Industry: Mathematical Programming and Modeling Techniques in Practice I I John Wiley and Sons, Ltd., 1993.

20. Алексеев О.Г. Комплексное применение методов дискретной оптимизации//Наука, 1986.

21. Held М., Karp R. A dynamic programming approach to sequencing problem // SIAM, 1962.

22. Land A.H., and Doig A. G. An automatic method of solving discrete programming problems // Econometrica. v28 (1960), pp 497-520.

23. ЛиттлД.Ж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи коммивояжера // Экономика и математические методы, Т. 1, вып. 1,С. 90-107,1965.

24. Корбут А.А., Финкелъштейн Ю.Ю. Дискретное программирование // М. Наука. Гл. ред. физ.-мат. лит. 1969.

25. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов // М.: Радио и связь, 1983.

26. Panwalkar S., Iskander W. A survey of scheduling rules // Operations Research. 25(1):45-61,1977.

27. Штовба С. Д. Муравьиные алгоритмы // ExponentaPro. Математика в приложениях, № 4(4), 2003.

28. Laarhoven P., Aarts Е., Lenstra J. Job Shop Scheduling by Simulated Annealing // Operations Research, 40(1):113-125,1992.

29. Shen С., Pao K, Yip P. Scheduling multiple job problems with guided evolutionary simulated annealing approach // Proceedings of the First IEEE Conference on Evolutionary Computations, pages 702-706,1994.

30. Glover F., Laguna M. Chapter 3: Tabu search // In Colin R. Reeves, editor, Modern Heuristics Techniques for Combinatorial Problems, Blackwell Scientific Publications, 1993.

31. Taillard E. Benchmarks for basic scheduling problems // European Journal of Operations Research, 64:278-285,1993.

32. Ross P., Hallam J. Lecture Notes on Connectionist Computing // Department of Artificial Intelligence, University of Edinburgh, 1993.

33. Hulle M. A goal programming network for mixed integer linear programming: A case study for the job-shop scheduling problem // International Journal of Neural Systems, 2(3):201-209,1991.

34. Меламед И.И. Нейронные сети и комбинаторная оптимизация // Автоматика и телемеханика, 11, С. 3-40,1994.

35. Костенко В.А., Смелянский Р.П., Трекин А.Г. Синтез структур вычислительных систем реального времени с использованием генетических алгоритмов // Программирование, 2000, № 5.

36. Трекин A.F. Структурный синтез вычислительной системы с помощью генетических алгоритмов: Дис. канд. физ.-мат. наук. М., 2002. 111 с.

37. Holland J.N. Adaptation in Natural and Artificial Systems // Ann Arbor, Michigan: Univ. of Michigan Press, 1975.

38. Michalewicz Z Genetic Algorithms + Data Structures = Evolution Programs // Third, Revised and Extended Edition, Springer, 1999.

39. Goldberg D.E. Genetic Algorithms in Search Optimization & Machine Learning // Addison Wesley, Reading, 1989.

40. Mataric M., Cliff D. Challenges in Evolving Controllers for Physical Robots // Robotics and autonomous systems, 19(1), p. 67-83, 1996.

41. Periaux J. and Winter G. editors. Genetic Algorithms in Engineering and Computer Science // John Wiley & Sons Ltd., 1995.

42. Come D., Fang H.-L., Mellish C. Solving the Modular Exam Scheduling Problem with Genetic Algorithms // DAI Research Paper №622.

43. Bierwirth C., Kopfer H., Mattfeld D. C., Rixen I. Genetic Algorithm based Scheduling in a Dynamic Manufacturing Environment // Proceedings of the IEEE Conf. on Evolutionary Computation, Perth, IEEE Press, 1995, p.439-443.

44. Daaldr J., Eklund P. W., Ohmori K. High-Level Synthesis Optimization with Genetic Algorithms // Proceedings of the 4th Pacific Rim International Conference on Artificial Intelligence, Cairns (Australia), 26-30 August 1996, p.276-287.

45. Кормен Т., Лейзерсон 4., Pueecm Р. Алгоритмы: построение и анализ // М.-.МЦНМО, 2001.

46. Посыпкин М.А., Сигал И.Х., Гамилъянова Н.Н. Алгоритмы параллельных вычислений для решения некоторых классов задач дискретной оптимизации. М.: ВЦ РАН, 2005.

47. Rao V. Nageshwara and Kumar V. Parallel depth-first search, part I: Implementation//International Journal of Parallel Programming, 1987,16 (6). P. 479-499.

48. Rao V. Nageshwara and Kumar V. Parallel depth-first search, part II: Analysis // International Journal of Parallel Programming, 1987,16(6). P. 501-519.

49. Kumar V., Grama A., Rao V. Nageshwara. Scalable Load balancing Techniques for Parallel Computers // Journal of Parallel and Distributed Computing, 1994,22(1). P. 60-79.

50. Gotlieb A. The NYU ultracomputer designing a MIMD, shared memory parallel processor // IEEE Transactions on Computers, February, 1983. P. 175- 189.

51. Тимошевская H. E. Параллельные методы обхода дереваЛ Математическое моделирование. 2004,16(4). С.105-114.

52. Kouichi Kimura, Ichiyoshi Nobuyuki. Probabilistic analysis of the efficiency of the dynamic load distribution // Sixth Distributed Memory Computing Conference Proceedings, 1991. P. 145-152.

53. Shu W., Kale L. V. A dynamic scheduling strategy for the chare-kernel system // Supercomputing, 1989. P. 389-398.

54. Ranade A. Optimal speedup for backtrack search on butterfly network // ACM Symposium on Parallel Algorithms and Architectures, 1991. P. 40-48.

55. Raghavan R. Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs I I Journal of Computer and System Sciences 37,130-143,1988.

56. Сигал И.Х. Задача коммивояжера большой размерности // ВЦ АН СССР, 1986.

57. Трекин А.Г. Структурный синтез вычислительной системы с помощью генетических алгоритмов // Москва, 2002.

58. Michael J. Quinn. Designing Efficient Algorithms for Parallel Computers // McGraw-Hill, 1987.

59. Красовский Д.В., Фуругян М.Г. Комплексное применение методов дискретной оптимизации при решении задач минимаксной теории расписаний // МФТИ М., 2003. «Моделирование и обработка информации» - С. 96-103.

60. Гуз Д.С., Красовский Д.В., Фуругян М.Г. Некоторые алгоритмы составления расписаний в многопроцессорных системах //Проблемы управления безопасностью сложных систем: Труды 11-й международной конференции /ИПУ РАН. М., 2003 - С. 12-14.

61. Гуз Д.С., Красовский Д.В., Фуругян М.Г. Эффективные алгоритмы планирования вычислений в многопроцессорных системах реального времени / ВЦ РАН. М., 2004. - 65 с.

62. Guz D., Krasovskiy D., Furugian M. Effective scheduling algorithms for multiprocessor real-time systems //Proceedings of IV Moscow International Conference on Operations Research /ВЦ PAH. M., 2004 - C. 100-103.

63. Гуз Д.С., Красовский Д. В., Фуругян М.Г. Некоторые алгоритмы анализа многопроцессорных систем реального времени / ВЦ РАН. М., 2005. -42 с.

64. Красовский Д. В. Решение задачи составления оптимального расписания без прерываний на произвольных процессорах с использованием вероятностного алгоритма // Современные проблемы фундаментальных и прикладных наук общая и прикладная физика:

65. Сборник трудов 48-й научной конференции МФТИ / МФТИ М., 2005, -С. 76-78.

66. Красовский Д.В., Фуругян М.Г. Агрегирование в задаче составления оптимального расписания для многопроцессорных АСУ // Автоматика и телемеханика. 2006. - №12 - С. 205-212.

67. Красовский Д.В., Фуругян М.Г. Псевдополиномиальные алгоритмы упорядочения работ без прерываний по произвольным процессорам // Вестник Московского университета, сер. 15, Вычислительная математика и кибернетика, 2006, № 4, С. 25-29

68. Красовский Д.В., Фуругян М.Г. Некоторые алгоритмы составления многопроцессорных расписаний с использованием параллельных вычислений / ВЦ РАН. М., 2006. - 27 с.72. http://www.mathematik.uni-osnabrueck.de/research/OR/class/