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

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

БАЛАШЕВА Светлана Юрьевна

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

Специальность 05.13.18 - Математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Воронеж - 2005

Работа выполнена в Воронежском государственном университете.

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

Леденева Татьяна Михайловна

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

Семенов Михаил Евгеньевич;

кандидат физико-математических наук, доцент Гудович Ирина Семеновна

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

Защита состоится «15» декабря 2005г. в 10 часов в конференц-зале на заседании диссертационного совета Д212.037.01 Воронежского государственного технического университета по адресу: 394026, г. Воронеж, Московский просп., 14.

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

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

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

Питолин В.М.

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

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

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

Работа выполнена в соответствии с одним из основных научных направлений Воронежского государственного университета «Анализ и математическое моделирование сложных систем».

За ценные идеи, позволившие обозначить круг проблем, определить направления исследования, а также за содействие в его реализации выражаю искреннюю благодарность Лениной А.Я., кандидату технических наук, доценту кафедры ММИО факультета ПММ ВГУ.

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

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

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

»

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

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

■ оценка эффективности разработанных алгоритмов и программ на примере реальных технологических систем.

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

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

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

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

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

• теорема об эквивалентности критерия минимизации суммы моментов завершения обслуживания требований и критерия минимизации суммарного времени пребывания требований в системе;

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

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

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

Реализация и внедрение результатов работы. Предложенные в диссертационной работе модели, методы и программное обеспечение использовались при решении задачи оптимизации загрузки оборудования для механических цехов машиностроительного предприятия ОАО «ВЭКС». На основе реальных данных о длительностях обработки и планах выпуска были построены расписания, сокращающие отклонение загрузки приборов от равномерной. Материалы диссертации использу-

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

Апробация работы. Основные результаты работы докладывались и обсуждались на VI, X Международных конференциях женщин-математиков «Математика. Образование. Экономика» (Чебоксары, 1998; Ростов-на-Дону, 2002); на VI Международной конференции «Экология и здоровье человека. Экологическое образование. Математические модели и информационные технологии» (Краснодар, 2001); на 24-й международной школе-семинаре им. Шаталина С.С. «Системное моделирование социально-экономических процессов» (Воронеж, 2001); на Международной конференции «Математика. Образование. Экология. Тендерные проблемы» (Воронеж, 2000; Пущнно, 2001; Воронеж, 2003); на V, VII, IX, X Международных конференциях «Математика. Компьютер. Образование» (Дубна, 1998, 2000, 2002; Пущине, 2003); на международной школе-семинаре «Современные проблемы механики и прикладной математики» (Воронеж, 2004); на ежегодных научных конференциях Воронежского государственного университета.

Публикации. Основное содержание диссертационной работы отражено в 23 печатных работах, список основных из них приведен в конце автореферата. В работах, опубликованных в соавторстве, лично соискателю принадлежат: [2,3] - модель, алгоритм решения, упрощенные формулы вычисления субградиента; [4] - теорема об эквивалентности двух критериев, априорная нижняя оценка, алгоритм решения; [5] - теорема (со следствием), обосновывающая возможность перехода от задачи с директивными сроками к задаче с неодновременным поступлением требований; [6] - модель, алгоритм решения; [9] - модели, оценка длины расписания с непрерывной работой приборов; [11] - модели, расчет остающихся времен обработки при дооб-служивании, промежутков начальной занятости приборов при запрете прерываний,

[13] - новый способ оценивания верхних границ простоев приборов и требований;

[14] - расчет промежутков между стадиями, модель задачи с циклическим производством; [16] - обзорная, ссылки на другие публикации автора.

Структура работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 152 страницах, списка литературы из 70 наименований и приложений, содержит 10 рисунков и 13 таблиц.

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

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

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

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

Во второй главе представлен комплекс моделей задач составления расписаний для систем поточного типа (flow shop), отражающих различные аспекты функционирования этих систем, с различными критериями оптимальности. Комплекс включает следующие задачи: с неодновременным поступлением требований в систему (1); с обязательными задержками между стадиями обслуживания (2); с непрерывным технологическим циклом (3); с непрерывной работой приборов (4); с директивными сроками завершения обслуживания (5); с ограничением времени обслуживания (6); задача минимизации суммы моментов завершения обслуживания требований в системе с неодновременным поступлением (7); динамическая задача с групповым поступлением требований (8); задача для системы с циклическим производством (9).

Задача 1 отличается от классической задачи Беллмана - Джонсона возможностью неодновременного поступления требований в систему (в моменты t0l > 0 ). Ее математическая модель имеет вид:

£>,-, =1, j = 1,л; Ё% = 1, * = 1,и; xij = {ОД}, i,j = \,n\ 0)

/=1 У=1

УЦ> 0, 2fg 2:0, Ук)2кз =°> * = !,», , j -1,"; (2)

fn{x,y,z)=Q-, (3)

fk\(x,y,z) -Ук-1,1 =0, к - 2,т ; (4)

f\j{x,y,z) +zij-i =0, j = 2,п ; (5)

flg(.x,y,z) -Ул-ij + zkj-l =0. к = 2,т, (6)

л п £ (Z'mixiJ + Ут/) -*■min > (7)

)=1 /=1

л -

где /к\(х,у,г) = - + Ук\ ~Ч\> к = 1»™. (8)

1=1

я я _

2>о,*</ + > / = 2." • (9)

