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



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

1. Теория расписаний


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

Цель теории расписаний – изучить то общее, что характеризует такие задачи независимо от их конкретного содержания.

Формальная схема процесса упорядочения примерно такова.

Пусть: 1)  есть совокупность последствий при выполнении сначала задачи А, затем задачи В; 2)  есть совокупность последствий при выполнении сначала задачи В, а затем задачи А. Тогда, если  предпочтительнее, чем , то выбирается последовательность выполнения сначала задачи А, затем задачи В.

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

1.1. Математическая модель «идеального» упорядочения


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

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

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

Кроме этого предполагается следующее.

1. Подлежащие выполнению работы определены и известны полностью.

2. Однозначно определены устройства, выделяемые для выполнения заданных работ,  машины. Понятие «машина» будем употреблять в обобщенном смысле, включающем в себя совокупность людей, машин и вспомогательного оборудования, необходимых для выполнения операции.

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

Существует определенное различие между упорядочением и составлением расписания. Упорядочение подразумевает формирование очередности операций, выполняемых одной машиной, в то время как составление расписания означает задание последовательности действий нескольким машинам. Оба – термины-синонимы.

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

Каждая операция характеризуется следующим:

1) индексом принадлежности к определенной работе;

2) работы представляют собой строго упорядоченные последовательности операций;

3) каждая операция выполняется только одной машиной;

4) существует только по одной машине каждого типа;

5) отсутствуют прерывания операций;

6) интервалы выполнения последовательных операции одной и той же работы не пересекаются;

7) в каждый момент времени машина может выполнять не более одной операции.

В настоящее время описанная формализация применяется в большинстве исследований.

Необходимо четко представлять себе разницу между исходными и искомыми величинами задачи. Первые из них определяются спецификой решаемой задачи, которая может быть учтена в рамках теории «идеальных» расписаний, вторые являются результатом составления расписания. Чтобы подчеркнуть эту разницу, при обозначениях исходных величин используются строчные латинские буквы, а при обозначении искомых  прописные, например h, x, y, z и Н, X, Y, Z.

1.2. Исходные величины при составлении расписаний


Постановка задачи теории в расписании начинается с описания системы машин и множества работ.

Мы будем говорить о системе из m машин и считать, что каждая машина отождествляется соответствующим индексом 1, 2, ..., m.

Занумеруем работы числами от 1 до n.

Обозначим: ri  момент готовности, то есть момент поступления i-й работы в систему, ri есть минимально возможное время начала первой операции работы i (рис. 1);



di  плановый срок – это момент, к которому работа должна быть выполнена или директивное время окончания последней операции работы (рис. 1);

ai = di ri  допустимая длительность прохождения работы в системе.

Рис. 1. Искомые и исходные величины расписания

Фактически задаются две из трех величин ri, di, ai. Для каждой из работ они все считаются заданными.

Пусть работа i состоит из gi операций. Для каждой операции j работы i задается набор величин: (mi1, pi1), (mi2, pi2), ..., (mi2, pi2), где mij  номер машины, на которой выполняется операция j работы i; pij  длительность выполнения операции j работы i;  общая длительность всех операций работы i.

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

1.3. Искомые величины при составлении расписаний


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

Обозначим Wij  интервал времени между окончаниями (j1)-й и началом j-й операции работы i. Тогда общая длительность ожидания для работы i равна сумме длительностей ожидания всех ее операций: . Результатом составления расписания всегда является задание множества чисел Wij.

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

Искомыми величинами, являющимися функциями Wij, будут (рис. 1):

1) момент окончания работы

;

2) длительность прохождения работы в системе Fi (цикл обработки или производственный цикл)



;

3) разница между плановым сроком и моментом фактического окончания работы: временное смещение Li = Cidi = Fidi; запаздывание Тi = max(0, Li); опережение Ei = max(0, Li).

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

1.4. Критерии оценки расписаний


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

Регулярный критерий М является возрастающей функцией моментов окончания каждой из n работ: M = f (С1, С2, ..., Сn). Пусть M' = f (С1', С2', ..., Сn'), тогда если Ci C1' (i =1, 2, …, n) по крайней мере для одного i, то М > M',

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

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

Нетрудно представить себе случаи, когда более удобен тот или иной подход. Например, при ремонте станков расписание ремонтных работ для определённого типа станков должно составляться так, чтобы минимизировать число работ в системе, так как это, по-видимому, максимизирует число станков, доступных для работы на них. С другой стороны, в производстве стоимость запасов является, очевидно, более точным отражением затраченных на их изготовление средств, нежели просто их число.

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


1.5. Расписания и стоимость


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

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

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

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


1.6. Классификация задач теории расписаний


Задача теории расписаний считается заданной, если определены:

1) подлежащие выполнению работы и операции;

2) количество и типы машин, выполняющих операции;

3) порядок прохождения машин;

4) критерий оценки расписания.

При составлении любого расписания задан порядок выполнения операций для каждой работы.

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

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

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

Для классификации задач теории расписаний в дальнейшем используется запись А|В|C|Д.

А  характеризует процесс поступления работ. Для динамических задач А представляет собой функцию распределения времени между поступлениями. Для статических задач А соответствует числу одновременно поступивших работ, если по этому поводу ничего специально не оговорено. Если на месте А стоит n, то это означает произвольное, но конечное число работ в статическом случае.

В  характеризует число машин в системе. Если на месте В стоит m, то это означает произвольное число машин.

C  характеризует порядок выполнения работ машинами. Если на месте С находится F, то это соответствует конвейерной системе; если R  то случайной, если G  произвольной. Для системы из одной машины (m = 1) третий параметр не задается.

Д  характеризует критерий оценки расписания.

В качестве примера употребления указанных обозначений запишем задачу в виде n|2|F|Fmax; это означает, что требуется упорядочить n работ в конвейерной системе, состоящей из двух машин, чтобы минимизировать максимальную длительность прохождения работ. Общая задача теории расписаний запишется так: n|m|G|Fmax, то есть упорядочить n работ в произвольной системе из m машин так, чтобы минимизировать максимальную длительность прохождения работ.


Каталог: 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
обратиться к администрации

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