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

На правах рукописи

Вяхирев Дмитрий Валерьевич

АЛЬТЕРНАТИВНОЕ РАСПРЕДЕЛЕНИЕ РЕСУРСОВ В СЕТЕВЫХ КАНОНИЧЕСКИХ СТРУКТУРАХ С ИНТЕРВАЛЬНЫМИ ХАРАКТЕРИСТИКАМИ

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ (технические науки)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Нижний Новгород

2005

Работа выполнена на кафедре информатики и автоматизации научных исследований Нижегородского государственного университета им. Н.И. Лобачевского

Научный руководитель: доктор технических наук, профессор ПРИЛУЦКИЙ М.Х.

Официальные оппоненты:

доктор технических наук, профессор Федосенко Ю.С. кандидат физико-математических наук, доцент Гришагин В.А.

Ведущая организация: Институт проблем управления РАН (Москва)

14

Защита диссертации состоится « ^ ' » ф^-У Р&Л* 2005 г. в аудитории 21в корпуса ) _Нижегородского государственного университета

им. Н.И. Лобачевского в Д212.166.13.

часов на заседании диссертационного совета

Заверенные отзывы просим направлять по адресу: 603600, Нижний Новгород, проспект Гагарина, 23, Нижегородский государственный университет им. Н.И. Лобачевского, диссертационный совет Д 212.166.13.

С диссертацией можно ознакомиться в фундаментальной библиотеке университета.

Автореферат разослан

2005 г.

Ученый секретарь диссертационного совета, кандидат физико-математических наук, доцент

Савельев В. П.

Актуальность темы исследования

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

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

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

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

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

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

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

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

Цели исследовании

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

Основными направлениями работы являются

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

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

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

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

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

1. Задача программного управления (без обратных связей).

2. Задача оперативного управления (с обратными связями).

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

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

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

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

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

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

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

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

Теоретическая и практическая ценность

В рамках построенной математической модели ставятся различные

прикладные задачи, возникающие в сфере управления сложными процессами.

Типичными областями применения задач распределения ресурсов являются:

• управление производственной деятельностью;

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

• разработка программного обеспечения;

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

• изготовление сложных изделий;

• строительство объектов;

• управление ресурсами многопроцессорного вычислительного комплекса при параллельных вычислениях,

и другие.

В рамках построенных в работе математических моделей могут быть

поставлены такие известные задачи дискретной оптимизации, как каноническая

и многомерная задачи о ранце, задача Беллмана-Джонсона и др.

Апробация полученных результатов

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

Разработанная система была апробирована на реальных исходных данных в опытном производстве ОКБМ им. И.И. Африкантова (Нижний Новгород) при составлении оптимальных расписаний для цехов опытного производства ОКБМ. Эффективность полученных результатов свидетельствует об адекватности используемых математических моделей условиям производства.

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

Полученные в диссертационной работе результаты обсуждались на всероссийских конференциях «Интеллектуальные информационные системы» (Воронеж, 2000 и 2001 г.), конференции факультета ВМК ННГУ и НИИ ПМК «Математика и кибернетика 2002» (Нижний Новгород, 2002 г.), всероссийской конференции «КоГраф 2002» (Нижний Новгород, 2002 г.), Нижегородской сессии молодых ученых (Дзержинск, 2004 г.), юбилейной конференции, посвященной 50-летию факультета ВМК ННГУ, «Математика и кибернетика 2003» (Нижний Новгород, 2004 г.), шестом международном конгрессе по математическому моделированию (Нижний Новгород, 2004 г.), а также на научных семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ (2002-2004 г.).

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

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

Публикации

Основные полученные в диссертации результаты отражены в 10 публикациях (в т.ч. 3 статьях), список которых приведен в конце автореферата.

Краткое содержание работы

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

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

Рассматриваются задачи дискретного программирования, как подкласс задач математического программирования. Задачи дискретного программирования классифицируются; рассматриваются задачи теории расписаний как подкласс задач дискретного программирования. Задачи теории расписаний традиционно классифицируются на 3 группы: упорядочивания, согласования и распределения. Рассматривается класс задач распределения ресурсов, как объединяющий в себе элементы всех трех групп.

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

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

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

• продолжительность выполнения работы должна принадлежать заданному интервалу длительностей;

• работы в период своего выполнения должны потреблять ресурсы с интенсивностями, принадлежащими заданным интервалам;

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

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

Перечисленные выше требования образуют группу условий технологического типа.

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

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

Глава 2 посвящена рассмотрению общей математической модели интервального альтернативного распределения ресурсов.

В разделе 2.1 построена общая математическая модель. Исходными параметрами модели являются: Т' = |Г",...,7"'| - множество моментов времени, на которые разбит период планирования, / = {],...,/и} и */={1,...,и} - множества ресурсов и работ соответственно, - множество работ, непосредственно предшествующих работе - число множеств альтернативных,

для работы ресурсов, - множества ресурсов, альтернативных для

работы - множество работ, имеющих директивные сроки интервал допустимых длительностей выполнения работы - интервал

допустимых интенсивностей потребления ресурса работой ресурсоемкость работы по ресурсу - директивный срок работы количество, в котором ресурс г будет доступен в период [1,1 +1].