(=1 /=1

и я - -

/¡д(х,у,г) = - Т.'к-ЦхО + 1'И*/,У-1 +Ук)-Ч]» * = 2,т , / = 2,я . (10) 1=1 /=1 В модели использованы следующие переменные: _ [1, если 1-е требование обслуживается в расписании / - м по порядку, у ~ (0, в противном случае;

- время простоя к-го прибора перед обслуживанием /-го по порядку требования в расписании;

2]д - длительность простоя (задержки в обслуживании) у-го по порядку требования из-за занятости ¿-го прибора и обозначение

¡¡а - время обслуживания /-го требования ¿-м прибором. (1) - стандартные ограничения задачи о назначениях, (2) - требование неотрицательности и вытекающие из содержательного смысла задачи ограничения У1д2/д = 0. Ограничения (3) - (6) отражают правила функционирования конвейера

и определяют значения величин у/д и в зависимости от очередности обслуживания требований.

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

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

'Ог =°)-

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

№ Описание Особенности в моделях

2 Заданы длительности обязательных задержек од между окончанием обслуживания /'-го требования прибором (к-1) и началом обслуживания ¿-м прибором. Возможны а/с <0 -операция начинается до полного завершения предыдущей. Ограничения (4) и (6) меняются на я _ fk\ix,y,¿) - i -Ук-1,1 =0, к = 2,от; i=l л я flg(x,y,z) - Y,aktxij + " Z=1 Z=1 -Ук-lj + zkj~\ =0. к = 2,m, j = 2,n .

3 Обслуживание требования на каждой стадии должно начи- Ограничения (4)-(6) меняются на

наться сразу после окончания его обслуживания на предыдущей стадии. m — f\j(x,y,z) + £ zkj_i =0, j = 2,n; *=1 fig (x,y,z) ~Ук-\,} =0, k = 2,m, j = \,n.

4 Все приборы работают непрерывно, допустимы только начальные простои. Ограничения (3)-(6) меняются на /tl(*,.V>z)=0> k = l,m; flg{x,y,z) -zkJ-\ =0, k = l,m, j = 2,n . Целевая функция (длина расписания): п п m п I Y'mixij + Т. Y,y/y-+min. 7=1 »=1 к=\ М

5 Поиск расписания с минимальным наибольшим превышением моментов завершения обслуживания над заданными директивными фоками £>,. Целевая функция: Fj (а) = max. A, (er) -» min, »=1л а где A,(cr) = Tí(cr)-Dl, Г, (а) - момент завершения обслуживания i-ro требования при расписании а .

6 Задана длительность рабочей смены Т, в течение которой все требования не могут быть обслужены. Максимизируется: а) количество обслуженных требований (с приоритетами щ); б) суммарная загрузка приборов (с коэффициентами ^ ). В ограничениях (1) размерность 2п за счет введения п фиктивных требований i = п+\,...,2п. Дополнительное ограничение: ¿(I'm, x,j+ymj)-T<0. 1 /=1 Целевые функции: п п а) ~ I Z ß,*,, -» min ; '=iy=I б) к=l /=iy=l

7 Минимизация суммы моментов завершения обслуживания требований. Целевая функция: п я I ("-j + l)CL'mixij + Уmj) j=l <=1

8 Требования поступают группами, моменты поступления следующих групп заранее не известны. Минимизируется длина расписания. Динамическая задача сводится к последовательному рассмотрению и решению серии статических задач для групп требований с учетом оставшихся требований из предыдущих групп. Рассматриваются 2 варианта: 1) разрешены прерывания (с дообслуживанием) в моменты поступления следующих групп; 2) прерывания запрещены.

9 Циклическое производство; требования обслуживаются Используется «смещение»: требование, которое обслуживается последним в подпериоде на некотором приборе к, на (А+1)-м приборе переносит-

партиями, возможны а/ц <0.

Цикл разбит на подпериоды. Минимизируется максимальное относительное отклонение длин расписаний по каждому прибору в каждом подпериоде Ту от

«идеальных» значений > соответствующих отсутствию простоев._

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

Ти~1к1

Целевая функция: тах _

А=/,ш,/=1,3

-* тт.

В задаче 2 величины а^ можно интерпретировать как задержку, связанную, например, с настройкой, охлаждением, сушкой и т.д. Считается, что задержки удовлетворяют неравенству:

|ад,| 5 к = 2,т, I = к,к-1, /' = 1,л .

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

| = - О т'»(.'к-\,1>'к1)-

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

образом: рассматривается конвейерная система 2, в которой с/,- = Отах - ,

/ = 1,л, являются моментами поступления требований (здесь отах = тах £>,),

¡=\,п

директивные сроки отсутствуют, а последовательность операций обратна нумерации приборов (т.е. т, т-1,...,1). В этой системе критерием будет служить длина расписания, то есть

О) = тдсА(.а), 1=1,и

где //(о) - момент завершения обслуживания 1-го требования в системе 2. Возможность такого перехода обоснована следующей теоремой.

Теорема 1. Пусть расписание <т = (»1,»2>•••,'«) в системе 2 имеет длину

/^(ст) . Тогда расписание в исходной системе, соответствующее перестановке 5 = (»„, ;„_|,..., /5) , имеет значение критерия, равное /•"¡(сг) = /•¿(ст) - ¡У""*

Следствие. Если расписание а = (i),/'2, in) оптимально в системе 2, то расписание а = ('п>'п-1>-- >'l) (т.е. обратное) будет оптимальным в исходной системе. Таким образом, чтобы найти оптимальное расписание, нужно рассмотреть систему 2, найти в ней расписание с минимальной длиной и затем взять обратное ему расписание.

В задаче 7 рассматриваются критерии оценки качества расписаний, основанные на анализе среднего: 1) минимизация суммы моментов завершения обслуживания требований и 2) минимизация суммарного времени пребывания требований в системе. Доказана следующая теорема.

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

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

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

Рассмотрим применение метода к решению задачи 1 (с неодновременным поступлением требований), модель которой описывается с помощью (1)-(7). Функция Лагранжа после преобразований принимает вид:

п п m п m п

<P(x,y,z,w) = I S сужу +1 S ayyç + S S biyzç , (11)

(x,y,z)eS, w (=1 j=1 A=1 j=1 *=l j=1

где коэффициенты ctj, a ¡g, by зависят от значений двойственных переменных w, соответствующих ограничениям (3)-(6), а множество 5 описывается ограничениями ОН2).

С помощью функции Лагранжа задача (1)-(7) и двойственная к ней задача могут быть записаны соответственно в виде

min тах Ф(х, у, z, w) и тах min Ф(х, у, z, w). (x,y,z)eS w w (x,y,z)eS

Изменим множество S следующим образом. Так как ограничение у/у z/g = О

является нелинейным, заменим его ограничениями у ¡у Zdy и z/y <.hy . Значения

верхних границ ( d/g и Ъщ ) при этом должны быть достаточно большими, чтобы

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

