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

• Красный, Дмитрий Георгиевич
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Красный, Дмитрий Георгиевич

ВВЕДЕНИЕ.

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

1.1. Распределительные задачи теории расписаний и области их применения

1.1.1. История возникновения и применения.

1.1.2. Распределение заданий в вычислительных системах.

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

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

1.3. Математическое описание неоднородной распределительной задачи

1.3.1. Теоретико-множественная составляющая распределительной задачи.

1.3.2. Критериально-оценочная составляющая распределительной задачи.

1.3.3. Оптимизационная составляющая распределительной задачи.

1.3.4. Понятие среды решения распределительной задачи и ее характеристики.

1.4. Анализ существующих методов решения рас1 1ределительных задач.

1.4.1. Детерминированные методы точного решения распределительных задач.

1.4.2. Списочные методы точного решения распределительных задач.

1.4.3. Комбинаторный подход решения распределительных задач.

1.4.4. Эвристические и вероятностные методы.

1.5. Выводы по первой главе.

2. СПИСОЧНО-МОДИФИЦИРОВАННЫЙ АЛГОРИТМ ТОЧНОГО РЕШЕНИЯ НЕОДНОРОДНОЙ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ.

2.1. Списочно-модификацированиый алгоритм Алексеева.

2.1.1. Общая характеристика алгоритма Алексеева.

2.1.2. Списочная модификация алгоритма Алексеева для распределительной задачи с количественной неоднородностью.

2.1.3. Списочная модификация алгоритма Алексеева для распределительной задачи с качественной неоднородностью.

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

2.2.1. Решение распределительной задачи с количественной неоднородностью.

2.2.2. Решение распределительной задачи с качественной неоднородностью.

2.3. Имитационное исследование применения СМ АА для точного решения неоднородных распределительных задач.

2.3.1. Организация вычислительного эксперимента.

2.3.2. Исследование свойств СМАА при решении распределительных задач с количественной неоднородностью.

2.3.3. Исследование свойств СМАА (КК) и (К) при решении распределительных задач с качественной неоднородностью.

2.4. выводы по второй главе.

3. ИССЛЕДОВАНИЕ РЕШЕНИЯ НЕОДНОРОДНОЙ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ ПРИБЛИЖЕННЫМИ МЕТОДАМИ.

3.1. Приближенное решение неоднород!юй распределительной задачи.

3.1.1. Приближенное решение и алгоритмы.

3.1.2. Показательная распределительная задача с количественной неоднородностью.

3.1.3. Решение неоднородной распределительной задачи алгоритмом Плотникова-Зверева

3.2. Модификация списочного алгоритма Алексеева для приближенного решения неоднородной распределительной задачи.

3.2.1. Списочно-модифицированный алгоритм Алексеева без возвратов.

3.2.2. Решение неоднородной распределительной задачи СМАА без возвратов.

3.2.3. Исследование точности решения СМАА без возвратов.

3.2.4. Исследование зависимости относительного улучшения точности СМАА без возвратов в сравнении с алгоритмом ПЗ от изменения параметров задачи.

3.3. Применение эволюционно-генетической модели для решения неоднородной распределительной задачи.

3.3.1. Возможность решения неоднородной распределительной задачи генетическим алгоритмом.

3.3.2. Исследование ЭГА при решении неоднородной распределительной задачи.

3.3.3. Описание перспективной области значений параметров ЭГА.

3.3.4. Решение неоднородной распределительной задачи ЭГА.

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

3.4.1. Организация вычислительного эксперимента.

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

3.5. Выводы по третьей главе.

4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

РЕШЕНИЯ НЕОДНОРОДНЫХ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ.

4.1. Вычислительный эксперимент и требования к программному обеспечению.

4.1.1. Требования к программному обеспечению.

4.1.2. Концептуальная схема функционирования программного обеспечения.

4.1.3. Объектно-ориентированная модель реализации ПО.

4.2. Структура хранения данных программного обеспечения.

4.2.1. Использование базы данных.

4.2.2. Концептуальная модель объекта хранения и функциональные зависимости.

4.2.3. Реляционные выражения и таблицы базы данных.

