Разработка метода прогнозирования и оценки расписаний в обслуживании систем поточного типа

• Автор: Сирдах Магди Дарвиш
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 149 с. : ил

Содержание
Введение .

Глава 1. Задачи календарного планирования, теории расписаний.

Проблемы и подходы к решению

1.1. Задачи теории расписаний и их классификация

1.2. Проблемы задач теории расписаний .

1.3. Методы решения задач теории расписаний .

1.4. Постановка задачи диссертационной работы

Глава 2. Разработка методов и средств прогнозирования решения

задач в обслуживании систем поточного типа

2.1. Аналитическая оценка количества обслуживающих приборов

при минимальной длине расписания
2.2. Аналитическая оценка времени выполнения работ при заданных количествах обслуживающих приборов различного типа.
2.3. Аналитическая оценка времени выполнения работ в задачах
конвейерного типа .
Выводы по главе 2 .
Глава 3. Алгоритмизация решения задач в обслуживании систем
поточного типа
3.1. Алгоритмы моделирования составления расписаний .
3.2. Программное обеспечение .
Выводы по главе 3
I лава 4. Результаты расчетов и статистические испытания моделей составления расписаний.
4.1. Примеры результатов расчетов.
4.2. Статистические испытания моделей составления расписаний
Выводы по диссертационной работе
Литература


Такое разбиение используется в алгоритме поочередного включения работ, при котором вес назначения моментов начала операций одной работы производятся последовательно, но чередуясь с назначениями моментов начала операций других работ. Так как существует п перестановок п работ, то, если ограничиться только алгоритмами, дающими компактные расписания, получим равно п однократных алгоритмов такого типа. Каждый из них приводит к единственному компактному расписанию, однако эти расписания не обязательно различны, в частности, если некоторые работы требуют разных комплектов машин. Второй способ разбиения {5да} заключается в том, что в выделяется т машин обозначаемых, к = ], . Иначе говоря, подмножество{? Первоначально имеется п операций разбитых на т подмножеств {? В процессе составления расписания некоторые подмножества могут становиться то пустыми, то непустыми и пополняться до тех пор, пока все подмножества не окажутся пустыми и составление расписания будет завершено. Выбирая операции из {$»} и назначая минимально возможные моменты начала выполнения операций (с учетом ограничений на последовательность выполнения операций и уже составленной части расписания), можно получить любые компактные расписания. Однако такой алгоритм не является диспетчеризацией, т. Это связано с тем, что программа воспроизводит физический процесс выполнения операций во времени в том смысле, что порядок назначений совпадает с порядком реального выполнения операций. Важное значение имеет понятие приоритета работы или операции. Приоритет - это числовая характеристика работы или операции, используемая при выборе из всех возможных. Например, в алгоритме последовательного включения работ должно существовать какое-то правило, определяющее порядок включения работ в расписание, и это правило удобно формулировать в терминах приоритетов: работы выбираю гея в порядке возрастания приписанных им числовых характеристик. Каждому из п способов назначения приоритетов работ будет в этом случае соответствовать один вполне определенный алгоритм указанного типа - алгоритм последовательного включения работ. Система приоритетов должна быть достаточно полной, чтобы две «конкурирующие» работы (операции) всегда имели различные приоритеты и был бы возможен однозначный выбор. В противном случае потребуется дополнительно ввести вторичные приоритеты на случай равенства основных. Например, в алгоритме поочередного включения работ в качестве первичного приоритета работы можно выбрать число входящих в нее операций. Поскольку числа операций некоторых работ могут совпадать, нужно задать вторичные приоритеты и из таких работ выбрать в первую очередь ту, которая имеет минимальный вторичный приоритет. Весьма общим методом задания приоритетов является получение их с помощью некоторого вероятностного правила с использованием различных распределений для различных наборов операций и работ. При таком подходе особое значение приобретает идея многократного составления расписания для одной и той же задачи. Это связано с тем, что случайность при вычислении приоритетов каждый раз будет приводить к другому расписанию. Поэтому термин диспетчеризация означает определенный тип алгоритма составления расписания, основанный на некоторых стохастических правилах назначения приоритетов. Предполагают [1, что цель - это получение плана длительностью не более /о. Вели для некоторого фиксированного значения Iо получен допустимый план обработки детали на станках, проводится новый расчет при меньшем значении /о и т. Процесс вычислений заканчивается, если для принятого значения /0 в реально возможное машинное время удается получить допустимый план. Итак, пусть величина /о задана. Длительность плана является функцией N переменных, т. Р, . Р«, g= 1,. М Если / < /о, то задача решена; если же / > /о, то реализованную последовательность $1, . ЛГ нужно изменять, причем изменять каждый элемент с тем большей вероятностью, чем величина / больше порогового значения /о. Поэтому на практике, определяя стратегию, исходят из реальных возможностей машинного времени и типа ЭВМ. Если среди деталей, образующих очередь перед станкомом, будет несколько деталей с одинаковым приоритетом (в соответствии с принятыми правилами Р9 .