Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

Глава десятая. Методы оптимального распределения времени. Элементы машинного проектирования систем и процессов

10.1. Организация работ в многоканальной системе. Конечность алгоритма

Возможности практического применения и характеристики сходимости общего алгоритма (см. § 9.5) во многом определяются соответствующими показателями

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

Исследуемая в этом разделе задача представляет интерес по трем причинам: она является типичной задачей теории расписаний, к ней сводится вся проблема организации работ при M = 1, методы ее решения оказываются применимыми и для поиска Т*С(И) (см. § 9.4).

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

В дальнейшем достаточно рассматривать только линейные уравнения вида


в которых b и ai являются рациональными дробями. Приведя их к общему знаменателю, легко получить целочисленные b и аi (например, для n = 3 соотношения


и 66x1 + 70x2 + 14x3 = 21 эквивалентны).

Пусть имеются N работ, проводимых на участке, объединяющем L однотипных каналов. Каждый канал самостоятельно реализует все операции, предусмотренные технологией, поэтому любая работа может выполняться в любом канале, и время, необходимое для этого, известно. Требуется распределить N работ по L каналам так, чтобы полное время (Т) занятости участка этими работами было минимальным (предполагаем N>>L). На рис. 10.1 показан возможный вариант распределения работ. Здесь t0 - общее начало отсчета времени, τυl - продолжительность выполнения υ-й (по порядку) работы в l-м канале (1≤υ≤ni, 1≤l≤L); Δtυ-1,l - задержка начала υ-й работы относительно окончания (υ-1)-й работы, Δt0l - задержка начала забот в l-м канале относительно момента t0. Очевидно,


Время занятости канала с номером l(1≤l≤L) оценивается как


Оно отличается от среднего времени


причем всегда


Следовательно, нельзя ожидать значений T, меньших Tcp, и задача заключается в том, чтобы минимизировать отклонения Tl(l=1,...,L) от Тср (наилучшим из всех было бы решение, дающее Т = Тср). В этих условиях увеличение Тср является нежелательным, но оно может произойти из-за неудачного выбора Δtυ-1,l. Если Δtυ-1,l фиксированы заранее (например, учтены потери времени на подготовку очередных работ или запланированы какие-то вспомогательные операции), то их удобно включить в соответствующие τυl, изъяв формально из рассмотрения. Если же Δtυ-1,l выбираются произвольно, их лучше считать равными нулю с самого начала и не вводить в оценку Тср. Таким образом, в любом случае достаточно исследовать схему на рис. 10.2 с целью отыскания величины


Здесь оказывается удобным использовать понятие линейного диофантова уравнения, возможности практического применения которого связаны с задачами об отыскании способов разбиения положительного числа А на слагаемые с известными свойствами или составления отрезка заданной длины из меньших отрезков и т. п. (в последнем случае требуется выбрать из имеющихся N отрезков с длинами τj (j = 1,...., N), такие, которые точно составят величину В. Формально это приводит к анализу уравнения


при условии, что переменные yj могут принимать значения 0 или 1).

Рис. 10.1
Рис. 10.1

Рис. 10.2
Рис. 10.2

Диофантовы уравнения (и тем более системы таких уравнений) разрешимы далеко не всегда, но для линейного случая условия существования решений сформулированы в общем виде.

Предположим, что из каких-то соображений выбраны Тl>0 (l = 1,...,L). Можно ли указать вариант загрузки участка работами, отвечащий принятым Тl? Ответ на вопрос будет утвердительным, если существуют неотрицательные решения системы диофантовых уравнений

(10.1)

где τ1, τ2, ...,τN - известные длительности выполнения работ (в произвольной нумерации). Каждое соотношение


выражает требование точно составить из комбинаций "отрезков" τj величину Тl (после чего вводятся обозначения τυl (рис. 10.2)). Ограничения на знак переменных хjl (j = 1,...,N; l = 1,...,L) вместе с условиями


исключает возможность использования одного и того же τ для составления разных Т; (каждая работа выполняется только один раз в одном из L каналов), что равносильно требованию


Основные трудности заключаются здесь в следующем:

- неясны принципы выбора величин T1, Т2, ..., ТL;

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

Первая трудность может быть частично устранена, если иметь в виду, что наилучшей (в смысле минимума Т) комбинацией значений T1, Т2, ....,TL является Тlср (l = 1,....,L) и ее нужно исследовать в первую очередь. Кроме того, всегда можно указать значения Тl (l = 1,...,L), при которых система (10.1) разрешима, но которые почти наверное не доставляют минимума Т.

Для этого достаточно упорядочить τj по признаку не убывания, определить наименьший номер j=р, отвечающий условию


(рис. 10.3), сравнить между собой разности


выбрать в качестве Т1 либо величину


(если первая разность меньше второй), либо


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


так что


Если расхождение между Тсp и найденным maxl Tl, окажется слишком большим, возникнет необходимость анализировать тысячи комбинаций Т1, Т2, ..., ТL многие из которых будут затем отброшены как ненужные. Чтобы избежать этого, достаточно использовать следующий простой прием: фиксируется величина


вычисляется разность


(на рис. 10.2 это было бы ТL-1-TL) и производится перераспределение работ между двумя каналами, позволяющее получить лучшее значение


Рис. 10.3
Рис. 10.3

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