4.3. Интерфейс взаимодействия с пользователем.

4.4. Выводы по четвертой главе.

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

Задачи теории расписаний имеют не только большое теоретическое значение, но и получили широкое практическое применение во многих инженерных и управленческих задачах [35,41,62]. Там, где требуется упорядочить и распределить любые ресурсы между исполнителями, возникает задача эффективного планирования. Одним из широко исследуемых направлений теории расписаний, является теория распределительных задач. В ней основное внимание уделяется вопросам, связанным с построением наилучших календарных планов - расписаний последовательно-параллельного исполнения конечного множества требований, обслуживаемых детерминированными системами одного или нескольких устройств. Классические распределительные задачи теории расписаний являются схематичными теоретическими моделями многих задач, встречающихся на практике, и чрезвычайно сложны для теоретического и экспериментального изучения как относящееся в подавляющем большинстве случаев к классу КР-полных задач.

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

Основной характеристикой распределительной системы является однородность системы используемых устройств относительно выполняемых работ. Оптимальное решение неоднородной распределительной задачи чрезвычайно сложно даже для современных вычислительных систем, особенно при использовании точных методов решения. Применение таких методов для неоднородной распределительной задачи при её большой 5 размерности оказывается неэффективным, т.к. её КР-полнота приводит к недостижимости оптимального решения [14]. Повышение эффективности методов точного решения позволяет повысить размерность задач, для которых оказывается возможным получать решения за доступное время.

Другой путь обеспечения доступности решения - применение методов приближенного решения, которые позволяют при небольших ресурсных затратах получать некоторое решение. Однако они не обеспечивают оптимальность результатов, и могут давать большую погрешность, достигающую 30%. Для практических задач такая потеря точности не всегда является приемлемой. Вследствие этого возникает необходимость в разработке таких приближённых методов, которые позволили бы повысить точность решения распределительных задач, при допустимых вычислительных затратах.

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

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

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

1. исследование и модификация точного алгоритма Алексеева решения неоднородной распределительной задачи применительно к количественным и качественным неоднородностям;

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

3. разработка и исследование вариантов эволюционно-генетического алгоритма (ЭГА) для предметно-ориентированного решения неоднородных распределительных задач теории расписаний;

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

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

Содержательные научные результаты и степень их новизны

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

2. Разработана списочная модификация точного алгоритма Алексеева с применением качественно-количественной оценки неоднородности и избирательности матрицы загрузки для распределительных задач с качественной неоднородностью. Данная модификация позволяет значительно (не менее чем на 30%) уменьшить время поиска оптимального решения и расширить размерность задач (не менее чем на 20%), решение которых можно найти за приемлемое время.

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

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

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

Методы исследования. В диссертации применялись методы исследования операций, оптимизации, математического моделирования, теории расписаний, математической статистики, теории планирования экспериментов.

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

При реализации программного средства «Система вычислительных исследований неоднородной распределительной задачи «РтсГМечуМеШос!» применялись концепции объектно-ориентированного программирования и реляционных баз данных.

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

Практически значимыми эффектами применения результатов диссертационных исследований являются существенное (10-30%) снижение времени решения неоднородных и распределительных задач точными алгоритмами; существенное (16%) • повышение точности решения неоднородных и распределительных задач приближёнными алгоритмами; введение в практику решения неоднородных распределительных задач предметно оптимизированных эволюционно-генетических алгоритмов. Кроме того, работа дала хорошее практическое приложение в учебном процессе, т.к. предложенные решения позволяют изучать на практике задачи теории расписаний. Автором опубликованы методические указания по теме «Теория расписаний» (см. список публикаций) для дисциплин «Алгоритмические языки и программирование», «Вычислительная техника и программирование», «Теория принятия решений», «Теория оптимизации».

Разработанное для исследований программное обеспечение «Система вычислительных исследований неоднородной распределительной задачи «РтсШелуМеШос!», с помощью которого осуществлялось автоматизированное проведение имитационных экспериментов, прошло официальную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (ФГУ ФИПС свидетельство № 2008613599 от 28.07.2008).

