задача о графе, по которому должны идти несколько различных потоков

[kirillkucelap]

Объясните как решать следующую задачу:
Есть некоторые группы станков : N1 станков 1-ого типа,N2 станков 2-ого типа, …. NN станков N-ого типа. Станки стоят в цехе известны расстояния между любыми двумя станками, а также между входом цеха и любым станком, выходом из цеха и любым станком. Есть технологические маршруты (далее ТМ), описывающие , какие группы станков и в каком порядке должна пройти заготовка (пример ТМ: вход- станок 7 типа – станок 2 типа – станок 5 типа - выход). Все ТМ начинаются со входа и заканчиваются выходом. Таких ТМ несколько, они все известны,также известно количество заготовок, которые должны пройти по данному ТМ, а также масса заготовки для данного ТМ (считается, что в процессе обработки на станке масса заготовки не меняется).Когда заготовка проходит по ТМ через какой-то станок, это называется операция. Каждая операция занимает некоторое время, величина этого времени для каждой операции каждого ТМ известна. Каждый отдельный станок может работать не более , чем некоторое время Т (это время одинаково для всех станков независимо от их группы). Необходимо выполнить все заданные ТМ. Предложите алгоритм для такого распределения ТМ по станкам, чтобы при этом величина мощности грузопотока по цеху была минимальна. Мощность грузопотока для одной заготовки равна произведению ее массы на расстояние, ей пройденное. Мощность грузопотока для цеха – сумма мощностей грузопотока для всех деталей, прошедших через цех. Считать, что все расстояния, время каждой операции каждого ТМ и время Т – рациональные положительные числа.
Алгоритм по возможности должен быть быстрым, но если не можете придумать такой, дайте хоть какой-нибудь
Я так понял, что если ТМ один, то получается классическая задача о поиске потока минимальной стоимости. Но из-за того , что ТМ несколько, у меня не получается решить задачу. Более того, я даже не могу сформулировать эту задачу как задачу линейного программирования (возможно у меня просто кривые руки).

[Sonic86]

А задача нахождения потока в графе может быть сформулирована как задача ЛП? Если да, то можно пытаться делать по аналогии. Если нет, то фигово...
Вспоминается название раздела "теория расписаний". Попробуйте погуглить (в Википедии есть статья). Но боюсь, что все будет переборное. И тогда надо будет либо учитывать специфику задачи, либо юзать жадные алгоритмы.

NN станков N-ого типа

:blink: тогда уж станков -го типа

[kirillkucelap]

в общем мне удалось сформулировать эту задачу ка к задачу линейного программирования. для этого я пронумеровал все операции, (например, если есть 5 ТМ по 10 операций в каждом, то получается всего 50 операций), и придумал граф, чьи вершины- это станки, и они соединяются несколькими ребрами Bijk , если на итом станке выполняется катая операция, и после нее заготовка идет на джитый станок. Поставив каждой такой дуге в соответствие количество заготовок, по ней прошедшее, получим переменные величины, чье значение однозначно определяет весь поток по графу. Накладывая на эти переменные ограничения , следующие из условия, получаем задачу линейного программирования.


У меня, как у человека, никогда ничего не программировавшего, есть вопрос - на каком языке программирования мне ,новичку, будет проще всего реализовать такой алгоритм?


Так же буду рад если кто-то предложит более быстрый алгоритм решения описанной выше задачи