8) CR = STR / OT (Critical Ratio) – критическое отношение. Отношение времени, оставшегося до сдачи работы ко времени выполнения работы. Чем меньше это отношение, тем приоритетнее работа.
9) QR (Queue Ratio) – коэффициент очередности, т.е. время остающееся по графику работы до сдачи деленное на время пребывания в очереди.
10) Random – в случайном порядке.
Выбор того или иного правила приоритетов производится по условию минимизации: а) общей продолжительности выполнения комплекса работ;
б) общего опоздания для этого же комплекса
FCFSприменяется в системах с равномерным потоком.
LCFS – используется редко, напр. когда срочные заказы должны быть пропущены вперед плановых.
SPT, LPT- если имеется большой разброс по времени выполнения между заказами.
SPT –если большинство заказов — с длительным сроком выполнения, но есть и с коротким.
LPT- если большинство заказов с небольшим временем исполнения
Кроме этих правил существуют: SPT/OP, LPT/OP, STR/OP. Эти правила учитывают не общее время выполнения работ, а среднее время на одну операцию.
Выбор правил приоритетов основывается на анализе поступающих в систему работ. Критерием выбора является суммарное время опоздания всех работ, которое должно быть минимизировано. Если суммарное опоздание в системе равно нулю, используется критерий минимального времени выполнения всего комплекса работ. Если какое-либо из правил приоритетов оказывается наиболее эффективным в подавляющем большинстве случаев, то в последующем его применяют без подтверждающих расчетов, пока производственная система остается стабильной.
26.Календарное планирование для нескольких рабочих центров.
Задача Джонсона, методы Кемпбела и Петрова-Соколицина.
Пусть поток работ проходит последовательно через несколько операционных узлов (например, станков). Условием эффективной загрузки этих узлов является минимизация суммарных простоев.
Рассмотрим простейший случай, когда имеются только два узла (станка).
Из условия минимизации простоя первого узла, следует располагать работы в порядке уменьшения продолжительности их выполнения на втором узле.
Из условия минимизации простоя второго узла, необходимо добиться роста продолжительности их выполнения на первом узле.
Для выполнения этих двух условий пользуются правилом Джонсона.
- из всей последовательности выбирается работа с наименьшим временем выполнения, не важно, на каком станке.
- если такая работа оказалась на первом станке, то ее ставят в начало последовательности, если на втором, то в конец.
- распределенную работу вычеркивают,
- снова запускается тот же алгоритм. Следующую распределяемую работу ставят
* либо в начало последовательности, но после уже распределенных в начало работ,
* либо в конец последовательности, но перед уже распределенными в конец работами.
Предположим, что станков больше двух.
Метод Кемпбела предполагает сведение задачи к задаче Джонсона, путем условного объединения станков.
Например, если имеется три станка, то возможны два варианта:
1. объединить 1 и 2 станок, 3- отдельно.
2. 1 станок отдельно, 2 и 3 объединить.
При применении правила Джонсона получатся два варианта последовательности запуска работ, из которых нужно выбрать вариант с минимальными простоями (или минимальным временем выполнения всей последовательности работ)
Понятно, что при увеличении количества станков, количество вариантов прогрессирующе возрастает, что усложняет использование метода.
Поэтому, для большого количества станков используют метод Петрова-Соколицына.
Данный метод является эвристическим. С его помощью в большинстве случаев (но не во всех) будет получена оптимальная последовательность работ.
Петров и Соколицын доказали, что оптимальная последовательность работ будет чаще всего наблюдаться в одном из трех случаев:
*в случае распределения работ в порядке возрастания суммы времени выполнения от первого до предпоследнего станка;
*в случае распределения работ в порядке убывания суммы времени выполнения от второго до последнего станка;
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.