Основное содержание работы

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

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

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

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

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

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

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

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

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

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

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

Для построенной эволюционно-генетической модели разработана методика проведения параметрической оптимизации ее настроек.

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

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

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Красный, Дмитрий Георгиевич

4.4. Выводы по четвертой главе

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

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

ЗАКЛЮЧЕНИЕ

1. Точное решение неоднородной распределительной задачи теории расписаний является значимым для многих практических задач, и зачастую погрешность от методов приближенного решения не может быть приемлема. Применение СМ АА для поиска точного решения неоднородной распределительной задачи как количественной, так и качественной (для задачи с качественной неоднородностью применение СМ АА с качественно-количественным учетом избирательности) позволяет повысить эффективность нахождения точного решения не менее чем на 10-30%, и расширить область размерностей задач (не менее чем на 5%), для которых точное решение может быть найдено за приемлемые временные сроки.

2. Однако, возможность получения точного решения для задач большой размерности в силу КР полноты исследуемой задачи остается недостижимым в приемлемые временные сроки. В этом случае необходимость в решении практических задач теории расписаний большой размерности приводит к неизбежности использования приближенных методов решения, среди которых можно выделить СМ АА без возвратов и эволюционно-генетический алгоритм, адаптированный для неоднородной распределительной задачи. Причем СМ АА без возвратов позволяет получать приемлемое по точности решение и лучшее от 4% -16%, в зависимости от степени однородности значений матрицы вычислительной сложности, если сравнивать с алгоритмом Плотникова-Зверева. А в сравнении с эволюционно-генетическим алгоритмом эффект выигрыша по качеству решения для СМ АА без возвратов наблюдается для задач большой размерности, причем временные затраты на поиск решения незначительны, к примеру для задачи размерности п=10, т=899 время решения не превышает одной секунды.

3. ЭГА также показал эффективность применения его для решения неоднородной распределительной задачи, но в большей степени для случая двухприборной задачи. Исследования с использованием полнофакторного анализа позволили параметрически оптимизировать ЭГА для исследуемого в работе набора исходных параметров решаемой неоднородной распределительной задачи. Были получены более эффективные, по сравнению с рекомендуемыми в научной литературе по ЭГА, параметры, позволившие повысить точностные показатели при решении двухприборной распределительной задачи п=2, т=45 в 2,57 раза. Причем точность решения эволюционно-генетическим алгоритмом двухприборной неоднородной распределительной задачи выше, чем для решения этой же задачи, но СМ АА без возвратов или алгоритм Плотникова-Зверева. ЭГА минимум с 80% вероятностью позволяет получить точное решение задач п=2, т=45.

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

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

6. Результаты диссертационной работы внедрены в учебном процессе и научно-исследовательской работе кафедры ПО ВТ и АС Донского государственного технического университета, а также использованы при решении практических производственных задач, что подтверждается актами внедрений, которые приведены в приложении.

Список литературы диссертационного исследования кандидат технических наук Красный, Дмитрий Георгиевич, 2008 год

1. Адлер Ю.П. Планирование эксперимента при поиске оптимальных условий/ Адлер Ю.П., Маркова Е.В., Гранковский Ю.В. М.:Наука, 1976.-278с.

2. Айра Пол Объектно-ориентированное программирование на С++ — М.:Бином, 2001.-464 с.

3. Алексеев В.Ю. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987 - 247с.

4. Ахназарова С.Л. Оптимизация эксперимента в химии и химической технологии / Ахназарова С.Л., Кафаров B.B. М.: Высшая школа, 1978.-319 с.

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

6. Безгинов А.Н. Обзор существующих методов составления расписания. Информационные технологии и программирование / Безгинов А.Н. Трегубов С.Ю. // Межвузовский сборник статей. Вып. 2(14). -М.гМГИУ, 2005. 60с.

7. Боровков A.A. Теория вероятностей: Учебное пособие для вузов. -2-е изд М.: Наука, 1986.

8. Будиловский Д.М. Анализ эффективности генетического алгоритма при решении задач теории расписаний большой размерности/ Будиловский Д.М., Кобак В.Г. Ростов-на-Дону: Издательство ДГТУ, 2007, 131-134с.

9. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. М.:Бином, 1998. 560 с.

10. И.Вентцель Е.С. Исследование операций. -М.: Наука, 1980, 208 с.

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

12. Гладков JI. А. Генетические алгоритмы/JI. А. Гладков, В. В. Курейчик В. М. Курейчик М.: ФИЗМАТ ЛИТ, 2006.-320с

13. Глушков В. М., Капитонова Ю. В., Летичевский А. А., Горлач С. П. Макроконвейерные вычисления функций над структурами данных -Кибернетика, 1981, № 4, 13 21 с.

14. Глушков В. М., Молчанов И. Н. О некоторых проблемах решения задач на ЭВМ с параллельной организацией вычислений Кибернетика, 1981, №4, 82-88 с.

15. Головкин Б.А. Параллельные вычислительные системы. М. : Энергия, 1980.

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

17. Дейт К. Введение в системы баз данных. М.: Диалектика, 1998. 784 с.

18. Джексон Г. Проектирование реляционных баз данных для использования с микро-ЭВМ М.: Мир, 1991. - 252 с.

19. Джон Макгрейтор, Девис Сайке Тестирование объектноориентированноных программ М.: ДиаСофт, 2002. - 417 с.

20. Емельянов В.В. Теория и практика эволюционного моделирования/В.В. Емельянов, В.В. Курейчик , В.М. Курейчик.-М.:ФИЗМАТЛИТ,2003.-432 с.

21. Еремеев A.B. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Дисс. канд.физ.-мат.наук. Омск, 2000

22. Ермаков С.М. Математическая теория оптимального эксперимента: учебное пособие / Ермаков С.М., Жиглявский A.A. М.:Наука, 1987. -320с.

23. Жак C.B. О методах решения задач, сочетающих эвристики и случайный выбор -М.: Кибернетика, 1972. №1 - с. 119-121.

24. Жак C.B. Приближенный метод выбора оптимальной системы сельскохозяйственных машин// Математические модели и методы оптимального планирования Новосибирск: Наука,1966. - с.255-162.

25. Задачи календарного планирования. Часть 1-2. // http://Math.nsc.ru/lbrt/k5/lec6.pdf

26. Ивоботенко Б.А. Планирование эксперимента в электромеханике /

27. Ивоботенко Б.А., Ильинский Н.Ф., Копылов И.П. М.:Наука, 1975. -184с.

28. Клемент Р. «Генетические алгоритмы: почему они работают? Когда их применять?», Компьютерра, №289, 1999, 20-23 с.

29. Кобак В. Г. Соотношение квадратичного и минимаксного оптимальных распределений загрузки однородных трехприборных систем/В. Г. Кобак, P.A. Нейдорф// Из. вузов, <Электромеханика>, 2005, №3, 60-65 с.

30. Кобак В. Г. Сравнительный анализ алгоритмов решения минимакс-ной задачи в однородных системах/ Кобак В. Г., Федоров С.Е./

31. Математические мето-ды в технике и техно-логиях ММТТ-16: сб. тр.169

32. XVI Междунар. на-уч. конф. / РГАСХМ.-Ростов н/Д, 2003. Т. 8, секц.12

33. Кобак В.Г. Определение оптимального значения критерия равномерности по оптимальному минимаксному критерию для однородных трехприборных систем (статья)// Электровозостроение: сб. науч. тр. Новочеркасск, 2002.- Т.44.

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

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

36. Корнеев В.В. Параллельные вычислительные системы/В.В Корнеев.-М.:Нолидж. 1999. 311 с.

37. Корнеев В.В. Современные микропроцессоры/В.В. Корнеев, А.В Киселев. М:Нолидж. - 1998. - 237 с.

38. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975.

39. Кофман А. Методы и модели исследования операций. -М.: Мир, 1977, 432 с.

40. Коффман Э.Г. Теория расписания и вычислительные машины М.: Наука, 1987.

41. Красный Д.Г. Анализ эффективности модифицированного алгоритма Алексеева приблеженного решения неоднородной распределительной задачи//«Системный анализ, управление и обработка информации» -Ростов-на-Дону: Издательство ДГТУ, 2007, 126-130 с.