По смыслу исходной задачи все τj и Тl есть рациональные числа. В формальном рассмотрении их можно считать целыми числами, меняющимися дискретно, причем такой же характер изменения должен иметь минимум Т. Это позволяет наметить пути перехода от одного (лучшего, но недостижимого) значения min Т к другому (сравнительно худшему) значению. Эти пути заключаются в последовательном анализе разрешимости диофантовых уравнений при тех Тl, которые соответствуют принятому min Т.

Обратимся к теореме (20): диофантово уравнение


с целочисленными ai и b имеет решения (положительные, отрицательные, нулевые), если наибольший общий делитель величин ai(i = 1, ...,n) делит b.

Использовать это утверждение применительно к (10.1) можно лишь в негативном смысле (из-за жестких ограничений в выборе yj, не учитываемых условиями теоремы). В результате станут известны Т1, Т2, ..., TL, заведомо непригодные для включения в систему (10.1), а допустимые Тl (l = 1,..., L) вместе с решениями уравнений будут определяться другими методами.

Рис. 10.4
Рис. 10.4

Пусть дано простейшее уравнение τ1y12y2=B. Очевидно, его решения в виде комбинаций нулей и единиц существуют тогда, когда выполнено хотя бы одно из условий: τ1 = B, τ2 = B, τ12 = B. В общем случае (N переменных) число подобных условий составляет


однако не все они представляют интерес.

Если упорядочить значения τj и найти соответственно наименьший и наибольший номера j = p, j = q, для которых



(рис. 10.4), то легко указать сочетания величин τо, подлежащие оценке (не имеет смысла рассматривать сочетания более чем из р-1 и менее чем из N-q+1 элементов, так как р самых коротких и N-q+1 самых длинных отрезков в сумме уже превысили B). Таким образом, количество сохраняемых условий уменьшается до


формирование связано с затратой значительных усилий, поэтому целесообразно ориентироваться сразу на все возможные значения B (вертикальные штриховые линии, рис. 10.4), классифицируя получаемые решения по признаку соответствия тем или иным B.

Если уравнение


решено при допустимых B, то тем самым указаны наборы величин τj, дающих в сумме эти 38. Очевидно, план работы участка составляется только из "не пересекающихся" (т. е. не содержащих одинаковые τj) наборов, что позволяет ввести дополнительную классификацию найденных решений и затем организовать на этой основе поочередную проверку следующих гипотез: minT = Тср, min Т = Тср+НОДτj, min T = Тср+2НОДτj, ... (число гипотез определяется наилучшим


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

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

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


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

Алгоритм решения рассмотренной задачи объединяет 6 основных этапов поиска min T. К ним относятся:

- оценка Тср и определение наибольшего общего делителя чисел τ1, τ2, ...,τN- НОДτj;

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


(см- рис. 10.3);

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


- определение нижней границы значений


как


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


которые делятся без остатка на НОДτj;

- решение диофантова уравнения


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

- выбор гипотезы:


2НОДτj,... и поиск соответствующих ей "не пересекающихся" наборов τj в зависимости от исхода поиска - конец процесса или переход к новой гипотезе.

Ниже дан пример применения предложенного метода.

Пример: четырехканальный производственный участок (L = 4) загружается семнадцатью работами (N = 17), продолжительность выполнения которых задана таблицей требуется найти оптимальный (в смысле min Т). вариант распределения работ на участке.


Решение: вычисляются


составляются



что дает р = 7; величина


сравнивается с


и фиксируется T1 = 399 (в первый канал идут первые 6 работ);

- составляются суммы τ7 + τ8 = 180 < 423, τ7 + τ8 + τ9 = 276 < 423,... из которых первой, превысившей Tcp, оказывается


сравниваются


принимается Т2 = 384 (во второй канал идут работы 7 - 10) и т. д.; в результате формируется следующий предварительный план загрузки участка:


где


- производится перераспределение работ между вторым и третьим каналами с целью уменьшить T3 (и соответственно увеличить Т2) примерно на 0,5 (T3-T2) = 45 единиц, что приводит к передаче в третий канал работ 90, 96 (взамен 111, 120) и получению нового (улучшенного) плана (54 60 60 72 75 78), (90 108 111 120), (90 96 120 123), (135 150 150), в котором разность


еще довольно велика; имеет смысл повторить операцию уточнения плана, передав в четвертый канал работы 60, 72 (взамен 150), и получить 54 60 75 78 150 90 108 111 120 90 96 120 123 60 72 135 150


для значения


определяется


и исследуется набор чисел 405,406, ...,429; из них на НОДτj = 3 делятся лишь 405, 408, 411, 414, 417, 420, 423, 426, 429 - возможные

- решается уравнение


сразу для всех найденных

поскольку





значения р. и q составят 7 и N-2, т. е. сочетания из 17 элементов по m должны рассматриваться при 3≤m≤6; их число есть ~22 000 и для их составления удобно использовать сводку сочетаний по 2 элемента; в результате заполняется таблица решений


- принимается гипотеза: min Т = Тср = 423; в рамках этой гипотезы достаточно анализировать лишь одну (седьмую) строку таблицы решений;

"не пересекающиеся" наборы τj здесь - либо (60 72 90 90 111), (120 120 108 75), (150 54 123 96) (150 78 135 60), либо (60 75 78 90 120), (150 54 111 108), (135 72 120 96), (150 60 123 90); они представляют собой два (из возможных оптимальных) решения исходной задачи планирования работ на участке.

Дальнейшее накопление сочетаний τj привело бы к получению всех оптимальных решений, но это представляло бы чисто академический интерес.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"