Есть конвейер на котором работает n станков. Есть m деталей. Детали обарабатываются по очереди сначала на 1-ом, потом на 2-ом ... n-ом станке за некоторое извесное время t[i][j] (1<=i<=n, 1<=j<=m). В каком порядке надо ложить детали на конвеер, что бы время полной обработки было минимальным(соответственно время простоя станков тоже минимальное)? Время транспорта между станками не учитывается ( ==0 ). Станок может принять на обработку следующую деталь, даже если предыдущая еще небыла принята следующим станком(т.е. места между станками достаточно, но порядок чредования деталей неизменный).
В случае с n=2 задача решается просто путем разбиения таблицы времен на две части(1 часть t[1][j]/t[2][j] < 1, вторая — остальные) с последующей сортировкой по одной из строчек, а вот для n>=3 я таки универсального алгоритма не нашел.
Здравствуйте, PanychY, Вы писали:
PY>В случае с n=2 задача решается просто путем разбиения таблицы времен на две части(1 часть t[1][j]/t[2][j] < 1, вторая — остальные) с последующей сортировкой по одной из строчек, а вот для n>=3 я таки универсального алгоритма не нашел.
Это задача Джонсона, для трех и более станков она NP-полная
Здравствуйте, MBo, Вы писали:
MBo>Это задача Джонсона, для трех и более станков она NP-полная
Тогда, если задача NP-полная, то можно предложить найти удовлетворительное решение
с помощью генетического алгоритма. Генерировать популяцию из векторов решения — последовательности деталей, мутация — единичные перестановки деталей, оценочная функция — время обработки деталей, критерий остановки — либо допустимое время обработки, либо максимально допустимое количество поколений.
Здравствуйте, TheEvilOne, Вы писали: TEO>Тогда, если задача NP-полная, то можно предложить найти удовлетворительное решение TEO>с помощью генетического алгоритма. Генерировать популяцию из векторов решения — последовательности деталей, мутация — единичные перестановки деталей, оценочная функция — время обработки деталей, критерий остановки — либо допустимое время обработки, либо максимально допустимое количество поколений.
Таки послали меня к Генетическим алгоритмам. Я только слышал что такое существует, но что оно такое я понятия не имею.
Ладно, и на том спасибо.
