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

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

Исследованы свойства задач построения допустимых и оптимальных расписаний выполнения N заданий на m машинах в условиях потерь времени на перекладки. На основе установленных свойств конструируются операторы исключения из рассмотрения подмножеств расписаний, не содержащих допустимых решений. Предложен...

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Системні дослідження та інформаційні технології
Дата:2012
Автор: Зак, Ю.А.
Формат: Стаття
Мова:Russian
Опубліковано: Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2012
Теми:
Методи оптимізації, оптимальне управління і теорія ігор
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/50167
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Разбиение на подмножества и построение допустимых и оптимальных последовательностей выполнения множества заданий на нескольких машинах / Ю.А. Зак // Систем. дослідж. та інформ. технології. — 2012. — № 2. — С. 87-101. — Бібліогр.: 14 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-50167
record_format dspace
spelling Зак, Ю.А.
2013-10-06T14:06:15Z
2013-10-06T14:06:15Z
2012
Разбиение на подмножества и построение допустимых и оптимальных последовательностей выполнения множества заданий на нескольких машинах / Ю.А. Зак // Систем. дослідж. та інформ. технології. — 2012. — № 2. — С. 87-101. — Бібліогр.: 14 назв. — рос.
1681–6048
https://nasplib.isofts.kiev.ua/handle/123456789/50167
519.874
Исследованы свойства задач построения допустимых и оптимальных расписаний выполнения N заданий на m машинах в условиях потерь времени на перекладки. На основе установленных свойств конструируются операторы исключения из рассмотрения подмножеств расписаний, не содержащих допустимых решений. Предложены алгоритмы вычисления нижних оценок различных критериев оптимальности, а также алгоритмы решения рассматриваемых задач последовательными алгоритмами оптимизации.
Досліджено властивості задач побудови допустимих та оптимальних розкладів виконання N завдань на m машинах за умов втрат часу на переналагодження. На основі встановлених якостей конструюються оператори включення із розгляду підмножин описів, які не містять допустимих рішень. Запропоновано алгоритми обчислення нижніх оцінок різних критеріїв оптимальності, а також алгоритми вирішення задач, що розглядаються послідовними алгоритмами оптимізації.
The properties of the problems of building the admissible and optimal schedules for implementation of N tasks on the m machines under the condition of a loss of time on changeovers are investigated. On the basis of the established properties the operators of the inclusions are constructed from a consideration of the descriptions subsets, which do not contain admissible solutions. The algorithms for computing lower bounds for various optimality criteria and algorithms for solving the problems, which are considered by sequential algorithm optimization are proposed.
ru
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
Системні дослідження та інформаційні технології
Методи оптимізації, оптимальне управління і теорія ігор
Разбиение на подмножества и построение допустимых и оптимальных последовательностей выполнения множества заданий на нескольких машинах
Розбиття на підмножини і побудова допустимих та оптимальних послідовностей виконання множин завдань на декількох машинах
Partition into subsets and building admissible and optimal sequence of the tasks set performance on multiple machines
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Разбиение на подмножества и построение допустимых и оптимальных последовательностей выполнения множества заданий на нескольких машинах
spellingShingle Разбиение на подмножества и построение допустимых и оптимальных последовательностей выполнения множества заданий на нескольких машинах
Зак, Ю.А.
Методи оптимізації, оптимальне управління і теорія ігор
title_short Разбиение на подмножества и построение допустимых и оптимальных последовательностей выполнения множества заданий на нескольких машинах
title_full Разбиение на подмножества и построение допустимых и оптимальных последовательностей выполнения множества заданий на нескольких машинах
title_fullStr Разбиение на подмножества и построение допустимых и оптимальных последовательностей выполнения множества заданий на нескольких машинах
title_full_unstemmed Разбиение на подмножества и построение допустимых и оптимальных последовательностей выполнения множества заданий на нескольких машинах
title_sort разбиение на подмножества и построение допустимых и оптимальных последовательностей выполнения множества заданий на нескольких машинах
author Зак, Ю.А.
author_facet Зак, Ю.А.
topic Методи оптимізації, оптимальне управління і теорія ігор
topic_facet Методи оптимізації, оптимальне управління і теорія ігор
publishDate 2012
language Russian
container_title Системні дослідження та інформаційні технології
publisher Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
format Article
title_alt Розбиття на підмножини і побудова допустимих та оптимальних послідовностей виконання множин завдань на декількох машинах
Partition into subsets and building admissible and optimal sequence of the tasks set performance on multiple machines
description Исследованы свойства задач построения допустимых и оптимальных расписаний выполнения N заданий на m машинах в условиях потерь времени на перекладки. На основе установленных свойств конструируются операторы исключения из рассмотрения подмножеств расписаний, не содержащих допустимых решений. Предложены алгоритмы вычисления нижних оценок различных критериев оптимальности, а также алгоритмы решения рассматриваемых задач последовательными алгоритмами оптимизации. Досліджено властивості задач побудови допустимих та оптимальних розкладів виконання N завдань на m машинах за умов втрат часу на переналагодження. На основі встановлених якостей конструюються оператори включення із розгляду підмножин описів, які не містять допустимих рішень. Запропоновано алгоритми обчислення нижніх оцінок різних критеріїв оптимальності, а також алгоритми вирішення задач, що розглядаються послідовними алгоритмами оптимізації. The properties of the problems of building the admissible and optimal schedules for implementation of N tasks on the m machines under the condition of a loss of time on changeovers are investigated. On the basis of the established properties the operators of the inclusions are constructed from a consideration of the descriptions subsets, which do not contain admissible solutions. The algorithms for computing lower bounds for various optimality criteria and algorithms for solving the problems, which are considered by sequential algorithm optimization are proposed.
issn 1681–6048
url https://nasplib.isofts.kiev.ua/handle/123456789/50167
citation_txt Разбиение на подмножества и построение допустимых и оптимальных последовательностей выполнения множества заданий на нескольких машинах / Ю.А. Зак // Систем. дослідж. та інформ. технології. — 2012. — № 2. — С. 87-101. — Бібліогр.: 14 назв. — рос.
work_keys_str_mv AT zakûa razbienienapodmnožestvaipostroeniedopustimyhioptimalʹnyhposledovatelʹnosteivypolneniâmnožestvazadaniinaneskolʹkihmašinah
AT zakûa rozbittânapídmnožiniípobudovadopustimihtaoptimalʹnihposlídovnosteivikonannâmnožinzavdanʹnadekílʹkohmašinah
AT zakûa partitionintosubsetsandbuildingadmissibleandoptimalsequenceofthetaskssetperformanceonmultiplemachines
first_indexed 2025-11-25T21:05:31Z
last_indexed 2025-11-25T21:05:31Z
_version_ 1850548210959908864
fulltext © Ю.А. Зак, 2012 Системні дослідження та інформаційні технології, 2012, № 2 87 TIДC МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ УПРАВЛІННЯ І ТЕОРІЯ ІГОР УДК 519.874 РАЗБИЕНИЕ НА ПОДМНОЖЕСТВА И ПОСТРОЕНИЕ ДОПУСТИМЫХ И ОПТИМАЛЬНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ВЫПОЛНЕНИЯ МНОЖЕСТВА ЗАДАНИЙ НА НЕСКОЛЬКИХ МАШИНАХ Ю.А. ЗАК Исследованы свойства задач построения допустимых и оптимальных расписа- ний выполнения N заданий на m машинах в условиях потерь времени на пере- кладки. На основе установленных свойств конструируются операторы исклю- чения из рассмотрения подмножеств расписаний, не содержащих допустимых решений. Предложены алгоритмы вычисления нижних оценок различных кри- териев оптимальности, а также алгоритмы решения рассматриваемых задач последовательными алгоритмами оптимизации. ВВЕДЕНИЕ Задачи распределения множества заданий подлежащих выполнению по рабочим станциям (машинам) и определения оптимальных последователь- ностей их выполнения на каждой машине в условиях потерь времени на пе- реналадки имеют большое количество приложений в календарном планиро- вании производства, маршрутизации перевозок, а также организации обслуживания и выполнения ремонтных работ, организации вычислитель- ного процесса и т.д. Приведем только некоторые из таких постановок. КАЛЕНДАРНОЕ ПЛАНИРОВАНИЕ ПРОИЗВОДСТВА На K различных по техническим характеристикам единицах технологиче- ского оборудования (станках) необходимо произвести N различных партий деталей. Заданы времена обработки партии деталей каждого вида на каждом из станков, матрицы времен переналадок при переходе каждого станка от выпуска одной партии деталей на другую, а также временные ресурсы воз- можности использования оборудования и ограничения на сроки завершения обработки каждой партии деталей. Каждая партия деталей может обрабаты- ваться только на одном станке. Необходимо определить, партии каких дета- лей должны обрабатываться на каждом станке, а также последовательности их обработки на каждой единице технологического оборудования, которые Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 88 обеспечивают выполнение всех ограничений на временные ресурсы работы оборудования и сроки завершения выполнения заданий, а также экстре- мальное значение выбранного критерия оптимальности. В качестве крите- рия оптимальности может быть выбрано завершение обработки всех партий деталей в кратчайшие сроки или минимизация суммарного средневзвешен- ного времени занятости технологического оборудования. ПЛАНИРОВАНИЕ РЕМОНТНО-ПРОФИЛАКТИЧЕСКИХ РАБОТ K различных по своей квалификации и по уровню технического оснащения бригад должны обслужить N объектов (ремонтно-профилактические, мон- тажные работы, доставка, погрузка, разгрузка товаров и т.д.). Заданы време- на, необходимые каждой бригаде для выполнения всего объема работ на каждом из объектов, а также потери времени при переходе каждой бригады от одного объекта на другой. Необходимо определить подмножества объек- тов, обслуживаемых каждой бригадой, а также последовательности выпол- нения этих подмножеств работ, которые обеспечили выполнение всех зада- ний в установленные ограничениями сроки. В качестве критериев оптимальности построенного расписания могут быть выбраны минималь- ные суммарные затраты рабочего времени и времени на переезды всех бри- гад или выполнение всего множества заданий в кратчайшие сроки. Методам решения данного класса задач уделялось значительное место в монографиях и периодической литературе [1–3, 7, 9, 10]. Подходы, свя- занные с построением линейных и нелинейных целочисленных моделей и использование методов математического программирования для решения задач данного класса достаточно большой размерности, представляющих практический интерес, требуют больших объемов вычислений [6–8]. Наиболее широкое распространение получили приближенные методы решения задач данного класса с использованием генераторов случайных расписаний [6, 7, 12, 13], использующих различные правила предпочтения [7–11, 13], эвристические подходы [5, 9], а также генетические алгоритмы и эволюционные стратегии [4, 11]. Алгоритмы решения данной задачи без учета ограничений на директивные сроки выполнения заданий методами построения кратчайших допустимых путей на графах приведены в работе автора [12]. Указанные подходы позволили в ряде случаев находить эффек- тивные расписания выполнения заданий для многих практических приложе- ний. Однако наличие жестких ограничений на директивные сроки выполне- ния заданий в ряде случаев затрудняет процесс генерирования допустимых расписаний и существенно увеличивает затраты на поиск [13]. Кроме того, отсутствие нижних оценок значения критерия оптимальности построенного расписания не позволяет объективно оценить эффективность полученного решения. В данной работе изучаются свойства задач данного класса, на основе которых конструируются операторы исключения из рассмотрения подмно- жеств расписаний, не содержащих допустимых решений, предлагаются ал- горитмы вычисления нижних оценок различных критериев оптимальности. На основе установленных свойств предлагаются алгоритмы решения Разбиение на подмножества и построение допустимых и оптимальных… Системні дослідження та інформаційні технології, 2012, № 2 89 рассматриваемых задач последовательными алгоритмами оптимизации. В качестве частного случая рассматриваются свойства и алгоритмы реше- ния задачи определения допустимых и оптимальных последовательностей выполнения заданий на одной машине. ПОСТАНОВКА ЗАДАЧИ На K , Kk ,...,1= рабочих станциях (машинах) должны быть выполнены N различных работ (заданий), .,...,1, Nji = Каждое из заданий должно вы- полняться только на одной машине и без разрывов времени в процессе его выполнения. Пусть заданы: • директивные сроки завершения каждого из заданий iT , .,...,1 Ni = • матрица времен выполнения каждого из заданий на всех машинах ),....,,....,,( 21 k N k i kkk ttttt = , ;,...,1 Kk = • kθ — наиболее ранние допустимые сроки начала выполнения работ на k -й машине; • || k ij k aA = , Nji ,...,1,0, = — матрицы времен потерь времени на пе- реналадки при переходе k -й машины от выполнения одного задания к дру- гому. На пересечении i -й строки и j -го столбца этих матриц стоят потери времени на переналадки k -й машины при переходе после выполнения i -го задания к j -му. В 0 -й строке каждой матрицы kA заданы времена настрой- ки машины из состояния, в котором находится в момент начала выполнения расписания работ, в режим выполнения i -го задания. Элементы 0 -го столбца определяют затраты времени на переход k -й машины после завер- шения выполнения j -го задания в режим простоя (или возвращения маши- ны из j -го пункта на базу). Необходимо найти распределение всего множества заданий по маши- нам, а также определить последовательности всех назначенных на каждой машине заданий, обеспечивающие выполнение всех ограничений на установ- ленные сроки их выполнения ,iT и минимизировать время завершения всего комплекса работ (критерий оптимальности 1F ). В качестве другого критерия оптимальности 2F может быть выбрано минимальное средневзвешенное время работы машин, необходимое для вы- полнения всего комплекса работ. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ. СВОЙСТВА ДОПУСТИМЫХ И ОПТИМАЛЬНЫХ РАСПИСАНИЙ Построим матрицы || k ij k bB = , Nji ,...,1,0, = ; Kk ,...,1= суммарных затрат времени на выполнение заданий на каждой машине, учитывающие времена выполнения заданий, плюс потери времени на переналадки. Элементы этой матрицы определяются по формулам Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 90 k ij k j k ij atb += , Nji ,...,1,0, = ; .,...,1 Kk = (1) Определим также k ij Nj k i bb ≤≤ = 0 min, min , Ni ,...,1,0= , .,...,1 Kk = (2) Построим вспомогательную матрицу || ijβ=Β , ,,...,1,0, Nji = элемен- ты которой определяются согласно выражению k ijKkij b ≤≤ = 1 minβ , .,...,1,0, Nji = (3) С учетом времен пусконаладочных работ и (или) переналадок каждое i -е из заданий на k -й машине не может быть завершено ранее чем за время min,k ib , не ранее чем через промежуток времени k ijb после завершения вы- полнения задания, стоящего в последовательности перед ним, а на любой из всего множества машин — за время ijβ . Найдем минимальное значение элементов каждого столбца матрицы || ijβ=Β ijNij ββ ≤≤ = 0 min min , .,...,1,0 Nj = (4) Упорядочим все множество выполняемых заданий },...,,...,2,1{~ NiI = в порядке невозрастания граничных сроков их завершения }.....|,...,,{~ 21211 NiiiN TTTiiiU ≤≤≤= (5) Введем булевые переменные k ix : 1=k ix , если i -е задание выполняется на k -й машине, и 0=k ix — в противном случае. Так как каждое из заданий может выполняться только на одной машине, то справедливо ограничение 1 1 =∑ = K k k ix , .,...,1 Ni = (6) Пусть определено подмножество заданий, выполняемых на k -й маши- не — },...,,{~ 21 k N kkk iiiJ = . Рассмотрим последовательность выполнения этих заданий в порядке невозрастания граничных времен их завершения: }....|,...,,{~ 21 211 k N kk jjj k N kkk TTTjjjU ≤≤≤= (7) Утверждение 1. Если не выполняется хотя бы одно из неравенств сис- темы k r k l j r l j k T≤+∑ =1 minβθ , k N kk jjjr ;...,, 21= , (8) то не существует допустимых расписаний выполнения данного комплекса на k -й машине. Доказательство аналогичного утверждения приведено в [1, 13]. Разбиение на подмножества и построение допустимых и оптимальных… Системні дослідження та інформаційні технології, 2012, № 2 91 Если определены подмножества kJ~ и построены последовательности kU1 ~ для всех машин, Kk ,...,1= , то справедливо утверждение 2. Утверждение 2. Если хотя бы для одного из индексов Kk ,...,1= не выполняется хотя бы одно из неравенств системы (8), то для данного рас- пределения заданий по рабочим станциям kJ~ , Kk ,...,1= не существует до- пустимых расписаний выполнения всех заданий в установленные ограниче- ниями сроки. Сформулируем задачу распределения заданий по рабочим станциям (машинам) и выполнения их на каждой из машин в последовательности не- возрастания граничных сроков их завершения (последовательности (5)) в виде следующей задачи булевого линейного программирования ⎩ ⎨ ⎧ = 1 0k ilx , Nl ,...,1= , ,,...,1 Kk = (9) 1 1 =∑ = K k k il x , ,,...,1 Nl = (10) lll i r l k ii k Tx ≤+∑ =1 minβθ , Nr ,...,1= , ,,...,1 Kk = (11) lll i r l k i k i k Txb ≤+∑ =1 min,θ Nr ,...,1= , .,...,1 Kk = (12) Утверждение 3. Если не выполняется система неравенств (9)–(11) или (9), (10), (12), то система ограничений задачи является несовместной. Утверждение 4. Время завершения выполнения всех заданий на рабо- чих станциях не может быть меньше значения η , которое определяется в результате решения следующей задачи булевого линейного программиро- вания ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ =≤−+∑ = Kkx N l k ii k ll ,...,1,0|min 1 1 min ηβθη (13) в условиях ограничений (9)–(11) или задачи },...,1,0|min{ 1 1 min, 1 Kkxb N l k i k i k ll =≤−+∑ = ηθη (14) в условиях ограничений (9), (10), (12). Так как min,min k ii ll b≤β для всех Nl ,...,1= , ,,...,1 Kk = то система огра- ничений (9), (10), (12) является более жесткой, чем система ограничений (9)–(11), и не все значения переменных, удовлетворяющие системе ограни- чений (9)–(11), обеспечат выполнение условий (9), (10), (12). Поэтому для значений ,η определяемым в результате решения задачи (9)–(11), (13) и значения ,1η определяемого из условий (9), (10), (12), (14), справедливо соотношение .1 ηη ≥ Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 92 Пусть на некотором шаге решения задачи определены подмножества +,~ kI и частичные последовательности выполнения заданий на каждой ма- шине },,,{~ 21 k m kkk k jjjV …= , каждая из которых включает km , Kk ,...,1= за- даний. Здесь , 1 Nmm K k k <=∑ = где k mj 1 — последнее задание, выполняемое на k -й машине в построенной подпоследовательности .~ kV Пусть mNP −= , ∪ K k kII 1 ,~~ = ++ = — подмножество всех включенных во все подпоследовательности заданий. Вычислим для каждой из машин вре- мена завершения, выполняемых в этих частичных последовательностях за- даний: )( 1 1 k i m l k ii kk l k ll ta ++= ∑ = − θθ , .,...,1 Kk = (15) Обозначим },...,,{ˆ 21 PJ γγγ= — подмножество не включенных в час- тичные последовательности и подлежащих выполнению заданий. Упорядо- чим эти задания в последовательность по невозрастанию граничных значе- ний времен их завершения }....|,...,,{ˆ 1121 PvvvP TTTvvvV ≤≤≤=− (16) Преобразуем матрицы kB следующим образом: • вычеркнем 0 -й столбец, а также строки, соответствующие индексам заданий, входящих в подмножество заданий ;~ +I • удалим в каждой из матриц kB строки, соответствующие индексам заданий, принадлежащим подмножеству k mjIkI 1 /~)(~ ++ = . Назовем такое преобразование матриц kB преобразованием 1. Вновь образованные прямоугольные матрицы меньших размеров обо- значим || k ij k dD = , .,...,1 Kk = Найдем k ij Vj k i dd −∈ = ˆ min, min , −∈Vi ˆ , .,...,1 Kk = (17) На основе этих вновь образованных матриц построим матрицу || ijdD = , элементы которой определяются по формулам: k ijKkij dd ≤≤ = 1 min , }0{ˆ ∪∈ −Vi , .ˆ −∈Vj (18) Определим ij Jj i d ˆ min min ∈ =β , }.0{ˆ ∪∈ −Vi (19) Следствием утверждений 3 и 4 является утверждение 5. Разбиение на подмножества и построение допустимых и оптимальных… Системні дослідження та інформаційні технології, 2012, № 2 93 Утверждение 5. Если не выполняется система неравенств ⎩ ⎨ ⎧ = 1 0k vl x , −∈Vvl ˆ , ,,...,1 Kk = (20) 1 1 =∑ = K k k vl x , ,ˆ −∈Vvl (21) lll v p l k vv k Tx ≤+∑ =1 minβθ , −∈Vvl ˆ , Pp ,...,1= , ,,...,1 Kk = (22) где значения kθ определяются по формулам (15), а величины min lvβ — в соответствии с выражениями (19), или система неравенств (20), (21), (23): lll v p l k v k v k Txd ≤+∑ =1 min,θ , −∈Vvl ˆ , Pp ,...,1= , ,,...,1 Kk = (23) где значения min,k vl d вычисляются по формулам (17), то при выбранном рас- пределении заданий по рабочим станциям и выполнении их на каждой ма- шине в последовательности kV~ , Kk ,...,1= не существует допустимых рас- писаний, обеспечивающих выполнение всего оставшегося подмножества заданий Ĵ в установленные ограничениями задачи сроки. Утверждение 6. Если построены частичные последовательности вы- полнения некотoрого подмножества заданий kV~ на машинах ,,...,1 Kk = определены сроки завершения выполнения этих заданий на каждой из ма- шин ,kθ и необходимо распределить по машинам и построить на них рас- писание выполнения оставшегося подмножества заданий ,ˆ −V то время за- вершения расписания выполнения всех заданий на этих машинах не может быть меньше величины ςς ≥1 , определяемых соответственно в результате решения следующих задач линейного булевого программирования: ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ =∈≤−+ − = ∑ KkVvTx lv P l k vv k lll ,...,1,ˆ,|min 1 min ςβθς (24) в условиях ограничений (20)–(22) или ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ =∈≤−+ − = ∑ KkVvTxd lv P l k v k v k lll ,...,1,ˆ,|min 1 1 min, 1 ςθς (25) в условиях ограничений (20), (21), (23). Следовательно, результаты решения задач (9)–(11) (или (9), (10), (12)) и (20)–(22) (или (20), (21), (23)) являются соответственно необходимыми, но не достаточными условиями возможности выполнения всей системы огра- ничений как на начальном этапе решения, так и этапе решения, когда сфор- мированы некоторые частичные подпоследовательности выполнения непе- ресекающихся подмножеств заданий на каждой машине. Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 94 Результаты решения задач (9)–(11), (13) (или (9), (10), (12), (14)) и (20)– (22), (24) (или (20), (21), (23), (25)) позволяют вычислить нижнюю границу длины оптимального расписания в решении. Решение сформулированных оценочных задач булевого линейного программирования при больших размерностях K и N может потребовать значительных объемов вычислений. Поэтому в качестве грубой оценки воз- можности выполнения всей системы ограничений на различных этапах ре- шения могут рассматриваться результаты решения задач (9)–(11) (или (9), (10), (12)) и (20)–(22) (или (20), (21), (23)) не для всего множества перемен- ных ( N — на начальном этапе или mNP −= — в процессе решения), а для некоторой части подлежащих выполнению заданий, стоящих в левой части соответственно последовательностей I~ и Ĵ , т.е. для количества заданий NM < или PP <1 ). Для вычисления более грубой, но требующей существенно меньшего объема вычислений оценки, нижней границы функции цели 1F можно вос- пользоваться алгоритмом. Вычислим , 1 min∑ = = P l vl E β ,max 1max k Kk k θθ ≤≤ = ,max kk k θθ −=∆ ;,...,1 Kk = . 1 1 ∑ = ∆−= K k kEE (26) Тогда K E F k 1 max1)( += θξ . (27) Здесь ⋅ — целая часть частного от деления. Пусть 10 ≤≤ kλ , Kk ,...,1= , 1 1 =∑ = K k kλ — весовые коэффициенты, оп- ределяющие степень важности резерва свободного времени машин. Утверждение 6. Минимальное средневзвешенное время работы машин, необходимое для выполнения всего комплекса работ, как на начальном эта- пе решения, так и этапе решения, когда сформированы некоторые частич- ные подпоследовательности выполнения непересекающихся подмножеств заданий на каждой машине, не может быть меньше значения min)( 1 min,min, 1 2 → ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ += ∑∑ == N l k i k i k K k k ll xbF θλξ (28) в условиях ограничений (9)–(11) или (9), (10), (12), либо определяется в ре- зультате решения задачи min)( 1 1 min, 2 → ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ += ∑ ∑ = = K k P l k v k v k ll xdF θξ (29) в условиях ограничений (20)–(22) или (20), (21), (23). Разбиение на подмножества и построение допустимых и оптимальных… Системні дослідження та інформаційні технології, 2012, № 2 95 Следовательно, значение )( 2Fξ является нижней границей второго критерия оптимальности на различных этапах решения. Для вычисления грубой оценки нижней границы функции цели )( 21 Fξ можно воспользоваться выражениями ∑ = = N i iF 1 min 21 )( βξ или .)( ˆ ,1 min 1 21 ∑∑ ∈ == += P Jv l v K k k l l F βθξ (30) Пусть k ij Vj dkj −∈ = minarg),( * , (31) т.е. ),( ** kj — пара индексов Jj ˆ∈ , ,,...,1 Kk = на которых достигается ij Jj i d ˆ min min ∈ =β . Обозначим )(ki s , Kk ,...,1= — номера заданий, выполняемых в строя- щихся последовательностях на каждой машине последними. Вычислим )}.,()ˆ,ˆ(|minminmin{argarg)ˆ,ˆ( ** ),(ˆ1ˆ min kjkjdkj k jkiVjKkJj i s ≠== −∈≤≤∈ δ (32) Ясно, что если в строящемся расписании выполнения заданий будет выбрана не пара индексов ),( ** kj , а некоторая другая пара, то суммарное время выпонения всех оставшихся невыполненных заданий на всех маши- нах будет увеличено не менее чем на величину min )( min )()( kikiki sss βδ −=∆ . Сле- довательно, значение )( 21 Fξ увеличиться не менее чем на величину )(kis∆ , а значение )( 11 Fξ — не менее чем на величину K kis )( ∆ , где . — целая часть частного от деления этих величин. Найдем =−== −∈ )(minargarg),,( min )( min )(ˆ min )( *** kikiViki ssskji βδδ ]minminmin)}ˆ,ˆ(|minminmin[{min ),(ˆ1ˆ)(),(ˆ1ˆ)(ˆ k jkiVjKkJki k jkiVjKkJkiVi ssss dkjd −−− ∈≤≤∈∈≤≤∈∈ −= . (33) Выбор на данном шаге алгоритма для включения в строящиеся после- довательности выполнения заданий соответствующего элемента ),,( *** kji (т.е. выполнение задания *j на машине )*k обеспечит уменьшение границы функции цели задачи на минимальную величину. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ Сформулированные оптимизационные задачи относятся к классу NP- полных задач. Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 96 Ниже рассматриваются алгоритмы решения задачи последовательными алгоритмами оптимизации: методом «ветвей и границ» [1, 12] и методом последовательного анализа и отсева неперспективных вариантов [2]. Рассматриваемые ниже методы строят на каждой машине альтернатив- ные допустимые подпоследовательности заданий в порядке их выполнения. Каждое из заданий может и должно входить только в одну из строящихся последовательностей, выполняемых на одной какой-либо машине. На каж- дом этапе решения задачи эти подпоследовательности расширяются путем включения для какой-то одной из машин нового задания. При этом рассчи- тываются времена начала и завершения выполнения этого задания и на ос- новании утверждения 3 проверяется допустимость выполнения всех ограни- чений для этих построенных подпоследовательностей. Если установка выбираемого задания на данной машине на соответствующее место в после- довательности является недопустимым, то выбирается следующее альтерна- тивное задание для этой или другой машины. В противном случае на осно- вании утверждений 4, 5 вычисляется нижняя оценка времени выполнения расписания. В методе ветвей и границ на каждом шаге алгоритма выбирает- ся для развития множество подпоследовательностей с наименьшей нижней границей (оценкой), а в методе последовательного анализа вариантов — конструируются и рассматриваются все допустимые множества построен- ных подпоследовательностей с заданным количеством заданий. Если соот- ветствующее множество подпоследовательностей выполняемых заданий на всех машинах является недопустимым, то значение нижней оценки полага- ется равным ∞ . В методе ветвей и границ факт несовместимости системы ограничений задачи устанавливается в случае, если для всех вершин дерева значение нижней границы равно ,∞ а факт получения оптимального реше- ния (если построены последовательности выполнения всех заданий на всех машинах с временем завершения) не большим чем значения оценок всех множеств не построенных до конца подпоследовательностей. Ниже приводится формальное описание алгоритмов решения задачи. Упорядочим множество подлежащих выполнению заданий I~ в после- довательность 1 ~U , т.е. в порядке возрастания граничных времен их завер- шения в соответствии с выражением (5). Вычислим значения величин k ijb , min,k ib и ijβ по формулам (1)–(2). Сформулируем и решим систему нера- венств (9), (10), (12) относительно булевых переменных .k il x Если данная система неравенств несовместима, то не существует расписаний, обеспечи- вающих выполнение всей системы ограничений задачи, и алгоритм с этим сообщением заканчивает свою работу. Заметим, что, если сформулирован- ная задача большого размера и требует значительных объемов у вычисле- ний, то она может быть решена для части последовательности, содержащей NN <1 членов. Решение этой задачи даст более грубую оценку совместнос- ти ограничений, так как учитывает только первые 1N членов последова- тельности 1 ~U . Если получено решение системы линейных неравенств, то может быть вычислена либо грубая оценка минимальной длины расписания выполнения заданий по формулам (26), (27), либо более точная как резуль- Разбиение на подмножества и построение допустимых и оптимальных… Системні дослідження та інформаційні технології, 2012, № 2 97 тат решения задачи (9), (10), (12), (14). Менее точное значение нижней гра- ницы средневзвешенного времени работы машин вычисляется по формуле (30), а более точная оценка определяется в результате решения задачи (9), (10), (12), (28). ВЫЧИСЛИТЕЛЬНАЯ СХЕМА МЕТОДА ВЕТВЕЙ И ГРАНИЦ Каждая метка s -й вершины дерева состоит из следующих компонент: sq1 — номер вершины дерева; sq2 — признак того, целесообразно ли дальнейшее развитие данной вершины дерева )1( 2 =sq или нет );0( 2 =sq ss Fq =3 — зна- чение нижней границы функции цели для данной вершины дерева; sq4 — признак того, получено допустимое решение задачи )1( 4 =sq или нет );0( 4 = sq )1(5 ss iq = , )(,),(,),2( 446 Kiqkiqiq ss K ss k ss === ++ …… — номера заданий, выполняемых в строящихся последовательностях на каждой маши- не последними; || sk i s gG = — матрица размерностью K строк и N столб- цов, элементами которой является место, которое занимает задание i в по- следовательности выполнения его на машине .k Если для вершины s еще не установлены, что задание i выполняется на k -й машине то 0=sk ig . Ес- ли назначено, что это задание выполняется на какой-то другой машине, то соответствующий элемент матрицы равен «–1»; ,skθ Kk ,...,1= — вектор допустимых времен начала выполнения на k -й машине следующего задания. Пусть S — количество вершин дерева на данном этапе решения. Если выполнены все описанные в начале данного раздела вычисления и не уста- новлен факт несовместности исходной системы ограничений, то выполняем начальный предварительный шаг. Шаг 0. Формируем метку корневой вершины дерева 1=s следующим образом: ;11 =sq ;12 = sq 04 =sq ; 04 =+ s kq , ;,...,1 Kk = 0=s kig , ,,...,1 Kk = .,...,1 Ni = Значения skθ полагаем равными ksk θθ = , .,...,1 Kk = Значение ss Fq =3 определяем в виде грубой или точной оценки (по ре- зультатам решения задачи булевого линейного программирования) и в зави- симости от выбранного критерия оптимальности sF1( или )2 sF . Алгоритм решения задачи состоит из некоторого количества итераций, на каждой из которых в определенной логической последовательности вы- полняются следующие шаги. Шаг 1. Среди меток вершин дерева, для которых 12 =sq , 04 =sq , выби- раем метку с наименьшим значением sq3 , т.е. метку с номером ,γ для кото- рой }0,1|min{ 42313 === ≤≤ sss Ss qqqg γ . Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 98 Если таких не существует, то переходим к шагу 2. В противном случае переходим к шагу 3. Шаг 2. Находим среди меток дерева, для которых ,14 = sq метку с но- мером ρ , для которой }1,0|min{ 42313 === ≤≤ sss Ss qqqg ρ . Если таких меток не существует, то переходим к шагу 5. В противном случае метка дерева с но- мером ρ является оптимальным решением и переходим к шагу 5. Шаг 3. • Определим из матрицы γG подмножества заданий ,ˆ ,, +kI γ выбран- ных в γ -м частичном плане для выполнения на каждой машине (т.е. номера столбцов в каждой k -й строке матрицы γG метки с номером ,γ элемент которых 0>k ig γ ). Пусть количество таких элементов в каждой строке соот- ветственно равно .khγ Найдем номера заданий, стоящих в подпоследова- тельностях и выполняемых последними (т.е. }|),({ kk i hgki γγγ = ). Опреде- лим также множество всех выполненных на различных машинах заданий .ˆˆ 1 ,,, ∪ K k kII = ++ = γγ • В каждой матрице k ij k bB = , Kk ,...,1= вычеркиваем все столбцы подмножества ,ˆ ,+∈ γIj а также все строки ),(/ˆ , kiIi γγ +∈ (т.е. все строки, соответствующие индексам выполненных на всех машинах заданий, кроме задания, выполненного на данной машине последним). • Выполним преобразование 1 вновь полученных матриц kB и по- строение матриц .kD • Определяем значения min,k vl d , ijd и min lvβ по формулам (17)–(19). 4) Определяем грубую или точную оценку возможности выполнения системы ограничений задачи в результате решения системы линейных нера- венств с булевыми переменными (20), (21), (23) размерностью P или .1 PP < Если система неравенств несовместна, то подмножество не содер- жит допустимых планов. Полагаем 02 =γq , ∞=γF и переходим к шагу 1. Если получено решение системы неравенств, то вычисляем грубую (по формулам (30)) или точную оценку функции цели задачи (в результате ре- шения задачи булевого линейного программирования (20), (21), (23) с кри- терием оптимальности (28) или (29)). По результатам решения одной из оптимизационных задач коррек- тируем для γ -й метки вершины дерева значение оценки функции цели (признак )3 γγ Fq = и переходим к шагу 4. Шаг 4 (разбиение на подмножества). Для метки с номером γ , выпол- нив вычисления (31)–(33), находим элемент ),,,( *** kji т.е. номер машины *k и номер задания ,*j которое должно быть выбрано на этой машине Разбиение на подмножества и построение допустимых и оптимальных… Системні дослідження та інформаційні технології, 2012, № 2 99 и установлено на следующее место последовательности после выполненно- го на этой же машине задания γγ *4 ** )( k qkii + == . Формируем )1( +S -ю вершину дерева, признаки которой определяют- ся следующим образом: ,11 1 +=+ Sq S ,11 2 =+Sq ,1 3 γFq S =+ ,4 1 4 γ k S k qq + + + = Kk ,...,1= , ;*kk ≠ ;*1 4 jq S k =+ + ,,,1 k i kS i qq γ=+ ,,...,1 Ni = Kk ,...,1= , *kk ≠ ; ** ,,1 k i kS i gg γ=+ , ,,...,1 Ni = ;*ji ≠ );1( ** ,,1 +=+ k i kS i gg γ kkS ,,1 γθθ =+ , Kk ,...,1= , *kk ≠ ; * *),*( ** ,,1 kkkS jki b+=+ γθθ . Формируем )2( +S -ю вершину дерева, признаки которой определяют- ся следующим образом: 22 1 +=+ Sq S , ,12 2 =+Sq K Fq kiS )( 1 2 3 *∆ +=+ γ (или )(2 2 3 *ki S Fq ∆+=+ γ ); γ k S k qq + + + = 4 2 4 , Kk ,...,1= ; k i kS i gg ,,2 γ=+ , Ni ,...,1= , Kk ,...,1= , *kk ≠ ; , ** ,,1 k i kS i gg γ=+ Ni ,...,1= , *ji ≠ ; 1 *,1 −=+ kS ig ; kkS ,,2 γθθ =+ , .,...,1 Kk = В метке вершины γ изменяем только один признак, полагая .02 =γq Полагаем SS =+ :)2( и переходим к шагу 1. Шаг 5. Восстанавливаем оптимальные расписания выполнения заданий на каждой машине и рассчитываем времена начала и завершения выполне- ния каждого из этих заданий, а также соответствующие потери времени на переналадки. Формируем матрицу последовательностей выполнения зада- ний W~ на каждой машине, включающую K строк и N столбцов, а также трехмерный массив времен выполнения заданий k ljT τ= , размерностью Kk ,...,1= , 4,...,1=l , .,...,1 Nj = В первой строке каждой двухмерной мат- рицы kT указываются: k j1τ — время начала настройки k -й машины для выполнения задания ;j k j2τ , k j3τ — соответственно времена начала и за- вершения на k -й машине выполнения задания .j Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2012, № 2 100 В начале процесса полагаем, что все члены этой матрицы последова- тельностей равными 0 — 0=k iw , ,,...,1 Kk = .,...,1 Ni = Все элементы трехмерной матрицы T положим также равными 0. Введем также некото- рое вспомогательный вектор ,kH компоненты которого в начале процесса положим равными .kkH θ= Введем также вектор )( kππ = . В начале процесса положим 0=kπ , .,...,1 Kk = Для каждой k -й строки матрицы γG выполняем следующий объем вычислений. Для Ni ,...,1= выполним: если ,kk ig πγ > полагаем .k i k g γπ = После завершения этой процедуры значения kπ определят количество заданий, выполняемых в оптимальном расписании на каждой машине. Полагаем 1=kλ . Пусть K — текущий номер задания, соответствую- щего предыдущему члену последовательности. Значение kω в начале про- цесса полагаем равным нулю. Переходим к пункту (а). а) Среди элементов вектора kGγ находим элемент kkg λγ µ = µ( -й эле- мент вектора). Полагаем kk i λω = . Полагаем kk H=µτ1 , kkk aωµµµ ττ += 12 , kkk tµµµ ττ += 23 . Полагаем ,kk µω = 13 += kkH µτ . Переходим к пункту (б). б) Полагаем 1+= kk λλ . Если 1+= kk πλ , то определены все характе- ристики оптимального расписания выполнения заданий, и алгоритм закан- чивает работу. В противном случае переходим к пункту (а). Заметим, что если поставлена задача построения допустимого расписа- ния выполнения заданий, то 2-й шаг алгоритма выглядит таким же образом. В качестве частных случаев рассматриваемой задачи в работе автора [14] предложены математические модели и более простые алгоритмы по- строения допустимых и оптимальных расписаний выполнения заданий на одной машине, требуещие существенно меньшего объема вычислений. ВЫВОД В работе предложены математические модели оптимального разбиения на непересекающиеся подмножества всего комплекса заданий, подлежащих выполнению на нескольких машинах, и построения оптимальных последо- вательностей их выполнения на каждой из машин. Сформулированная зада- ча решается в условиях учета потерь времени на переналадки или потери времени при переходе от выполнения одного задания к другому, а также с учетом заданных ограничений на начальные и конечные сроки выполне- ния каждого из заданий и относится к классу NP-сложных задач. На основе установленных в работе свойств допустимых и оптимальных решений пред- ложены эффективные точные и приближенные (в случае использования ле- восторонней схемы ветвления) алгоритмы решения последовательными ме- Разбиение на подмножества и построение допустимых и оптимальных… Системні дослідження та інформаційні технології, 2012, № 2 101 тодами оптимизации, которые уже на ранних этапах решения позволяют установить факт несовместности исходной системы ограничений и при не- большом объеме вычислений получить эффективное приближенное реше- ние. Полученные в работе результаты могут найти широкое применение в календарном планировании производства, организации технического об- служивания объектов, планировании параллельных вычислений и в маршру- тизации перевозок. ЛИТЕРАТУРА. 1. Танаев В.С., Шкурба В.С. Введение в теорию расписаний. — М.: Наука, 1975. — 256 с. 2. Танаев В.С., Ковалев М.Я., Шафранский Я.М. Теория расписаний. Групповые технологии. — Минск: ИТК НАН Беларуси, 1998. — 289 с. 3. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. — М.: Наука, 1975. — 360 с. 4. Курейчик В.М. Генетические алгоритмы: монография. — Таганрог: Изд. ТРТУ, 1998. — 242 с. 5. Батищев Д.И., Гудман Э.Д., Норенков И.П., Прилуцкий М.Х. Метод комбини- рования эвристик для решения комбинаторных задач упорядочения и рас- пределения ресурсов // Информационные технологии. — № 2. — 1997. — С. 29–32. 6. Pinedo M. Scheduling: Theory, Algorithms and Systems. — Berlin-Heidelberg: Springer-Verlag, 1999. — 671 р. 7. Brucker P. Scheduling algorithms. — Berlin: Springer-Verlag, 2007. — 371 р. 8. Blazewicz J., Domschke W., Pesch E. The job shop scheduling problem: Conven- tional and new solution techniques // European Journal of Operational Re- search. — 1996. — Vol. 93. — P. 1–33. 9. Herrmann J. Supply Chain Scheduling. Transaktionskostentheorie; Parallele Maschinen; Heuristik; Optimierungsmodelle. — Berlin-Heidelberg: Gabler Ver- lag, 2010. — 162 р. 10. Blazewicz J., Ecker K.H., Pesch E., Schmidt G., Weglarz J. Scheduling Computer and Manufacturing Processes. — Berlin-Heidelberg: Springer-Verlag, 2001. — 485 р. 11. Szelke E., Kerr R.M. Artificial Intelligence in Reactive Scheduling. — Chapman & Hall, London, 1995. — 164 р. 12. Зак Ю.А. Определение порядка выполнения независимых операций на парал- лельных машинах // Изв. АН СССР. Техническая кибернетика. — 1969. — № 2. — С. 15–20. 13. Зак Ю.А. Решение обобщенной задачи Джонсона с ограничениями на сроки выполнения заданий и времена работы машин. Ч.1. Точные методы решения // Проблемы управления. — 2010. — № 3. — С. 17–25; Ч.2. При- ближенные методы решения // Проблемы управления. — 2010. — № 4. — С. 12–19. 14. Зак Ю.А. Оптимизация планирования производства и раскроя бумажной про- дукции // Управляющие системы и машины. — 2010. — № 5. — С. 82–93. Поступила 07.10.2010

Схожі ресурси