Я собираюсь попытаться атаковать «идеальный» случай, в котором никакие задания не разбиты на полосы или напечатаны в одиночку.
Пусть n будет количеством заданий, округленным до ближайшего кратного 3. Можно создать фиктивные задания нулевой длины, чтобы число заданий было кратным 3.
Если n = 3, это тривиально, потому что есть только одно возможное решение. Итак, предположим, что n> 3.
Задание (или одно из заданий, если их несколько) с наибольшим количеством должно неизбежно быть самым высоким или самым большим из самой длинной группы заданий (или одной из самых продолжительных групп заданий, если есть связь). Задания равного количества являются взаимозаменяемыми, поэтому просто выберите одно и назовите его наибольшим, если есть связь.
Таким образом, если n = 6, у вас есть две группы работ, из которых самая длинная или равная имеет фиксированное наибольшее или совместное наибольшее количество заданий. Таким образом, единственный вопрос заключается в том, как организовать остальные 5 рабочих мест между группами. Формула для расчета отходов группировки может быть выражена как 2∑h i - ∑x j , где h i s - это наибольшие количества в каждой группе и x j s - остальные величины. Таким образом, переход от одного возможного решения к другому будет включать в себя замену одного из h на один из x. (Если вы поменяете местами один из h с другим h, или один из x с другим x, это не будет иметь никакого значения, поэтому вы бы не перешли к другому решению.) Поскольку h 2 фиксирован, и x 1 и x 2 бесполезны для нас, что мы на самом деле пытаемся минимизировать, это w (h 1, х 3 , х 4 ) = 2 ч 1 - (х 3 + х 4 ). Если h 1 <= x <sub>3 <= x <sub>4 , это оптимальная группировка, поскольку никакой своп не может улучшить ситуацию. (Чтобы увидеть это, пусть d = x 3 - h 1 и обратите внимание, что w (x 3 , h 1 , x 4 ) - ш (ч 1 , х 3 , х 4 ) = 3d, что неотрицательно и по симметрии одинаковы Аргумент справедлив для замены с x 4 ). Итак, это касается случая n = 6.
Для n = 9 у нас есть 8 заданий, которые можно перемещать, но опять же, бесполезно перемещать самые короткие два. Таким образом, формула на этот раз W (ч 1 , ч 2 , х 3 , х 4 , х 5 , х 6 ) = 2 ч 1 + 2 ч 2 - (х 3 + х 4 + x 5 + x 6 ), но на этот раз мы имеем ограничение, что h 2 не должен быть меньше второго наименьшего x в формуле (в противном случае она не может быть самой высокой или самой высокой в любой группе). Как отмечалось ранее, h 1 и h 2 нельзя поменять местами друг с другом, поэтому либо поменяйте местами один из них с соответствующим x (без нарушения ограничения), либо вы поменяйте местами их обоих, каждый с отличным х. Взять h 1 <= x <sub>3 <= x <sub>4 <= h <sub>2 <= x <sub>5 < = х 6 . Опять же, одиночные свопы не могут помочь, и двойной своп тоже не может помочь, потому что его эффект обязательно должен быть суммой эффектов двух отдельных свопов. Опять же, это оптимальное решение.
Похоже, этот аргумент будет работать для любого n. В этом случае поиск оптимального решения, когда у вас есть «идеальный случай» (как определено в верхней части моего ответа), будет простым: сортируйте задания по количеству, а затем разбивайте отсортированный список на последовательные группы по 3 Если это решение окажется неподходящим, вы знаете, что у вас нет идеального случая.
Я подумаю о неидеальных случаях и обновлю этот ответ, если что-нибудь придумаю.