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


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

Глава девятая. Принципы формирования расписаний в системах конвейерного типа. Подготовка плановых решении

9.1. Условия оптимального взаимодействия участков. Декомпозиция систем

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

Пусть множество допустимых значений переменных исходной задачи планирования не пусто, т. е. ограничения совместны. Рассмотрим лишь те из них, которыми связаны работы с номерами "1, k-1", "N, k-1", "1, k", "N, k". Можно утверждать

(9.1)

где Тk - полное время занятости k-го участка N работами; Δt0,k-1 ≥зk-1 - задержка начала выполнения работ на (k-1)-м участке при норме потерь времени зk-1, τ1,k-1 - продолжительность первой работы на (k-1)-м участке; τNk- продолжительность N-й работы на k-м участке; εNk≥0- задержка начала работы с номером "N, k" относительно момента окончания работы с номером "N, k-1" (рис. 9.1).

Время Тс оценивается здесь как


Любая из величин Тk (k = 1,...,М) есть скалярная

функция векторного аргумента, составляющими которого являются известные длительности работ по этапам (τsk) и простои (Δts-1,k), неизбежно возникающие в каналах из-за организационных неувязок и необходимости учета всех ограничений, входящих в систему gi(X)≤bi.

Рис. 9.1
Рис. 9.1

Существуют точные нижние границы inf Тk, и их можно было бы достичь, составляя оптимальные схемы загрузки каждого участка отдельно. В реальных условиях, когда планы участков взаимосвязаны, на результат решения задачи системного планирования начинают влиять расхождения хk = Тk-inf Tk и сверхнормативные потери zk-1=Δt0,k-1,-зk-1. Чтобы выяснить степень этого влияния, обратимся к задаче: найти xk, εNk, zk-1, доставляющие


при

(9.2)

Очевидно, равенства (9.2) являются повторением (9.1), и смысл представленной задачи (она относится к классу линейных) заключается в поиске возможностей свести решение проблемы организации взаимодействия участков к исследованию более частных задач оптимального планирования (например, к случаям М=1 или ku = 1 и т. п.). Анализ такой промежуточной задачи линейного программирования становится целесообразным, если удается избежать громоздких процедур решения (как это имеет место в данном случае).

Из выражения Тс следует, что всякое допустимое базисное решение системы (9.2), содержащее в числе свободных переменные x1, εNk (k = 2,...,M),будет и оптимальным. Но подобные решения могут быть получены далеко не всегда, поэтому необходимы дополнительные оценки свойств (9.2).

Теорема (19): среди оптимальных базисных решений системы (9.2) всегда найдется такое, которое содержит в числе свободных переменную х1, все переменные zk-1, и одновременно удовлетворяет требованиям xkεNk = 0, k = 2,...,M (xk может войти в базис только тогда, когда εNk является свободной, и наоборот).

Доказательство: пусть K есть множество номеров k, таких, что εNk является базисной переменной при k∈K (соответственно xk является свободной); пусть далее kε есть наибольший из номеров k∈K. В этой ситуации нетрудно указать те εNk которые заведомо относятся к числу свободных (они собраны под знаком


равенстве


Независимо от того, какие ещё хk, εNk (k<kε) являются свободными, а какие базисными, можно утверждать


где


Таким образом, выражение Tc, отвечающее рассматриваемому базисному решению, имеет вид


Все входящие в него свободные переменные имеют неотрицательные коэффициенты (признак оптимальности, см. п. 1.4). □

Из сказанного следует, что достижение минимума Тc всегда обеспечивается оптимальной организацией работ на участке 1 (x1≡0), хотя к остальным участкам подобное требование может не относиться (это зависит от величин Ωk-1, k = 2,...,M),

Оптимальные базисные решения систем (9.2) могут иметь структуру, отличную от той, которая указана в условиях теоремы (19). Чтобы убедиться в этом, достаточно перевести в разряд свободных переменные

хM, εNk k = 2,...,M) и положить xk-1zk-1=0 (k = 2,...,MЖ).

Такой переход означает решение задачи планирования "в обратном времени" без изменения результатов.

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

Предположим, что участок 1 имеет наименьшее количество технологических линий, т. е. L1<Lk (k = 2, ...,M), и на одну линию приходится, следовательно, наибольшее число работ. В этих условиях нетрудно указать способ построения системного плана, позволяющий определить верхнюю границу расписания, превышать которую не имеет смысла: произвольно взятому каналу I участка 1 ставится в соответствие (например," по признаку совпадения номеров) один канал k-го участка (2≤k≤M) рассматривается система, объединяющая только эти l-е каналы (всего можно образовать L1 таких систем). Если распределение работ по каналам участка 1 известно, вводится требование найти оптимальные планы проведения работ в каждой из указанных одноканальных систем с учетом исходных ограничений. В результате простого объединения этих планов возникает общий план, который не является искомым оптимальным и должен выступать лишь как предварительный.

Таким образом, удается перейти (по крайней мере на первых шагах) к анализу упрошенных задач составления расписаний, в которых легче учесть ограничения типа тех, которые упоминались в § 8.5. Основным недостатком здесь является неполная загрузка имеющихся каналов (на k-м участке остаются незанятыми Lk-L1 линий), и это приводит к необходимости дополнительных исследований.

Предположение о том, что L1<Lk (k = 2,...,M), не должно рассматриваться как слишком жесткое. Чтобы построить предварительный системный план при произвольном L1, достаточно найти участок m, для которого


положить число каналов первого участка равным Lm и решить задачу оптимального распределения работ на нем в новых условиях. Тем самым определится и оптимальный план m-го участка; он может быть зафиксирован и использован тогда, когда возникнет необходимость возвратиться к рассмотрению первого участка со всеми L1 каналами.

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

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





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


Диски от INNOBI.RU




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