42. Красный Д.Г. Официальная регистрация программы для ЭВМ ФГУ ФИПС «Система вычислительных исследований неоднородной распределительной задачи» // Нейдорф P.A., Кобак В. Г. // №2008613599 от 28.07.2008 г.

43. Красный Д.Г. Решение минимаксных задач в неоднородной среде избирательно работающих устройств модифицированным алгоритмом Алексеева// Вестник ДГТУ Ростов н/Д, 2007.- №4, Т.7. - С. 395-401170

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

45. Кузьменко В.М. Анализ современных методов искусственного интеллекта применительно к задачам календарного планирования единичного производства/ Кузьменко В.М., Таран C.B. Вестник Донбасской государственной машиностроительной академии, 2006 №1.

46. Курейчик В.М. Генетические алгоритмы, В.М. Курейчик, В.В. Курейчик, Л.А Гайдуков. -М.:ФИЗМАТЛИТ, 2006. 320 с.

47. Курейчик В.М., Родзин СИ. Эволюционные алгоритмы: генетическое программирование // Известия АН. Сер.: Теория и системы управления. 2002. —№1. - с. 127-137.

48. Ларионов A.M., Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы и сети. СПб.: Энергоатомиздат, 1987

49. М. Мину. Математическое программирование. Теория и алгоритмы.-М.: Наука, 1990.

50. Мейер М. Теория реляционных баз данных М.Мир, 1987. - 608 с.

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

52. Налимов В.В. Теория эксперимента. М.:Наука, 1971.

53. Нейдорф P.A. Практическое использование метода псевдократной загрузки//Р.А. Нейдорф, В.Г. Кобак, Д.Г. Красный Математическиемето-ды в технике и техно-логиях ММТТ-21: сб. тр. XXI Междунар. на-уч. конф. / Саратов, 2008. - Том 5, секция 11.

54. Нейдорф P.A. Точное решение неоднородной распределительной задачи модификацией алгоритма Алексеева//Р.А.Нейдорф, В.Г. Кобак, Д.Г. Красный Известия высших учебных заведений. СевероКавказский регион./Новочеркасск, 2008. №1. с. 17-22.

55. Нейдорф P.A., Кобак В.Г. Методологические проблемы теории расписаний//«Системный анализ, управление и обработка информации» Ростов-на-Дону: Издательство ДГТУ, 2007, 101-108 с.

56. Норенков И. П. Генетические методы структурного синтеза проектных решений // Информационные технологии, 1998. № I.e. 9-13.

57. Овчаров JI.A. Теория вероятностей и ее инженерные приложения: учебное пособие для втузов / Овчаров JI.A., Вентцель Е. С. М.: Высшая школа, 2007. - 491с.

58. Панкратьев Е. В. Алгоритмы и методы решения задач составления расписаний и других экстремальных задач на графах больших размерностей / Панкратьев Е. В., Чеповский А. М. // Фундаментальная и прикладная математика. 2003. - Т.9. - №1. - С. 235-251.

59. Плотников В.Н. Методы быстрого распределения алгоритмов в вычислительных системах./ В.Н. Плотников, В.Ю. Зверев Техническая кибернетика №3 М., 1974, 136- 143с.

60. Португал В. М. Теория расписаний / В. М. Португал, А. И. Семенов. -М.: Знание, 1972.-60с.

61. Праневичус Г.И. Модели и методы исследования вычислительных систем/Г.И. Праневичус.-Вильнюс: Мокслас, 1982.

62. Пупков К.А. Оценка и планирование эксперимента / Пупков К.А., Костюк Г.А. М.Машиностроение, 1977. 118с.

63. Растригин JI. А. Случайный поиск — специфика, этапы истории и предрассудки. Вопросы кибернетики. Вып. 33 (1978), с. 3-16.

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

65. Рутковская Д., Пилиньский М., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польского И.Д. Рудинский. М.: Горячая линия - Телеком, 2006 - 452 с.

