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

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

РАИМОВ Фарит Фатрахманович

РАЗРАБОТКА МЕТОДА И АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ СОСТАВЛЕНИЯ РАСПИСАНИЙ В ПОДСИСТЕМАХ АСУП

05.13.06 - Автоматизация и управление технологическими процессами и производствами (промышленность)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Оренбург 2005

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Оренбургский государственный университет».

Научный руководитель: доктор технических наук, профессор

Абдрашитов Рамзес Талгатович

Официальные оппоненты: доктор технических наук, профессор

Лысов Владимир Ефимович;

кандидат технических наук, доцент Черноусова Антонина Михайловна

Ведущая организация: ООО «Волго-уральский научно-

исследовательский и проектный институт нефти и газа»

Защита состоится «9» июля 2005 г. в «1400» часов на заседании диссертационного совета Д212.181.02 в ГОУ ВПО «Оренбургский государственный университет» по адресу: 460018, г. Оренбург, пр. Победы, 13, ауд. 6205.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Оренбургский государственный университет».

Автореферат разослан « » июня 2005 г.

Ученый секретарь диссертационного совета

Рассоха В.И.

ЬЪя-С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Это делает актуальным возврат к решению задач оптимизированного составления расписания. Работа по теме выполнялась в рамках научно-технических программ «Компьютерные интегрированные производственные системы» (приказ Гособразования СССР № 349 от 23.05.90 г.); программы № 50/24 «Технологии, машины и производства будущего» (1990-1996 гг., Государственный заказчик - Миннауки России); федеральной программы «Российская инжиниринговая сеть технических нововведений» (постановления Правительства РФ № 322 от 15.04.94 г. и № 1207 от 04.12.95 г.); госбюджетной научно-исследовательской темы «Синтез, реализация и исследование эффективности оптимальных технических и организационных систем» (ГР№ 01890036607).

