MAXimal | |
добавлено: 11 Jun 2008 11:21 Содержание [скрыть] Задача Джонсона с двумя станкамиИмеется Требуется составить такой порядок подачи деталей на станки, чтобы итоговое время обработки всех деталей было бы минимальным. Эта задача называется иногда задачей двухпроцессорного обслуживания задач, или задачей Джонсона (по имени S.M. Johnson, который в 1954 г. предложил алгоритм для её решения). Стоит отметить, что когда число станков больше двух, эта задача становится NP-полной (как доказал Гэри (Garey) в 1976 г.). Построение алгоритмаЗаметим вначале, что можно считать, что порядок обработки деталей на первом и втором станках должен совпадать. В самом деле, т.к. детали для второго станка становятся доступными только после обработки на первом, а при наличии нескольких доступных для второго станка деталей время их обработки будет равно сумме их Рассмотрим порядок подачи деталей на станки, совпадающий с их входным порядком: Обозначим через Для первой детали мы имеем: Для второй — т.к. она становится готовой к отправке на второй станок в момент времени Третья деталь становится доступной для второго станка в момент Таким образом, общий вид для Посчитаем теперь суммарный простой где (В это можно убедиться по индукции, либо последовательно находя выражения для суммы первых двух, трёх, и т.д. Воспользуемся теперь перестановочным приёмом: попробуем обменять какие-либо два соседних элемента По виду функции выражений для Таким образом, чтобы деталь (т.е. мы проигнорировали остальные, не изменившиеся, аргументы максимума в выражении для Отняв или, избавляясь от отрицательных чисел, получаем: Тем самым, мы получили компаратор: отсортировав детали по нему, мы, согласно приведённым выше выкладкам, придём к оптимальному порядку деталей, в котором нельзя переставить местами никакие две детали, улучшив итоговое время. Впрочем, можно ещё больше упростить сортировку, если посмотреть на этот компаратор с другой стороны. Фактически он говорит нам о том, что если минимум из четырёх чисел Так или иначе, получается, что задача Джонсона с двумя станками сводится к сортировке деталей с определённой функцией сравнения элементов. Таким образом, асимптотика решения составляет РеализацияРеализуем второй вариант описанного выше алгоритма, когда детали сортируются по минимуму из struct item { int a, b, id; bool operator< (item p) const { return min(a,b) < min(p.a,p.b); } }; sort (v.begin(), v.end()); vector<item> a, b; for (int i=0; i<n; ++i) (v[i].a<=v[i].b ? a : b) .push_back (v[i]); a.insert (a.end(), b.rbegin(), b.rend()); int t1=0, t2=0; for (int i=0; i<n; ++i) { t1 += a[i].a; t2 = max(t2,t1) + a[i].b; } Здесь все детали хранятся в виде структур Детали сортируются, затем распределяются по спискам Литература
|