Варьируемые параметры: х) и у) - соответственно моменты начала и окончания выполнения работы _/', г^ - интенсивности потребления работой _/ ресурса I в период времени + е1 - величины, принимающие значение 1, если ресурс / используется работой у, и 0 - в противном случае. Совокупность

расписание.

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

(1) (2)

(3)

(4)

(5)

(6)

(7)

(8)

Группа ограничений (1)-(5) - технологического типа. Смысл условий (1) в том, что начало работы возможно не раньше окончания всех работ, ей предшествующих; (2) - ограничения на длительности выполнения работ: продолжительность выполнения каждой работы принадлежит заданному интервалу; (3) - означают, что совокупность ресурсов, используемых работой, образует систему представителей множеств ресурсов, альтернативных для данной работы. Интерпретация условий (4) следующая. Если ресурс /(/€/) не входит в упомянутую выше систему представителей для работы то

данная работа этот ресурс не использует. Ресурсы, входящие в систему представителей, потребляются только в период выполнения данной работы,

причем интенсивности потребления работами ресурсов находятся в заданных интервалах. Ограничения (5) означают: если ресурс I входит в систему представителей ресурсов, которые используются работой }, то работа j должна использовать ресурс в количестве в противном случае ресурс работой не

используется. Условия (6) - организационного, а (7) - ресурсного типа. Ограничения (8) - естественные ограничения на введенные переменные.

В разделе 2.2 доказано, что проблема проверки совместности системы ограничений математической модели (1)-(8) не разрешима за полиномиальное время.

Для системы ограничений (1)-(8) в разделе 2.2 построена эквивалентная ей система линейных ограничений с частично целочисленными переменными.

В разделе 2.3 рассматривается ряд частных случаев общей математической модели.

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

Дня модели (1)-(5), (8) вопрос существования допустимого решения оказался разрешимым за полиномиальное время. Для всех пар (|,у), где /е/ и , вводятся величины

где {х) обозначает целую часть числа х. т~ и г* представляют собой соответственно минимальные и максимальные длительности выполнения работы у при потреблении ей одного лишь ресурса /'. На основе найденных величин г~ и , рассматривается множество

О, если Мв = --О оо.если=0,Гр >0

со,если т =0

представляющее собой совокупность технологически реализуемых длительностей работы у. Критерий совместности системы (1)-(5), (8) выглядит следующим образом

Теорема 1

Система (1)-(5), (8) совместна тогда и только тогда, когда для всех выполняется:

Второй рассмотренный в разделе 2.3 частный случай общей модели представляет собой систему, которая включает технологические требования (1)-(5), организационные условия (6) и ограничения (8) на введенные переменные. Модель (1)-(6), (8) отражает необходимость выполнить требования технологического и организационного типа; условия же ресурсного вида могут быть нарушены.

Для системы (1)-(6), (8) вопрос совместности также разрешим за полиномиальное время. Для каждой работы ] вводятся вспомогательные параметры и - моменты самого раннего начала и окончания, - которые

рассчитываются по следующим рекуррентным соотношениям

смысл которых - расчет временных характеристик сетевого графика. Теорема 2

Система ограничений (1)-(6), (8) совместна тогда и только тогда, когда одновременно выполняютсяусловия:

1) для всех ,/еУ;