Утверждение. Замена ограничений y/gZ/g =0 на y/g ¿d/g и z/g ¿h/g не

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

Согласно идее Удзавы, переходим к решению двойственной задачи

maxF(w), где F(w) = min <P(x,y,z,w) - двойственная функция. Двойственная w (х ,y,z)eS

задача проще исходной, так как исходная задача целочисленная, а w может принимать любые вещественные значения. Кроме того, F(w) выпукла вверх, что позволяет ее максимизировать с помощью итерационной субградиентной процедуры. По определению, для вычисления значения функции F(w) при некотором фиксированном w (что делается на каждой итерации) нужно минимизировать функцию Ла-гранжа по переменным х, у, z. Из вида (11) следует, что при фиксированном значении w двойственных переменных задача вычисления F(w) = min <P(x,y,z,w)

(x,y,z)eS

и нахождения соответствующих х , у, z , на которых этот минимум достигается, разбивается на 3 самостоятельные подзадачи: 1) - задача о назначениях по х, а 2) и 3) - простейшие линейные задачи по у и z с двусторонними ограничениями на переменные, решения которых могут быть найдены по формулам:

У lg

с1щ, если a/g < О,

О , еСЛИ üjg > 0, zig =

О <yig <,dig ,если а/д = 0;

h/g , если bfg < 0, 0, если bfg > О, О <.Z]g <, h/g , если bjg=0.

Значения у ¡g или /и г^ в случае, когда а/д = 0 или /и^=0, можно определять как реальные значения простоев у*/д и задержек при конкретном расписании х .

Значения d/g- и h/g в диссертации предлагается определять несколькими способами:

1) d/g = max(l;y'jg ), h/g = max(l;zy). (12)

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

2) dy^yy + Q, h/g =zq + Q.

Тогда решения линейных задач будут такими:

0, если Ь/д > О, z'/g + Q, если Ь/д <0,

если Ь/д =0.

