Методы случайного поиска в решении задач теории расписаний

Методы случайного поиска в решении задач теории расписаний

Сформулированы общие подходы, установлены свойства и параметры алгоритмов глобального случайного поиска, приемлемые для решения широкого класса задач теории расписаний в условиях ограничений на сроки выполнения заданий. General approaches are formulated, the properties and parameters of the algorith...

Full description

Saved in:
Bibliographic Details
Published in:Управляющие системы и машины
Date:2013
Main Author: Зак, Ю.А.
Format: Article
Language:Russian
Published: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2013
Subjects:
Новые методы в информатике
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/83163
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Методы случайного поиска в решении задач теории расписаний / Ю.А.. Зак // Управляющие системы и машины. — 2013. — № 3. — С. 21-29. — Бібліогр.: 6 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-83163
record_format dspace
spelling Зак, Ю.А.
2015-06-16T13:58:13Z
2015-06-16T13:58:13Z
2013
Методы случайного поиска в решении задач теории расписаний / Ю.А.. Зак // Управляющие системы и машины. — 2013. — № 3. — С. 21-29. — Бібліогр.: 6 назв. — рос.
0130-5395
https://nasplib.isofts.kiev.ua/handle/123456789/83163
519.8
Сформулированы общие подходы, установлены свойства и параметры алгоритмов глобального случайного поиска, приемлемые для решения широкого класса задач теории расписаний в условиях ограничений на сроки выполнения заданий.
General approaches are formulated, the properties and parameters of the algorithms of the global random search are established which are acceptable for solving a wide class of problems of the theory of schedule under conditions of the limits on assignments.
Сформульовано загальні підходи, встановлено властивості і параметри алгоритмів глобального випадкового пошуку, прийнятні для розв’язання широкого класу задач теорії розкладів за умов обмежень на терміни виконання завдань.
ru
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
Управляющие системы и машины
Новые методы в информатике
Методы случайного поиска в решении задач теории расписаний
Random Search Method in Solving Scheduling Problems
Методи випадкового пошуку в розв’язанні задач теорії розкладу
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 2013
language Russian
container_title Управляющие системы и машины
publisher Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
format Article
title_alt Random Search Method in Solving Scheduling Problems
Методи випадкового пошуку в розв’язанні задач теорії розкладу
description Сформулированы общие подходы, установлены свойства и параметры алгоритмов глобального случайного поиска, приемлемые для решения широкого класса задач теории расписаний в условиях ограничений на сроки выполнения заданий. General approaches are formulated, the properties and parameters of the algorithms of the global random search are established which are acceptable for solving a wide class of problems of the theory of schedule under conditions of the limits on assignments. Сформульовано загальні підходи, встановлено властивості і параметри алгоритмів глобального випадкового пошуку, прийнятні для розв’язання широкого класу задач теорії розкладів за умов обмежень на терміни виконання завдань.
issn 0130-5395
url https://nasplib.isofts.kiev.ua/handle/123456789/83163
citation_txt Методы случайного поиска в решении задач теории расписаний / Ю.А.. Зак // Управляющие системы и машины. — 2013. — № 3. — С. 21-29. — Бібліогр.: 6 назв. — рос.
work_keys_str_mv AT zakûa metodyslučainogopoiskavrešeniizadačteoriiraspisanii
AT zakûa randomsearchmethodinsolvingschedulingproblems
AT zakûa metodivipadkovogopošukuvrozvâzannízadačteoríírozkladu
first_indexed 2025-11-25T23:07:23Z
last_indexed 2025-11-25T23:07:23Z
_version_ 1850578069037776896
fulltext УСиМ, 2013, № 3 21 Новые методы в информатике УДК 519.8 Ю.А. Зак Методы случайного поиска в решении задач теории расписаний Сформулированы общие подходы, установлены свойства и параметры алгоритмов глобального случайного поиска, приемле- мые для решения широкого класса задач теории расписаний в условиях ограничений на сроки выполнения заданий. General approaches are formulated, the properties and parameters of the algorithms of the global random search are established which are acceptable for solving a wide class of problems of the theory of schedule under conditions of the limits on assignments. Сформульовано загальні підходи, встановлено властивості і параметри алгоритмів глобального випадкового пошуку, прийня- тні для розв’язання широкого класу задач теорії розкладів за умов обмежень на терміни виконання завдань. Введение. Характерной особенностью методов случайного поиска есть то, что на каждой ите- рации процесса выбор нового решения прово- дится не детерминированно, а в результате ре- ализации некоторого случайного процесса, при- чем выбираемая стратегия может зависеть от предыстории поиска [1]. Для большинства таких алгоритмов при до- статочно большом количестве реализаций слу- чайных значений вектора переменных в задаче доказана сходимость в окрестность точки ло- кального или глобального экстремума с веро- ятностью, равной единице, т.е.  *lim ε 1k k P X X     ,  *lim ( ) ( ) δ 1k k P F X F X     , (1) где  и  – любые наперед заданные неотрица- тельные числа; *X и )( *XF – соответственно значение вектора переменных и функции цели в точке экстремума; X k, F(X k), k = 1, 2, , K – последовательность векторов переменных и значений функции цели на различных итера- циях алгоритма. Данные методы могут применяться как при решении задач локальной оптимизации, так и при поиске глобального экстремума. Ключевые слова: разбиение на подмножества и упо- рядочение заданий, глобальный случайный поиск, опти- мальные расписания выполнения работ, ограничения на сроки выполнения заданий. В алгоритмах направленного случайного по- иска результаты вычислений, выполненных на предыдущих итерациях, используются для выбо- ра направлений дальнейших испытаний и изме- нений вектора оптимизируемых переменных. Алгоритмы локального случайного поиска [2] сводятся, по сути, к случайному перебору на каждом k-м шаге векторов X из некоторой окрестности X k – X  , проверке эффектив- ности каждого из этих векторов (пробного ша- га) {F(X) – F(X k)} и к выбору соответствующей реакции на исход эксперимента. Различные ал- горитмы данного класса отличаются друг от дру- га реализацией отдельных этапов выбора экс- периментальных точек и методами принятия решений. Наибольшее распространение сегод- ня получили монотонные алгоритмы случайно- го поиска, в которых переход к следующему зна- чению вектора переменных задачи происходит лишь в том случае, если F(X k +1) > F(X k) в задаче максимизации целевой функции или в случае, если F(X k +1) < F(X k) – в задаче минимизации. Решение задач теории расписаний, в самом общем случае, состоит из двух этапов. На пер- вом этапе решения проводится разбиение не- которого множества объектов с заданным на- бором характеристик на непересекающиеся под- множества, а на втором – упорядочение объек- тов каждого из сформированных подмножеств в соответствии с выбранным критерием опти- мальности и обеспечивающим выполнение за- данной системы ограничений. 22 УСиМ, 2013, № 3 В рассматриваемых задачах теории расписа- ний все граничные значения времени выполне- ния операций предполагаются целочисленными величинами. Не допускается прерывание работ в процессе их выполнения. Известно большое количество публикаций, в которых методы случайного поиска приме- няются для решения различных частных задач теории расписаний. Подробный обзор таких ме- тодов изложен в монографиях [3, 4]. Цель ста- тьи – формирование некоторых общих подхо- дов и установление общих свойств и парамет- ров алгоритмов, приемлемых для решения ши- рокого класса задач теории расписаний. Пред- ложенные алгоритмы иллюстрируются при по- строении алгоритмов решения этими методами классических задач разбиения на подмноже- ства и упорядочения: синхронизация работы конвейерных линий и минимизация суммы штрафов при построении допустимых распи- саний на одной машине. Общая вычислительная схема методов глобального случайного поиска После выполнения каждой большой итера- ции глобального случайного поиска сохраня- ется одно допустимое расписание выполнения заданий и соответствующее ему значение кри- терия оптимальности, наилучшее среди всех построенных на предыдущих итерациях гене- рирования расписаний. Опишем итерацию алгоритма глобального случайного поиска применительно к решению задачи теории расписаний. Необходимо осуще- ствить разбиение некоторого подмножества, со- стоящего из N объектов, на m непересекаю- щихся подмножеств и затем упорядочить эле- менты каждого из образованных подмножеств. Пусть },...,,...,,{~ 21 Nl iiiiJ  – множество всех N объектов, упорядоченных по возрастанию их индексов. Каждый шаг итерации состоит из двух по- следовательных этапов:  разбиение случайным образом всех N объ- ектов на m непересекающихся подмножеств, соответствующих подмножествам заданий, вы- полняемых на различных машинах;  упорядочение случайным образом элемен- тов каждого из этих подмножеств, т.е. постро- ение допустимых последовательностей выпол- нения этих заданий на различных машинах. Пусть на каком-то s-м шаге s = 1, , N ма- лой итерации первого этапа построены: ,s kJ   1 2, ,...,sk sk sk rj j j , k = 1, , m – подмножества заданий, назначенных для выполнения на k-й машине; },...,{ )(1 sn s iiI  – подмножество зада- ний, еще не включенных ни в одно из подмно- жеств ksJ , ,          m k kss JII 1 ,/ . Элементы в под- множестве sI упорядочены в последователь- ность sI~ по возрастанию их индексов. Выполнение второго этапа начинается, ко- гда сформированы все подмножества элемен- тов mII ,...,1 , каждое из которых включает со- ответственно N1,  , N m членов, причем NN m j j  1 , II m j j    1 , lj II  , , 1,..., ;j l m j l  . (2) Пусть на каком-то g-м шаге малой итерации второго этапа уже сформированы m подпосле- довательностей },...,,{~ 21 gk N gkgkkg gkiiiV  . Каждая из них содержит соответственно gkN ( kgk NN  ) членов. В каждом из подмножеств 1,..., ,...g gkI I ..., gmI еще осталось ,gk k gkn N N  не вклю- ченных в эти последовательности элементов, каждый из которых стоит на определенном мес- те в последовательности gkU~ 1 2{ , ,..., },gk gk gk gk n u u u k = 1, , m. Пусть m (g)  m – количество после- довательностей, для которых справедливо со- отношение N k > N gk. При отсутствии ограничений на сроки завер- шения выполнения заданий на каждой боль- шой итерации первого этапа выполняем сле- дующий объем вычислений. Алгоритм 1. 1) Реализуем случайное число, распределенное по некоторому закону распре- деления s 1 на интервале чисел ],0[ξ1 ms  . Оп- ределим значение УСиМ, 2013, № 3 23 1 1 1 1 1 1 1 , если 0,5, μ ( 1), если 0,5. s s s s s s s             (3) 2) Реализуем случайное число, распределен- ное по некоторому закону распределения на интервале чисел )](,0[2 sns  , где k – номер шага на первом этапе итерации алгоритма, а n(s) определяет число элементов в последова- тельности sI~ , до настоящего момента еще не отнесенных к какому-либо из подмножеств. Вычислим значение 2 2 2 2 2 2 2 , если 0,5, ( 1), если 0,5. s s s s s s s              (4) 3) Определим элемент, стоящий на s 2 -м мес- те последовательности .sI Пусть это будет эле- мент )( 2 si  . Включим этот элемент в подмно- жество, номер которого равен s 1 , и исключим его из подмножества sI и из последовательно- сти sI~ , уменьшив тем самым количество чле- нов этой последовательности на единицу. В зависимости от количества членов, включен- ных на данном этапе в каждое из подмножеств, скорректируем закон распределения случай- ных чисел s 1 . Если sI~ , т.е. 0)( sn , то возвращаемся к выполнению пп. 1–3. В про- тивном случае переходим к выполнению вы- числений второго этапа. Объем вычислений на втором этапе каждой большой итерации заключается в следующем. 4) Реализуем случайное число, распределен- ное по равномерному закону распределения g 2 на интервале чисел )](,0[3 gmg  . Вычис- лим значение 3 3 3 3 3 3 3 , если 0,5, ( 1), если 0,5, g g g g g g g              (5) которое определяет номер подпоследовательно- сти k, на последнее место в которой будет ус- тановлен выбираемый в дальнейшем элемент. 5) Реализуем случайное число, распределен- ное по некоторому закону распределения на ин- тервале чисел ],0[4 gkg n . Вычислим значение 4 4 4 3 4 4 4 , если 0,5, ( 1), если 0,5. g g g gk g g g              (6) Это число определяет элемент, стоящий в последовательности gkU~ на соответствующем месте. Пусть это будет элемент )( 3 gki  . Устано- вим этот элемент на последнее место в под- последовательности gkV~ и исключим его из gkU~ . Скорректируем значения 1,1  gkkg NN , 11,  lttl nn . Если 0,1  kgn , то полагаем 1)()1(  gmgm . Если 0)1( gm , то боль- шая итерация алгоритма заканчивает работу. В противном случае – переходим к выполнению пп. 4, 5. Если в результате выполненной большой ите- рации получено допустимое расписание SGP~ и )()~( min PFPF SG  , то полагаем )(min PF ( )SGF P и переходим к следующей большой итерации случайного поиска. При наличии ограничений на сроки заверше- ния выполнения заданий Ti, i = 1, , N, объем вычислений на каждой большой итерации ал- горитма увеличивается. Упорядочим все зада- ния  NI ,...,1 , а также подмножества заданий  ll NI ,...,1 , l = 1, , m, выполняемых на каж- дой машине по возрастанию значений Ti:  1 21 2, ,...., | ... NN i i iW i i i T T T    ,  1 2 1 2 , ,..., | ( ) ( ) ... ( ) N N l l l l l l l i i i i i iW i i i T i T i T i    , (7) l = 1, , m . Упорядочим подмножества заданий ksJ , в последовательность (7) в порядке возрастания значений )( sk piT – , 1 2 1, ,..., | ( )s k sk sk sk sk rV v v v T v  )(...)( 2 sk r sk vTvT  . Пусть )(min, sk p k vt – мини- мальное суммарное время, необходимое для переналадки и выполнения li -го задания на k-й машине, k = 1, , m. Автором показано [3], что если выполняется хотя бы одно из системы неравенств )()( ,, 1 min ks p ks l p l k vTvt    , 24 УСиМ, 2013, № 3 1,...,p r , mk ,...,1 , (8) то на k-й машине не может быть построено расписание выполнения заданий, удовлетворя- ющее всем ограничениям задачи. Пусть на k-й машине построена некоторая подпоследовательность выполнения заданий },...,,{~ 21 gk N gkgkkg gkiiiV  . }~{ kgVT – время заверше- ния выполнения этой подпоследовательности заданий kgV~ на k-й машине. Пусть на следую- щее место в этой последовательности (после задания gk N gki ) устанавливается задание  gk Ni 1 )( 3 gki  и время выполнения этого задания с учетом потерь времени на переналадку k-й ма- шины составляет )( 1 gk Nit  . Если )()(}~{ 11 gk N gk N kg iTitVT   , k = 1, , m, (9) то задание gk N gki не может быть установлено на данное место, а следовательно, и на любое дру- гое более дальнее место последовательности выполнения заданий на k-й машине. Следовательно, строящаяся последователь- ность выполнения заданий на данной машине недопустима. Поэтому на каждом g-м шаге ма- лой итерации второго этапа выбор заданий для установки на )1( gkN -е место в последователь- ности kgV~ может выбираться только из не- которого подмножества gkgk UW ~~  , где  gkgk p gk p gkgkgk p gk npuTutVTUuW ,...,1),()(}~{,~~  , k = 1, , m. (10) Рассмотрим также некоторую другую мо- дификацию описанного алгоритма. Алгоритм 2. Пусть на некотором s-м шаге формирования допустимого расписания выпол- нения N заданий на m машинах построены до- пустимые подпоследовательности 1 2{ , ,...ks ks ksV i i ..., }ks ks N i выполнения некоторого подмножества заданий ksI на каждой машине. Обозначим }~{ kgVT – время завершения выполнения этой подпоследовательности заданий ksV~ на k -й ма- шине, k = 1, , m. Пусть sJ – подмножество за- даний, не включенных ни в одну из последова- тельностей ksV~ . Определим и упорядочим по возрастанию значений Ti подмножество зада- ний 1{ ,ks ksj  1 2 ..., | ... }ks ks ks n ks n j j j j T T T   , кото- рые без нарушения сроков завершения их вы- полнения могут быть установлены на (N ks + 1)- е место в ksV~ . Пусть ksn – количество элемен- тов подмножества ks . Следовательно, ks l ksksks j ks l ks l ks N ks TjtjiaVT  )(),(}~{ , ksks nj  . Определим }|,...,,{ 21   ksssss kkkM – под- множество машин, упорядоченное по возрас- танию индексов этих машин, последователь- ность выполнения заданий на которых может быть продолжена, количество таких машин рав- но mms 1 . Если ks , 1,...,k m и при этом sJ , то построено допустимое расписание выполнения заданий. Если при этом )~( sPF )~(PFopt , то полагаем )~()~( s opt PFPF  . Если  ks , k = 1, , m и при этом sJ , то на данной итерации не может быть построено до- пустимое расписание выполнения заданий. Как в первом, так и во втором случае переходим к следующей большой итерации случайного поис- ка, положив s = 0, },...,,...,1{ mkIJ s  , mms 1 ; 0ks N ksi , kksVT }~{ , k = 1, , m и определив соответствующим образом множества ks . Ес- ли 11  sm и ks , sMk  , то – на каждом s-м шаге большой итерации ал- горитма реализуем случайное число ],0[ 11 ss m , с помощью которого определяем номер маши- ны, последовательность выполнения заданий на которой ksV~ должна быть продолжена; – реализуем случайное число ],0[2 kss n , на основании которого выбираем номер задания ksks lj  , которое устанавливается на (N ks + 1)- е место в последовательности ks ; – полагаем )1(:  ss , корректируем под- множества ksV~ , ks , sM , значения }~{ ksVT , sm1 и переходим к выполнению п. 1 большой ите- рации алгоритма. УСиМ, 2013, № 3 25 Если в процессе выполнения достаточно большого количества итераций S   алго- ритма не получено ни одного допустимого ре- шения задачи, то на основании этого делается заключение, что система ограничений задачи несовместна. В противном случае наилучшее из полученных решений opt ( )F P принимается в ка- честве оптимального решения задачи. Синхронизация работы сборочных конвей- еров Пусть последовательность технологических операций сборки задана некоторым графом. Вер- шины графа i = 1, , n определяют технологи- ческие операции, длительность которых равна ti, где ti – целые числа, а дуги определяют по- следовательность их выполнения. Рассматриваемая задача заключается в раз- биении всего множества выполняемых опера- ций I~ на m )( nm  непересекающихся подмно- жеств mIII ~,...,~,~ 21 (здесь m – количество рабо- чих станций) таким образом, что II m k k ~~ 1    , pk II ~~  , mpk ,...,1,  , (11) а также в определении последовательности вы- полнения операций на каждом рабочем посту и порядка расстановки рабочих постов, обеспе- чивающих допустимую последовательность вы- полнения операций сборки и экстремальное значение некоторого критерия оптимальности. В качестве критерия оптимальности рассмот- рим минимизацию времени такта или цикла сборки (максимальной производительности) при заданном количестве рабочих станций. Время такта сборки , т.е. промежуток вре- мени между завершением сборки r-го и (r + 1)-го изделия или обратная ему величина – произво- дительность сборочного конвейера (количест- во изделий, выпущенных линией за время T), определяется максимальной длительностью вы- полнения всех технологических операций на наиболее напряженном рабочем посту конвей- ерной линии     kIi imk t ~1 max , (12) где  – время транспортировки собираемого из делия с одного поста на другой; (k =k+1 = , k = 1, , m – 1), kI~ – подмножество операций вы- полняемых на k-м сборочном посту. Для исследования свойств оптимальных ре- шений и описания алгоритмов решения задачи введем следующие обозначения: U~ – множество всех дуг графа; )(iA (непо- средственно после i) – множество всех дуг Ij ~ , для которых Uji ~),(  ; )(iB (непосред- ственно перед i) – множество всех дуг Ij ~ , для которых Uij ~),(  , }~),(|~{)( UjiIjiA  , }~),(|~{)( UijIjiB  . (13) Определим также следующие показатели: )(iA – множество операций, которые могут выполняться только после завершения опера- ции i; )(iB – множество операций, которые долж- ны быть выполнены перед началом операции i. Нижняя граница величины такта работы кон- вейерной линии определяется выражением            ini n i i tt m 11 max;1max)( . (14) Здесь и в дальнейшем || – целая часть част- ного от деления двух величин. Пусть на некотором этапе решения опреде- лено назначение и последовательность выпол- нения подмножества II ~~1  – операция на пер- вых m1 < m рабочих станциях, т.е. определены подмножества операций kI~ , 1,...,1 mk  и вы- числено значение     kIi imk tIT ~1 1 1 max)~( . (15) Необходимо распределить оставшееся под- множество 12 ~/~ˆ III  операций на последую- щих m2, k = m1 + 1, m1 + 2, , m = m1 + m2 рабо- чих постах. В данном случае нижняя граница величины такта работы конвейерной линии оп- ределяется по формуле             )~(;max;1max)~|( 1 ˆˆ2 1 2 2 ITtt m I i IiIi i . (16) 26 УСиМ, 2013, № 3 Рассматривается алгоритм решения задачи методами глобального случайного поиска, ис- пользующими установленные формулами (14)– (16) оценки. Алгоритм решения состоит из некоторого ко- личества p = 1, , P больших итераций, в каж- дой из которых S (s = 1, , S) шагов. Введем следующие обозначения: s = 1, , S – номер шага итеративного про- цесса; 1 ,sI sI 2ˆ – соответственно множество опера- ций, выполнение которых на s-м шаге назна- чено и не назначено ни на одной из рабочих станций; s kI~ – множество операций, выполнение ко- торых на s-м шаге итеративного процесса на- значено на k-й рабочей станции; ss IU 2ˆ~  – множество операций на s-м шаге, не имеющих предшественников,  2ˆ | ( )s sU i I B i   ; (17)    s kIi i s k tT ~ , 1,...,1 mk  – суммарное время выполнения всех операций на k-й рабочей стан- ции на s-м шаге алгоритма;    s kIi i s k tI ~ 1)~|( – свободный ресурс времени k-й рабочей станции на s-м шаге ите- ративного процесса; k(s) – номер рабочей станции, рассматри- ваемой на s-м шаге итеративного процесса. s kU 1 – подмножество операций, выполнение которых на s-м шаге может быть назначено на k-й рабочей станции }|~{1 s ki ss k tUiU  . (18) Пусть  (P1) – наилучшее из допустимых ре- шений, полученных в результате выполнения P1  P больших итераций. В начале выполнения каждой p-й большой итерации положим 1s , },...,1{~ˆ2 nII ss  ; s kI~ , s k , mk ,...,1 ; 1)( sk , })(|~{~  iBIiU s . (19) Значение  (P1) =  и вычисляем по формуле (12). Ш а г 1. 1) Для рабочей станции k(s) опре- деляем в соответствии с выражениями (17) и (18) подмножества операций sU~ и s kU 1 . Пусть )( 11 s k s k Um  – количество элементов в множе- стве s kU 1 . 2) Разобьем весь диапазон изменения D  [0; 1,0] на s km 1 равномерных интервалов, длиной 11/ s km каждый. Упорядочим все элементы под- множества s kU 1 , например, в последовательность s kV 1 ~ по возрастанию величин tj. Реализуем слу- чайное число, равномерно распределенное в диапазоне d  [0; 1,0]. Выбираем j-й элемент последовательности s kV 1 ~ в соответствии с тем, в какой из рассматриваемых интервалов попало это случайное число. Для выбранной операции s kUj 1 , время вы- полнения которой равно tj, определяем }/ˆ{ˆ 22 jII ss  , }~{~ 11 jII ss  , j s k s k tTT  , j s k s k t . (20) Определяем подмножество s kU 1 в соответ- ствии с выражением (18). Если s kU 1 , вновь выполняем шаг 1. В противном случае перехо- дим к шагу 2. Ш а г 2. Полагаем 1:  ss , : 1k k  , а также 1: 11  mm , 1: 22  mm , вычислим зна- чение )~|( 1I по формуле (16). В дальнейшем выполняем следующий объем вычислений: 1) Если s = S, если )()~|( 1 1 PI  , то полага- ем )~|()( 1 1 IP  . Запоминаем все подмноже- ства операций )(~ 1PI s k msk ,...,1,  и соответству- ющие им последовательности выполнения на каждой машине )( 1PW s k , удовлетворяющие ус- ловиям технологической последовательности выполнения операций. Определяем P1 := P1 + 1. Если    )( 1P либо PP 1 , (21) где  – установленная точность решения зада- чи, то алгоритм завершает работу. Множества УСиМ, 2013, № 3 27 )(~ 1PI s k и последовательности )( 1PW s k и есть решение задачи. Если одно из условий (21) не выполняется, то, приняв значения всех вели- чин согласно выражению (19), вновь перехо- дим к выполнению шага 1. 2) Если Ss  , то переходим к шагу 1. Автором выполнен вычислительный экспе- римент, в процессе которого решались задачи размерностью n = 100 – 250 операций и m = 8 – 25 рабочих станций. Матрица смежности графа по- следовательности технологических операций со- держала 15–20 процентов единиц. Время вы- полнения технологических операций в диапа- зоне ti  [3, 10] выбиралось случайным образом. Было решено более 70 задач, исходные данные которых выбирались случайным образом. В ре- зультате выполненного вычислительного экс- перимента установлено, что за количество боль- ших итераций, равное P  300, как правило, по- лучено решение, значение критерия оптималь- ности которого отличалось от нижней границы функции цели, вычисленной по формуле (12), не более чем на 8–13,5 процентов. В работах автора [3, 5] приведены алгорит- мы получения точных решений этой задачи по- следовательными алгоритмами оптимизации. Минимизация суммы штрафов, связанных со сроками завершения выполнения зада- ний на одной машине Пусть заданы время начала выполнения i, а также время выполнения ti и произвольные нелинейные функции штрафов, связанных со сроками завершения выполнения каждого из заданий fi (Ti), i = 1, , n . Если определена некоторая последовательность выполнения заданий  nii uuuuuU ...,,,...,,, 121  , то время выполнения задания iu определяется по фор- муле   iiii tTT   ,1max 1 , ni ,...,1 . (22) В качестве примеров функций fi (Ti) могут встречаться нелинейные функции вида )()( iiii TTf  , 0, если , ( ) ( ) если , i i i i i i i i T B f T T T B      1 1 1 2 , 0, если , , если , ( ) ...... , если , i i i i i i i i ri r i i T B c B T B f T c B T         (23) где i (Ti) – произвольные нелинейные функ- ции, которые могут быть недифференцируемы- ми и разрывными. На сроки выполнения неко- торых заданий могут быть наложены ограни- чения вида Ti  bi. Необходимо найти последо- вательность выполнения заданий, минимизи- рующую сумму штрафов .min)()( 1   i n i i TfUF (24) В случае нелинейных функций штрафов не существует простого решающего правила, при- веденного например в [3, 4, 6], позволяющего построить оптимальную последовательность вы- полнения заданий за полиномиальное время, и рассматриваемая задача относится к классу NP-полных задач. Для ее решения могут быть использованы описанные методы глобального случайного поиска. Алгоритм решения состоит из некоторого ко- личества p = 1, , P больших итераций, каждая из которых состоит из S (s = 1, , S) шагов. Пусть F (P1) – наилучшее из допустимых ре- шений, полученных в результате выполнения P1  P больших итераций. Введем следующие обозначения: s = 1, , S – номер шага итеративного про- цесса; 1 ,sI sI 2ˆ – соответственно множество за- даний, выполнение которых на s-м шаге на- значено и не назначено на данной машине; sU 1 – последовательность выполнения заданий подмножества sI 1~ ; Ts–1 – время завершения всех операций подмножества sI 1~ в последователь- ности их выполнения sU 1 ; sR – наиболее ран- нее время начала выполнения операций подмно- жества 2ˆ ,sI которое вычисляется по формуле 21 ˆ max 1, max s s s i i I R T         ; (25)    sIi ii s TfIF 1~ 1 )()~( – сумма штрафов, связанная 28 УСиМ, 2013, № 3 с завершением подмножества операций sIi 1~ в рассчитанные сроки Ti. Упорядочим все задания sIi 2ˆ в последова- тельность sU 2 по невозрастанию значений bi   2 2 1 2 1 ˆ, ,..., ,..., | , 1,... ; ( ) ( ) . s s s s s s s p R p s s r r U u u u u u I r R b u b u     (26) Если выполняется хотя бы одно из системы неравенств [3] 1( ) max ( ) 1, ( ) ( ) ( )s s s s s r r r p rT u T u u t u b u       , Rr ,...,1 , (27) где ss RuT )( 0 ,      1 1 1 )()( r l s l ss r utRuT , R – ко- личество элементов в последовательности 2 ,sU то подпоследовательность выполнения зада- ний sU 1 не имеет допустимых решений и мо- жет быть отброшена как неперспективная. В начале выполнения каждой p-й большой итерации положим F(P1) = , а также 1s , },...,1{~ˆ2 nII s  ;  ss UI 11~ , 0)~( 1 sIF . (28) Ш а г 1. Определим по формулам (26) по- следовательность sU 2 и проверим выполнение неравенств (27). Если хотя бы для одного зна- чения индекса r = 1, , R не выполняется нера- венство (27), то sU 1 не имеет допустимых ре- шений. Если s = 1 и p = 1, то система ограниче- ний несовместна и алгоритм с соответствую- щим сообщением завершает работу. Если s > 1, то устанавливаем (28), p := (p + 1). Если p = P, то в случае F(P1) < , алгоритм заканчивает ра- боту, и последовательность )( 1PU – решение задачи, а F(P1)– соответствующее этому реше- нию значение критерия оптимальности. В слу- чае если F(P1) <= , то алгоритм завершает ра- боту с сообщением, что допустимых решений не получено. Если p =< P и s > 1, то переходим ко второму шагу алгоритма. Ш а г 2. Определим   ii s Ii s l tRt s   ,maxmin 1~ ,  2 2ˆ ˆ | 1 0s s s i lJ i I t      , ss IJ 22 ˆˆ  . (29) Если sJ 2ˆ , то построим последователь- ность заданий   2 2 1 2 1 ˆ, ,..., ,..., | , 1,..., ; ( ) ( ) , s s s s s s s l L l s s l l V v v v v u J L L R b v b v      (30) где L – количество элементов в множестве sJ 2ˆ и последовательности sV 2 . Разобьем весь диапазон изменения D  [0; 1,0] на L интервалов, длина каждого из кото- рых dl пропорциональна величине )(1 s lvb , т.е. чем меньше граничное время завершения за- дания, тем длина интервала больше. Реализуем случайное число равномерно распределенное в диапазоне D  [0; 1,0]. Выбираем тот k-й эле- мент последовательности в соответствии с тем, в какой из рассматриваемых интервалов попа- ло это случайное число. Пусть это будет задание с индексом s k Ji 2ˆ . Переходим к шагу 3. Ш а г 3. Полагаем k ss iII 11 ~~  , k ss iII /ˆˆ 22  . Включаем элемент ik последним членом строя- щейся последовательности 1 .sU Вычисляем зна- чения   1,max  kkk ii s i tRT  , )()~()~( 11,1 kk ii ss TfIFIF  . (31) Полагаем s := (s + 1). Если s := S + 1, т.е. II s ~~1  и sI 2ˆ , то полагаем F(p) )~()~( 1,1 sS IFIF  . Если F(P) < F(P1), то определяем F(P1) = F(p) и запоминаем последовательность 1 ,sU т.е. U (P1)= 1 1S sU U  . Полагаем p := (p + 1). Если p = P и F(P1)  , то получено решение задачи, которое определяется расписанием вы- полнения заданий )( 1PU со значением крите- рия оптимальности F(P1). Если p = P и F(P1) = , то алгоритм заканчи- вает работу с сообщением, что допустимых ре- шений не получено. Если p < P, то полагаем 1:s , 1 1s sI U  , II s ~ˆ2  , 0)~( 1 sIF и переходим к первому шагу алгоритма. УСиМ, 2013, № 3 29 Заключение. Проведен вычислительный экс- перимент, в процессе которого решались задачи размерностью n = 20 – 25 заданий с нелинейны- ми разрывными функциями штрафов. Время вы- полнения заданий выбиралось случайным обра- зом и варьировалось в диапазоне ti  [5, 12]. Для 30–50 процентов заданий устанавливались гра- ничные сроки завершения их выполнения. Про- цесс решения включал 200–250 больших итера- ций. В процессе выполненных расчетов в боль- шинстве случаев факт несовместности системы ограничений устанавливался уже на первой большой итерации алгоритма в результате про- верки выполнения системы неравенств (27). На- илучшее решение, которое на 12–20 процентов хуже значения достаточно грубой нижней гра- ницы оптимального решения задачи, достига- лось уже на 120–140 большой итерации и в дальнейшем ходе вычислений не улучшалось. Отметим, что в монографии автора [3] приве- ден алгоритм решения этой задачи методом вет- вей и границ, который позволяет получить точ- ное решение задачи за экспоненциальное время. Разработанные методы иллюстрируются при построении алгоритмов решения различных классических задач разбиения на подмножества и упорядочения, имеющих прикладное значе- ние в проблемах календарного планирования производства, маршрутизации перевозок и ор- ганизации технического и сервисного обслу- живания объектов. Описанные методы глобального случайного поиска в сочетании с различными эвристиками и оценками нижних границ оптимального ре- шения могут успешно применяться и для реше- ния других задач теории расписаний: Job–Shop– Problem, Flow–Shop–Problem, построение распи- саний работы на параллельных машинах и др. Некоторые из этих алгоритмов описаны в [2, 3, 6]. 1. Жиглявский А.А., Жилинскас А.Г. Методы поиска гло- бального экстремума. – М.: Наука, 1991. – 205 c. 2. Растригин Л.А. Статистические методы поиска. – М.: Наука, 1968. – 376 с. 3. Зак Ю.А. Прикладные задачи теории расписаний и маршрутизации перевозок. – М.: Книжный дом «Либ- роком», 2012. – 393 c. 4. Domschke W., Scholl A., Voß S. Produktionsplanung. Ablauforganisatorische Aspekte. – Berlin, Heidelberg: Springer Verlag, 2005. – 456 р. 5. Зак Ю.А. Оптимальное распределение технологи- ческих операций на сборочном конвейере // Ки- бернетика. – 1990. – № 4. – С. 45–54. 6. Brücker P. Scheduling Algorithms. – Leipzig: Sprin- ger, 2007. – 371 р. Поступила 12.08.2012 Тел. для справок: +49 241 543-255 (Aachen, Deutschland) E-mail: yuriy_zack@hotmail.com Сайт: www.optimorum.de © Ю.А. Зак, 2013  << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E> /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e> /JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice

Similar Items