алгоритм Джонсона

← →
GanibalLector © (2004-06-13 13:36) [0]

Имеется технологическая линия из N станков через которую необходимо пропустить M деталей.Нужно минимизировать время обработки всех деталей.N=2

Все множество деталей разбивается на 2 группы:
-все детали,для которых время обработки на 1 станке меньше времени обработки на 2
- во вторую все остальные

А что дальше???Как эти детали пускать на станки???В какой очередности.
З.Ы. Может кто знает???

← →
default © (2004-06-13 13:41) [1]

"Все множество деталей разбивается на 2 группы:
-все детали,для которых время обработки на 1 станке меньше времени обработки на 2
- во вторую все остальные"
ерунда...а если только одна деталь из 1000, например, имеет время обраб-ки на втором станке меньше чем на первом?она обраб-ся и станок будет простаивать?

← →
GanibalLector © (2004-06-13 13:44) [2]

2 default
Ну...я с тобой согласен.Но давай это пропустим,это преп выдал.
Что дальше???Как их запускать на станках???

← →
default © (2004-06-13 13:56) [3]

GanibalLector © (13.06.04 13:44) [2]
а алгоритм Джонса причём?
надо программу что-ли написать?

← →
GanibalLector © (2004-06-13 13:59) [4]

ну да...
Ну это без проблем,я сам справлюсь.
Мне алгоритм нужен,как эти детали запускать...

>а алгоритм Джонса причём?
Преп сказал,что это задача Джонсона...вот и спрашиваю,млин

← →
default © (2004-06-13 14:04) [5]

попробуй задачу формально описать

2 default
>попробуй задачу формально описать
Это как???

по-моему просто делишь на M на N частей (N>1) по критерию скорости обраб-ки - получаешь очереди на станки
если какая-то очередь кончилась - по тому же крит-ию берёшь детали по мере обраб-ки из другой очереди(то есть из той детали из которой быстрей обраб-ся на освобод-ся станке) и ставишь в освобод-ся и тд

алгоритм Джонсона Найти похожие ветки