sobolevБудьте добры, кто может, дайте ссылки на описания алгоритмов планирования (планирование загрузки оборудования, составление расписаний и т.д.).
Берут объекты для планирования (строка заказа и т.д.), проверяют на доступность несвязанных к требуемому моменту, если нет, то выбирают процесс с требуемым выходом, создают граф процессов, анализируют на доступность полуфабрикатов, машин, инструмента, оснастки, операторов и т.д. и если все указанное доступно В ПРИНЦИПЕ (т.е. имеется у кого заказать, арендовать, находится в рабочем состоянии и т.д.). Так обрабатываю все подлежащее планированию объекты.
После начинают строит расписание с учетом определенных критериев ОДНОВРЕМЕННО для ВСЕХ объектов подлежащих планированию, при этом учитывають все ограничения подлежащие учету (доступность, затратность, расстояния, чкорость и т.д.).
Каждый строит по своему усморению, но некоторые деоают ПРОЗРАЧНЫЕ намеки на математически строгую оптимизацию, на вскую там устойчивость расписаний и т.д. Врут в основном.
В простых случаях обычно хватает туда-сюда планирования. Т.е., планируете вперед исопльзуя ранний запуск, находите дату выпуска, потом назад использую найденные даты, что бы дать иллюзию JIT (иногда это объязательно - очень длинные операции, нехватка мест хранения, краткие сроки годности полуфабриката и т.д.), при этом могут ввести временные буферы (резер) на критические процессы.
При процессах с коротким циклом можно выбрать стратегию "машины съедают работы", т.е. каждая свободная машина может сожрать с очереди подходящую работу. Хорошо бы при этом чуток пройтись по следующим машинам, что бы не было блокировок (лучше всего разработать правила съедения, как запуск тразакций в БД, что бы не было дедлоков).
Посложнее. Сначала анализируется вся загрузка, находятся явные пересечения (узкие места). Потом планируют вниз от узких мест пытаясь сместить работы для узкого места как можно ближе к началу .
Используют эвристики другого характера -
- Запускают работы с относительно меньшей трудоемкостью вперед (идея, как быстрее законишь ты, так быстрее начнут работать другие)
- с точностью наоборот (сделать основные работы, а мелочь можно всега, даже сверхурочно)
...

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

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

На русском языке нет ничего. Последняя мода на западе - constraint programming. У нас слов таких мало кто слышал.
А так все зависит от класса задачи. Есть классификатор задач. К каждому классу можно подобрать свой алгоритм. Малейшее отклонение от класса убивает алгоритм.
Про полезные эвристики я вам рассказал. Это то что на виду. Эвристика появляется во время анализа. Что бы анализировать нужен инструмент - моделирование, сбор статистики, выводы.
Если хотите заниматься серьезно, то начните с начала - линейное программирование, целочисленное и смещанное программирование, логическое программирование. Дальше динамическое программиервание и все разновидности ветвей и границ, локальный поиск.
Если надо просто стрит "след протектора", как в исвестных программах, то хватит и форвард-баквард планирования.
Не попадайтесь на удочку ДБР и т.д., которые заяавляют о ноу-хау и закрытость алгоритмов.
Есть тестовые задачи, с рейтингами, временем счета и оптимумом. При покупке или презентации требуйте, что бы дали , а еще лучше показали соответствие этим рейтингам. А то на словах все все оптимизируют, а на самом деле кроме машинного времени ничего в расчет не берут и не могут расситать даже машинное время ( а брать надо - доступность материалов, транспорта, складских помещений, людей, состояния машин, времен переналадок, стоимость переналадок, стоимость работ, порядок работ, директивную дату выпуска и поставок, ранний срок запуска, поздний срок выпуск, штрафное время, зона ошибок, возможность объединения работ, возможность прерывания работ, сроки годности полуфабрикатов и ГП и еще кучу вещей).
Требуйте, что бы вам дали целевые функции в явном виде и распечатали математическую модель.
Не верьте когда говорят о многокритериальной оптимизации - пусть проводят однокритериальную оптимизацию и потом каскадно и совместно. При МК хрен концов найдешь и не докажешь неоптимальность.
Требуйте, что бы программа рассчитывала дату выпуска (при заданных директивных сроках обычно запускают все заказы по EDD - ранний срок выпуска, то есть просто сортируют заказы по дате выпуска и заполняют дырки.
Если заяавляют о многих критериях оптимизации, то просите, что бы вам дали доказательство и независимости критеиев. Например, критерий "минимизация времени переналодок" есть то же самое, что и Cmax - минимизация максимума времен выпуска (фундаментальный критерий для джоб шоп и прожект манаджмент), а "минимизация стоимости переналодок" - минимизация стоимости всех работ. Таких надуманных критериев "на лоха" много, потому пусть математически докажут неприводимость критериев.
Если будут вопросы, дальше еще поговорим.

sobolevЕще раз спасибо.
Особенное спасибо за "constraint programming". Google сразу выдал любопытные ссылки (меня английский не напрягает).

CP вещь наивная, но очень мощная.

LunxКроме тупого моделирования ничего пока не могу приджумать. Но как интересно однако.

Что такое "тупое" моделирование?

Di_Ablo
...


:)

Genetic Algorithms in Timetabling and Scheduling.pdf
Попросите ишака.

belugin
вот тут Genetic Algorithms in Timetabling and Scheduling - Fang, Thesis (ResearchIndex)

Хороший ресурс, спасибо.