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

Диаграммы Гантта.

Исходная информация для такой задачи может быть записана в следующей таблице (Таблица 1).

Таблица 1.

	Первый станок	Второй станок
Первая деталь
Вторая деталь
Третья деталь

 

Диаграмма Гантта для такой задачи, если порядок обработки деталей совпадает с указанным в Таблице 1, строится следующим образом (Рис. 1).

I

II

Рис. 1. Диаграмма Гантта для задачи Джонсона (Таблица 1).

 

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

5. Критерии оптимальности расписаний.

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

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

- минимизация времени обработки поступивших работ, заданий или операций на используемом оборудовании;

- минимизация времени запаздывания по срокам выполнения работ, заданий или операций;

- максимизация минимального коэффициента загрузки используемого оборудования.

Рассмотрим эти критерии более подробно.

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

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

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

 

* * *

 

Для определения такого расписания строится следующий функционал

,

где , а - временное смещение, которое определяется следующим образом

= - , .

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

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

,

где - моменты времени окончания выполнения работ 1, 2, …, соответственно. К регулярным критериям относятся два первых критерия из приведенных выше.

В последнем, третьем критерии требуется максимизировать минимальный коэффициент загрузки используемого оборудования.

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

Так для расписания, представленного на рис. 1 коэффициент загрузки первого станка будет равен 1, а коэффициент загрузки второго станка будет равен 50/85. Для расписания, представленного на рис. 2 коэффициент загрузки первого станка будет равен 1, а коэффициент загрузки второго станка будет равен 5/6. Для расписания, представленного на рис. 3 коэффициент загрузки первого станка будет равен 1, а коэффициент загрузки второго станка будет равен 50/55.

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

6. Алгоритмы построения расписаний обработки. Решающие правила. Построение комбинированных решающих правил.

Наиболее эффективным переходом для решения задач теории расписаний являются методы искусственного интеллекта.

Применение этих методов основано на использовании приоритетных правил, которые весьма похожи на продукционные правила.

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

 

 

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

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

Приоритетные правила условно можно разделить на два класса – простые и сложные.

К простым правилам относят правила с одним предусловием. Предусловия простых правил нельзя представить в виде совокупности некоторых предусловий.

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

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

Простые приоритетные правила.

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

2. Правило FCFS. Если первым пришел, то первым обслуживается.

3. Правило SPT – правило кратчайшей операции. Если время обработки детали на данной операции минимальное, то эта деталь обрабатывается в первую очередь.

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

4. Правило LPT – максимально длинной операции. Если время обработки детали на данной операции максимально, то эта деталь обрабатывается в первую очередь.

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

5. Правило LUKR – выбор работы, для которой длительность всех оставшихся операций минимальна, т. е.

Если длительность всех оставшихся операций обработки для детали минимальна, то данная деталь обрабатывается первой.

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

6. Правило MWKR – выбор детали, для которой длительность оставшихся операций максимальна.

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

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

7. Правило FOPNR – минимального числа оставшихся невыполненных операций. Если количество невыполненных операций по обработке детали минимально, то эта деталь обрабатывается первой.

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

Рис. 1. Процесс накопления деталей между станками

 

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

и .

Здесь - количество деталей, которое было обработано на первом станке за время и на втором станке за время . Тогда

.

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

, где .

Отсюда получаем

,

.

Время работы первого станка до отключения будет равно

,

а время повторного включения первого станка определяется из следующего условия

.

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

Рассмотрим теперь случай, когда .

В этом случае процесс накопления деталей между станками имеет такой же вид, что и представленный на рис. 2.1.4. Однако первый станок в этом случае работает все время, а второй начинает с момента времени и заканчивает в момент времени . Уравнение издержек имеет такой же вид

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

и , .

Тогда выражение для функции и ее производной принимают вид

,

.

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

Времена и в этом случае оказываются равными

17. Задача о «рождественской елке». #8 стр3

Уравнение издержек.

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

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

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

.

Таблица 3.2.1

Потребовалось запасных деталей							6 и более
Число генераторов, для которых потребовались детали
Эмпирическая вероятность выхода из строя указанного числа деталей.	0,90	0,05	0,02	0,01	0,01	0,01

 

Подсчитаем сначала численно ожидаемый суммарный расход при различных, но разумных уровнях запасов (т.е. от 0 до 5).

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

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

Это показывает, что оптимальный уровень запасов равен 2.

Рассмотрим аналитическое решение этой задачи.

Определим величину S, при которой ожидаемые суммарные доходы будут минимальными

.

Положим в этом уравнении , тогда

.

Но =1 или =1- .

Отсюда получаем

.

Точно также можно получить, что

.

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

.

Для любого целого , большего , и любого целого , меньшего , эти неравенства будут выполняться, поскольку при будет больше , а при будет меньше .

Поэтому при любом и при любом .

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

.

Если таково, что

,

то из уравнения для определения получим

.

Если же таково, что

,

то из уравнения для определения получим

.
20. Проблемы управления многопродуктовыми запасами. А, В, С анализ. №9-4

Задачи диспетчеризации

 

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

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

При обнаружении отклонений состояния системы или ее элементов от нормального состояния ситуация полагается аварийной.

Причинами таких отклонений могут быть:

- задержки в поставках заготовок к обрабатывающему оборудованию;

- поломки оборудования;

- задержки в поставках заготовок и комплектующих деталей, узлов и агрегатов к заданным срокам на производственный участок;

- задержки в поставках к заданным срокам инструментов и технологической оснастки;

- поломки инструментов и технологической оснастки;