Цель работы: сокращение сроков и """""'гирте раскованности принятия решений при составлении расписаний в пацййЯ^ШМЧЮИКЬИЛЯ

^ Н К Г »ИМИвГМА

! ¿»аст

ття *

Поставленная цель определила следующие основные задачи диссертационной работы:

- анализ существующих методов решения задачи о расписании;

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

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

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

- оценка эффективности предлагаемого метода при составлении расписания для конкретных объектов.

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

Предмет исследований - процесс составления расписания для рассматриваемых видов деятельности.

Методика исследования: методы теории управления, теории расписаний, системной оптимизации, графов, объектно-ориентированного программирования.

Научную новизну составляют:

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

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

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

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

- алгоритм формирования оптимального расписания.

Практическая значимость состоит:

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

£ УЩЧ»**^ > I

I .,« м

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

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

Реализация результатов работы. Фрагменты результатов исследования в виде программной системы «LogiPlan» (per. № 89 от 03.05.05 г.) использованы в ОАО «Оренбургуголь» при разработке проекта «Создание углепромышленной компании на базе Тюльганского угольного разреза», в ЗАО «Уралэлектро-СТМ» при разработке календарного плана освоения нового изделия, в ООО КБ «Гидропресс» при разработке технологических процессов отдельных производств, в учебном процессе Оренбургского государственного университета, приняты к использованию ООО «Фрэйм».

Апробация работы. Основные положений, материалы и результаты работы докладывались, обсуждались и были одобрены на межвузовской научно-методической конференции «Технологии образовательного процесса» (Оренбург, 1997), всероссийской научно-практической конференции «Качество профессионального образования: обеспечение, контроль и управление» (Оренбург, 2003), VIII международной научной конференции «Проблемы менеджмента и рынка» (Оренбург, 2003), VII международной научно-методической конференции «Университетское образование» (Пенза, 2003).

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

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

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

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

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

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

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

Публикации. По материалам диссертационной работы опубликованы 11 печатных работ, в том числе 6 статей в сборниках научных трудов и 1 учебное пособие, получено 1 свидетельство о регистрации программного средства.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

На основании анализа состояния проблемы сформулированы цель и задачи исследования.

Во второй главе «Теоретические основы решения задачи о расписании в подсистемах АСУП» рассматривается постановка производственной задачи оперативно-календарного планирования (ОКП) и задачи управления проектами, сформулированы основные положения предлагаемого подхода к решению задач составления расписания.

В производственной задаче ОКП производственный процесс рассматривается состоящим из конечного множества N = {1,2.....я} производственных

операций, выполняемых конечным множеством М ={1,2.....т} производственных

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

При этом выполнение производственного процесса предполагает, что каждая производственная операция < в N каждого уровня с/, 1 < г/ < /;, может быть исполнена некоторым множеством производственных единиц М' стланного уровня. В зависимости от типа обслуживающей системы производственная операция / уровня г/ либо может быть выполнена любой производственной единицей из всех имеющихся Ье ЛГ (но не более чем одной одновременно), либо должна выполняться конкретно заданной производственной единицей из множества М'ц.

В управлении проектами рассматривается конечное множество

N = {1,2,...,п} работ по проекту и конечное множество М = {1,2.....т} исполнителей.

Процесс выполнения работы / е N включает г, стадий. При этом каждой работе <6 N и каждой стадии q, 1 < <7 < г,, сопоставляется некоторое множество исполнителей М'ч с М . В зависимости от типа обслуживающей системы работа / на стадии ц либо может быть выполнена любым из исполнителей ¿6 М'н (но не более чем одним одновременно), либо должна одновременно выполняться всеми исполнителями из множества М'ч.

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

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

Таблица 1 - Совокупность понятий для описания различных процессов

Элемент Определение Связь с другими элементами Свойства

Производственная единица <ПЕ) понятие некоторого абстрактного производственного узла, на котором совершаются некоторые также абстрактные производственные операции с другими производственными единицами; с производственными операциями • список закрепленных производственных операций; • неприоригеный список ПЕ

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

Уровень процесса (УП) очередность выполнения групп производственных операций каждый УП можез относиться только к одному процессу; последовательность УП задает невозможность выполнения операций из нижнего уровня раньше операции верхнего уровня • список вариантов последовательностей выполнения ПО

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

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

Граф вариантов путей возможные варианты производственного процесса без проекции на производственную базу учитываются возможные связи между ПЕ •ПО; • ПЕ

Карта путей варианты прохождения производственных единиц состоит из ПЕ и всех возможных для нее ПО •ПЕ; •список ПО

Производственный путь найденная по заданным условиям последовательность выполнения операций элемент графа вариантов путей • ПО; • ПЕ; •производительность; •длина ребра

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

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

Информационная модель включает:

- модель производственной базы;

- модель человеческих ресурсов;

- модель выработки;

- модель процесса.

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

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

Каждая ПЕ идентифицируется классификационным признаком (из которого следует Список возможных к выполнению операций) и характеризуется следующими атрибутами (рис. 1):

ВОЗМОЖНЫЕ ПРОИЗВОДСТВЕННЫЕ ОПЕРАЦИИ Прои9»оли**я»иосп Длин* путч 1|§§ 1 8® £ о ~ й

ПрМЯкОдаТААНОеП Длим« «утн

П р оюв одат«л» ноет» ГЕР ОИЗВОДС ХВЕНИАЯ ЕДИНИЦА Длин» пути

* а» • * ф ф

Пр ОК» ОДИТ« /X» ноет» Ддаи» * гтут**

..... - .......-

: ЪЛ ОН ДЛЯ | ! производственной ■ МОП для пути | единицы ;

Рис. 1 - Производственная единица

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

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

в) наличие человеческих ресурсов.

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

В общем виде информационная модель объекта исследования (рис. 2) представляет собой список процессов, реализация которых необходима для достижения конечной цели.

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

и

¡ПУТИ, ОПРЕДЕЛЯЮЩИЕ ВОЗМОЖНЫЕ СВЯЗИ МЕЖДУ {ПГОШВОДСТВЕННЫМИ ЕДИНИЦАМИ, ХАРАКТЕРИЗУЮТСЯ I ДЛИНОЙ ПУТИ И МАТРИЦЕЙ ОТНОСИТЕЛЬНОЙ | ПРОИЗВОДИТЕЛЬНОСТИ ДЛЯ ПУТИ (МОП П)

Рис. 2 - Информационная модель объекта исследования

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

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

Рис. 3 - Алгоритм поиска решений

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

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

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

В выводе результатов предусмотрено три варианта:

а) вывести список производственных единиц, на которых может быть выполнена та или иная операция;

б) вывести список длин производственных путей;

в) вывести варианты решений.

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

На основании представленных моделей и алгоритмов разработан программный комплекс «Ьо£1Р1ап» (рис. 4).

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

а) при составлении календарного графика выполнения работ по проекту;

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

в) для решения типовой задачи производственной логистики.

Результатом использования программного комплекса в управлении

проектом служит календарный план выполнения нового проекта на ОАО «Оренбургуголь». Календарный план (рис. 5) представлен в виде двух граничных вариантов - с минимально- и максимально возможной трудоемкостью.

оптимального расписания

Экономия времени при решении данной задачи с использованием программы «1^1Р1ап» составила 9,1 %.

На ООО КБ «Гидропресс» изготовление группы деталей «Штуцер ОСТ2 Э94-10-75» выполнялось по типовому технологическому маршруту. При этом для обработки центрального отверстия квалитета Н9 в диапазоне диаметров <1|=6,5-г46,5 мм (для разных типоразмеров штуцеров) предусматривался единый набор технологических переходов: Сверлить, рассверлить отверстие до (¡¡.

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

Для поиска оптимального варианта индивидуального технологического процесса в системе «1^1Р1ап» была составлена схема процесса обработки от-

верстия с возможными вариантами обработки (рис. 6), и для разных значений с)| получены различные варианты содержания технологической операции.

Запуск проекта л Я

Проектирование Я

Разработка спецификаций А я V

Оценка поставщиков к *

Заказ материалов я к

Получение материалов я

Разработка производственных планов

Проектирование оборудования //

Изготовление корпуса щ *

Изготовление исходных частей 5]

Основная сборка * Я

Тестирование У*

X ><х

Контроль качества устройства я >

Поставка оборудования 7 > V

янв фев мар апр май *юн июл авг сен окт ноя , [ек янв

пЯl^.ччN чя?ГХ X Л Гтп=337

Тт-370

ГруппаЗ» ГруппаЛЬиМ«^

Максимальная длина пути Минимальная длина пути

Рис. 5 - Календарный план выполнения проекта в двух граничных вариантах

Уровень 1

Сверло ¿10

Уровень2 _г

¥

Сверло ЬЗЗ

Зенкер

УроОеньЗ

Г7

Резец проходной Развертка

Резец проходной

Рис. 6 - Схема возможных вариантов обработки отверстия

Результаты работы системы, дающие ответ на поставленные вопросы, выводятся для информационной модели процесса с конкретными значениями входных параметров. Однажды составив информационную модель какого-либо процесса, и сохранив ее в файле данных «Ьо§1'Р!ап», можно в дальнейшем получать различные варианты его выполнения для тех или иных конкретных данных.

Таким образом, система «Ьо^Р1ап» на выходе дает не только однозначное решение, но и позволяет исследовать производственный процесс как с изменением исходных данных, так и без изменения их. Если требуется получить оптимальное решение, то включается алгоритм отсечения длинных путей.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ ПО РАБОТЕ

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

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

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

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

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

5. Использование разработанной программы позволяет добиться улучшения показателей эффективности производственных процессов за счет оптимизации последовательности выполнения производственных операций в среднем на 10 % без учета сокращения времени за счет автоматизации составления расписаний.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В РАБОТАХ

I. Раимов, Ф. Ф. Составление расписания для школ / Ф. Ф. Раимов, О. В. Буреш, М. А. Токарева, В. И. Чепасов // Анализ структур электронной и вычислительной техники : сб. науч. ст. / Оренбург, гос. ун-т. - Оренбург, 1996. -С. 79-85.

2. Токарева, М. А. Построение рейтинговых моделей / М. А. Токарева, Ф. Ф. Раимов, О. В. Буреш // Анализ структур электронной и вычислительной техники : сб. науч. ст. / Оренбург, гос. ун-т. - Оренбург, 1996. - С. 86 - 90.

3. Буреш, О.В. Дискретная последовательность экономических показателей длительности и периода / О. В. Буреш, Ф. Ф. Раимов, М. А. Токарева // Анализ структур электронной и вычислительной техники : сб. науч. ст. / Оренбург, гос. ун-т. - Оренбург, 1996. - С. 91 - 96.

4. Раимов, Ф. Ф. Составление расписания для технологических процессов // Оптимизация информационных систем : межвуз. сб. науч. ст. / Оренбург, гос. ун-т. - Оренбург, 1997. - С. 138 - 141.

5. Чепасов, В. И., Раимов, Ф. Ф. Расписание для школы на Прологе // Оптимизация информационных систем : межвуз. сб. науч. ст. / Оренбург, гос. ун-т. - Оренбург, 1997. - С. 142 - 148.

6. Чепасов, В. И. Алгоритм не пересечений на Прологе / В. И. Чепасов, Ф. Ф. Раимов, О. В. Буреш // Технология образовательного процесса : тез. докл. межвуз. науч.-метод. конф. / Оренбург, гос. ун-т. - Оренбург, 1997. - С. 19.

7. Чепасов, В. И. Алгоритмическая и программная реализация задачи о расписании : учеб. пособ. / В. И. Чепасов, С. К. Кулов, Ф. Ф. Раимов / Оренбург, гос. ун-т. - Оренбург, 1999. - 192 с.

8. Чепасов В. И., Раимов Ф. Ф. Основные характеристики алгоритма составления расписания. - Деп. в ВИНИТИ 27.04.01, № 1110.

9. Раимов Ф. Ф. Роль компьютерного составления расписания в повышении качества образования // Качество профессионального образования: обеспечение, контроль и управление : сб. науч. стат. / Оренбург, гос. ун-т. -Оренбург, 2003. - С. 367 - 368.

10. Раимов Ф. Ф. Применение компьютерных методов при составлении расписания // Университетское образование : сб. материалов VII Междунар. науч.-метод. конф. / Пензен. гос. ун-т. - Пенза, 2003. - С. 509 - 510.

11. Раимов Ф. Ф. Роль информатизации в региональном управлении // Проблемы менеджмента и рынка : материалы VIII Междунар. науч. конф. / Оренбург, гос. ун-т. - Оренбург, 2004. - С. 62 - 63.

12. Раимов Ф. Ф. LogiPIan / Ф. Ф. Раимов, Р. Т. Абдрашитов // Свидетельство о регистрации разработки программы система автоматизированного составления расписания : [Электронный ресурс] / Оренбург, гос. ун-т., Университетский фонд алгоритмов и программ (1551 Кб). - Оренбург: ОГУ, 2005. - 1 электрон, опт. диск (CD-ROM).

Лицензия ЛР 020716 от 02.11.98 Подписано в печать 03.05.2005 Формат 60x84 / , гарнитура «Тайме» Усл. печ. листов 1,0. Тираж 100 экз. Заказ 336.

ИПКОГУ 460018, г. Оренбург, пр. Победы 13, ГОУ ВПО «Оренбургский государственный университет».

>118 49

РНБ Русский фонд

2006-4 6876

Введение.

Глава 1 Современное состояние вопроса. Цель и задачи исследования.

1.1 Актуальность проблемы составления оптимального расписания.

1.2 Постановка задач теории расписаний.

1.3 Критерии построения оптимальных расписаний.

1А Существующие средства оптимизации расписаний.

1.4.1 Алгоритм оптимизации матрицы расписания.

1.4.2 Алгоритм заполнения матрицы расписания.

Ф 1.5 Выводы. Цель и задачи исследования.,.

Глава 2 Теоретические основы оптимизации решений задачи о расписании в АСУП.

2.1 Постановка трудно решаемых задач теории расписаний.

2.1.1 Производственная задача оперативно-календарного планирования.

2.1.2 Понятие проекта.

2.1.3 Направленность на достижение цели.

2.1.4 Координированное выполнение взаимосвязанных действий.

2.1.5 Ограниченная протяженность во времени.

2.1.6 Уникальность.

2.1.7 Управление проектом.

2.1.8 Жизненный цикл проекта.

2.2 Формирование расписания работы оборудования методами линейного и динамического программирования.

2.3 Основные понятия алгоритма оптимизации для задач составления расписаний.

Глава 3 Реализация алгоритмов поиска решений.

3.1 Общая структура производственного процесса.

3.1.1 Описание модели производственной базы.

3.1.2 Описание модели человеческих ресурсов.

3.1.3 Описание схемы выработки производственных единиц.

3.1.4 Модель производственного процесса.

3.1.5 Общая информационная модель объекта исследования.

3.2 Описание алгоритмов работы программы.

3.3 Используемые структурные данные.

3.4 Описание принципов работы и интерфейса программы «LogiPlan».

3.5 Пример работы программы.

Щс Глава 4 Области применение системы «LogiPlan».

4.1 Применение «LogiPlan» при управлении проектом.

4.1.1 Общая характеристика Тюльганского угольного разреза.

4.1.2 Существо проекта.

4.1.3 Экономическая ситуация на Тюльганском угольном разрезе.

4.1.4 Стратегия реализации проекта.

4.2 Применение системы «LogiPlan» для составления карты типовой операции механической обработки.

4.3 Применение системы «LogiPlan» для решения задач производственной логистики.

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

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

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

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

Это делает актуальным возврат к решению задач оптимизированного составления расписания. Работа по теме выполнялась в рамках научно-технических программ «Компьютерные интегрированные производственные системы» (приказ Гособразования СССР № 349 от 23.05.90 г.); программы № 50/24 «Технологии, машины и производства будущего» (1990-1996 гг., Государственный заказчик - Миннауки России); федеральной программы «Российская инжиниринговая сеть технических нововведений» (постановления Правительства РФ № 322 от 15.04.94 г. и № 1207 от 04.12.95 г.); госбюджетной научно-исследовательской темы «Синтез, реализация и исследование эффективности оптимальных технических и организационных систем» (ГР № 01890036607).

Цель работы: сокращение сроков и повышение обоснованности принятия решений при составлении расписаний в подсистемах АСУП.

Поставленная цель определила следующие основные задачи диссертационной работы:

- анализ существующих методов решения задачи о расписании;

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

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

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

- оценка эффективности предлагаемого метода при составлении расписания для конкретных объектов.

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

Предмет исследований - процесс составления расписания для рассматриваемых видов деятельности.

Методика исследования: методы теории управления, теории расписаний, системной оптимизации, графов, объектно-ориентированного программирования.

Научную новизну составляют:

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

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

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

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

- алгоритм формирования оптимального расписания.

Практическая значимость состоит:

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

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

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

Реализация результатов работы. Фрагменты результатов исследования в виде программной системы «LogiPlan» (per. № 89 от 03.05.05 г.) использованы в ОАО «Оренбургуголь» при разработке проекта «Создание углепромышленной компании на базе Тюльганского угольного разреза», в ЗАО «Уралэлектро-СТМ» при разработке календарного плана освоения нового изделия, в ООО КБ «Гидропресс» при разработке технологических процессов отдельных производств, в учебном процессе Оренбургского государственного университета, приняты к использованию ООО «Фрэйм».

Апробация работы. Основные положения, материалы и результаты работы докладывались, обсуждались и были одобрены на межвузовской научно-методической конференции «Технологии образовательного процесса» (Оренбург, 1997), всероссийской научно-практической конференции «Качество профессионального образования: обеспечение, контроль и управление» (Оренбург, 2003), VIII международной научной конференции «Проблемы менеджмента и рынка» (Оренбург, 2003), VII международной научно-методической конференции «Университетское образование» (Пенза, 2003).

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

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

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

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

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

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

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

Публикации. По материалам диссертационной работы опубликованы 11 печатных работ, в том числе 6 статей в сборниках научных трудов и 1 учебное пособие, получено 1 свидетельство о регистрации программного средства.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ ПО РАБОТЕ

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

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

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

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

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

5. Использование разработанной программы позволяет добиться улучшения показателей эффективности производственных процессов за счет оптимизации последовательности выполнения производственных операций в среднем на 10 % без учета сокращения времени за счет автоматизации составления расписаний.

1. Автоматизированное проектирование и производство в машиностроении / под ред. Ю. М. Соломенцева, В. Г. Митрофанова. М.: Машиностроение, 1986. - 256 с.

2. Адельсон-Вельский, Г. М. О некоторых вопросах сетевого планирования / Г. М. Адельсон-Вельский // Исследования по дискретной математике : сб. / под ред. Г. М. Адельсон-Вельского. М. : Наука, 1973. -С. 105-134.

3. Адельсон-Вельский, Г. М. Потоковые алгоритмы / Г. М. Адельсон-Вельский, Е. А. Диниц, А. В. Карзанов. М. : Наука, 1975. -120 с.

4. Айзенштат, В. С. Многооператорные циклические процессы / В. С. Айзенштат // Докл. АН БССР. 1963. - Т. 7, № 4. - С. 224-227.

5. Алюшкевич, В. Б. Исследование устойчивости оптимальных по быстродействию расписаний : препр. / В. Б. Алюшкевич, Ю. Н. Сотсков ; Акад. наук Белорус. ССР. Минск : АН БССР, 1987. - № 9. - 20 с.

6. Ангуладзе, М. X. Об использовании метода статистического поиска с применением правил предпочтения в задачах составления расписаний : сообщ. / М. X. Ангуладзе ; Акад. наук Груз. ССР. Тбилиси : АН ГССР, 1972. -Т. 65, № 2. - С. 417-420.

7. Андронов, А. М. Математические методы планирования и управления производственно-хозяйственной деятельностью предприятий гражданской авиации / А. М. Андронов, А. П. Хижняк. М. : Транспорт, 1977.-215 с.

8. Аронович, А. Б. О выборе оптимальных комбинаций локальных правил календарного планирования / А. Б. Аронович // Экон. и мат. методы. 1970. - Т. 6, № 4. - С. 548-557.

9. Артамонов, И. М. Алгоритмы определения последовательности обработки деталей, имеющих одинаковый технологический маршрут / И. М. Артамонов // Мат. исслед. Кишинев, 1979. - Вып. 52. - С. 3-8.

10. Артамонов, И. М. Об одном алгоритме решения задачи Беллмана -Джонсона / И. М. Артамонов // Модели и алгоритмы решения задач планирования и управления / гл. ред. И. М. Артамонов. Кишинев, 1982.-С. 3-10.

11. Афанасьев, В. А. Определение возможного минимума продолжительности выполнения комплекса работ / В. А. Афанасьев, В. В. Карелин // Кибернетика. 1986. - № 1. - С. 89-90.

12. Бабушкин, А. И. Построение календарных планов дли многомаршрутной задачи трех станков / А. И. Бабушкин, A. JI. Башта, И. С. Белое // Автоматика и телемеханика. 1976. - № 7. - С. 154-158.

13. Минимизация цикла работы поточной линии / А. И. Бабушкин и др. // Автоматика и телемеханика. 1975. - № 6. - С. 161-167.

14. Бабушкин, А. И. Оптимальные комбинации приоритетных правил составления расписаний / А. И. Бабушкин, И. С. Белов // Автоматика и телемеханика. 1986. - № 5. - С. 82-90.

15. Болун, И. Ф. К задаче упорядочения работ в многофазных системах обслуживания / И. Ф. Болун // Модели и алгоритмы АСУ : сб. / гл. ред. В. А. Коленов. Кишинев, 1986. - С. 29 - 58.

16. Бородич, С. А. Об одной задаче минимизации максимального временного смещения в двухстадийной системе обслуживания с нефиксированными маршрутами / С. А. Бородич // Изв. АН БССР. Сер. Физ.-мат. наук. 1985. - № 5. - С. 109.

17. Бородич, С. А. К вопросу сложности построения оптимальных, но быстродействию расписаний для одного класса обслуживающих систем с операторами переноса / С. А. Бородич // Изв. АН БССР. Сер. Физ.-мат. наук. 1986. -№4. -С. 116-117.

18. Бородин, С. А. Расписания обслуживания частично упорядоченного множества требований для одного класса детерминированных систем / С. А. Бородич, В. А. Струсевич // Изв. АН БССР. Сер. Физ.-мат. наук. -1986.-№3.-С. 19-22.

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

20. Бурков, В. Н. Распределение ресурсов как задача оптимального быстродействия / В. Н. Бурков // Автоматика и телемеханика. 1966. - Т. 27, вып. 7.-С. 119-129.

21. Сетевые модели и задачи управления / В. Н. Бурков и др.. М. : Сов. радио. - 1967. - 144 с.

22. Бурков, В. Н. Методы решения экстремальных комбинаторных задач (обзор) / В. Н. Бурков, С. JI. Ловецкий // Изв. АН СССР. Сер. Техн. кибернетика. 1968. - № 4. - С. 82-93.

23. Вишняков, В. А. Планирование мультипрограммной работы в параллельных вычислительных системах / В. А. Вишняков, О. В. Герман // Изв. АН СССР. Сер. Техн. кибернетика. 1984. -№ 1. - С. 206-213.

24. Гимади, Э. X. Исследования по теории расписаний / Э. X. Гимади, Н. И. Глебов, В. А. Перепелица // Управляемые системы. 1974. - Вып. 12. -С. 3-10.

25. Гимади, Э. X. Алгоритмы с оценками для задач дискретной оптимизации / Э. X. Гимади, Н. И. Глебов, В. А. Перепелица // Проблемы кибернетики. М., 1975. - Вып. 31. - С. 35-42.

26. Гимади, Э. X. Задача календарного планирования крупномасштабного проекта в условиях ограниченных ресурсов: опыт построения математического обеспечения / Э. X. Гимади, Н. М. Пузынина // Управляемые системы. 1983. - Вып. 23. - С. 24-32.

27. Гиффлер, Б. Алгебры календарного планирования и их применение при формулировании моделей общих систем / Б. Гиффлер // Календарное планирование. -М.: Прогресс, 1966. С. 62-83.

28. Асимптотические точные оценки для одномаршрутных задач теории расписаний / Д. И. Голенко и др. // Численные методы нелинейного программирования : материалы I Всесоюз. семинара. Киев, 1976. - С. 180186.

29. Голенко, Д. И. Оптимизация календарных планов методами направленного поиска / Д. И. Голенко, Ю. Я. Тарнопольский // Кибернетика. 1970. - № 6. - С. 138-144.

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

31. Гордон, В. С. О минимаксных задачах теории расписаний с одним прибором / B.C. Гордон, В. С. Танаев // Изв. АН БССР. Сер. Физ.-мат. наук. -1983.-№3.-С. 3-9.

32. Гордон, В. С. Об одном классе задач теории расписаний с частично упорядоченными требованиями / В. С. Гордон, Я. М. Шафранский // IV Всесоюз. конф. по проблемам теоретической кибернетики : тез. докл. -Новосибирск, 1977.-С. 101-103.

33. Гофман, Э. Ф. Алгоритмизация решения задач календарного планирования / Э. Ф. Гофман, С. Ш. Кеслер // Труды / Ленингр. инж.-экон. ин-т. JL, 1976.-Вып. 120.-С. 12-33.

34. Данильченко, А. М. Приближенный алгоритм решения задачи трех станков / А. М. Данильченко, С. Н. Левченко, А. В. Панишев // Автоматика и телемеханика. 1985. - № 7. - С. 133-139.

35. Джексон, Д. Р. Очереди с динамическим правилом приоритета / Д. Р. Джексон // Календарное планирование. М.: Прогресс, 1966. - С. 357-377.

36. Доцатов, В. В. О некоторых обобщениях одномаршрутной задачи календарного планирования / В. В. Доцатов, А. В. Тогер // Машинная обработка информации. Киев, 1970. - Вып. 29. - С. 92-98.

37. Душин, Б. И. Замечание к алгоритму в одномаршрутной задаче Джонсона /Б. И. Душин //Кибернетика. 1980. - № 2. - С. 129-131.

38. Планирование производства в условиях АСУ : справочник / К. Ф. Ефетова и др.. Киев : Технша, 1984. - 135 с.

39. Закревский, А. Д. Алгоритмы синтеза дискретных автоматов / А. Д. Закревский. М.: Наука, 1971. - С. 213-268.

40. Зиноер, Я. А. Эффективные итеративные алгоритмы теории расписаний/Я. А. Зиноер, В. В. Шкурба// Кибернетика. 1985.- № 1. - С. 72-75.

41. Золотухин, В. Ф. Об исключении заведомо неоптимальных решений задачи Беллмана Джонсона / В. Ф. Золотухин // Изв. АН СССР. Сер. Техн. кибернетика. - 1979. - № 1. С. 44-51.

42. Зыков, A. JI. Теория конечных графов / A. JI. Зыков. -Новосибирск : Наука, 1969. 544 с.

43. Ипьницкий, А. Л. Оценка целевой функции одной дискретной задачи теории расписаний / А. Л. Ипьницкий // Исследование операций и АСУ / Киев, гос. ун-т. Киев : КГУ, 1979. - Вып. 13. - С. 54-58

44. Иоффе, Э. Г. Об одном алгоритме расчета календарных расписаний дня производственного участка / Э. Г. Иоффе // Экон. и мат. методы. 1971. - Т. 7, № 6. - С. 86-88.

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

46. Канцедал, С. А. Алгоритм сокращения поиска решений в задаче теории расписаний сетевой структуры / С. А. Канцедал // Автоматика и телемеханика. 1982. - № 4. - С. 72-77.

47. Канцедал, С. А. О классах расписаний / С. А. Канцедал, О. Н. Малых//Кибернетика. 1981. - № 6. - С. 66-74.

48. Ковалев, М. Я. Эффективный е-приближенный алгоритм для задачи максимизации быстродействия в двухстадийной системе из параллельных приборов / М. Я. Ковалев // Изв. АН БССР. Сер. Физ.-мат. наук. 1985. -№3.-С. 118.

49. Ковалев, М. Я. Приближенное решение задачи минимизации суммарного запаздывания требований / М. Я. Ковалев // Изв. АН БССР. Сер. Физ.-мат. наук. 1985. - № 5. - С. 110.

50. Коглер, В. Перечислительные и итеративные алгоритмы / В. Коглер, К. Штиглиц // Теория расписаний и вычислительные машины / под ред. В. Коглера. М.: Наука, 1984. - С. 249-317.

51. Костевич, JI. С. Теория игр. Исследование операций / JI. С. Костевич, А. А. Лапко. Минск : Вышэйшая шк., 1982. - 232 с.

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

53. Кузин, Б. И. Организация и оперативно-календарное планирование машиностроительного производства в АСУП / Б. И. Кузин, В. А. Дуболазов ; Ленинград, гос. ун-т. Л. : ЛГУ, 1978. - 238 с.

54. Лапко, А. А. Об оптимизации приоритетных систем обслуживания / А. А. Лапко // Изв. АН БССР Сер. Физ.-мат. наук. 1977. - № 2. - С. 117-120.

55. Лапко, А. А. Обслуживание детерминированных потоков требований в заданные сроки / А. А. Лапко // Изв. АН БССР. Сер. Физ-мат. наук. 1980. - № 4-5. - С. 130.

56. Лапко, А. А. Диспетчеризация потоков требований с переменными параметрами в приоритетных системах массового обслуживания / А. А.

57. Лапко, М. М. Повари // Теория и методы оптимизации в проектировании / Акад. наук Белорус. ССР. Минск : АН БССР, 1978. - Вып 1. - С. 98-104.

58. Левин, Г. М. Декомпозиционные методы оптимизации проектных решений / Г. М. Левин, В. С. Танаев Минск : Наука и техника, 1978. -240 с.

59. Левин, Л. А. Универсальные задачи перебора / Л. А. Левин // Проблемы передачи информации. 1973. - Т. 9, № 3. - С. 115-116.

60. Левин, М. Ш. Об эффективном решении некоторых задач теории расписаний на сетях / М. Ш. Левин // Кибернетика. 1980. - № 1. - С. 131135.

61. Лескин, А. А. Алгебраические модели гибких производственных систем / А. А. Лескин. Л. : Наука, 1986. - 153 с.

62. Лившиц, Э. М. О сравнительной сложности некоторых задач дискретной оптимизации / Э. М. Лившиц, В. И. Рублинецкий // Вычислительная математика и вычислительная техника. 1972. - Вып. 3. -С. 78-85.

63. Алгоритм для решения задачи о коммивояжере / Дж. Литл и др. // Экон. и мат. методы. 1965. - Т. 4, вып. 1. - С. 94-107.

64. Марков, Л. А. Правило узких мест в задаче Джонсона / Л. А. Марков, А. А. Первозванский // Кибернетика. 1974. - № 5. - С. 142-144.

65. Маршалл, А. Неравенства: Теория мажоризации и ее приложения / А. Маршалл, И. Олкин. М.: Мир, 1983. - 576 с.

66. Мельников, О. И. Параметрическая задача теории расписаний / О. И. Мельников, Я. М. Шафранский // Кибернетика. 1979. - № 3. - С. 53-57.

67. Метельский, А. С. О некоторых периодических процессах / А. С. Метельский // Докл. АН БССР. 1963. - Т. 7, № 9. - С. 584-587.

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

69. Мироносецкий, Н. Б. Управление подготовкой производства / Н. Б. Мироносецкий, А. Р. Андерсон. Новосибирск : Наука, 1976. - 160 с.

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

71. Моисеев, Н. Н. Численные методы оптимального управления / Н. Н. Моисеев ; Моск. гос. ун-т. М. : ВЦ МГУ, 1982 - 264 с. 72. Моисеев, Н. Н. Численные методы в теории оптимальных систем / Н. Н. Моисеев. - М. : Наука, 1971. - 424 с.

72. Моисеев, Н. Н. Элементы теории оптимальных систем / Н. Н. Моисеев. М. : Наука, 1975. - 52с.

73. Организация, планирование и управление предприятием электронной промышленности / под ред. П. М. Стукалова. М.: Высш. шк., 1980. - 351 с.

74. Оре, О. Теория графов / О. Ope. М.: Наука, 1980. - 336 с.

75. Основные положения по разработке и применению систем сетевого планирования и управления / под ред. JI. Н. Колосова. М. : Экономика, 1974.-216 с.

76. Пападимитриу, X. Комбинаторная оптимизация. Алгоритмы и сложность / X. Пападимитриу, К. Стайглиц. М.: Мир, 1985. - 510 с.

77. Петров, В. JI. Планирование гибких производственных систем / В. JI. Петров, А. Н. Масленников, JI. JI. Осипов. JI. : Машиностроение, 1985. -182 с.

78. Потшебовски, Г. Приближенные алгоритмы решения общей задачи теории расписаний / Г. Потшебовски // Прикл. пробл. больших систем управления. София, 1980. - С. 115-124.

79. Раимов, Ф. Ф. Составление расписания для технологических процессов // Оптимизация информационных систем : межвуз. сб. науч. ст. / Оренбур. гос. ун-т. Оренбург : ОГУ, 1997. - С. 138 - 141.

80. Чепасов, В. И. Алгоритмическая и программная реализация задачи о расписании : учеб. пособ. / В. И. Чепасов, С. К. Кулов, Ф. Ф. Раимов / Оренбург, гос. ун-т. Оренбург, 1999. - 192 с.

81. Чепасов, В. И. Основные характеристики алгоритма составления расписания / В. И. Чепасов, Ф. Ф. Раимов. Деп. в ВИНИТИ 27.04.01, № 1110.

82. Раимов, Ф. Ф. Применение компьютерных методов при составлении расписания / Ф. Ф. Раимов // Университетское образование : сб. материалов VII Междунар. науч.-метод. конф. / Пензен. гос. ун-т. Пенза, 2003. - С.509-510.

83. Ревчук, Т. Н. Выделение контуров смешанного графа / Т. Н. Ревчук, Ю. М. Сотсков // Методы и программы решения экстремальных задач / Акад. наук Белорус. ССР. Минск : АН БССР, 1981. - С. 46-52.

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

85. Сальвадор, М. Календарное планирование и упорядочение работ / М. Сальвадор // Исследование операций. М.: Мир, 1981. - Т. 2. - С. 232-263.

86. Севастьянов, С. В. О приближенном решении некоторых задач теории расписаний / С. В. Севастьянов // Дискретный анализ. 1978. - Вып. 32. -С. 66-75.

87. Севастьянов, С. В. Эффективное построение расписаний, близких к оптимальным для случаев произвольных и альтернативных маршрутов деталей / С. В. Севастьянов // Докл. Акад. наук СССР. 1984. - Т. 276, № 1.1. С. 46-49.

88. Сергиенко, И. В. Математические модели и методы решения задач дискретной оптимизации / И. В. Сергиенко. Киев : Наукова думка, 1985.-384 с.

89. Смоляр, JI. И. Теория расписаний и управление / JI. И. Смоляр. М. : Знание, 1977. - 64 с.

90. Смоляр, JI. И. Модели оперативного планирования в дискретном производстве / JI. И. Смоляр. М. : Наука, 1978. - 320 с.

91. Смоляр, JI. И. Оперативно-календарное планирование: Модели и методы / JI. И. Смоляр. М.: Экономика, 1979. - 136 с.

92. Сотсков, Ю. М. Задача теории расписаний на смешанных графах / Ю. М. Сотсков // Теория и методы автоматизации проектирования / Акад. наук Белорус. ССР. Минск : АН БССР, 1980. - С. 19-22.

93. Сотсков, Ю. М. Определение числа орграфов, порождаемых смешанным графом / Ю. М. Сотсков // Алгоритмы и программы решения задач оптимизации / Акад. наук Белорус. ССР. Минск : АН БССР, 1980. -С. 36-39.

94. Сотсков, Ю. Н. Перечисление расписаний, заданных смешанным графом / Ю. Н. Сотсков // Изв. АН БССР. Сер. Физ.-мат. наук. 1980. - № 5. -С. 132-133.

95. Сотсков, Ю. Н. Сетевые модели в теории расписаний / Ю. Н. Сотсков // Оптимизация, принятие решений, микропроцессорные системы. -София : ИТКР БАН, 1985. С. 157-162.

96. Сотсков, Ю М. Устойчивость оптимальной ориентации ребер смешанного графа / Ю. М. Сотсков, В. Б. Алюшкевич // Докл. АН БССР. -1988.- Т. 32, №4.-С. 108-111.

97. Сотсков, Ю. Н. Минимизация максимального штрафа за обслуживание требований последовательными приборами / Ю. Н. Сотсков, С. М. Барановская // Сложность и методы решения задач оптимизации / Акад. наук Белорус. ССР. Минск : АН БССР, 1984. - С. 37-47.

98. Сотсков, Ю. М. Об одном подходе к перечислению ориентированных бесконтурных графов, порождаемых смешанным графом / Ю. М. Сотсков, В. С. Танаев // Изв. АН БССР. Сер. Физ.-мат. наук. 1976. -№5.-С. 99-102.

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

100. Струсевич, В. А. Некоторые эффективно разрешимые классы задачи Беллмана-Джонсона / В. А. Струсевич // Математические методы и их приложения в больших экономически технических системах : тез. докл. Всесоюз., школы-семинара. М., 1980. - С. 177-180.

101. Струсевич, В. А. К задаче Беллмана-Джонсона / В. А. Струсевич // Докл. АН БССР. -1981. -Т. 32, № 6.- С. 518-521.

102. Струсевич, В. А. Класс регулярных задач Беллмана-Джонсона // Изв. АН БССР. Сер. Физ.-мат. наук. 1982. - № 1. - С. 28-33.

103. Струсевич, В. А. Задача трех станков: достаточное условие сводимости в выпуклой форме / В. А. Струсевич // Вестн. БГУ. Сер. 1, Физика. Математика. Механика. 1985. - № 1. - С. 36-39.

104. Струсевич, В. А. Минимизация суммарного времени обслуживания для систем с нефиксированными маршрутами // Вестн. БГУ. Сер. 1, Физика. Математика. Механика. 1988. № 1. - С. 44-46.

105. Сытник, В. Ф. Некоторые модификации алгоритма решения календарной задачи по методу Монте-Карло / В. Ф. Сытник, JI. И. Кузьменко // Исследование операций и АСУ / Киев. гос. ун-т. Киев : КГУ, 1975. -Вып. 6.-С. 45-51.

106. Танаев, В. С. Теория расписаний / В. С. Танаев. М. : Знание. -1988.- 40 с.

107. Танаев, В. С. Современное состояние и основные тенденции развития теории расписаний / В. С. Танаев // Оптимизация, принятие решений, микропроцессорные системы. София : ИТКР БАН, 1985. -С. 148-151.

108. Танаев, В. С. Некоторые вопросы оптимизации проектных решений в САПР / В. С. Танаев // Автоматизация процессов проектирования / Акад. наук Белорус. ССР. Минск : АН БССР, 1985. -С. 73-85.

109. Танаев, В. С. Декомпозиция и агрегирование в задачах математического программирования / В. С. Танаев. Минск : Наука и техника, 1987. - 184 с.

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

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

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

113. Уздемир, А. П. Система планирования дискретного производства / А. П. Уздемир, В. А. Большаков. М. : ВНИИСИ, 1983. - 32 с.

114. Фейгин, JI. И. Управление и прогнозирование в задачах теории расписаний при полной информации / Л. И. Фейгин // Докл. АН СССР. -1971. Т. 200, № 6. - С. 1298-1301.

115. Финкелыитейн, Ю. М. Приближенные методы и прикладные задачи дискретного программирования / Ю. М. Финкелыитейн. М. : Наука, 1976.-264 с.

116. Фишер, Г. Комбинации локальных правил календарного планирования применительно к самонастраивающимся на вероятностной основе программам для ЭВМ / Г. Фишер, Г. JT. Томпсон // Календарное планирование. М.: Прогресс, 1966. - С. 260.

117. Форд, JI. Потоки в сетях / JT. Форд, Д. Фалкерсон. М. : Мир, 1966.- 276 с.

118. Франчук, В. И. Некоторые алгоритмы решения задач календарного планирования / В. И. Франчук // Мат. методы решения экон. задач. 1974. -Вып. 5.-С. 109-113.

119. Харари, Ф. Теория графов / Ф. Харари. М.: Мир, 1973. - 300 с.

120. Чудаков, А. Д. Автоматизированное оперативно-календарное планирование / А. Д. Чудаков, Б. Я. Фалевич. М. : Машиностроение, 1986. -224 с.

121. Шафранский, В. В. Математические модели и методы планирования развития отраслей промышленности / В. В. Шафранский. М. : Наука, 1984. -224 с.

122. Шевченко, В. Н. Задача о равномерном распределении простоев (несколько смен) / В. Н. Шевченко // Экон. и мат. методы. 1967. - Т. 3, вып. 4.-С. 619-623.

123. Шкурба, В. М. Вычислительные схемы решения задач теории расписаний / В. М. Шкурба // Кибернетика. 1965. - № 3. - С. 72-76.

124. Шкурба, В. В. Задача трех станков / В. В. Шкурба. М. : Наука, 1976.-96 с.

125. Шкурба, В. М. Планирование и управление в автоматизированном производстве / В. М. Шкурба, С. JI. Белецкий, К. Ф. Ефетова. — Киев : Наукова думка, 1984. 224 с.

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

127. Шлепаков, П. А. Алгоритмы и программы оперативно-календарного планирования производств нефтепереработки / П. А. Шлепаков, A. JI. Зиглина // Оперативное планирование и управление производством. М.: Энергоатомиздат, 1985. - С. 27-31.

128. Шлепаков, П. А. Пакет программ для календарного планирования производства / П. А. Шлепаков, A. JI. Зиглина, О. С. Соболев // Механизация и автоматизация производства. 1984. - № 12. - С. 27-30.

129. Шмелев, В. Д. Динамическая задача межцехового планирования / В. Д. Шмелев // Моделирование и управление в развивающихся системах : сб. / отв. ред. В. Г. Вдовин. М.: Наука, 1978. - С. 120-125.

130. Якимов, Р. М. Об одном функциональном уравнении, описывающем оптимальную последовательность обработки изделий / Р. М. Якимов // Труды / Перм. политехи, ин-т. Пермь, 1960. - Вып. 21. - С. 6271.