Подход к проблеме Bin Packing sql - PullRequest
2 голосов
/ 01 октября 2009

У меня проблема в sql, где мне нужно создать список упаковки из списка транзакций.

Модель данных

Транзакции хранятся в таблице, которая содержит:

  • идентификатор транзакции
  • идентификатор товара
  • количество товара

Каждая транзакция может иметь несколько элементов (и одновременно несколько строк с одинаковым идентификатором транзакции). Каждый элемент имеет количество от 1 до N.

Бизнес-проблема

Бизнес требует, чтобы мы создали список упаковки, где каждая позиция в списке упаковки содержит количество каждого элемента в коробке.

Каждая коробка может содержать только 160 предметов (все они имеют одинаковый размер / вес). Исходя из общего количества заказов, нам нужно разделить элементы на разные блоки (иногда даже отдельные коллекции элементов разбиваются на две части)

Таким образом, задача состоит в том, чтобы взять эту схему данных и создать результирующий набор, который включает в себя, сколько каждого элемента содержится в каждом блоке.

В настоящее время я грубо заставляю это делать некоторые не очень красивые способы и задаюсь вопросом, есть ли у кого-нибудь элегантное / простое решение, которое я пропустил.

Пример входа / выхода

Нам действительно нужно определить, сколько каждого элемента окажется в каждом поле ... например:

Заказ 1:

  • 100 позиции A
  • 100 позиции B
  • 140 позиции C

Это должно привести к трем строкам в наборе результатов:
  • Блок 1: A (100), B (60)
  • Блок 2: B (40), C (120)
  • Блок 3: C (20)


В идеале запрос был бы достаточно умен, чтобы собрать все Си, но на данный момент - мы не слишком обеспокоены этим.

Ответы [ 5 ]

3 голосов
/ 01 октября 2009

Вы читали библию упаковки бина?

https://sqlserverfast.com/?s=bin+packing

2 голосов
/ 01 октября 2009

Как насчет чего-то вроде

SELECT SUM([Item quantity]) as totalItems
     , SUM([Item quantity]) / 160 as totalBoxes
     , MOD(SUM([Item Quantity), 160) amountInLastBox
FROM [Transactions]
GROUP BY [Transaction Id]

Дайте мне знать, какие поля в наборе результатов вы ищете, и я мог бы найти лучшее

1 голос
/ 10 октября 2009

попробуйте выбрать несколько идей из http://www.postgresonline.com/journal/index.php?/archives/138-Allocating-People-into-Groups-with-SQL-the-Sequel.html

используется CTE

1 голос
/ 08 октября 2009

Я искал что-то похожее, и все, чего я мог достичь, - это расширить строки до количества элементов в транзакции и сгруппировать их в ячейки. Хотя не очень элегантно. Более того, поскольку в SQL Server агрегирование строк по-прежнему очень громоздко (Oracle, я скучаю по тебе!), Я должен пропустить последнюю часть. Я имею в виду подсчет в один ряд ..

Мое решение заключается в следующем:

Пример таблицы транзакций:

INSERT INTO transactions
(trans_id, item, cnt) VALUES
('1','A','50'), 
('2','A','140'), 
('3','B','100'), 
('4','C','80');
GO

Создать фиктивную таблицу последовательности, которая содержит числа от 1 до 1000 (я предполагаю, что максимально допустимое количество для элемента в одной транзакции равно 1000):

CREATE TABLE numseq (n INT NOT NULL IDENTITY) ;
GO
INSERT numseq DEFAULT VALUES ;
WHILE SCOPE_IDENTITY() < 1000 INSERT numseq DEFAULT VALUES ;
GO

Теперь мы можем сгенерировать временную таблицу из таблицы транзакций, в которой каждая транзакция и элемент существуют "cnt" раз в подзапросе, а затем присвоить номера бинам с использованием деления и сгруппировать по номеру бина :

SELECT bin_nr, item, count(*) count_in_bin
INTO result
FROM (
  SELECT t.item, ((row_number() over (order by t.item, s.n) - 1) / 160) + 1 as bin_nr
  FROM transactions t 
  INNER JOIN numseq s
  ON t.cnt >= s.n -- join conditionally to repeat transaction rows "cnt" times
) a
GROUP BY bin_id, item
ORDER BY bin_id, item
GO

Результат:

bin_id item count_in_bin
1      A    160
2      A    30
2      B    100
2      C    30
3      C    50

В Oracle последний шаг будет таким простым:

SELECT bin_id, WM_CONCAT(CONCAT(item,'(',count_in_bin,')')) contents
FROM result
GROUP BY bin_id
0 голосов
/ 09 октября 2009

Это не самый красивый ответ, но я использую аналогичный метод для отслеживания складских запасов в процессе заказа, и его легко понять, и это может привести к разработке вами лучшего метода, чем у меня.

Я бы создал таблицу с именем "PackedItem" или что-то подобное. Столбцы будут:

packed_item_id (int) - Primary Key, Identity column
trans_id (int)
item_id (int)
box_number (int)

Каждая запись в этой таблице представляет 1 физическую единицу, которую вы отправите.

Допустим, кто-то добавляет строку в транзакцию 4 с 20 из элемента 12, я бы добавил 20 записей в таблицу PackedItem, все с идентификатором транзакции, идентификатором элемента и пустым номером поля. Если строка обновлена, вам нужно добавить или удалить записи из таблицы PackedItem, чтобы всегда была корреляция 1: 1.

Когда придет время отправлять, вы можете просто

SELECT TOP 160 FROM PackedItem WHERE trans_id = 4 AND box_number IS NULL

и установите box_number в этих записях на следующий доступный номер ящика, пока не останется записей, где box_number равно NULL. Это возможно, используя один довольно сложный оператор UPDATE внутри цикла WHILE - у меня нет времени полностью его построить.

Теперь вы можете легко получить желаемый упаковочный лист, запросив эту таблицу следующим образом:

SELECT box_number, item_id, COUNT(*) AS Qty
FROM PackedItem
WHERE trans_id = 4
GROUP BY box_number, item_id

Преимущества - легко понять, довольно легко реализовать. Подводные камни - если таблица не синхронизируется со строками транзакции, конечный результат может быть неверным; Эта таблица будет содержать много записей и будет дополнительной работой для сервера. Потребуется, чтобы каждое поле ID было проиндексировано для поддержания хорошей производительности.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...