- появление брака при обработке каких-либо партий деталей или сборке узлов, агрегатов или изделий;

- появление новых партий деталей и заказов в производственной программе предприятия;

- исключение некоторых партий деталей и заказов из производственной программы предприятия;

- необходимость изменения сроков готовности некоторых заказов на более ранние сроки.

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

Дальнейший ход работы системы в зависимости типа аварийной ситуации может протекать следующим образом:

● продолжение работы по намеченному плану, невзирая на сложившуюся аварийную ситуацию;

● переход в ожидание появления задержанных заготовок и повторная идентификация состояния оборудования производственной системы;

● выявление аварийного элемента, вывод его из эксплуатации и подача заявки на устранение неполадки в аварийную службу;

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

● пересчет плановых заданий в связи с появлением новых партий деталей и заказов в производственной программе предприятия;

● пересчет плановых заданий в связи с исключение некоторых партий деталей и заказов из производственной программы предприятия;

● пересчет плановых заданий в связи с изменением сроков готовности некоторых заказов на более ранние.

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

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

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

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

 

Диспетчеризация в производственных системах осуществляется на двух уровнях: внутри модульном и межмодульном.

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

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

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

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

Система внутри модульной диспетчеризации должна быть рассчитана на работу в различных режимах []:

- программном (цикловом) режиме диспетчеризации;

- диспетчеризации при наличии сменно-суточного задания;

- динамической диспетчеризации.

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

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

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

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

 

 

Для обеспечения эффективной работы производственных систем

возможности

 

*******************************************************

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

Причинами таких отклонений могут быть:

- задержки в поставках заготовок к обрабатывающему оборудованию;

- поломки оборудования;

- задержки в поставках заготовок и комплектующих деталей, узлов и агрегатов к заданным срокам;

- задержки в поставках к заданным срокам инструментов и технологической оснастки;

- поломки инструментов и технологической оснастки;

- появление новых партий деталей и заказов в производственной программе предприятия;

- исключение некоторых партий деталей и заказов из производственной программы предприятия;

- необходимость изменения сроков готовности некоторых заказов на более ранние.

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

 

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

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

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

· продолжение дальнейшей работы, невзирая на сложившуюся аварийную ситуацию;

· выявление аварийного элемента, вывод его из эксплуатации и подача заявки на устранение неполадки в аварийную службу;

· переход в ожидание появления или ремонта проблемного ресурса (инструмента, станка, заготовки и т.д.);

· выполнение следующего по порядку действия.

Теоретически, в системе возникновение аварийной ситуации может распознаваться по следующим событиям:

· получение сообщения от элемента производственной системы о его отказе;

· аварийное завершение текущего действия или невозможность его продолжения;

· обнаружение невозможности продолжения дальнейшего хода вдоль какой-либо ветви сети действий;

· определение такого производственного состояния участка, которое не заложено и не предусмотрено в алгоритмах принятия решения и действий системы управления.

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

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

Классификация аварийных ситуаций:

­ Оборудование - станки (будет проверяться готовность к выполнению технологических операций, зависящая от текущего состояния оборудования, то есть от его функционального состояния):

· возобновляемая поломка оборудования (действие: сформировать заявку на ремонт; перестроить планы и задания): система должная определить тип поломки, составить соответствующий типу заказ на проведение либо вынужденной амортизации, либо ремонта, определить приблизительное время, через которое единица оборудования сможет снова выполнять свою нормальную работу, и откорректировать сменно-суточные задания и оперативные планы с тем учетом, что текущая единица оборудования не будет доступна в течение определенного и внесенного в систему момента времени;

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

­ Инструмент:

· наличие на складе (действие: сформировать заказ на недостающие комплекты инструмент;, скорректировать планы и задания): на предприятии необходимо осуществлять планирование рабочего инструмента и его количества (задача о «Рождественской елки») на складах, и, если система управления установила, что требуемого на изготовление текущей партии инструмента не достает, но она должна сформировать заказ на его получение, просчитать приблизительное время его выполнения (если это возможно) и внести корректировки в планы и задания, если они к этому времени уже были сформированы - то есть фактически реализация партии изделий дойдет до определенного шага и остановится, так как не будет возможности проводить дальнейшие технологические операции с деталями;

· поломка инструмента (действие: сформировать заказ на поставку нового инструмента; скорректировать планы и задания, если требуемого инструмента временно нет на складе): если однотипный инструмент имеется на складе, то производится обычная его замета с внесением соответствующих изменений в БД системы, если же система управления определяет, что требуемого инструмента нет на складе, но формируется заказ на его поставку и производится соответствующая корректировка планов и заданий с учетом невозможности выполнения технологической операции, в который был задействован данный вид инструментальной оснастки.

­ Люди, производственный персонал (действие: перераспределить сменно-суточные задания по работникам участка; возможно, увеличить количество смен и "растянуть" задания и планы): может произойти такая ситуация, что (по причине болезни или отпуска) на реализацию сменно-суточного задания к сроку не будет хвать работников участка – в этом случае, в системе должна быть предусмотрена возможность перераспределять задания между оставшимся на участке производственным персоналом и одновременно возможность увеличения количества смен, так как работы у персонала прибавится и ему просто может не хватить времени на то, чтобы уложиться к требуемому сроку выполнения заказа. На производстве должны быть предусмотрены стандартные на случай нехватки персонала.

­ Материалы и заготовки:

· опоздание с поставками (действие: скорректировать по времени сменно-суточные задания и оперативные планы): вследствие задержек с поставкой придется увеличить время выполнения заказа, соответственно возможно придется увеличивать количество смен ил