2) для всех /е/*.

Третий частный случай модели (1)-(8), рассмотренный в диссертационной работе, описывает математическую модель, содержащую ограничения (1)-(5) технологического типа, ресурсные условия (7) и ограничения (8) на введенные

Г,еслиАГ(у) = 0

Х' ~ «пах:{у,),еслиК(])ф<2>

переменные. Модель типа (1)-(5). (7), (8) требует обязательного соблюдения требований технологического и ресурсного характера; организационные условия могут быть нарушены.

В работе показано, что задача определения совместности системы (1)-(5), (7), (8) является КР-полной.

Тем не менее, проблема совместности системы (1)-(5), (7), (8) оказалась разрешимой за полиномиальное время в частном случае, когда одновременно выполняются следующие два условия: 1) для каждого IеI выполняется: Ув = У1 для всех 1еТ;

В этом случае всем jeJ мы можем поставить в соответствие множества

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

Если условия 1) и 2) выполняются одновременно, то система (1)-(5). (7),

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

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

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

будет превосходить величину располагаемого ресурса Уи на 1% от значения У1:. Знак - обозначает операцию усеченной разности а-й = тах(я-6,0). '

2)

(8) совместна тогда и только тогда, когда для всех

IX-к,

Г„{Х,У,2,Е) = риЯ—--100, ¡е1,1еТ,

VЛ

И

(9)

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

(10)

Здесь коэффициент - значение штрафа, который будет взиматься, если завершение выполнения работы j произойдет на 1% позже ее директивного срока Dr

Кроме того, в разделе 3.1 формулируются три оптимизационные задачи. Первая из них - задача поиска эффективных технологически и организационно допустимых расписаний, которая получается путем добавления к системе (1)-(6), (8) технологических и организационных ограничений критерия

f„(X,Y,Z,E)->mm,ieI,teT, (11)

где функции f„(X,Y,Z,E) определяются соотношениями (9). Задача (1)-(6), (8), (11) посвящена нахождению расписаний вида a' = (X",Y',Z',E'} таких что

1) а' удовлетворяют ограничениям (1 )-(6), (8);

2) не найдется расписания a = (X,Y,Z,E), удовлетворяющего (1)-(6), (8), такого, что для всех и для некоторых i0 е/, /„еГ.

Вторая оптимизационная задача - поиска эффективных технологически и ресурсно допустимых расписаний - получается посредством добавления к системе (1)-(5)> (7), (8) технологических и ресурсных ограничений критерия

gj(X,Y,Z,E)->mm,jeJ\ (12)

где g^XJtZtE) определяются соотношениями (10). Задача (1)-(5), (7), (8), (12)

посвящена нахождению расписаний вида таких что

1) удовлетворяют ограничениям (1)-(5), (7), (8);

2) не найдется расписания , удовлетворяющего (1)-(5), (7), (8), такого что для всех и для некоторого

Третья оптимизационная задача - поиска эффективных технологически допустимых расписаний - представляет собой комбинацию ограничений (1)-(5),

(8) технологического типа и критериев (11), (12) - штрафов за невыполнение условий соответственно ресурсного и организационного типа. Решением данной задачи будет множество таких расписаний rf = (X',Y',Z',E'}, для которых не

найдется расписания ц = (X,Y,Z,E), которое было бы не хуже расписания t}' по всем критериям и лучше хотя бы по одному критерию (имеется в виду, что г}' и - допустимы для данной задачи).

В разделе 3.2 рассмотрены схемы компромиссов для свертки критериев вида (11) и (12). В результате в качестве свертки критериев (11) выбрана суперпозиция максиминной и аддитивной сверток:

(13)

а для критериев вида (12) - аддитивная свертка вида

g(X,Y.Z,E)^gj{X,Y,Z,E)-niiim. (14)

Критерий в постановке (13) отражает стремление «равномерно» расходовать ресурсы. Максиминная свертка по времени означает: если в некоторый момент времени количество потребляемого ресурса превышает количество доступного ресурса на некоторую величину, то значение критерия не ухудшится, если потребление того же ресурса в другой момент времени превысит доступное количество ресурса на ту же величину. Аддитивная свертка по ресурсам означает стремление равномерно расходовать ресурсы, минимизировав суммарный штраф за нарушение требований ресурсного вида.

Каждая величина - штраф за завершение выполнения

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

Критерии (13), (14) используются в работе для постановки следующих трех оптимизационных задач.

1. Задача типа А. Это задача поиска оптимального технологически и организационно допустимого расписания, включающая ограничения (1)-(6), (8) и критерий (13).

2. Задача типа В. Это задача поиска оптимального технологически и ресурсно допустимого расписания. Она включает ограничения (1)-(5), (7), (8) и

критерий (14). Задачу типа В, для которой для всех 1е1, 1еТ, и

Т*-Т > ^тах {Н^ , будем называть равномерной задачей типа В.

3. Задача типа С. Это задача поиска эффективного технологически допустимого расписания - задача с ограничениями (1)-(5), (8), и критериями (13), (И).

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

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

В разделе 4.1 предложен интервальный подход к описанию решений задач распределения ресурсов с интервальными параметрами. Вводится понятие интервального вектора на множестве Я, как упорядоченной совокупности интервалов X = ([*,';.*?].....[■*";*"])> где для всех у = 1,и. Предложена

концепция интервального расписания как средства описания решения, содержащего неопределенность.

Определение 1

Интервальным расписанием будем называть упорядоченную пару

5 = (Х,У) п-мерных интервальных векторов на множестве Т, где X и У удовлетворяют одновременно следующим требованиям'

1)*)<у);

2)*)<У)

для всех J eJ

Интервальное расписание является результатом решения задачи программного управления В расписании моменты начала и окончания

каждой работы заданы интервально.

Любое расписание, полученное из S путем уточнения параметров, определяет способ, которым будет на практике реализовываться интервальное расписание. Мы приходим, тем самым, к понятию реализации.

Определение 2

Реализацией интервальногорасписаниВ = (Х,У) называетсярасписание р = {Х,У,2,Е), в котором для всех у'е./ одновременно выполняютсяусловия:

1) х, е 3)х,<Уг

Раздел 4.2 посвящен решению задачи типа А. Предлагаемый метод представляет собой человеко-машинную процедуру, выполняющую следующие действия:

1. построение интервального расписания

2. изменение интервального расписания по мере выбора пользователем моментов начала/окончания работ;

3. выбор используемых ресурсов на основании зафиксированных моментов начала/окончания работ;

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

5. определение интенсивностей используемых ресурсов.

Заметим, что на этапе 1 решается задача программного, а на этапах 2-5 -оперативного управления. Совокупность процедур 1-5 объединена в т.н. А-алгоритм.

Теорема3

А-алгоритм обладает следующими свойствами:

1. вычислительная сложностьА-алгоритма непревосходиЮ{п*т};

2. если задача типа А имеет решение, то А-алгоритм находит интервальное расписание 5 = (X, У) прилюбыхзначенияхисходныхпараметров;

3. интервальноерасписание 5 = {Х,У), построенное А-алгоритмом,допускает хотя бы одну реализацию р - (Л", Уу1, £);

4. если р = (Х,У,2,Е) -построеннаяА-алгоритмомреализацияинтервального расписания $ = (Х,У),то р -А-допустимое расписание и не существует

расписания р'= (Х',У',2',Е'), где Х' = Х, У' — У, такого что /(р)—Е,

где £ - заданная точность; 5. при для всех ¡^У и У„~У, для всех /е/, 1еТ интервальное

расписание 5 = допускает реализацию р ,У >2 ,Е являющуюся

€ -оптимальным решением задачи типа А.

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

1. выбор ресурсов для каждой работы;

2. построение интервального расписания 5 = (А',}');

3. определение интервала возможных значений штрафа;

4. изменение интервального расписания и интервального значения штрафа по мере выбора пользователем моментов начала/окончания работ или интенсивностей потребления ресурсов;

Процедуры 1-2 решают задачу программного, а 3-4 - оперативного управления. Совокупность процедур 1-4 объединена в т.н. В-алгоритм.

Теорема 4

В-алгоритм обладает следующими свойствами: 1 вычислительная сложность В-алгоритма не превосходит

2. для равномерной задачи типа В алгоритм строит некоторое интервальное расписание 5 = (Х,У) и интервал [я^*] значений критерия (14), для любых значений исходных параметров, при которых задача имеет решение;

3. если 5 = У) - интервальное расписание, построенное В-алгоритмом, то алгоритм способен построить хотя бы одну реализацию интервального расписания S;

4. любая найденная В-алгоритмом реализация р интервального расписания S

является В-допустимым расписанием, и

5. при Уц^^Мц для всех /б/, 1еТ интервальное расписание S допускает

реализацию являющуюся оптимальным решением задачи

типа В.

В главе 5 рассматривается диалоговая программная система нахождения интервальных расписаний и их реализаций.

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

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

В разделе 5.3 описан пример решения прикладной задачи оптимизации план-графиков для инструментального производства с помощью диалоговой системы.

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

Основные результаты

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

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

• с ограничениями технологического типа;

• с ограничениями технологического и организационного типа;

• с ограничениями технологического и ресурсного типа,

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

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

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

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

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

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

Публикации по теме диссертации

1. Прилуцкий М.Х., Вяхирев Д.В. Распределение ресурсов на основе обобщенных временных характеристик сетевой модели. // Интеллектуальные информационные системы: Труды всероссийской конференции. - Воронеж,

2000, стр. 42.

2. Прилуцкий М.Х., Вяхирев Д.В. Оптимальный и приближенно оптимальный алгоритмы решения задач сетевого планирования. // Интеллектуальные информационные системы: Труды всероссийской конференции. - Воронеж,

2001, стр. 79-80.

3. Вяхирев Д.В. Распределение ресурсов в сетевых структурах с интервально заданными параметрами // Математика и кибернетика 2002: Материалы докладов конференции. - Нижний Новгород, 2002, стр. 30-32.

4. Прилуцкий М.Х., Вяхирев Д.В. Распределение ресурсов в сетевых структурах с интервальными значениями параметров // Математическое моделирование и оптимальное управление: Вестник Нижегородского государственного университета, вып. 1 (25), 2002, стр. 224-233.

5. Вяхирев Д.В. Интервальное распределение ресурсов в сетевых канонических структурах // КоГраф 2002: Материалы докладов всероссийской конференции. - Нижний Новгород, 2002, стр. 97-102.

6. Вяхирев Д.В. Метод декомпозиции при решении задач распределения ресурсов в сетевых канонических структурах // Математика и кибернетика 2003: Сборник научных статей конференции. - Нижний Новгород, 2003, стр. 90-92.

7. Вяхирев Д.В. Об одном алгоритме решения задачи альтернативного распределения ресурсов в сетевых моделях // Технические, программные и математические аспекты управления сложными распределенными системами: Тезисы докладов конференции. - Нижний Новгород, 2003, стр. 18-22.

8. Вяхирев Д.В. Альтернативное распределение ресурсов в сетевых канонических структурах. // Вестник ВГАВТ. Межвузовская серия «Моделирование и оптимизация сложных систем», вып. 9, Нижний Новгород, 2004, стр. 52-59.

9. Вяхирев Д.В. Нахождение интервальных решений задачи альтернативного распределения ресурсов. // IX Нижегородской сессии молодых ученых: Тезисы докладов. - Нижний Новгород, 2004, стр. 8-10.

10.Vyakhirev D.V. Interval approach to alternative resource allocation. // VI International Congress on Mathematical Modeling: Book of Abstracts. - University ofNizhny Novgorod, 2004, p. 132.

Подписано в печать 14.01.05. Формат 60x84 '/16. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 3.

Нижегородский государственный технический университет. Типография НГТУ. 603600, Нижний Новгород, ул. Минина, 24.

введение.

глава 1. задачи распределения ресурсов как задачи математического программирования.

1.1. Место задач распределения ресурсов в классе задач математического программирования.

1.1.1. Место задач теории щсписаний в классе задач математического программирования.,.

1.1.2. Классификация задач теории расписаний.

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

1.2.1. Классификация по способу задания параметров.

1.2.2. Классификация по типу ресурса.

1.2.3. Интервальная арифметика.

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

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

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

2.1. Общая математическая модель.

2.1.1. Исходные параметры модели.

2.1.2. Варьируемые параметры модели.

2.1.3. Ограничения математической модели.

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

2.2.1. NP-полнота проблемы существования решения.

2.2.2. Линеаризация общей математической модели.

2.3. Частные «подмодели» и условия их разрешимости.

2.3.1. Модель с технологическими ограничениями.

2.3.2. Модель с технологическими и организационными ограничениями

2.3.3. Модель с технологическими и ресурсными ограничениями.

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

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

3.1. Многокритериальные задачи альтернативного распределения ресурсов.

3.1.1. Задача типа А'(поиска эффективных технологически и организационно допустимых расписаний).

3.1.2. Задача типа В'(поиска эффективных технологически и ресурсно допустимых расписаний).

3.1.3. Задача типа С'(поиска эффективных технологически допустимых расписаний).

3.2. Схемы компромиссов для постановок задач альтернативного распределения ресурсов с интервальными характеристиками.

3.2.1. Задача типа А (поиска оптимального технологически и организационно допустимого расписания).

3.2.2. Задача типа В (поиска оптимального технологически и ресурсно допустимого расписания).

3.2.3. Задача типа С (поиска эффективного технологически допустимого расписания).

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

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

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

4.2. Алгоритм построения A-допустимых расписаний.

4.2.1. Алгоритм А1 (построения интервального расписания).

4.2.2. Алгоритм А2 (уточнения расписания).

4.2.3. Алгоритм A3 (выбораресурсов).

4.2.4. Алгоритм А4 (определения оптимального значения штрафа).

4.2.5. Алгоритм А5 (расчета интенсивностей потребления ресурсов)

4.2.6. Алгоритм А6 (уточнения интенсивностей потребления ресурсов)

4.2.7. А-алгоритм построения расписаний.

4.3. Алгоритм построения В-допустимых расписаний.

4.3.1. Алгоритм В1 (построения интервального расписания).

4.3.2. Алгоритм В2 (построения реализации интервального расписания)

4.3.3. В-алгоритм построения расписаний.

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

ГЛАВА 5. ДИАЛОГОВАЯ ПРОГРАММНАЯ СИСТЕМА РЕШЕНИЯ ЗАДАЧ ПОСТРОЕНИЯ ИНТЕРВАЛЬНЫХ РАСПИСАНИЙ.

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

5.2. Типовые сценарии решения задач интервального распределения ресурсов.

5.3. Решение задачи оптимизации план-графиков для инструментального производства при изготовлении пресс-форм . 113 Выводы по главе 5.

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

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

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

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

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

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

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

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

Типичными областями применения задач распределения ресурсов являются:

• управление производственной деятельностью;

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

• разработка программного обеспечения;

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

• изготовление сложных изделий;

• строительство объектов;

• управление ресурсами многопроцессорного вычислительного комплекса при параллельных вычислениях, и другие.

Цели исследования

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

Основными направлениями работы являются

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

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

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

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

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

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

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

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

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

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

Диалоговая программная система «Распределение ресурсов», составляющая прикладную часть диссертационной работы, была апробирована на реальных исходных данных в опытном производстве ОКБМ им. И.И. Африкантова (Нижний Новгород) при составлении оптимальных расписаний для цехов опытного производства ОКБМ. Эффективность полученных результатов свидетельствует об адекватности используемых математических моделей условиям производства.

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

Полученные в диссертационной работе результаты опубликованы в 10 работах. Помимо этого, полученные результаты обсуждались на всероссийских конференциях «Интеллектуальные информационные системы» (Воронеж, 2000 и 2001 г.), конференции факультета ВМК ННГУ и ВИИ ПМК «Математика и кибернетика 2002» (Нижний Новгород, 2002 г.), всероссийской конференции «КоГраф2002» (Нижний Новгород, 2002 г.), Нижегородской сессии молодых ученых (Дзержинск, 2004 г.), юбилейной конференции, посвященной 50-летию факультета ВМК ННГУ, «Математика и кибернетика 2003» (Нижний Новгород, 2004 г.), шестом международном конгрессе по математическому моделированию (Нижний Новгород, 2004 г.), а также на научных семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ (20022004 г.).

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

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

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

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

1 альтернативного распределения ресурсов с интервальными параметрами.

В главе 2 рассмотрена общая математическая модель интервального альтернативного интервального распределения ресурсов. Исследована на предмет NP-полноты проблема существования допустимого решения как для общей математической модели, так и для некоторых ее частных случаев.

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

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

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

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

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

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

• Исследованы также модели

- с ограничениями технологического типа;

- с ограничениями технологического и организационного типа;

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

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

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

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

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

• На основе предложенных методов создана диалоговая программная система решения задач распределения ресурсов и упорядочения работ с интервальными значениями параметров.

Заключение

1. Акоф Р., СасиениМ. Основы исследования операций. - М.: Наука, 1971,534 с.

2. Архипова Н.И., КульбаВ.В. Управление в чрезвычайных ситуациях. -М.: Российский гуманитарный университет, 1998, 316 с.

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

4. Батищев Д.И., Прилуцкий М.Х., Тарбеев А.Ф. Перспективное планирование НИОКР в условиях НПО. // В кн.: Моделирование и оптимизация сложных систем. Воронеж, 1984, с. 28-34.

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

6. Берж К. Теория графов и ее применения. М.: ИЛ, 1962,319 с.

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

8. Бурдюк В.Я., Шкурба В.В. Теория расписаний. Задачи и методы решений. //Кибернетика, №1, 1971, с. 89-102.

9. Бурков В.Н. Основы математической теории активных систем. М.: Наука, 1977, 255 с.

10. Бурков В.Н., Кондратьев В.В. Механизмы функционирования организационных систем. М.: Наука, 1981, 383 с.

11. Бурков В.Н., Ланда Б.Д., Ловецкий С.Е., Тейман А.И., Чернышев В.Н. Сетевые модели и задачи управления. М.: Советское радио, 1967, 144 с.

12. БусленкоН.П. Математическое моделирование производственных процессов на цифровых вычислительных машинах. М.: Наука, 1964, 364 с.

13. Вагнер Г. Основы исследования операций. — М.: Мир, 1972, 1, 336 с.

14. Витковский Я.Я. Основы сетевого планирования и управления. — Рига, 1966, 91 с.

15. Вяхирев Д.В. Альтернативное распределение ресурсов в сетевых канонических структурах. // Вестник ВГАВТ. Межвузовская серия «Моделирование и оптимизация сложных систем», вып. 9. Нижний Новгород, 2004, стр. 52-59.

16. Вяхирев Д.В. Интервальное распределение ресурсов в сетевых канонических структурах // КоГраф 2002: Материалы докладов всероссийской конференции. -Нижний Новгород, 2002, с. 97-102.

17. Вяхирев Д.В. Нахождение интервальных решений задачи альтернативного распределения ресурсов. // IX Нижегородская сессия молодых ученых: Тезисы докладов. Нижний Новгород, 2004, с. 8-10.

18. Вяхирев Д.В. Метод декомпозиции при решении задач распределения ресурсов в сетевых канонических структурах. // Математика и кибернетика 2003: Сборник научных статей конференции. Нижний Новгород, 2003, с. 90-92.

19. Вяхирев Д.В. Распределение ресурсов в сетевых структурах с интервальными значениями параметров. // Математика и кибернетика 2002: Материалы докладов конференции. Нижний Новгород, 2002, с. 30-32

20. Гасс С. Линейное программирование. М.: Физматгиз, 1961,303 с.

21. ГергельВ.П., Гришагин В.А., СтронгинР.Г. Передовая технология автоматизированного выбора оптимальных параметров технических устройств и производственных процессов на основе ЭВМ. Горький, 1989, 58 с.

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

23. Гофман А.Дж., Краскал Дж.Б. Целочисленные граничные точки выпуклых многогранников. // В сб. «Линейные неравенства и смежные вопросы». -М.: ИЛ, 1959, с. 325-347.

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

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

26. Давыдов Э.Г. Исследование операций. М/. Высшая школа, 1990, 383 с.

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

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

29. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. М., 1964,460 с.

30. Зуховицкий С.М., Радчик И.А. Математические методы сетевого планирования. -М.: Наука, 1965, 245 с.

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

32. Калбертсон Дж. Математика и логика цифровых устройств. М.: Просвещение, 1965,267 с.

33. Калмыков С.А., Шокин Ю.И., Юлдашев З.Х. Методы интервального анализа. Новосибирск: Наука, 1986,224 с.

34. КиниР.Л., РайфаХ. Принятие решений при многих критериях: предпочтения и замещения: Пер. с англ./ Под ред. И.Ф. Шахнова. М.: Радио и связь, 1981, 650 с.

35. Кладов Г.К., Лившиц Э.М. О задаче минимизации суммы штрафов при составлении расписания. // Кибернетика, №6, 1968, с. 99-100.

36. Коган Д.И., Федосенко Ю.С. Задача диспетчеризации: анализ вычислительной сложности и полиномиально разрешимые подклассы. // Дискретная математика, 1996, т.8, № 3, с. 135-147.

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

38. Конвей Р., Джонсон Б., Максвелл У. Экспериментальные исследования распределения работ в соответствии с фиксированными правилами очередности их выполнения // В сб. «Применение статистических методов в производстве». М., 1963, с. 212-232.

39. Конвей Р., Максвелл У. Календарное планирование в условиях сети очередей с дисциплиной по кратчайшей операции. // В сб. «Календарное планирование». М., 1966, с. 321-347.

40. Корбут А.А. Неоднородные задачи размещения (типа транспортной). // В сб. «Применение математики при размещении производительных сил». -М.: Наука, 1964, с. 49-53.

41. Корбут А.А., Малинников В.В., Приближенное решение некоторых неоднородных моделей размещения. // Эконом, и матем. методы, 1965, 1, №3, с. 425-441.

42. Корбут А.А., Финкелыптейн Ю.Ю. Дискретное программирование. -М.: Наука, 1969,368 с.

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

44. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б., Математическое программирование. -М.: Высшая школа, 1980, 300 с.

45. Левин Г.М., Танаев B.C. Декомпозиционные методы оптимизации проектных решений. Минск: Наука и техника, 1978,240 с.

46. Мамиконов А.Г., Кульба В.В. Синтез оптимальных модульных систем обработки данных. -М.: Наука, 1986,275 с.

47. Матюшков Л.П., Танаев B.C. Программные генераторы допустимых расписаний. // В сб. «Вычислительная техника в машиностроении». -Минск, 1967, июль, с. 35-48; 1968, февраль, с. 12-28.

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

49. Михалевич В.С, Шкурба В.В. Последовательные схемы оптимизации в задачах упорядочения выполнения работ. // Кибернетика, №2, 1966, с. 34-40.

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

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

52. Подчасова Т.П., Лагода А.П., Рудницкий В.Ф. Управление в иерархических производственных структурах. — Киев: Наукова думка, 1989, 183 с.

53. Португал В.М. Применение комбинаторного метода для решения задачи составления расписаний. //Кибернетика, №4, 1967, с. 98-100.

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

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

56. Прилуцкий М.Х. Распределение однородного ресурса в иерархических системах древовидной структуры. // Идентификация систем и задачи управления SICPRO 2000: Труды международной конференции. М.: ИПУ РАН, 2000, с. 2038-2049.

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

58. Прилуцкий М.Х., Вяхирев Д.В. Оптимальный и приближенно оптимальный ; алгоритмы решения задач сетевого планирования. // Интеллектуальные информационные системы: Труды всероссийской конференции. Воронеж, 2001, с. 79-80.

59. Прилуцкий М.Х., Вяхирев Д.В. Распределение ресурсов на основе обобщенных временных характеристик сетевой модели. // Интеллектуальные информационные системы: Труды всероссийской конференции. Воронеж, 2000, с. 42.

60. Прилуцкий М.Х., Кумагина Е.А. Задача упорядочения работ как задача о назначениях. // Вестник Нижегородского государственного университета, серия «Математическое моделирование и оптимальное управление», вып. 21, 1999, с. 18-24.

61. Прилуцкий М.Х., Кумагина Е.А. Задачи распределения разнородных ресурсов в сетевых канонических структурах. // Перспективныеинформационные технологии и интеллектуальные системы, 2000, №4, с. 46-52.

62. Прилуцкий М.Х., Нефедов Д.С., Попов Д.В. Распределение ресурсов в дискретно управляемых системах. // Электронный журнал «Исследовано в России», 2002, 032/020228, с. 322-337 http://zhurnal.ape.relarn.ru/articles/2002/032.pdf.

63. Прилуцкий М.Х., Попов Д.В. Многостадийные задачи распределения и упорядочивания с нечеткими характеристиками. // Электронный журнал «Исследовано в России», 109, 1182-1189, 1998 http://zhurnal.ape.relarn.ru/articles/2001/109.pdf.

64. Прилуцкий М.Х., Попов Д.В. Распределение и упорядочение работ в многостадийных системах. // Межвузовский тематический сборник научных трудов ВГАВТ. Нижний Новгород, 1999, с. 84-93.

65. Прилуцкий М.Х., Рапопорт И.А. Распределение ограниченных ресурсов в иерархических компьютерных системах И Сб. трудов ВятГТУ. Киров: ВятГТУ, 2000, с. 67-72.

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

67. Прилуцкий М.Х., Тарбеев А.Ф. Планирование и управление НИОКР в условиях НПО. // Передовой опыт, 1984, №1, с. 3-7.

68. Прилуцкий М.Х., Шевченко В.Н. Об одном подходе к составлению оптимального плана работ. // Сб. «Исследования по кибернетике». — М.: «Советское радио», 1970, с. 18-20.

69. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975, 320 с.

70. Сафроненко В.А. Математическое и электронное моделирование задачи оптимального календарного планирования. — Минск, «Наука и техника», 1972, 182 с.

71. Семенов А.И., Португал В.М. Задачи теории расписаний в календарном планировании мелкосерийного производства. -М.: Наука, 1972, 183 с.

72. Смирнов B.C., Власов С.А. и др. Методы и модели управления проектами в металлургии. М.: СИНТЕГ, 2001, 176 с.

73. Стори А.Е., Вагнер Х.М. Опыт применения целочисленного программирования при расчете календарного плана для предприятий единичного и мелкосерийного производства. // В сб. «Календарное планирование». -М.: Прогресс, 1966, с. 241-256.

74. Таланов В.А. Математическая модель некоторых задач теории расписаний. // В сб. «Вычислительная техника в машиностроении», 1972, декабрь, с. 12-16.

75. Танаев B.C. Декомпозиция и агрегирование в задачах математического программирования. Минск: Наука и техника, 1987,180 с.

76. Танаев B.C. К теории расписаний. ДАН БССР 8, №12, 1964, с. 792794.

77. Танаев B.C. Метод решения задач дискретного программирования. // Экономика и матем. методы 4, вып. 5, 1968, с. 776-782.

78. Танаев B.C. Прерывания в детерминированных системах обслуживания с параллельными идентичными приборами. //Изв. АН БССР, сер. физмат. наук, №6,1973, с. 44-48.84,85.86,87,88,89,90,9192,93,94,95,96,97

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

80. ТанаевВ.С., Гордон B.C., Шафранский Я.М. Теория расписаний.

81. Одностадийные системы. -М.: Наука, 1984, 382 с.

82. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний.

83. Многостадийные системы. -М.: Наука, 1989, 327 с.

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

85. Хеллер И., Томпкинс Ч.Б. Обобщение одной теоремы Данцига. // В сб. «Линейные неравенства и смежные вопросы». М.: ИЛ, 1959, с. 348354.

86. Шкурба В.В., Подчасова Т.П., ПшичукА.Н., ТурЛ.П. Задачи календарного планирования и методы их решения. Киев: Наукова думка, 1966, 155 с.

87. Шокин Ю.И. Интервальный анализ. Новосибирск: Наука, 1981, 112 с. Юдин Д.Б. Методы количественного анализа сложных систем. // I. ИАН СССР, техн. киберн., 1965, №1, с. 3-13.

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

89. Antill J.M., Woodhead R.W. Critical Path Methods in Construction Practice. Wiley, New York, 1990, 448 p.

90. Archibald R.D., Villoria R.L. Network-Based Management Systems (PERT/CPM). Wiley, New York, 1967, 532 p.

91. Balas E. Machine sequencing via disjunctive graphs: an implicit enumeration algorithm. // Operat. Res. 17, №6, 1969, p. 941-957.

92. Bellman R. Dynamic programming treatment of the traveling salesman problem. // J. Assoc. Comput. Mach., 1962, 9, №1, p. 61-63.

93. Bellman R. Mathematical aspects of scheduling theory. // J. Soc. Industr. and Appl. Math. 4, №3, 1956, p. 168-205.

94. Bellman R., Gross O. Some combinatorial problems arising in the theory of multistage processes. // J. Soc. Industr. and Appl. Math. 2, №3, 1954, p. 175-183.

95. Dantzig G.B. Linear programming and extensions. New Jersey, Princeton University Press, 1963, 648 p.

96. Davis L. Handbook of Genetic Algorithms. van Nostrand Reinhold. New York, 1991,384 р.

97. Even S., Itai A., Shamir A. On the complexity of timetable and multicommodity flow problems. // SIAM J: Comput. 5, 1976, p. 691-703.

98. Garey M.R., Johnson D.S., Sethi R. The complexity of flowshop and jobshop scheduling.//Math.Oper.Res. 1, 1979, p. 117-129.

99. Gonzalez Т., Sahni S. Flowshop and jobshop schedules: complexity and approximation. // Oper. Res. 26, 1978, p. 36-52.

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

101. Heller J., Logemann G. An algorithm for construction and evaluation of feasible schedules. // Manag. Sci. 8, №2,1962, p. 168-183.

102. Johnson S.M. Discussion: sequencing «-jobs on two machines with arbitrary time lags. // Manag. Sci. 5, №3, 1959, p. 299-303.

103. Johnson S.M. Optimal two- and three-stage production schedules with set-up times included. //Nav. Res. Log. Quart. 1, №1, 1954, p. 61-68.

104. Kuhn H.W. Variants of the Hungarian Method for Assignment Problems. // Naval Research Logistics Quarterly, 1956, 3, p. 253-258.

105. Land A.H., Doig A.G. An automatic method of solving discrete programming problems. // Econometrica, 1960, 28, №3, p. 497-520.

106. Little J.D.C., MurtyK.G., Sweeny D.W., Karel C. An algorithm for the traveling salesman problem. // Operat. Res., 1963, 11, №6, p. 972-989.

107. Maxwell W.L., Mehra M. Multiple-factor rules for sequencing with assembly constraints. //Nav. Res. Log. Quart. 15, №2, 1968, p. 241-254.

108. Miller C.E., Tucker A.W., Zemlin R.A. Integer programming formulation of traveling salesman problems. // J. Assoc. Comput. Mach., 1960, 7, №4, p. 326-329.

109. Mitten L.G. Sequencing л-jobs on two machines with arbitrary time lags. // Manag. Sci. 5, №3, 1959, p. 293-298.

110. Moore R.E. Interval Analysis. // Englewood Cliffs. N.J.: Prentice-Hall, 1966.

111. Ratschek H. Die Subdistributivitat der Intervallarithmetik. // ZAMM, 1971, Bd 51, S. 189-192.

112. Ratschek H. Nichtnumerische Aspekte der Intervallarithmetik. // In: Interval Mathematics/Ed. By K. Nickel. Lecture Notes in Computer Science, 29. Berlin-Heidelberg: Springer-Verl., 1975, p. 48-74.

113. Sisson R.L. Methods of sequencing in job shops (A review). // Operat. Res. 7, №1, 1959, p. 10-29.

114. Sisson R.L. Sequencing theory. // Progr. Operat. Res., vol. 1, New York -London, John Wiley and Sons Inc., 1961, p. 293-326.

115. Spaniol O. Die Distributivitat in der Intervallarithmetik. // Computing, 1970, v. 5, p. 6-16.

116. Vyakhirev D.V. Interval approach to alternative resource allocation. // VI International Congress on Mathematical Modeling: Book of Abstracts. -University of Nizhny Novgorod, 2004, p. 132.

117. Young R.C. The algebra of many-valued quantities. // Math. Ann., 1931, v. 104, p. 260-290.