10. Задача Джонсона.

2) Модель теории расписания.

Задача Джонсона. 1910 год. Требуется обработать m-деталей, причём каждая деталь должна последовательно пройти обработку на n-станках. Технология обработки не задана, детали обрабатываются в любом порядке. Расписанием G называется множество следующего вида:

где -- время начала обработки i-ой детали на j-ом станке;

-- время окончания обработки i-ой детали на j-ом станке.

Задано -- время обработки i-ой детали на j-ом станке.

На времена обработки ( , ) накладываются ограничения:

1. для каждой детали обработка на станке j+1 должна начинаться не раньше чем закончится обработка на станке j, т. е.

2. На каждом станке одновременно может обрабатываться не более одной детали, т. е. , где s=1..m,

3. Начатая операция не прерывается до полного её завершения. = +

Требуется определить порядок обработки деталей на станках, то есть расписание G – минимизирующее общее время обработки.

F(G) – пример оптимизации.

Решение этой задачи есть для 1,2,3 станков, для 4 станков решение уже не известно.

Трудности решения задач теории расписания – это большое количество вариантов.

Подобные задачи решаются тремя способами:

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

2. Метод случайного поиска (метод Монте-Карло) Предположим, что есть хотя бы один станок и 6 деталей. Надо сгенерировать равномерно распределенные случайные числа. Например:

1 2 3 4 5 6

0,5 0,3 0,1 0,7 0,9 0,4

Далее упорядочим по возрастанию случайной величины, и получим случайное расписание 3, 2, 6, 1, 4, 5. Потом возьмем следующие случайные числа и повторим операцию и выберем ту последовательность, где время выполнения наименьшее. Недостаток: последовательности случайных чисел псевдослучайны и ограничены.

3. Смешанный метод. Вероятностным образом выбираются длины операций и каждый получает свой метод. Используют random’изированные правила предпочтения. Достоинство: расписание выбирается случайно, но из хороших.

11. Эффективность автоматизации управления

УС

I II III IV V

Реализация (Р)

производство

О У

1

2

3

4

5

УС-управляющая система

ОУ - объект управления

I- V - причины принятия неоптимальных решений: I – уровень организации труда; II – квалификация;

III – наличие информации; IV – наличие вычислительной техники и связи; V – структура управления.

1-5 - воздействие на производство случайных факторов: 1 – технический отказ оборудования; 2 – технологические изменения; 3 – случайные факторы организационного порядка (срывы сроков и т.д.);

4 – факторы социального порядка (невыходы на работу, хищения); 5 – климатические факторы.

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

Вероятность выполнения этих действий определяет надёжность функционирования данной системы, которая зависит от выработки и реализации ρ(В, Р) = Н_сд. Т.к. выработка и реализация решений являются зависимыми, то зависимость есть произведение двух вероятностей и условной вероятности, т.е. ρ(В,Р) = Н_сд = ρ(В)* ρ _В(Р), обеспечивает достижение заданного результата. При условии, что ρ(В) состоялось, т.е. имелось принятое решение. Из этой формулы следует вывод, что надёжность системы состоит из двух частей. Под надёжностью управления системы можно понимать её способность удовлетворительно выполнять свои функции с заданными условиями, т.е. принимать допустимые решения, которые обеспечивают достижение, т.е решения, в которых отсутствует ошибка и ρ(В) = 1

Р_н = Р * V_в

M и K – коэффициенты, которые определяют влияние вероятностных факторов на качество процесса принятия решений. К – класс сложностей задач управления. К=0 – выработка управляющего измерения не нужна. М=0 – исполнение принимается только оптимальное решение. М_исп = М₁+М₂+…+М₅

М₁ – потери времени по причине или остановок работ;

М₂ – потери времени обусловленные квалификации испытаний;

М₃ – потери времени обусловленные неравномерным поступлением информации;

М₄ – потери времени обусловленные неравенством скорости обработки информации техническим средством и человеком;

М₅ – потеря времени связанная с совершенствованием каналом связи.