0, если а/д >0, УЩ + (?,если а/д <0, г/ унесли а/д =0;

Заметим, что можно использовать и различные параметры (У/у ¿1 в формулах верхних границ:

3) Ь/д=г*Ь+()1д.

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

г/у в линейных задачах также обсуждаются в главе 3.

Субградиент двойственной функции в точке имеет вид

= (#11 ,<?21 >■••, > 812 >■■■>8к) >•- > Зтп ) причем его координатами являются левые части ограничений (3)-(6), вычисленные при х , у, г .

В диссертации предлагается упростить вычисление координат субградиента исходя из следующих соображений. Вычисление простоев приборов у^ и задержек требований г ^ при заданном порядке обслуживания х основывалось на том, что они обращают ограничения (3)-(6) в равенства, то есть обращают в 0 их левые части. Поэтому координаты субградиента 5/^ будут отличаться от 0 на столько, на

сколько отличаются от 0 соответствующие разности ( у^ - у^) и (г/д -Таким образом,

= "*1 " У*1 - «к-1,1 > к = 2,т, =«1уУ = 2,п ,

к = 2,т, у = 2,л .

Здесь введены обозначения иц = Ук/ ~У%> •

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

, к = 1,/и, у =1 ,п,

где 8 ,£ >0 можно выбирать целыми; Е - число, как-либо связанное с размерностью задачи (т и п).

Если для значений целевой функции задачи может быть вычислена априорная оценка снизу, то получение на текущей итерации расписания со значением критерия (в данном случае, длины), равным этой оценке, означает, что получено точное

г _ г

решение. Поэтому в случае, если -—— < Т , где Л - значение критерия, Р- априорная нижняя оценка, 05 т <1 - параметр, задаваемый пользователем, можно завершить работу алгоритма и объявить текущее расписание приближенным решением. Очевидно, чем меньше параметр Т, тем точнее решение. Оценку длины расписания - целевой функции (7) - в задаче 1 можно определять как

К = тах /у . г=\,т

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

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

двойственных переменных. Он осуществляется по формулам где <?дг - величина шага на Л^-ой итерации. Поскольку в алгоритме Удзавы предполагается Ит вц = 0 , то можно выбрать шаг в^ = У^. После этого необходимо

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

Алгоритм решения задачи 1 изображен ниже в виде блок-схемы:

Остановимся на особенностях решения других задач.

Для задачи 2 нижняя оценка длины расписания вычисляется по той же схеме, что и для задачи 1: Р = тах /у , но при вычислении Р г учитываются обяза-

г~\,т

тельные задержки а^ .

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

т п

Для задачи 4 можно использовать оценку Р = £ + £ /т1 ,

/•=1 /=1

где Рг - оценка суммы сдвигов вправо по г-му прибору для ликвидации его промежуточных простоев:

^ = тах

О, /Ц™

1=1

Рг = тах

С-р Ьг-^-Ъп+с ¿=1 /=1

-2,т.

В задаче 6 в математической модели присутствует ограничение-неравенство на продолжительность рабочей смены. При составлении функции Лагранжа ему в соответствие ставится двойственная переменная и>о 2:0, поэтому при переходе к

следующей итерации =[и<о+^<Уо]+>гДе = тах(0;а) .

В задаче 7 для целевой функции получена априорная нижняя оценка: Р = max.Fr ,

Г=1,Л1

п п т

где Рг = £(л-/ + 1)/п + £ + "Ш.

/=1 <=1 *=г+1 '=1,»

г-1 /-1

я 1'И + К'г/ "'л) *=0 /=1

при г=т средний член (двойная сумма) отсутствует.

При наличии обязательных задержек между стадиями

г-1 г I-1

+»!«*/ +Юг/ *=0 4=2 /=1

(=1 ,=1Ь=г+1 /=1,п

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

В задаче 9 (с циклическим производством) перед составлением функции Лагранжа были проведены некоторые преобразования модели, уменьшающие ее размерность. Функция Лагранжа может быть приведена к виду:

Ф(х,у,г,Л,*>,у) = I 2 с0хУ + 2 I аиУк, + ! Е ь1д21у ■

(х,у,т)е8, у-ЦО /=1 у=1 *=1 у=1 ¿=1 у=1

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

1оЯ-*тт вводятся формальные ограничения: А > Л, A S Л .

Разработана компьютерная программа «Решение задач теории расписаний для конвейерных систем (Schedules)» в среде Borland Delphi 6.0, поддерживающая реализацию на ЭВМ алгоритмов получения субоптимальных расписаний для различных задач. Она состоит из основного блока и дополнительных частей, учитывающих модификации алгоритма, расчетов для каждой конкретной задачи, имеет удобный для пользователя интерфейс. Ниже изображена структура программы.

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

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

В четвертой главе рассмотрена задача оптимизации загрузки оборудования для одного из механических цехов машиностроительного предприятия ОАО «ВЭКС» (Воронежский экскаваторный завод), где производятся детали, необходимые для редукторов (одного из сборочных узлов экскаватора). Производство циклическое, период — месяц. Для каждого наименования деталей известно количество, которое должно быть произведено за месяц. Каждая деталь в процессе производства подвергается поочередно определенным операциям, так что систему обслуживания (переходя уже к терминам теории расписаний) можно считать многостадийной системой конвейерного типа. План запуска деталей в производство составляется для каждой декады месяца Число деталей данного типа (плановое месячное) распределяется по трем декадам пропорционально числу рабочих дней в декадах. Так как за месяц детали должны быть произведены в сравнительно больших количествах, они запускаются в производство не единично, а партиями.

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

Как выяснилось в результате исследования, эту задачу можно смоделировать в виде циклической задачи с критерием равномерной подекадной загрузки приборов в течение месяца (задача 9). На основе реальных данных о длительностях обработки и планах выпуска были построены расписания, сокращающие отклонение загрузки приборов от равномерной, что ведет к сокращению технологического времени на 10-12% по разным типам деталей.

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

был получен календарный план. Значение целевой функции для него составляет 0,74, тогда как для исходного расписания - 0,96. В таблице 2 показан результат работы программы в виде календарного плана для шестерен 5225.01.17.008 (план -28 деталей в месяц).

Таблица 1.

_Вид шестерни № опер (прибора)1 5225.01 17.004 5225 01 17 005 5225 01 17 008 301.01 17.001 30Ь01 17.002 5225 03 02.001

1 (токарн.) 62,12 63,18 67,24 58,1 87,3 69,02

2 (зубофрез.) 38,27 50,4 22,33 44,5 26 22,67

ЖЖ1 шягт V 7,21

3 (токарн.) 42,73 24,54 52,35 42,8 30,7 54,24

4 (токарн.) 66,29 43,64 - 66,4 70 64,09

5 (протяжн.) - - 12,31 - 12,3 8,63

6 (токарн.) - - - - 14,4 20,26

7 (протяжн.) - - 12,31 - 12,3 8,63

8 (шлифов.) - 18,47 - 18,4 -

9 (шлицефрез.) - - 55,73 - 55,6 -

'ййюЩШ! рь/-»" » Г чг&г' ........... * //

10 (зубошлиф.) 73,47 117,27 51,73 86 59,3 52,4

11 (слес.+маркир.) 21,75 12,06 8,76 21,9 8,8 8,76

Таблица 2.

^Цень Оп^х 1,2 3,4 5,6 7,8 9,10 11,12 13,14 13,16 17,18 19,20 21,22

1 4 10 14

2 4 10 14

3 14 14

4 5 4 10 5| | 4

5 5 4 10 9

6 9 4 10 S

7 9 4 10 5

8 14 4 10

9 14 4 10

10 14 4 10

11 5, , 9 4 10

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 1. Разработаны математические модели задач составления расписаний для технологических систем конвейерного типа, различающихся дополнительными требованиями к функционированию, в форме задач целочисленного программирования. На основе анализа существующих методов решения задач теории расписаний сделан вывод о необходимости поиска и разработки новых приближенных алгоритмов решения;

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

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

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

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

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

Основные результаты диссертации опубликованы в следующих работах:

1. Балашева С.Ю. О задаче теории расписаний с различными моментами поступления требований в систему И Сб. работ студентов и аспирантов факультета прикладной математики и механики. - Воронеж: ВГУ, 1998. - Вып.2. - С. 3-10.

2. Ленина А.Я., Балашева С.Ю. Оптимизация в системе конвейерного типа с ограничением времени обслуживания // Математика. Компьютер. Образование: Сб трудов V Междунар. конф. - М.: Прогресс-Традиция, 1998. - Вып 5. - Ч.П. - С. 12-18.

3. Ленина Л.Я., Балашева С.Ю., Мосьпан C.B. О задаче теории расписаний с различными моментами поступления требований в систему и ограничением времени обслуживания // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. тр. - Воронеж: ВГТУ, 1998. - С. 133-139.

4. Ленина Л.Я., Балашева С.Ю., Ефимова O.E. Модель конвейерной системы с критерием суммы моментов завершения обслуживания требований // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. тр. - Воронеж: ВГТУ, 1999.-С. 60-66.

5. Ленина Л.Я., Балашева С.Ю. О задаче теории расписаний с директивными сроками завершения обслуживания требований И Математика. Компьютер. Образование: Сб. трудов VII Междунар. конф. - М.: Прогресс-Традиция, 2000. - Вып.7. -4.II. - С. 502-506.

6. Ленина А.Я., Балашева С.Ю. О конвейерной системе с различными моментами поступления требований и обязательными задержками между стадиями // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. тр. - Воронеж: ВГТУ, 2000. - С. 150-158.

7. Балашева С.Ю. Комплекс задач теории расписаний для конвейерных систем II Математика. Образование. Экология. Тендерные проблемы: Материалы Междунар конф. - Воронеж, 2000. - С. 46-47.

8 Балашева С Ю. О некоторых подходах к решению задачи Беллмаиа - Джонсона и ее модификаций // Математика. Образование. Экология. Тендерные проблемы: Материалы Междунар. конф. - М.: Прогресс-Традиция, 2001 - Т. 2. - С 31-37

9 Асиина А.Я., Балашева С.Ю. О двух модификациях задачи Беллмана -Джонсона: модели и алгоритм решения // Вестник Воронежского государственного технического университета. Сер. САПР и системы автоматизации производства. -2001.-Вып. 3.1.-С. 34-39.

10. Аснина А.Я. О решении одной динамической задачи теории расписаний / А.Я. Аснина, С.Ю. Балашева // Математика. Экономика. Образование: Тез. докл. X Междунар. конф. - Ростов н/Д, 2002. - С. 248.

11 Аснина А.Я., Балашева С.Ю. Итерационный метод решения одной динамической задачи теории расписаний // Вестник Воронежского государственного технического университета. Сер. Вычислительные и информационно-телекоммуникационные системы. - 2002. - Вып. 8.2. - С. 24-27.

12. Балашева С.Ю. О некоторых задачах теории расписаний для систем конвейерного типа и формах их записи // Математика. Экономика. Образование. Ряды Фурье и их приложения: Труды Российской ассоциации «Женщины - математики» - Воронеж, 2002. - Т. 10. - Вып. 1. - С. 41-45.

13. Аснина А.Я., Балашева С.Ю. Математические методы поддержки синхронизации технологического процесса в системах конвейерного типа // Математика. Компьютер. Образование: Сб. тр. IX Междунар. конф. - Москва-Ижевск: R&C Dynamics, 2002. - Вып.9. - Ч. П. - С. 522-530.

14. Аснина А.Я., Балашева С.Ю. Моделирование и оптимизация функционирования механического цеха машиностроительного предприятия // Математика. Компьютер. Образование: Материалы X Междунар. конф. - Москва-Ижевск: R&C Dynamics, 2003. - Вып. 10. - Ч. IL - С. 127-135.

15. Аснина А.Я., Балашева С.Ю. Оптимизация обработки деталей при циклическом производстве // Математика. Образование. Экономика. Тендерные проблемы: Материалы конф. - М., 2003. - Т. 1. - С. 7-8.

16. Аснина А.Я., Балашева С.Ю. Теория двойственности как инструмент при решении задач теории расписаний // Моделирование сложных систем. Современные направления теории и практические приложения: Материалы Междунар. школы-семинара «Современные проблемы механики и прикладной математики». - Воронеж: ВГУ, 2004. - С. 9-13.

Подписано в печать 10.11.2005, Формат 60x84/16. Бумага для множительных аппаратов. Усл.печ.л. 1,0. Тираж 90 экз. Заказ №

Воронежский государственный технический университет 394026 Воронеж, Московский просп., 14

¡Ü2 2 4 76

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

2006-4 25914

Введение.

Глава 1. Задачи теории расписаний для систем конвейерного типа

1.1. Основные понятия теории расписаний.

1.2. Критерии оценки качества расписаний

1.3. Постановка задачи Беллмана - Джонсона.

NP-трудность задач теории расписаний

1.4. Обзор основных методов решения.

1.5. Выводы, постановка цели и задач исследования.

Глава 2. Модификации задачи Беллмана - Джонсона.

4 Математические модели.

2.1. Математическая модель для классической постановки.

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

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

2.4. Задача с директивными сроками завершения обслуживания

2.5. Задачи с ограничением времени обслуживания

2.6. Задачи с непрерывным технологическим циклом.

2.7. Задачи с запретом простоев приборов.

2.8. Динамическая задача теории расписаний

2.9. Задача для системы с циклическим производством.

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

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

3.1.1. Построение функции Лагранжа

3.1.2. Минимизация функции Лагранжа щ при фиксированных двойственных переменных.

3.1.3. Вычисление субградиента

3.1.4. Правила останова. ф 3.1.5. Пересчет двойственных переменных.

3.1.6. Нижняя оценка длины расписания

3.1.7. Формальный алгоритм

3.1.8. Различные подходы к оцениванию верхних границ простоев приборов и задержек требований.

3.2. Применение метода к другим задачам.

3.2.1. Задача с обязательными задержками между стадиями

3.2.2. Задача с непрерывным технологическим циклом

3.2.3. Задача с непрерывной работой приборов 3.2.4. Задача с директивными сроками завершения обслуживания .104 4 3.2.5. Задачи с ограничением времени обслуживания.

3.2.6. Задача минимизации суммы моментов завершения обслуживания требований в системе с различными моментами поступления .:.

3.2.7. Вычисление нижней оценки суммы моментов завершения обслуживания требований.

3.2.8. Задача для системы с циклическим производством

Глава 4. Расчет календарного плана выпуска деталей в ОАО «ВЭКС».

4.1. Постановка задачи.

4.2. Модель задачи и метод решения.

4.3. Расчет календарного плана. Результаты.

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

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

Работа выполнена в соответствии с одним из основных научных направлений Воронежского государственного университета «Анализ и математическое моделирование сложных систем».

За ценные идеи, позволившие обозначить круг проблем, определить направления исследования, а также за содействие в его реализации выражаю искреннюю благодарность Лениной А.Я., кандидату технических наук, доценту кафедры ММИО факультета ПММ ВГУ.

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

Для достижения указанной цели в диссертационной работе решаются следующие основные задачи:

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

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

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

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

- оценка эффективности разработанных алгоритмов и программ на примере реальных технологических систем.

Объектом исследования являются системы типа flow-shop.

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Предложенные в диссертационной работе модели, методы и программное обеспечение использовались при решении задачи оптимизации загрузки оборудования для механических цехов машиностроительного предприятия ОАО «ВЭКС». На основе реальных данных о длительностях обработки и планах выпуска были построены расписания, сокращающие отклонение загрузки приборов от равномерной.

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

Апробация работы. Основные результаты работы докладывались и обсуждались на VI, X Международных конференциях женщин-математиков «Математика. Образование. Экономика» (Чебоксары, 1998; Ростов-на-Дону,

2002); на VI Международной конференции «Экология и здоровье человека. Экологическое образование. Математические модели и информационные технологии» (Краснодар, 2001); на 24-й международной школе-семинаре им. Шаталина С.С. «Системное моделирование социально-экономических процессов» (Воронеж, 2001); на Международной конференции «Математика. Образование. Экология. Тендерные проблемы» (Воронеж, 2000; Пущино, 2001; Воронеж, 2003); на V, VII, IX, X Международных конференциях «Математика. Компьютер. Образование» (Дубна, 1998, 2000, 2002; Пущино,

2003); на международной школе-семинаре «Современные проблемы механики и прикладной математики» (Воронеж, 2004); на ежегодных научных конференциях Воронежского государственного университета.

Публикации. Основное содержание диссертационной работы отражено в 23 печатных работах.

Структура работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 152 страницах, списка литературы из 70 наименований и приложений, содержит 10 рисунков и 13 таблиц.

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

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

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

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

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

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

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

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

Предложенные в диссертационной работе модели, методы и программное обеспечение использовались при решении задачи оптимизации загрузки оборудования для механических цехов машиностроительного предприятия ОАО «ВЭКС». На основе реальных данных о длительностях обработки и планах выпуска были построены расписания, сокращающие отклонение загрузки приборов от равномерной;

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

ЗАКЛЮЧЕНИЕ

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

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

1. Bellman R. Some Combinatorial Problems Arising in the Theory of Multistage Processes / R. Bellman, O. Gross // J. Soc. 1.dust. and Appl. Math. - 1954. -V.2, №3. - P. 175-183.

2. Bellman R. Mathematical Aspects of Scheduling Theory / R. Bellman // J. Soc. Indust. and Appl. Math. 1956. - V.4, №3. - P. 168-205.

3. Конвей P.B. Теория расписаний / P.B. Конвей, В.Л. Максвелл, Л.В. Миллер. М.: Наука, 1975.

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

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

6. Реклейтис Г. Оптимизация в технике / Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. М.: Мир, 1986. - Т.1,2.

7. Левин В.И. Структурно-логические методы исследования сложных систем с применением ЭВМ / В.И. Левин М.: Наука, 1987.

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

9. Танаев B.C. Теория расписаний. Многостадийные системы / B.C. Танаев, Ю.Н. Сотсков, В.А. Струсевич М.: Наука, 1989.

10. Левин В.И. Задача М станков при поступлении деталей в режиме реального времени / В.И.Левин // Автомат, и телемех. 1989. - №1. - С. 141154.

11. Левин В.И. Оптимизация расписаний в системах с неопределенными временами обработки. 1,11 / В.И.Левин // Автомат, и телемех. 1995. - №2. -С. 99-110. - №3. - С. 106-116.

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

13. Бурдюк В .Я. О выборе последовательности загрузки станков / В.Я. Бурдюк//Экон. и мат. методы. 1970.-Т.6, №1.-С. 112-116.

14. Лепешкинский Н.А. К вопросу упорядочения обработки деталей / Н.А. Лепешкинский // Изв. АН БССР. Сер. физ.-мат. наук. 1966. - №2. - С. 3135.

15. Лепешкинский Н.А. Об одной задаче теории расписаний / Н.А. Лепешкинский // Изв. АН БССР. Сер. физ.-мат. наук. 1966. - №3. С. 90-96.

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

17. Солих Р. Задача календарного планирования для циклически повторяющегося производства / Р. Солих // ЖВМ и МФ. 1973. - Т.13, №2. - С. 326342.

18. Шурайц Ю.М. Минимизация времени ожидания комплексов работ при двухэтапном обслуживании / Ю.М. Шурайц // Автомат, и телемех. 1977. -№12. С. - 138-144.

19. Тимковский В.Г. К сложности составления расписания произвольной системы / В.Г. Тимковский // Изв. АН СССР. Техн. кибернетика. 1985. -№3.-С. 102-109.

20. Тимковский В.Г. Приближенное решение задачи составления расписания циклической системы / В.Г. Тимковский // Экон. и мат. методы. 1986. -Т.22, №1. - С. 171-174.

21. Левнер Е.В. Задача сетевого планирования в постановке "точно вовремя" и потоковый алгоритм ее решения / Е.В. Левнер, А.С. Немировский // Численные методы оптимизации и анализа. Новосибирск: Сиб. энерг. ин-т, 1992.-С. 18-53.

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

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

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

25. Левин В.И. Оптимальное планирование работ в конвейерных системах / В.И. Левин, И.Ю. Мирецкий // Автомат, и телемех. 1996. - №6. - С. 3-30.

26. Johnson S.M. Optimal Two and Three Stage Production Schedules with Set Up Times Included / S.M. Johnson // Nav. Res. Log. Quart. 1954. - V.l, №1. - P. 61-68.

27. Хоботов E.H. Некоторые замечания к теореме Джонсона / Е.Н. Хоботов // Автомат, и телемех. 1995. - №10. - С. 186-187.

28. Вагнер Г. Основы исследования операций / Г. Вагнер Т. 1,2. - М.: Мир, 1973.

29. Беллман Р. Прикладные задачи динамического программирования / Р. Беллман, С. Дрейфус М.: Наука, 1965.

30. Хореев В.И. Итеративные алгоритмы определения расписаний в информационно-вычислительных системах / В.И. Хореев // Автоматика и вычислит. техника. 1987. - №4. - С. 8-14.

31. Муравьев В.И. Использование метода переменного базиса для решения непрерывного аналога задачи Джонсона / В.И. Муравьев, И.В. Романовский // Исследование операций и статист, моделирование. Л., 1974. -Вып.2. - С. 27-37.

32. Giglio R.J. Approximate Solutions to the Three-Machine Scheduling Problems / R.J. Giglio, H.M. Wagner // Oper. Res. 1964. - V.12. №2. - P. 305-324.

33. Story A.E. Computational Experience with Integer Programming for Job-Shop Scheduling / A.E. Story, H.M. Wagner Englewood Cliffs, N.J.: Prentice-Hall, 1963. - Ch. 14.

34. Ленина А.Я. Приближенные методы решения задач теории расписаний на основе двойственных оценок / А.Я. Аснина // Экономико-математические модели и методы: Сб. науч. трудов. Воронеж: ВГУД989. - С. 162-168.

35. Аснина А.Я. Об опыте решения задач Джонсона с произвольным числом станков / А.Я. Аснина, Р.А. Тищенкова // Системный анализ и моделирование социально-экономических процессов: Тр. II Всесоюз. семинара. -М.,1981.

36. Аснина А.Я. Использование методов линейного программирования при решении некоторых задач теории расписаний / А.Я. Аснина, JI.A. Черникова // II Всесоюз. школа-семинар по оптимизации и ее приложениям в экономике: Тез. докл. Ашхабад, 1984.

37. Аснина А.Я. Оптимизация гибкого производства БИС на основе модели календарного планирования / А.Я. Аснина, Т.О. Толстых // Модели и алгоритмы оптимизации сложных систем. Воронеж, 1985.

38. Аснина А.Я. Об одном алгоритме решения задачи Джонсона / А.Я. Аснина, Г.Д. Чернышова // Тр. 4-й Междунар. конференции женщин-математиков, Волгоград, 27-31 мая 1996. Н.Новгород, 1997. - Т.4, вып.1 - С. 82-86.

39. Первозванский А.А. Математические модели в управлении производством / А.А. Первозванский М.: Наука, 1975.

40. Ворожеева С.В. Вероятностный алгоритм формирования поисковых функций при решении задач условной оптимизации / С.В. Ворожеева, Г.Д. Чернышова // Алгоритмы моделирования и оптимизации автоматизированных систем. Воронеж, 1990. - С. 115-121.

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

42. Аснина А .Я. Применение теории двойственности к решению задач теории расписаний / А .Я. Аснина, О.В. Толоконникова // Высокие технологии в технике, медицине и образовании: Межвуз. сб. науч. трудов. Воронеж: ВГТУ, 1997. - Ч. 1. - С. 30-36.

43. Балашева С.Ю. О задаче теории расписаний с различными моментами поступления требований в систему / С.Ю. Балашева // Сб. работ студентов и аспирантов факультета прикладной математики и механики. Воронеж: ВГУ, 1998.-Вып.2.-С. 3-10.

44. Ленина А.Я. Метод решения задачи теории расписаний с директивными сроками завершения обслуживания / А.Я. Ленина, С.Ю. Балашева // Математика. Компьютер. Образование: Сб. трудов VII Международной конференции. М.: Прогресс-Традиция, 2000. - С. 23.

45. Ленина А.Я. Модель конвейерной системы с ограничением времени обслуживания / А.Я. Ленина, С.Ю. Балашева, С.В. Мосьпан // Математика. Компьютер. Образование: Тез. докл. V Междунар. конференции. Дубна, 1998.-С. 12.

46. Аснина А.Я. О двух модификациях задачи Беллмана Джонсона: модели и алгоритм решения / А.Я. Аснина, С.Ю. Балашева // Вестник ВГТУ. Серия «САПР и системы автоматизации производства» - Воронеж: ВГТУ, 2001.-Выпуск3.1 - С. 34-39.

47. Аснина А.Я. Итерационный метод решения одной динамической задачи теории расписаний / А.Я. Аснина, С.Ю. Балашева // Вестник ВГТУ. Серия «Вычислительные и информационно-телекоммуникационные системы». -Воронеж: ВГТУ, 2002. Выпуск 8.2. - С. 24-27.

48. Куренков А.В. К вопросу решения некоторых динамических задач теории расписаний статическими методами / А.В. Куренков Тула: Тул. гос. университет, 1999. - 5 с. - Деп. ВИНИТИ №1963-В96 17.06.99 г.

49. Балашева С.Ю. Комплекс задач теории расписаний для конвейерных систем / С.Ю. Балашева // Математика. Образование. Экология. Тендерные проблемы: Материалы Международной конференции. Воронеж, 2000. -С. 46-47.

50. Аснина А.Я. О задаче теории расписаний для конвейерной системы с циклическим производством / А.Я. Аснина, С.Ю. Балашева // Математика. Компьютер. Образование: Тез. докл. X Международной конференции. Москва-Ижевск: R&C Dynamics, 2003. - С. 84.

51. Балашева С.Ю. О некоторых подходах к решению задачи Беллмана -Джонсона и ее модификаций / С.Ю. Балашева // Математика. Образование. Экология. Тендерные проблемы: Материалы Международной конференции. М.: Прогресс-Традиция, 2001. - Том 2. - С. 31-37.

52. Аснина А.Я. Некоторые предложения по оцениванию верхних границ простоев приборов и требований для систем конвейерного типа / А.Я.

53. Ленина, С.Ю. Балашева, В.В. Пшеничная // Математика. Компьютер. Образование: Тез. докл. IX Международной конференции. М.: Прогресс-Традиция, 2002. - С. 85.

54. Аснина А.Я. Оптимизация обработки деталей при циклическом производстве / А.Я. Аснина, С.Ю. Балашева // Математика. Образование. Экономика. Тендерные проблемы: Материалы конференции. Москва, 2003. — Том 1.-С. 7-8.

55. Воронежского зственного университетаи"- ъ-г, -г„у п, И.И. Борисов2005 г.1. АКТо внедрении результатов диссертационной работы в учебный процесс

56. Настоящим актом подтверждается:

57. Декан ф-та ПММ / Шашкин А.И.fise&'16В1. ОТКРЫТОЕ55 5

58. Платежные реквизиты: ИНН 3662063336, р/сч.40702810213ООО106482, Центрально-черноземныйбанк СБ РФ, к/сч.30101810600000000681, £ИК 042007681

59. Россия, 394712, Воронеж Московский пр-т., 11 Тел./факс (0732) 51-21-84 153912 BOX 0890010 E-mail: tyazhex(cpcomch. rutyazhex® KEX400. vrn.ru200 г.то'о 0A0"B8KG" аватор

60. СПРАВКА о внедрении результатов диссертационной работы Балашевой Светланы Юрьевны

61. В соответствии с этим рассчитаем длины расписаний стх, <т2 и <т3.0.1 5 4 1 2 32 3 4 10 15ft 5 11 18 22 27ft 9 18 20 26 29т2 4 1 5 3 21 2 4 9 15ft 7 14 17 22 26ft 14 16 21 24 300.3 4 1 2 5 3ft 1 2 8 10 15ft 7 14 18 21 26ft 14 16 22 26 28

62. Итак, длины расписаний, полученных с помощью 3 эвристических алгоритмов, равны соответственно 29, 30 и 28. Лучшее из этих расписаний сг3 = (4,1,2,5,3). Его будем считать рекордным, а его длину - начальным рекордом для метода ветвей и границ (R=28).

63. Дерево перебора изображено на рис. 1.1 (глава 1) и ниже. В кружках-вершинах указаны значения нижних оценок соответствующих подмножеств; рядом со стрелками указаны требования, фиксируемые при ветвлении.

64. Дерево перебора (метод ветвей и границ для примера).iTi

65. G54123 5 4 1 2 3 G54132 5 4 1 3 2ft 2 3 4 10 15 ft 2 3 4 9 15ft 5 11 18 22 27 ft 5 11 18 23 27ft 9 18 20 26 29 ft 9 18 20 25 31yt 5 2 0 2 1 yl 5 2 0 3 2

66. Заметим, что в системах рассматриваемого типа может быть вычислена априорная нижняя оценка длин всех расписаний п1. Yuai + min (б, +Cj),n

67. F = max-^ min a,- + bj + min ,i—\.n i~\ i-\.n nmin (a.j +b})+ с i i=\.n /=1

68. Решение примера закончено.

69. У Общая схема вычисления коэффициентов су на шаге 3 алгоритма,основанного на вычислении двойственных оценок (глава 1).

70. Из (1.7) следует, что 0<wkj+i<wkj для &=2.М, 7-I.JV-I, а из (1.6)можно получить неравенства wkj <wk+.j< 1 для A=2.iW-l, J-I.N. Таким образом, 0< Wk,j+\ Дш k=2.M, j=\.N-\ и 0< wkj < Wk+\,j -1 Для

71. JW-1, 7=1.TV. Следовательно, если для некоторого /* w *= 1, то и wkj-=l*для всех /< j , а если "и^.* =0, то и wkj =0 для всех /> у . С другой стороны,*ф если для некоторого к vtg то и wkj-l для всех к>к , а если тои wkj- =0 для всех к< к .

72. Рассмотрим 7=72. с^ = tMi + £ I tkiwk,M 1 • w*/2=1 дляk=2 " k=2с=2, а следовательно и для всех к=2.М. +i =0 для А=2. Если 73 = j2, тоw3,y2+l = ^з,7з +1иначе так как w37=l Для7з • Аналогично,для к=4.М wkj2+l= 0 в случае jk=j2 и wkj2+l=l в случае jk>j2

73. Если l2 нельзя найти (то есть даже jM =j2), то су7 -t\j+ t2i +. + tMi (таккак W£j2+i =0 для всех &=2.М).

74. Рассмотрим 7=1.-7*2-1 (в случае, если j2>\). При всех таких jм мwkj7=™kj2+. =1 для всех к, поэтому с у = tMi + X h-],iwkj ~ X hiwk,j+\ =к=2 к=21. М МММ

75. Mi + X h-\,i ~ Yhi = Hhi ~ Л hi =t\i ■ k=2 k=2 k=1 k=2

76. Для7=72+1 •• 73"1 (в случае, если 7з>72+1) w2j=w2j+l=0> a Для k>21. M МММwkj = wkj+1=1, поэтому Cy = tM + X = Х^/" X'*/ = hi ■к= 3 *=3 Л=2 £=31. М МММ

77. Для 7=73 С1Г1М1 + X ^-1,/ Х^/ = - Х^/ = hi +- + %-где3 ifc=/3 £=2 jfc=/33 = min {A: >3:jk>j3}, если jM > j3 , и /3 =М+1, если jM =j3 .

78. Итак, общую схему вычисления коэффициентов с у (на Шаге 3 описанного в главе 1 алгоритма) можно представить следующим образом:0. Положить р=2, д=1;

79. Если jp >q, то для j=q.jp-l положить с у =tpij для z—1 .N;

80. Haita lB = >p:Jl> JP * еСЛИ ju > ;у р \М +1, если 1м = 7лlp-1для 7= jp (=.=7/ .) положить с у = XOt/ Дляг-I.TV;3. Положить д= 7^+1, р=1р\если после этого /?=М+1, то для j=q.N, для z=l.JV положить с у =tMi и закончить вычисления, иначе перейти к 1).

81. Следуя упрощенной схеме вычисления коэффициентов с^ (в Приложении 2), получим сп =t.i+t2i, С12 — С12 =t2i, С/4 =t2i+t3i, Ci5 =t3i, то есть элементы сц матрицы С будут такими:хi \ 1 2 3 4 51 8 7 7 9 22 10 4 4 8 43 10 5 5 7 24 7 6 6 13 75 5 3 3 7 4

82. Ячейки, закрашенные серым, соответствуют базисным переменным Ху. В них ut + Vj = Су и, следовательно Ay-Uj+v j-Cy = 0.

83. Длина расписания составит 19 + 11 =30. Обновляем рекорд и рекордную перестановку: R=30, 7rR=7r= (4,1,2,3,5). Диаграмма Гантта для расписания:к=3 4 I 2 3 5к=2 4 1 2 3 5 Iк=1 4 1 2 3 5 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

84. Коэффициенты Сц будут вычисляться по формулам с л = t\i + %> сi2 = С;з = Cj4 = t2j, С/5 = t2j + /3/, то есть элементы Сц матрицы С будут такими:1 2 3 4 51 8 7 7 7 92 10 4 4 4 83 10 5 5 5 74 7 6 6 6 135 5 3 3 3 7

85. Далее вычисляются потенциалы ui и v; . В таблицах ниже приведены значения (мг+у. ) для вычисленных и{ и v.-, а также оценки Ai;-=Mf+v;--Cy.1. Аи 0 0 0 0 5-5 0 0 0 3-4 0 0 0 50 0 0 0-4 -3 -3 -3 0

86. Длина расписания составит 19 + 9 = 28. Обновляем рекорд и рекордную перестановку: R=28, 7ГК = 7Г= (4,5,2,3,1). Диаграмма Гантта для расписания:к=3 4 5 2 3 1к=2 4 5 2 3 1 к=1 4 5 2 3 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28w

87. Коэффициенты с у будут вычисляться по формулам c^-t^+t ci2 = с/3 = ci4 = hi> ci5 = hi + hi' то есть матрица С не изменилась:i 1 2 3 4 51 8 7 7 7 92 10 4 4 4 83 10 5 5 5 74 7 6 6 6 135 5 3 3 3 7