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

[Борис Лаврищев]

Доброго времени суток.
Подскажите, плз., где можно почитать что-нибудь (теория, примеры решений) близкое к такой задаче:
В цехе имеется N РАЗНЫХ станков; M рабочих (каждый может выполнять определенные работы); идет постоянный приток заказов на производство различных деталей (номенклатура большая ~10000).
На каждую деталь есть тех. процесс, т.е. пооперационное расписание, как ее делать (станок и время операции), порядок операций жесткий, но не однотипный, т.е. одну заготовку могут сначала сверлить, а потом фрезеровать, а другую -- наоборот.
Надо: так разместить операции по станкам (и рабочим), чтобы уложиться в срок заказа и + к этому использовать минимум рабочих (чтобы зарплату меньше платить .

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

Заранее спасибо.

[direktorSan]

Здравствуйте!
Есть в исследовании операций класс задач с названием "Транспортная задача" (она же, если мне память не изменяет, "Задача о комивояжере"). Условие ее такое.
Есть N пунктов назначения (N станков в данном случае), есть M автомобилей (M работников) и есть куча путевых листов (технологических карт на изделия). Цель задачи - составить такое расписание движения транспортных средств, чтобы минимизировать время на реализацию всех путевок.
По-моему какое-то сходство есть. Только вот не помню на счет условия о минимизации количества транспортных средств.
Задача решается с использованием матриц. Пути оптимизации решения и адаптации алгоритма алгоритма есть. Количество итераций вычислимо.
Удачи.

[Борис Лаврищев]

Спасибо, direktorSan, посмотрю-подумаю...

[direktorSan]

Я тут поднял свои записи...
В общем пардон.
Условие я сформулировал неправильно.
Там есть несколько поставщиков и несколько потребителей.
У потребителей есть потребность в товаре, а у поставщиков есть запасы товаров. Цель - удовлетворить всех потребителей с минимальными издержками.
А вот все остальное я говорил правильно. )
Еще раз пардон.
И, еще раз, удачи.

[--Zap--]

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

Ну вот примерно такая теория а реализовывать все будешь сам , direknorSan!!!

[Sacha]

Что-то мне из своих глубин мозг подсказывает (простите давно это было), что этот класс задач решается симплекс-методом. Целевая функция: "это уложиться в срок заказа и + к этому использовать минимум рабочих", а пространство решений: система уравнений (неравенств) "пооперационное расписание".

алгоритмик есть (но, к сожелению, в виде Дельфового проекта (для "домашнего" использования) и только для стандартной и расширенной задачи. Зато с правильными дробями).

[Dimka]

Открываем школьный учебник по программированию...
(Бондарев В.М., Рублинецкий В.И., Качко Е.Г. "Основы программирования" / Харьков: Фолио: Ростов н/Д: Феникс, 1997)

Раздел "Теория расписаний"

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

Имеем 2 станка. Обработка i-й детали производится путём исполнения операции длительности ai на первом станке, а затем (возможно, после перерыва) исполнения операции длительности bi на втором станке.

Решение. Теорема. Оптимальный порядок строится по следующему правилу: i-ая операция предшествует i+1-й, если

max(si, si+1) < max(s'i, s'i+1), где

si = sum(ak, k=1...i) - sum(bk, k=1...i-1)
si+1 = sum(ak, k=1...i+1) - sum(bk, k=1...i)
s'i = sum(ak, k=1...i-1) + ai+1 - sum(bk, k=1...i-1)
s'i+1 = sum(ak, k=1...i+1) - sum(bk, k=1...i-1) - bi+1

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

Может вышеприведённое поможет или направление поисков определит.

[Борис Лаврищев]

*На меня обрушился поток информации*
Спасибо всем.

Еще, говорят, "жадные" алгоритмы можно попробовать, быстро, надежно, волшебно, хорошо...
В сети инфы по ним полно, но нормального описания не найти.
Может и о них знает уважаемая общественность?
The Best в виде, как от dimka -- название, автор, издательство.... ?