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

СПИСОК СОКРАЩЕНИЙ 1 СОДЕРЖАНИЕ 3 ВВЕДЕНИЕ 4 ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ИЗУЧАЕМОЙ ТЕМЫ 8 1.1. Понятие о вычислительных системах 8 1.2. Описание масштабируемой задачи 15 1.3. Теория расписаний 15 ГЛАВА 2. ОПИСАНИЕ ПРОВЕДЁННОГО ПРАКТИЧЕСКОГО ИССЛЕДОВАНИЯ 21 2.1. Теоретическая часть 21 2.2. Описание эксперимента 29 2.3. Преимущество GRID системы 34 ГЛАВА 3. ПРАКТИЧЕСКОЕ ВНЕДРЕНИЕ СИСТЕМЫ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬОЙ НАГРУЗКИ 42 3.1. Параллельное операционное окружение 42 3.2. Тест Linpack и оценки его эффективности. 44 3.3. Развертывание программного обеспечения. 47 3.4. Решение эталонных задач. 52 ЗАКЛЮЧЕНИЕ 59 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 61

1. Абрамов С. М. (ИПС РАН, Россия), Велихов П. Е. (SDSC, США), Москов-ский А. А. (ИПС РАН, Россия), Роганов В. А. (ИПС РАН, Россия), СУПЕРКОМПЬЮ-ТЕРНЫЕ И GRID-ТЕХНОЛОГИИ. 2. А.В.Богданов, В.В.Корхов, В.В.Мареев, Е.Н.Станкова Архитектуры и то-пологии многопроцессорных вычислительных систем. Курс лекций. Учебное пособие.-М.: ИНТУИТ.РУ «Интернет-Университет ИнформационныхТехнологий»,2004. http://www.intxiit.ru/department/hardware/atmcs/ 3. А.В.Богданов, Е.Н.Станкова Распределенные Linux кластеры как основы сетей науки и образования будущего// Труды IX Всероссийской научно- методической конференции Телематика'2002. 4. А.В.Богданов, В.В.Корхов, В.В.Мареев, Е.Н.Станкова; Издательство: Ин-тернет- университет информационных технологий - ИНТУИТ.ру , Архитектуры и то-пологии многопроцессорных вычислительных систем, (учебник), Серия: Основы ин-формационных технологий , Год выпуска: 2004. 5. А.В.Богданов, E.H. Станкова, В.В. Мареев, СЕРВИС- ОРИЕНТИРО-ВАННАЯ АРХИТЕКТУРА: НОВЫЕ ВОЗМОЖНОСТИ В СВЕТЕ РАЗВИТИЯ GRID ТЕХНОЛОГИЙ, 191119, г. 6. А.В.Богданов, М.И.Павлова, Е.Н.Станкова, Л.С.Юденич, Высо-копроизводительные вычислительные алгоритмы (учебное пособие). http://www.csa.rU/old/analitik/distant/q start.html 7. А.В.Богданов, Мо Тун Тун , Разработка распределенных вычислительных систем и запуск приложений в гетерогенной вычислительной среде http://wwwact.edu.rii/vcon^index.php?a^conf&c=getFoim&r:H;hesisDesc&id_se c=283&id_vcon?=56&id_thesis=l0166&d=light. 2009 8. А.В.Богданов, Шошмина И.В., Абрамсон Д. Куда идет Grid?// ОИЯИ. Спе-циальный выпуск, посвященный Международной конференции по распределенным вычислениям и грид-технологиям в науке и образовании, 2004. 9. Ада Старосельская, Перспективные технологии. ГРИД , http://www.abitura.com/happy_physics/grid.html Ю.Армонк, штат Нью-Йорк, Grid-вычисления для охраны окружающей среды, 20 сентября 2004 года. http://n-t.ru/sp/ibm/04/09201 .htm 11. Андрей Колесов, SOA — итоги трехлетних дискуссий, 14.11.2008. http://www.bytemag.ru/articles/detail.php?ID=13238 12. Андрей Колесов, SOA: переход от теории к практике, 18.06.2008. http://www.bytemag.ru/articles/detail.php?ID=l 2164 13. Андрей Колесов, Реализация SOA как разработка композитных приложе-ний, 16.01.2007. http://www.bytemag.m/articles/detail.php?ID=6845 14. Андрей Коптелов, Виктор Голубев, Сервис-ориентированная архитектура: от концепции к применению, №6 (116), июнь 2008. http://www.bvtemag.ru/articles/detail.php?ID=l 2160 15. Андрей Шевель, Владимир Корхов, Эксперименты с фрагментами сетей GRID, http://www.osp.rU/text/print/302/l 80174.html 16. А.Е. Дорошенко, O.B. Алистратов, Ю.М. Тырчак, А.П. Розенблат, К.А. Рухлис, СИСТЕМЫ GRID-ВЫЧИСЛЕНИЙ — ПЕРСПЕКТИВА ДЛЯ НАУЧНЫХ ИС-СЛЕДОВАНИЙ, УДК 681.3.2006. 17. А.Е. Дорошенко, А.П. Розенблат, К.А. Рухлис, Ю.М. Тырчак, МОДЕЛИ И СРЕДСТВА ПРОГРАММИРОВАНИЯ ГРИД-СИСТЕМ,. 2007. 18. А.К. Кирьяновым и Ю.Ф. Рябовым, Введение в технологию Грид Состав-лено, 2006 г. 19. А.П. Демичев, В.А. Ильин, А.П. Крюков, Введение в грид-технологии, 2007. 20. Афанасьев А.П.,Ваньков А.И,Волошинов В.В.,Кривцов В.Е.,Попков Е.Ю.,Шляев П.Г., Современные технологии построения распределенных программных систем. 21. В.П.Гергель, Теория и практика параллельных вычислений. Учебное посо-бие - М.: ИНТУИТ.РУ «Интернет-Университет Информационных Технологий»,2007 http://www.intuit.ru/department/calculate/paralltp/ 22. Воеводин- В.В., Воеводин Вл.В.- Параллельные вычисления. - М.: "БХВ",2002 . 23. B.C. Заборовский, Развитие ГРИД-среды: аспекты создания, внедрения и использования, 28 июня 2007 г. 24. Виктор Коваленко, Евгения Коваленко, Дмитрий Корягин, Эдуард Любим-ский, Евгений Хухлаев, Управление заданиями в распределенной вычислительной сре-де. http://www.osp.ru/text/print/302/180168.html 25. Виктор Коваленко, Дмитрий Корягин, Вычислительная инфраструктура будущего, 2000 г. http://\vw\v.citfomm.ru/hardware/articles/iiiturvich.shtml 26. Владислав Шаров, Развитие grid-технологий, №9 (107), сентябрь 2007. http://www.bytemag.ru/articles/detai 1 .php ?ID=8725 27. B.H. Коваленко, Е.И. Коваленко, Д.А. Корягин, Э.З. Любимский, A.B. Ор-лов, Е.В. Хухлаев, Структура и проблемы развития программного обеспечения среды распределенных вычислений Грид, 2002 г . 28. Г.Р.Эндрюс Основы многопоточного, параллельного и распределенного программирования. - М.: Издательский дом «Вильяме», 2003. 29. Дж.Ортега,Введение в параллельные и векторные методы решения линей-ных систем. - М.:Мир, 1991 30. Дмитрий ПАТЫКО, Грид — технология будущего, Четверг, 20.08.2009г. http://nanb80.belta.by/m/press?id:=272632&mode=:press 31. Евгений Хухлаев, Евгения Коваленко,Дмитрий Корягин, Эдуард Любим-ский, Виктор Коваленко, Управление заданиями в распределенной вычислительной среде. 32. Жучков A.B., Арнаутов С.А., ЕДИНАЯ СРЕДА РАСПРЕДЕЛЕННЫХ РЕ-СУРСОВ (GRID) И ЦИФРОВЫЕ БИБЛИОТЕКИ. 33. Жучков Алексей Васильевич, HEALTH GRID Особенности национальной стратегии, Институт химической физики. 34. С.Немнюгин, О.Стесик, Параллельное программирование для многопро-цессорных вычислительных систем. СПб:, "БХВ-Петербург", 2002 35. И.Е. Зобов, A.B. Богданов, ОСОБЕННОСТИ ДИСПЕТЧЕРИЗАЦИИ РЕ-СУРСОВ SUN GRID ENGINE В ПРИМЕНЕНИИ К ГЕТЕРОГЕННЫМ GRID-КОМПЛЕКСАМ 36. К.Ю.Богачев Основы параллельного программирования. - М.: БИНОМ. Лаборатория знаний, 2003. 37. Корнеев В.В. Параллельные вычислительные системы. - М.: "Нолидж", 1999 38. Коваленко В.Н., Коваленко Е.И., Корягин Д.А., Любимский Э.З., Орлов A.B., Хухлаев Е.В., Структура и проблемы развития программного обеспечения среды распределенных вычислений Грид, 2002. http://www.keldysh.ru/papers/2002/prep22/prep2002 22.html 39. Козырев А.Н., Виртуальный технопарк на основе грид-технологий, 2006 г. 40. Коваленко В.Н., Корягин Д.А. Организация ресурсов грид, Москва, 2004. http://www.keldysh.ru/papers/2004/prep63/prep2004 63.html і 41. Леонид Бараш, Grid Computing ~ новая парадигма Internet-вычислений, 29 августа 2001, http://itc.ua/article.phtml?ID=7249&IDw=49 42. Леонид Бараш, Grid Computing ~ новая парадигма Internet-вычислений, 29 августа 2001, http://itc.ua/article.phtml?ID=7249&IDw=49 43. Леонид Бараш, Grid Computing ~ новая парадигма Internet вычислений , 22 августа 2001 г. http://itc.ua/node/7249 44. Марк Линеш, грид - масштабируемый распределенный компьютинг, сен-тября 2009. http ://www.bestreferat.ru/referat-101181 .html 45. Матг Хайнос, руководитель проекта, грид-маркетинг и стратегия, IBM, Перспективы грид: грид-компьютинг - следующее поколение распределённого компь-ютинга, 27 Jan 2004. http ://www-128. ibm.com/developerworks/grid/library/gr-heritage/ 46. Матг Хайнос, Перспективы грид: грид-компьютинг - следующее поколение распределённого компьютинга, 27 Jan 2004. http://www-128.ibm.com/developerworks/grid/library/gr-heritage/ 47. МИХАИЛ ПОПОВ, На счет grid, ОПУБЛИКОВАНО В ЖУРНАЛЕ "СЮ" №2 ОТ 16 ФЕВРАЛЯ 2005 ГОДА, http://www.cio-world.ru/offline/2005/34/37649/ 48. Н.В. Макаровой, Эталонные модели взаимодействия сетей, http://www.high-info.ru/Etalonnie modeli vzaimodevstviya setey.htm 49. Олег Спиряев, Технологии Grid в решениях HP, Платформы и технологии | №7/2005, http://www.bvtemag.ru/?ID=604025 50. Олег Спиряев, Технологии передачи информации в SAN, №7-8 (95), июль- август2006. http://www.bytemag.ru/articles/detail.php?ID=8664 51. Олег Таковицкий, Технология Grid Computing, http://grid.i inr.ru/materials/education/grid computin g-technolo gy.hun 52. Павел Шелякин, Архитектуры, ориентированные на сервисы, 02.08.2004. http://xmlhack.ru/texts/Q4/SOAvsWebservices/SOAvsWebserviccs.html 53. Посыпкин M.А. , Интеграция разнородных вычислительных ресурсов на прикладном уровне при решении сложных вычислительных задач. 54. Ричард Вирт, Конвергенция средств виртуализации, grid и SOA, 05.05.2008г. http://www.osp.ru/os/2008/03/5017055/ 55. Р.Миллер, Л.Боксер Последовательные и параллельные алгоритмы. - М.: БИНОМ. Лаборатория знаний, 2006 http://book.itep.ru/4/7/grid.htm#33 56. Савин Геннадий Иванович, Овсянников Алексей Павлович, Создание рас-пределенной инфраструктуры для суперкомпьютерных приложений. 57. C.B. Востокин, ТЕХНОЛОГИЯ МОДЕЛИРОВАНИЯ РАСПРЕДЕЛЕННЫХ СИСТЕМ, ОСНОВАННАЯ НА ВИЗУАЛЬНОМ ЯЗЫКЕ, И ЕЕ ПРИЛОЖЕНИЯ, 2004.

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ИЗУЧАЕМОЙ ТЕМЫ 1.1. Понятие о вычислительных системах Вычислительная система - совокупность аппаратно-программных средств, обра-зующих единую среду, предназначенную для решения задач обработки информации (вычислений). Первоначально универсальные В. с. создавались на основе однопроцессорных ЭВМ с целью увеличения их быстродействия. В первых ЭВМ процессоры сами управ-ляли операциями ввода-вывода. Однако скорость работы внешнего устройства значи-тельно меньше скорости работы процессора, поэтому во время операций ввода-вывода процессор фактически простаивал. Чтобы сбалансировать их работу, в конце 1950-х – начале 1960-х гг. ЭВМ начали комплектовать независимыми процессорами ввода-вывода для параллельного выполнения вычислений и операций обмена данными, тогда и появился термин «В. с.». Основными преимуществами вычислительной системы по сравнению с однопроцессорной ЭВМ являются: ? значительное повышение производительности за счёт статического или динамического распараллеливания процесса решения задачи (например, выполнение отдельных частей задачи на различных процессорах); ? увеличение эффективности использования оборудования за счёт более полной его загрузки; ? повышение надёжности системы и др. Постоянное увеличение степени интеграции и быстродействия элементов совре-менных микропроцессоров, высокий уровень их надёжности и относительная дешевизна позволяют строить вычислительные системы путём объединения необходимого числа микропроцессоров и организации параллельной обработки данных. Параллелизм в вычислениях в значительной степени усложнил управление вычислительным процес-сом, а также распределение аппаратных и программных ресурсов. Поэтому важная роль в вычислительной системе стала отводиться операционной системе, выполняющей функции планирования вычислительного процесса и распределения ресурсов (оперативной и внешней памяти, процессоров, периферийного оборудования и др.), а также оптимизирующим компиляторам с языков высокого уровня, позволяющим в наибольшей степени использовать архитектурные особенности микропроцессоров. Большую роль в достижении высокой эффективности работы вычислительной системы играет система коммутации, связывающая процессоры между собой или с модулями оперативной памяти. Как правило, для этого применяют общую шину, с которой со-единены процессоры и модули памяти. В вычислительной системе, состоящих из не-скольких процессоров, обычно используют матричные коммутаторы, а также тополо-гию связи – кольцо, звезда и др. При объединении большого числа процессоров при-меняют более сложные топологии связи – тор, гиперкуб и др. Выделяют два направления развития вычислительной техники: 1. Электронные вычислительные машины (ЭВМ) и простейшие вычислительные системы. Эти вычислительные средства основываются на эволюционных модификациях концептуальной последовательной машины Дж. фон Неймана (1945). Вычислительные средства данного направления постоянно совершенствуются. Однако расширение функциональных возможностей, повышение быстродействия и надежности, а также другое совершенствование достигается главным образом за счет улучшения физико-технологических характеристик элементов и внутренних информационных каналов. 2. Вычислительные системы. Эти средства базируются на принципе массового параллелизма при обработке информации. Прогресс в индустрии обработки информации обусловлен достижениями в архитектуре и теории функционирования «большемасштабных» ВС, в параллельной вычислительной математике, в программном обеспечении систем, а также успехами интегральной технологии. ? ВС базируется на трех принципах: ? массовый параллелизм; ? программируемость структуры; ? конструктивная однородность; Основной особенностью ВС является отсутствие единого функционального и конструктивно реализованного устройства: все компоненты (устройство управления, процессор и память) являются распределенными. Основной функционально-структурной единицей вычислительных ресурсов является ЭМ. Виды ВС представлены на рисунке 1 Рисунок 1. Виды вычислительных систем. В последнее время все чаще говорят о высоконагруженных приложениях. Нельзя не заметить, что это теперь очень популярная, можно даже сказать модная, область знаний. Итак, что же такое высоконагруженная система? Ответ на этот вопрос стоит начать с описания качественных свойств такого рода систем. Как правило, к таким качествам относят большое количество пользователей и данных. В целом это правда, но тут есть несколько нюансов: ? это не вся правда; ? приведенные факторы являются количественными, а не качественными. Ниже на основании предпосылки «много пользователей, много данных» будет сформулирован список качественных факторов присущих высоконагруженным систе-мам. Начнем с самого простого. Высоконагруженное приложение в первую очередь является многопользователь-ским. То есть в один момент времени с ним работает более чем один человек. Сейчас, в эру стремительного развития Интернета, это тысячи и сотни тысяч человек. Устойчивая ассоциация высоконагруженных систем с большим количеством пользователей в нашей индустрии появилась очень давно. Ничего принципиально не-верного в такой связи нет. Но если высокая нагрузка подразумевает большое количе-ство пользователей, то большое количество пользователей совсем не обязательно под-разумевает высоконагруженную систему. Если посмотреть на статистику Московского метрополитена за 2010 год, то ока-жется, что средняя часовая нагрузка на систему максимальна в диапазоне от 8 до 9 ча-сов утра. За этот час через турникеты проходят приблизительно 720 тысяч человек. Что порождает необходимость не менее 200 раз в секунду проверять статус предъявленных проездных и принимать решение о пропуске того или иного человека через турникет. В Интернете существует масса высоконагруженных ресурсов с подобными показателями пропускной способности. Например, статистика по StackOverflow за тот же 2010-й год показывает, что их средняя пропускная способность находится в диапазоне 100-150 хи-тов в секунду. Определенно у метрополитена более высокие требования к пропускной способ-ности. Но значит ли это что Московский метрополитен можно считать более «высоко-нагруженным» чем StackOverflow? Вряд ли, в частности потому, что эти две системы оперируют несравнимыми объемами информации. В обоих случаях приведена оценка пропускной способности, так как она дает больше информации о нагрузке, чем количество пользователей системы. Две разные системы могут подталкивать пользователей к разным паттернам их использования. Это может приводить к абсолютно разным требованиям по пропускной способности для этих систем. Пропускная способность точнее описывает количество работы, которую должна уметь выполнять система в единицу времени. К распределенным ВС относят макросистемы системы сложной конфигурации, в которых в качестве функциональных элементов выступают пространственно-рассредоточенные вычислительные средства, основанные на моделях вычислителя и коллектива вычислителей, и сети связи, обеспечивающие взаимный теледоступ между средствами обработки информации. Распределенная ВС объединение пространственно удаленных друг от друга со-средоточенных ВС, основанное на принципах: ? параллельности функционирования сосредоточенных ВС (т. e. способности нескольких или всех сосредоточенных систем совместно и одновременно решать одну сложную задачу, представленную параллельной программой); ? программируемости структуры (т. e. возможности автоматически настраи-вать сеть связи между сосредоточенными ВС); ? гомогенности состава (т. e. программной совместимости различных сосре-доточенных ВС и однотипности элементарных машин в каждой из них). В общем случае РВС предназначаются для реализации параллельных программ решения задач (произвольной сложности или c произвольным объемом вычислений, в монопрограммном и мультипрограммном режимах) на рассредоточенных в простран-стве вычислительных ресурсах. Они должны быть приспособленными и для выполнения функций, присущих вычислительным сетям, и для реализации последовательных программ. В распределенных ВС может быть как централизованное, так и децентрали-зованное управление вычислительными процессами. Самый простой вариант сосредоточенной ВС это ЭМ. Следовательно, простей-шим вариантом РВС является совокупность однотипных и регулярно соединенных ЭМ, использующая «длинные» программно-коммутируемые каналы межмашинной связи. В таком случае в состав ЭМ входят однотипные СУ. Более развитым вариантом распределенных ВС являются системы, структура сети связи которых в целом являются нерегулярной и которые компонyются из программно-совместимых ЭМ. B данном случае сеть связи организуется посредством программно-совместимых системных устройств. B топологическом плане такие ВС клас-сифицируются как централизованные, децентрализованные, кольцевые и радиально-кольцевые системы. B подкласс распределенных ВС входят вычислительные сети. Несмотря на внешнюю схожесть распределенных систем и сетей, существует принципиальное от-личие в их функционировании. Вычислительные сети выполняют обработку потоков задач, как правило, представленных последовательными программами. B распределенных ВС наряду c режимом работы, характерным для вычислитель-ных сетей, реализуется также режим решения общей сложной задачи. Задача представ-ляется параллельной программой, каждая макроветвь (или ветвь) которой реализуется на своей сосредоточенной ВС (или ЭМ). Для распределенных ВС при решении одной сложной задачи характерен режим группового обмена информацией между абонентами (машины - машины, машины - пользователь). Таким образом, распределенные системы относятся к более общему классу средств обработки информации по сравнению c вычислительными сетями и качественно от них отличаются возможностью решения одной сложной задачи на распределенных вычислительных ресурсах. B зависимости от сложности задач и характера их поступления можно выделить следующие основные режимы работы ВС c программируемой структурой: ? решение одной сложной задачи; ? обработка набора задач; ? обслуживание потока задач. Первый режим монопрограммный, т. e. для решения задачи используются все ре-сурсы ВС. Задача представляется в виде параллельной программы, число ветвей в ко-торой либо фиксировано, либо допускает варьирование в заданном диапазоне. B каче-стве единицы ресурса выступает элементарная машина ВС. Все машины используются для решения задачи. Если максимальное количество ветвей в параллельной программе менее общего количества ЭМ в системе, то избыточные машины используются для по-вышения надежности функционирования ВС. Второй и третий режимы функционирования ВС относятся к мультипрограмм-ным. При работе ВС в этих режимах одновременно решается несколько задач, следова-тельно, ресурсы системы делятся между несколькими задачами. При организации функционирования ВС в случае набора задач учитывается не только количество задач, но их параметры: число ветвей в программе (точнее, число машин, на которых она будет выполняться), время решения или вероятностный закон распределения времени решения и др. Алгоритмы организации функционирования ВС задают распределение задач по машинам и последовательность выполнения задач на каждой машине. B результате становится известным, в какой промежуток времени и на каких машинах (или на какой подсистеме) будет решаться любая задача набора. Этот режим, безусловно, является обобщением мультипрограммных режимов для ЭВМ, и он более сложный. B самом деле, при мультипрограммировании ресурсы ЭВМ (прежде всего процессор) делятся между несколькими последовательными программами. При обработке наборов параллельных задач ресурсы ВС (множество элементарных машин) также распределяются между задачами, однако в любой момент времени задачи реша-ются на непересекающихся подмножествах машин. Следовательно, мультипрограммные режимы работы ЭВМ реализуются путем разделения времени процессора, в то время как обработка наборов задач на ВС осуществляется посредством разделения «пространства» машин. Третий режим обслуживание потока задач на ВС принципиально отличается от обработки задач набора: задачи поступают в случайные моменты времени, их парамет-ры случайны, следовательно, детерминированный выбор подсистем для решения тех или иных задач исключен. Для режима потока задач созданы методы и алгоритмы, обеспечивающие стохастически оптимальное функционирование ВС. Следует подчеркнуть, что при работе ВС в любом из мультипрограммных режи-мов система представляется виде композиции подсистем различных рангов. По мере решения задач эта композиция «автоматически» (c помощью ОС) реконфигурируется так, чтобы обеспечить ее адекватность текущей мультипрограммной ситуации. Любая подсистема обладает всеми архитектурными свойствами системы, поэтому ее органи-зация при решении выделенной ей задачи может осуществляться теми же методами, что и организация работы всей ВС в первом режиме. 1.2. Описание масштабируемой задачи Под задачей будем понимать требование выполнить параллельную программу на ресурсах ВС. Исследования показывают, что 98 % вычислительных задач обладают возможностью адаптироваться под доступные конфигурации ресурсов ВС перед нача-лом решения. Такие задачи называют масштабируемыми (moldable). Пример задачи, которая используется в рамках данной работы, показан на рисунке 2. Рисунок 2. Масштабируемая задача. Пользователь направляет задачу в очередь СУР в виде паспорта (скрипта) для оболочки (shell), содержащего требования к ресурсам, атрибуты задания и набор ко-манд, которые необходимо выполнить. 1.3. Теория расписаний Теория расписаний – это раздел исследования операций, в котором строятся и анализируются математические модели календарного планирования (т.е. упорядочива-ния во времени) различных целенаправленных действий с учетом целевой функции и различных ограничений. Содержательно многие задачи теории расписаний являются оптимизационными. Т.е. состоят в выборе (нахождении) среди множества допустимых расписаний (распи-саний, допускаемых условиями задачи) тех решений, на которых достигается «опти-мальное» значение целевой функции. Обычно под «оптимальностью» понимается ми-нимальное или максимальное значение некоторой целевой функции. Допустимость расписания понимается в смысле его осуществимости, а оптимальность в смысле его целесообразности. Другой тип задач заключается в поиске допустимого расписания, удовлетворя-ющего всем условиям. Решение задач теории расписаний усложняется тем фактом, что большинство из них являются NP-трудными, т.е. алгоритмы их решения, реализованные на ЭВМ, могут требовать неприемлемо большое время работы для решения практических задач «большой размерности». Для решения задач ТР необходимо разработать алгоритм решения. То есть по-следовательность действий, выполняемых компьютером, с помощью которых можно построить искомое расписание (допустимое или оптимальное). Алгоритм решения задачи – это последовательность действий, с помощью кото-рых можно построить искомое решение для любого примера задачи. Встречающиеся на практике задачи составления расписаний содержат тысячи, а порой и миллионы за-даний. Поэтому основная цель при исследовании моделей (задач) ТР – это построение эффективных, т.е. быстрых, алгоритмов решения. Решение примера должно быть по-лучено за «разумное» время. Обычно задача теории расписаний характеризуется целевой функцией (критерием оптимальности), которую необходимо минимизировать (реже, максимизировать) на множестве допустимых расписаний. Целевая функция в задачах ТР вычисляется на ос-нове некоторого набора штрафов (штрафных функций), которые возникают при фик-сации порядка обслуживания требований в расписании. Дискретное программирование – раздел математического программирования, посвященный нахождению экстремумов функций, заданных на конечных множествах. Под задачей дискретного программирования (дискретной оптимизации) понима-ется задача математического программирования, в которой обычно необходимо мини-мизировать (или максимизировать) значение некоторой функции f(x) на множестве до-пустимых решений G. Для задач дискретной оптимизации необходимо построить алгоритм решения, время работы которого минимально. Искомый алгоритм должен находить оптимальное или приближенное решение за «разумное» время. То есть необходимо сократить количество выполняемых операций. Сделать это можно сузив круг поиска оптимального решения, то есть, рассматривая не все решения из множества G, а лишь небольшую их часть, подмножество, которое гарантированно содержит оптимальное решение. Метод решения задач дискретной оптимизации – это общая идея, применимая к широкому классу задач. Алгоритм решения – это реализация метода решения для кон-кретной задачи. Различают следующие методы решения: ? Эвристические алгоритмы (в т.ч. вероятностные алгоритмы и локальный поиск); ? Метод динамического программирования; ? Метод Ветвей и Границ; ? Метаэвристические методы; ? Графический метод и т.д. Эвристические алгоритмы – алгоритмы, основанные на правдоподобных, но не обоснованных математически предположениях о свойствах оптимального решения за-дачи. Фактически в эвристическом алгоритме учитывается одно или несколько свойств оптимального решения, на основе которых производится сокращение перебора воз-можных решений. Метод динамического программирования получил большое распространение при решении некоторых задач дискретной оптимизации. Динамическое программирование – раздел математического программирования, посвященный исследованию многошаговых задач принятия оптимальных решений. При этом многошаговость задачи отражает реальное протекание процесса принятия решений во времени, либо вводится в задачу искусственно за счет расчленения процесса принятия однократного решения на отдельные этапы, шаги. Цель такого представления состоит в сведении исходной задачи высокой размерности к решению на каждом шаге задачи меньшей размерности. В 70–90-е годы прошлого века в результате совершенствования эвристических алгоритмов появились т.н. метаэвристические методы, например,г енетические алго-ритмы (Genetic algorithms), метод имитации отжига (Simulated annealing), метод мура-вьиных колоний (Ant Colony Optimization) и др. Идеи этих методов были «заимствова-ны» из разных областей науки. Например, идея Генетического алгоритма из генетики, идея метода муравьиных колоний из биологии и т.д. Метод муравьиные колонии основан на следующем наблюдении из жизни мура-вейника. Муравьи пытаются отыскать пищу поближе к муравейнику. О том, где нахо-дится ближайшая пища, они сообщают друг другу следующим образом. При своем пе-редвижении муравьи оставляют на поверхности «феромонные следы», «запах» которых могут чувствовать другие муравьи. Очередной муравей при поиске пищи ориентируется на феромонный след других муравьев и старается с небольшими отклонениями следовать в том направлении, куда ведет большинство следов. Небольшие отклонения от общего направления позволяют строить новые маршруты и находить новую пищу, а накопление феромона позволяет двигаться в разумном (локально оптимальном) направлении. Основываясь на этом наблюдении, Марко Дориго в 1992 году предложил метод решения оптимизационных задач, названный методом муравьиных колоний. В генетических алгоритмах стараются комбинировать хорошие «решения», чтобы получить еще более «лучшее». В генетике также пытаются скрещивать разные био-логические виды (или особей одного вида), чтобы полученное потомство обладало по-лезными качествами своих родителей. Метаэвристические методы обычно обладают двумя важными особенностями: ? В результате их работы последовательно строятся несколько решений; ? Построение каждого нового решения основывается на накопленных знаниях о качестве предыдущих полученных решений.