Управление технологическими процессами


Расписания для систем конвейерного типа



страница6/16
Дата10.05.2018
Размер1.04 Mb.
ТипКонспект
1   2   3   4   5   6   7   8   9   ...   16

1.8. Расписания для систем конвейерного типа


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

Этот факт устанавливается в теоремах 1 и 2.

Теорема 1. Если составляется расписание для системы n|m|F и все работы доступны одновременно, то оптимальное, с точки зрения минимума регулярного критерия, расписание принадлежит к классу расписаний, в которых одинаков порядок выполнения работ на первых двух машинах.

Доказательство. Если в расписании (рис. 5) порядок выполнения работ на первых двух машинах различен, то найдется такая пара работ I и J, что на первой машине I непосредственно предшествует J, а на второй I следует за J (причем между I и J возможны промежуточные работы).



Рис. 5. Порядок выполнения пары работ в расписании

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

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

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

Теорема 2. Если составляется расписание для системы n|m|F|Fmax и все работы доступны одновременно, то оптимум ищется среди расписаний, в которых сохраняется порядок выполнения работ на двух первых (1 и 2) и двух последних (m1 и m) машинах.

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

1.8.1. Минимизация максимальной длительности прохождения в конвейерной системе из двух машин (n|2|F|Fmax)


Обозначим Ai = pi1  длительность первой операции i-й работы; Bi = pi2  длительность второй операции i-й работы; Fi  длительность прохождения i-й работы. Каждая работа характеризуется парой (Ai, Bi), где Ai  часть работы, выполняемая первой машиной, а Bi  второй машиной.

Задача состоит в следующем. Заданы 2n величин A1, …, An, B1, …, Bn; нужно упорядочить работы так, чтобы при сделанных допущениях минимизировать максимальную из длительностей прохождения Fi.

Из теорем 1 и 2 следует, что нужно рассматривать только расписания с одинаковым порядком выполнения работ каждой машиной. Поэтому решение представляет собой просто оптимальную перестановку работ.

Очевидно, что можно ограничиться рассмотрением расписаний, в которых работы на первой машине « упакованы « плотно, начиная с первой из них, т. е. первая машина работает без простоев до завершения A[k].

Оптимальное расписание определяется теоремой.

Теорема 3. В системе n|2|F|Fmax при одновременной доступности всех работ упорядочение, минимизирующее максимальную длительность прохождения, таково, что работа j предшествует работе j+1, если min(Аj, Bj+1) < min(Aj+1, Bj).

Упорядочение в соответствии с теоремой 3 (рис. 6) приводит к единственному оптимальному расписанию, если для каждой пары работ имеет место строгое неравенство.

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



Рис. 6. Пример оптимального упорядочения


1.8.2. Конвейерная система из трех машин (n|3|F|Fmax)


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

Однако в ряде частных случаев такие решения имеются. Например, рассмотрим систему из трех машин, когда выполняются соотношения minAi  maxBi или minDi  maxBi, где Di  время выполнения i-й работы на третьей машине. Согласно этим предположениям все операции на второй машине по длительности меньше любой операции на первой или на третьей. Очередность, минимизирующая максимальную длительность прохождения, формируется таким образом, чтобы работа i размещалась впереди работы j, если min(Ai+Bi, Dj+Bj)Aj+Bj, Di+Bi).

Алгоритм остается тем же самым, что и для системы из двух машин с естественной разницей в том, что Ai заменяется на Ai+Bi, а Bi  на Bi+Di.

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

Одна частная задача для системы из трех машин следующая. Предполагается, что первой машиной выполняются все первые операции работ, третьей  третьи операции, а для каждой второй операции существует отдельная машина. Таким образом, имеются n+2 машины; n соответствуют одной второй машине (могущей одновременно выполнять n работ) в конвейерной системе из трех машин. Упорядочение, минимизирующее максимальную длительность прохождения, таково, что работа i предшествует j, если min(Ai+Bi, Dj+Bj)Aj+Bj, Di+Bi), где Ai, Bi, Di имеют прежний смысл.

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


1.8.3. Упорядочение в больших системах конвейерного типа


Рассмотрим случай системы 2|m|F|Fmax, состоящей из многих машин, выполняющих две работы. Такая постановка допускает наглядный графический метод решения. Предположим, что номера машин 1, 2, ..., m соответствуют порядку выполнения на них работ и пусть длительности работ будут p11, p12, …, p1m для работы 1; p21, p22, ..., p2m  для работы 2.

На рис. 7 эти длительности отложены на осях координат.



Рис. 7. Графическое представление расписания для системы 2|m|F|Fmax

Графически расписание может быть представлено ломаной линией, которая: 1) проходит от точки (0,0) до точки ); 2) состоит из отрезков горизонтальных (при выполнении только первой работы), вертикальных (при выполнении только второй работы) и проходящих под углом 45º (при одновременном выполнении обеих работ); 3) лежит целиком за пределами заштрихованных на рисунке областей, которые соответствуют одновременному выполнению работы обеими машинами.

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



Каталог: general information -> institutes -> engineering institute -> department of quot mechanical engineering quot -> educational-methodical-activity
educational-methodical-activity -> Конспект лекций Омск 2007 удк
educational-methodical-activity -> Математическое моделирование элементов конструкции и технологического процесса механической обработки детали на основе теории графов
educational-methodical-activity -> Конспект лекций ч. 1 Омск
general information -> Тесты для аспирантов (общие вопросы философии науки) Базовый уровень
general information -> Программа вступительного экзамена по специальности


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   16


База данных защищена авторским правом ©znate.ru 2019
обратиться к администрации

    Главная страница