Есть конвейер на котором работает 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 я таки универсального алгоритма не нашел.
