Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Задача о трёх станках

Автор: ДобренькийПапаша 8.12.2009, 21:31

Есть три станка. Дано n деталей. Каждая деталь должна последовательно пройти обработку на всех трёх станках. Дан массив (двумерный), в котором указано за какое время какая деталь на каком станке будет обрабатываться. Если есть простой, то соответственно простой, если первая деталь на первом станке обработалась, на первый станок сразу поступает вторая деталь. Очереди вобщем надо соблюдать. Как сие решается? Там злобные вложенные циклы должны быть. Может есть исходники у кого?

Автор: Lamak 9.12.2009, 15:29

тут сплошное "дано:" а что надо найти?

Автор: maxdiver 9.12.2009, 16:04

Насколько мне известно, это NP-полная задача. Поэтому логичным будет написать переборное решение (прямо перебирать последовательность деталей в очереди и для каждой последовательности посчитать ответ, а потом выбрать наименьший).

Автор: Akina 9.12.2009, 16:09

Цитата(Lamak @  9.12.2009,  16:29 ) что надо найти?  Вероятно, минимальное время и план исполнения заказа. ДобренькийПапаша Допускается ли обработка деталей на следующем станке в порядке, отличном от порядка его обработки на предыдущем станке? Цитата(maxdiver @  9.12.2009,  17:04 ) Насколько мне известно, это NP-полная задача. Не факт... Правда, при тех дополнительных условиях, когда она неполная, возникает проблема доказательства оптимальности найденного решения - а вот доказательство в таком случае гарантированно NP-полное.

Автор: ДобренькийПапаша 9.12.2009, 16:38

Найти сколько уйдёт времени. Порядок обработки только такой: первый станок, второй станок, третий станок. Добавлено через 1 минуту и 13 секунд Вопрос о её NP-полноте не интересует. Это задачка для студиозуса в масштабе трёх деталей)))

Автор: Akina 9.12.2009, 16:42

Цитата(ДобренькийПапаша @  9.12.2009,  17:38 ) Порядок обработки только такой: первый станок, второй станок, третий станок. Возможен ли такой вариант: на первом станке обрабатывается деталь 1, потом деталь 2, затем деталь 3, на втором деталь 1, затем деталь 3, и наконец деталь 2? Или порядок изменять нельзя?

Автор: ДобренькийПапаша 9.12.2009, 16:43

порядок изменять нельзя

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)