66. Севастьянов C.B. Введение в теорию расписаний — Новосибирск, 2003, 173 с.

67. Сергиенко И. В., Лебедева Т. Т., Рощин В. А. Приближенные методы решения дискретных задач оптимизации Киев: Наукова думка, 1980. -276 с.

68. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации Киев: Наукова думка, 1981.

69. Скурихин. А.Н. Генетические алгоритмы // Новости искусственного интеллекта . 1995. - №4. - с. 6-46.

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

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

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

73. Taxa, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с англ. -М.: "Вильяме", 2005, 902 с.

74. Ульман Д. Базы данных на паскале. М.: Машиностроение, 1990. 386 с.

75. Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика/Ф. Уоссермен,-М.: Мир, 1992.

76. Федоров В.В. Теория оптимального эксперимента (планирование регрессионных экспериментов) / Федоров В.В. М.:Наука, 1971, 312с.

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

78. Хартман К. Планирование эксперимента в исследовании технологических процессов / Хартман, Э.Лецкий, В.Шефер и др-М.:Наука, 1977, 552с.

79. Эммерих В. Конструирование распределенных объектов. М.: Мир, 2001.-512 с.

80. Aarts Е. Local Serch in Combinatorial Optimization / E. Aarts, J.K. Lenstra John Wiley & Sons, 1997.

81. Blickle Т., Thiele L. A Comparison of Selection Schemes used in Genetic Algorithm /Т. Blickle, L. Thiele.-TIK-Report,1995.

82. Brucker P. Scheduling Algorithms/P. Brucker.- Springer, 2001

83. Btuns R. Direct Chromosome Representation and Advanced Genetic Operators for Production Scheduling // Proc. of 5th Int. Conf. on GA, Morgan Kaufmann Publ., 1993.

84. E.S.H. Hou, N. Ansari, H. Ren, «А Genetic Algorithm for Multiprocessor Scheduling» IEEE Transactions on Parallel and Distributed Systems, vol. 05, no. 2, pp. 113-120, Feb., 1994.

85. Gantt H.L. ASME Transactions, 1903, 24,- P. 1322-1336.

86. Goldberg D. E. Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley. 1989.

87. Holland J. H. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press. 1975.

88. Jackson J.R. Scheduling a production line to minimize maximum tardiness// Los Angeles, CA: University of California, 1955.- Manag. Sci. Res. Project. Research Report N 43.

89. Johnson S.M. Optimal two- and three-stage production schedules with setup times included// Naval Res. Logistics Quat.- 1954,- V. 1. P. 61 68.

90. Koza J.R. Genetic Programming.- Cambridge/MA:MIT Press, 1992.

91. Land A.H. An automatic method of solving discrete programming problems/ A.H. Land, A.G. Doig Econometrica. V28, 1960.

92. Michafewicz Z., Genetic Algorithm + Data Structures = Evolution Programs, Springer-verlag,1992

93. Mitchell M. An Introduction to Genetic Algorithms. Cambridge: MIT Press, 1996.

94. Nakano R. Conventional Genetic Algorithm for Job Shop Problems // Proc. of 4th Int. Conf. on GA, Morgan Kaufmann Publ., San Francisco, 1991.

95. P. Björn-Jorgensen, J. Madsen, "Critical path driven cosynthesis for heterogeneous target architectures," codes, p. 15, 5th International Workshop on Hardware/Software Co-Design (Codes/CASHE "97), 1997.

96. S. Kirkpatrick and C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, Vol 220, Number 4598, pages 671-680, 1983.

97. Sawada J. A Fast Algorithm to generate Beckett-Gray codes//Electronic notes in Discrete Mathematics (EuroComb 2007),2007lOl.Silvano Martello, Paolo Toth Knapsack Problem Algorithms and Computer Implementations// University of Bologna 1990.

98. Whitley D. A Genetic Algorithm Tutorial/D. Whitley D.-1993.

99. Whitley D.,Schedulong Problems and Traveling Saleman: the Genetic Edge Recombination Operator/D. Whitley, T. Starkweather, D. Fuduay // Proc. of 3d Int. Conf. on GA, 1989.