Алгоритм группировки заданий печати с минимальными отходами?
Я работаю в издательстве и настраиваю одну из наших печатных машин на "ganging", другими словами, на одновременную печать нескольких заданий. Учитывая, что разные задания на печать могут иметь разное количество, и одновременно может быть рассмотрено от 1 до 20 заданий, проблема заключается в том, чтобы определить, какие задания сгруппировать вместе, чтобы минимизировать отходы (отходы, возникающие из-за перепечатки заданий с меньшим количеством в данном наборе, то есть).
При следующих стабильных данных:
- Все задания равны по пространственному размеру - расположение на бумаге не учитывается.
- Имеется три "полосы", что означает, что три задания могут быть напечатаны одновременно.
- В идеале на каждой полосе находится одно задание. Частью проблемы является минимизация количества полос, на которых выполняется каждое задание.
- При необходимости одно задание может выполняться на двух полосах, а второе задание - на третьей полосе.
- Отходы "группировки" из данного набора заданий (допустим, их количество равно x, y и z) будут представлять собой наибольшее число минус два меньших числа. Таким образом, если x - наибольшее число, то отходы группировки будут (x - y) + (x - z). Иначе говоря, отходы образуются при печати заданий Y и Z (сверх их количества) до количества X. Группировочные отходы были бы классификатором для данного набора, то есть они не могли бы превышать определенное количество, иначе задание просто печаталось бы в одиночку.
Итак, вопрос сформулирован: как определить, какие наборы заданий будут сгруппированы вместе из любого заданного количества заданий, основываясь на классификаторах: 1) Три одинаковых количества ИЛИ 2) Два количества, где одно приблизительно в два раза больше другого, И с целью минимального общего количества отходов группировки среди различных наборов.
(Редактировать) Информация о количестве: Типичное количество заданий может составлять от 150 до 350 на иностранных языках или от 500 до 1000 на английском языке. Эти данные можно использовать для создания некоторых сценариев алгоритма. Например, допустим, у вас было 5 заданий:
1000, 500, 500, 450, 250
Посмотрев на это, я вижу несколько ответов. Очевидно, что (1000/500/500) неэффективно, так как у вас будут отходы от группировки в 1000. (500/500/450) лучше, так как у вас будет потеря 50, но тогда вы будете выполнять (1000) и (250) по отдельности. Но вы также можете выполнить (1000/500) с 1000 на двух дорожках, (500/250) с 500 на двух дорожках, а затем (450) в одиночку.
С точки зрения компромисса между минимизацией полос и расточительством, можно сказать, что любое расточительство при группировке более 200 является чрезмерным.
(End Edit)
... Нет нужды говорить, что это довольно сложная проблема. (Для меня.)
Я в меру опытный программист, но не очень хорошо знаком с алгоритмами и не до конца изучил математику в этой области. Я пишу программу типа "грубой силы", которая просто перебирает все варианты, игнорируя любое дерево вариантов, в котором, как кажется, слишком много отходов группировки. Однако я не могу не надеяться, что существует более простой и эффективный метод.
Я просмотрел различные веб-сайты, пытаясь узнать больше об алгоритмах в целом, и прокладываю свой путь через символы, но это происходит медленно. К сожалению, статьи Википедии на эту тему очень перекрестные, и трудно найти "вход". Единственное, что мне удалось найти, - это определение грубого типа алгоритма, который мне нужен: "Exclusive Distance Clustering", говоря одномерно.
Я просмотрел алгоритм, на который, кажется, часто ссылаются на этом сайте, Bin Packing, но я не смог понять, как именно он будет работать с моей проблемой.