Задача запроса: создание сегментов четного размера на основе показателя, а не числа строк

Я опишу проблему с точки зрения загрузки заказов на определенное количество грузовых автомобилей как можно более равномерно.

Входы:

@TruckCount - the number of empty trucks to fill

Множество:

OrderId, 
OrderDetailId, 
OrderDetailSize, 
TruckId (initially null)

Ordersсостоят из одного или нескольких OrderDetails.

Задача здесь состоит в том, чтобы назначить TruckIdкаждой записи.

Один заказ не может быть разделен на грузовики.

Грузовые автомобили должны быть равномерно загружены * , насколько это возможно, измеряются sum(OrderDetailSize).

* Равномерно: Наименьшая достижимая дельта между наименее загруженным грузовиком и наиболее загруженным грузовиком. По этому определению 1,2,3 распределяется более равномерно, чем 1,1,4. Если это поможет, представьте, что вы - алгоритм статистики, создавая гистограммы четной высоты.

Не учитывается максимальная загрузка грузовика. Это волшебные упругие грузовики. Количество грузовиков, однако, является фиксированным.

Существует очевидное решение, которое является итеративным - циклическое распределение заказов.

Но можно ли это сделать как логика, основанная на множестве?

Мой основной интерес для SQL Server 2014 или более поздней версии. Но сетевые решения для других платформ также могут быть интересными.

Это похоже на территорию Ицик Бен-Ган :)

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

CREATE TABLE #OrderDetail (
OrderId int NOT NULL,
OrderDetailId int NOT NULL PRIMARY KEY,
OrderDetailSize tinyint NOT NULL,
TruckId tinyint NULL)

-- Sample Data

INSERT #OrderDetail (OrderId, OrderDetailId, OrderDetailSize)
VALUES
(1  ,100    ,75 ),
(2  ,101    ,5  ),
(2  ,102    ,5  ),
(2  ,103    ,5  ),
(2  ,104    ,5  ),
(2  ,105    ,5  ),
(3  ,106    ,100),
(4  ,107    ,1  ),
(5  ,108    ,11 ),
(6  ,109    ,21 ),
(7  ,110    ,49 ),
(8  ,111    ,25 ),
(8  ,112    ,25 ),
(9  ,113    ,40 ),
(10 ,114    ,49 ),
(11 ,115    ,10 ),
(11 ,116    ,10 ),
(12 ,117    ,15 ),
(13 ,118    ,18 ),
(14 ,119    ,26 )

--> YOUR SOLUTION HERE

-- After assigning Trucks, Measure delta between most and least loaded trucks.
-- Zero is perfect score, however the challenge is a set based solution that will scale, and produce good results, rather
-- than iterative solution that will produce perfect results by exploring every possibility.

SELECT max(TruckOrderDetailSize) - MIN(TruckOrderDetailSize) AS TruckMinMaxDelta
FROM 
(SELECT SUM(OrderDetailSize) AS TruckOrderDetailSize FROM #OrderDetail GROUP BY TruckId) AS Truck


DROP TABLE #OrderDetail

Моя первая мысль была

select
    <best solution>
from
    <all possible combinations>

Часть «лучшее решение» определяется в вопросе - наименьшая разница между наиболее загруженными и наименее загруженными грузовиками. Другой бит - все комбинации - заставил меня задуматься.

Рассмотрим ситуацию, когда у нас есть три заказа A, B и C и три грузовика. Возможности

Truck 1 Truck 2 Truck 3
------- ------- -------
A       B       C
A       C       B
B       A       C
B       C       A
C       A       B
C       B       A
AB      C       -
AB      -       C
C       AB      -
-       AB      C
C       -       AB
-       C       AB
AC      B       -
AC      -       B
B       AC      -
-       AC      B
B       -       AC
-       B       AC
BC      A       -
BC      -       A
A       BC      -
-       BC      A
A       -       BC
-       A       BC
ABC     -       -
-       ABC     -
-       -       ABC

Table A: all permutations.

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

Есть известные запросы для производства перестановок и комбинаций. Тем не менее, они будут производить мероприятия в одном ведре. Для этой проблемы мне нужны меры по нескольким ведрам.

Просмотр результатов стандартного запроса "все комбинации"

;with Numbers as
(
    select n = 1
    union
    select 2
    union
    select 3
)
select
    a.n,
    b.n,
    c.n
from Numbers as a
cross join Numbers as b
cross join Numbers as c
order by 1, 2, 3;


  n   n   n
--- --- ---
  1   1   1
  1   1   2
  1   1   3
  1   2   1
 <snip>
  3   2   3
  3   3   1
  3   3   2
  3   3   3

Table B: cross join of three values.

Я отметил, что результаты сформировались по той же схеме, что и таблица A. Сделав резкий скачок, рассматривая каждый столбец как Орден ¹ , значения, указывающие , какой грузовик будет удерживать этот Орден, и строку, чтобы обозначить расположение Ордеров внутри грузовых автомобилей. Затем запрос становится

select
    Arrangement             = ROW_NUMBER() over(order by (select null)),
    First_order_goes_in     = a.TruckNumber,
    Second_order_goes_in    = b.TruckNumber,
    Third_order_goes_in     = c.TruckNumber
from Trucks a   -- aka Numbers in Table B
cross join Trucks b
cross join Trucks c

Arrangement First_order_goes_in Second_order_goes_in Third_order_goes_in
----------- ------------------- -------------------- -------------------
          1                   1                    1                   1
          2                   1                    1                   2
          3                   1                    1                   3
          4                   1                    2                   1
  <snip>

Query C: Orders in trucks.

Расширяя это, чтобы охватить четырнадцать Орденов в данных примера, и упрощая имена, мы получаем это:

;with Trucks as
(
    select * 
    from (values (1), (2), (3)) as T(TruckNumber)
)
select
    arrangement = ROW_NUMBER() over(order by (select null)),
    First       = a.TruckNumber,
    Second      = b.TruckNumber,
    Third       = c.TruckNumber,
    Fourth      = d.TruckNumber,
    Fifth       = e.TruckNumber,
    Sixth       = f.TruckNumber,
    Seventh     = g.TruckNumber,
    Eigth       = h.TruckNumber,
    Ninth       = i.TruckNumber,
    Tenth       = j.TruckNumber,
    Eleventh    = k.TruckNumber,
    Twelth      = l.TruckNumber,
    Thirteenth  = m.TruckNumber,
    Fourteenth  = n.TruckNumber
into #Arrangements
from Trucks a
cross join Trucks b
cross join Trucks c
cross join Trucks d
cross join Trucks e
cross join Trucks f
cross join Trucks g
cross join Trucks h
cross join Trucks i
cross join Trucks j
cross join Trucks k
cross join Trucks l
cross join Trucks m
cross join Trucks n;

Query D: Orders spread over trucks.

Для удобства я предпочитаю хранить промежуточные результаты во временных таблицах.

Последующие шаги будут намного проще, если данные сначала НЕИЗВЯЗАНЫ.

select
    Arrangement,
    TruckNumber,
    ItemNumber  = case NewColumn
                    when 'First'        then 1
                    when 'Second'       then 2
                    when 'Third'        then 3
                    when 'Fourth'       then 4
                    when 'Fifth'        then 5
                    when 'Sixth'        then 6
                    when 'Seventh'      then 7
                    when 'Eigth'        then 8
                    when 'Ninth'        then 9
                    when 'Tenth'        then 10
                    when 'Eleventh'     then 11
                    when 'Twelth'       then 12
                    when 'Thirteenth'   then 13
                    when 'Fourteenth'   then 14
                    else -1
                end
into #FilledTrucks
from #Arrangements
unpivot
(
    TruckNumber
    for NewColumn IN 
    (
        First,
        Second,
        Third,
        Fourth,
        Fifth,
        Sixth,
        Seventh,
        Eigth,
        Ninth,
        Tenth,
        Eleventh,
        Twelth,
        Thirteenth,
        Fourteenth
    )
) as q;

Query E: Filled trucks, unpivoted.

Веса можно ввести, присоединившись к таблице заказов.

select
    ft.arrangement,
    ft.TruckNumber,
    TruckWeight = sum(i.Size)
into #TruckWeights
from #FilledTrucks as ft
inner join #Order as i
    on i.OrderId = ft.ItemNumber
group by
    ft.arrangement,
    ft.TruckNumber;

Query F: truck weights

Теперь можно ответить на вопрос, найдя расположение (я), которые имеют наименьшую разницу между наиболее загруженными и наименее загруженными грузовиками

select
    Arrangement,
    LightestTruck   = MIN(TruckWeight),
    HeaviestTruck   = MAX(TruckWeight),
    Delta           = MAX(TruckWeight) - MIN(TruckWeight)
from #TruckWeights
group by
    arrangement
order by
    4 ASC;

Query G: most balanced arrangements

обсуждение

С этим очень много проблем. Во-первых, это алгоритм перебора. Количество строк в рабочих таблицах экспоненциально по количеству грузовых автомобилей и заказов. Количество строк в # Arrangements составляет (количество грузовиков) ^ (количество заказов). Это не будет хорошо масштабироваться.

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

В-третьих, избыточность в договоренностях. Это раздувает промежуточные таблицы, значительно увеличивая время выполнения.

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

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

мысли

Если бы был способ заполнить #FilledTrucks непосредственно из списка грузовиков и заказов, я думаю, что худшее из этих опасений было бы управляемым. К сожалению, мое воображение наткнулось на это препятствие. Я надеюсь, что какой-нибудь будущий участник сможет предоставить то, что ускользнуло от меня.

¹ Вы говорите, что все товары для заказа должны быть на одном грузовике. Это означает, что атом присваивания - это Order, а не OrderDetail. Я сгенерировал их из ваших тестовых данных таким образом:

select
    OrderId,
    Size = sum(OrderDetailSize)
into #Order
from #OrderDetail
group by OrderId;

Не имеет значения, однако, независимо от того, помечаем ли мы элементы в вопросе «Order» или «OrderDetail», решение остается тем же.

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

Есть ли причина, по которой вам нужно предварительно назначать процессы конкретным сегментам / процессорам? [Пытаясь понять ваши реальные требования]

Для вашего примера «обновления статистики», как узнать, сколько времени займет конкретная операция? Что если данная операция сталкивается с неожиданной задержкой (например, более чем запланированная / чрезмерная фрагментация таблицы / индекса, длительный пользователь txn блокирует операцию «обновления статистики»)?

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

Структура таблицы может быть изменена в соответствии с вашими требованиями, например:

create table tasks
(id        int             -- auto-increment?

,target    varchar(1000)   -- 'schema.table' to have stats updated, or perhaps ...
,command   varchar(1000)   -- actual command to be run, eg, 'update stats schema.table ... <options>'

,priority  int             -- provide means of ordering operations, eg, maybe you know some tasks will run really long so you want to kick them off first
,thread    int             -- identifier for parent process?
,start     datetime        -- default to NULL
,end       datetime        -- default to NULL
)

Затем я запускаю X число параллельных процессов для выполнения фактических операций «обновления статистики», причем каждый процесс выполняет следующее:

• установить эксклюзивную блокировку на tasksстол (гарантирует, что задача не будет выбрана более чем одним процессом; должна быть относительно недолговечной блокировкой)
• найдите строку 'first' где start = NULL('first' будет определяться вами, например, order by priority?)
• обновить набор строк start = getdate(), thread = <process_number>
• зафиксировать обновление (и снять эксклюзивную блокировку)
• записывать idи target/commandценить
• выполнить желаемую операцию против target(поочередно, запустить command) и когда закончите ...
• обновить tasksсend = getdate() where id = <id>
• Повторите выше, пока нет больше задач для выполнения

С вышеупомянутым дизайном я теперь получил динамически (в основном) сбалансированную работу.

ПРИМЕЧАНИЯ:

• Я пытаюсь предоставить какой-то метод расстановки приоритетов, чтобы я мог запустить более длительные задачи заранее; в то время как несколько процессов работают над задачами, выполняющимися дольше, другие процессы могут перемещаться по списку задач, выполняемых с более коротким сроком действия
• если процесс сталкивается с незапланированной задержкой (например, длительным, блокирующим пользователя txn), другие процессы могут «восполнить провал», продолжая извлекать «следующую доступную» операцию из tasks
• дизайн tasksтаблицы должен предусматривать другие преимущества, например, историю времени выполнения, которую вы можете архивировать для дальнейшего использования, историю времени выполнения, которая может использоваться для изменения приоритетов, предоставления статуса текущих операций и т. д.
• хотя «эксклюзивная блокировка» tasksможет показаться немного чрезмерной, имейте в виду, что мы должны планировать потенциальную проблему 2 (или более) процессов, пытающихся получить новую задачу в одно и то же время , поэтому мы должны гарантировать задачу присваивается только одному процессу (и да, вы можете получить те же результаты с помощью комбинированного оператора «обновить / выбрать» - в зависимости от возможностей языка вашей РСУБД SQL); шаг к получению новой «задачи» должен быть быстрым, то есть «эксклюзивная блокировка» должна быть недолгой, и в действительности процессы будут срабатывать tasksдовольно случайным образом, так что в любом случае будет небольшая блокировка

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

Очевидно, что для примера вы не можете заставить свои грузовики возвращаться к распределению / складу для следующего заказа, поэтому вам нужно предварительно назначить свои заказы различным грузовым автомобилям (учитывая, что UPS / Fedex / и т. Д. Также должны назначить на основе маршрутов доставки с целью сокращения сроков доставки и использования газа).

Однако в вашем примере с реальным миром («обновление статистики») нет причин, по которым назначения задач / процессов не могут выполняться динамически, что обеспечивает лучший шанс сбалансировать рабочую нагрузку (по всему процессору и с точки зрения сокращения общего времени выполнения). ,

ПРИМЕЧАНИЕ. Я обычно вижу (ИТ) людей, пытающихся предварительно назначить свои задачи (как форму балансировки нагрузки) перед тем, как фактически запускать указанные задачи, и в каждом случае ему / ей приходится постоянно настраивать процесс предварительного назначения, чтобы выполнить его. принимая во внимание постоянно меняющиеся задачи (например, уровень фрагментации в таблице / индексе, одновременная активность пользователей и т. д.).

создать и заполнить таблицу чисел, как вы хотите. Это только один раз.

 create table tblnumber(number int not null)

    insert into tblnumber (number)
    select ROW_NUMBER()over(order by a.number) from master..spt_values a
    , master..spt_values b

    CREATE unique clustered index CI_num on tblnumber(number)

Созданный грузовик стол

CREATE TABLE #PaulWhiteTruck (
Truckid int NOT NULL)

insert into #PaulWhiteTruck
values(113),(203),(303)

declare @PaulTruckCount int
Select @PaulTruckCount= count(*) from #PaulWhiteTruck

CREATE TABLE #OrderDetail (
id int identity(1,1),
OrderId int NOT NULL,
OrderDetailId int NOT NULL PRIMARY KEY,
OrderDetailSize int NOT NULL,
TruckId int NULL
)

INSERT
#OrderDetail (OrderId, OrderDetailId, OrderDetailSize)
VALUES
(
1 ,100 ,75 ),(2 ,101 ,5 ),
(2 ,102 ,5 ),(2 ,103 ,5 ),
(2 ,104 ,5 ),(2 ,105 ,5 ),
(3 ,106 ,100),(4 ,107 ,1 ),
(5 ,108 ,11 ),(6 ,109 ,21 ),
(7 ,110 ,49 ),(8 ,111 ,25 ),
(8 ,112 ,25 ),(9 ,113 ,40 ),
(10 ,114 ,49 ),(11 ,115 ,10 ),
(11 ,116 ,10 ),(12 ,117 ,15 ),
(13 ,118 ,18 ),(14 ,119 ,26 )

Я создал одну OrderSummaryтаблицу

create table #orderSummary(id int identity(1,1),OrderId int ,TruckOrderSize int
,bit_value AS
CONVERT
(
integer,
POWER(2, id - 1)
)
PERSISTED UNIQUE CLUSTERED)
insert into #orderSummary
SELECT OrderId, SUM(OrderDetailSize) AS TruckOrderSize
FROM #OrderDetail GROUP BY OrderId

DECLARE @max integer =
POWER(2,
(
SELECT COUNT(*) FROM #orderSummary 
)
) - 1
declare @Delta int
select @Delta= max(TruckOrderSize)-min(TruckOrderSize)   from #orderSummary

Пожалуйста, проверьте мое значение Delta и дайте мне знать, если это не так

;WITH cte 
     AS (SELECT n.number, 
                c.* 
         FROM   dbo.tblnumber AS N 
                CROSS apply (SELECT s.orderid, 
                                    s.truckordersize 
                             FROM   #ordersummary AS s 
                             WHERE  n.number & s.bit_value = s.bit_value) c 
         WHERE  N.number BETWEEN 1 AND @max), 
     cte1 
     AS (SELECT c.number, 
                Sum(truckordersize) SumSize 
         FROM   cte c 
         GROUP  BY c.number 
        --HAVING sum(TruckOrderSize) between(@Delta-25) and (@Delta+25) 
        ) 
SELECT c1.*, 
       c.orderid 
FROM   cte1 c1 
       INNER JOIN cte c 
               ON c1.number = c.number 
ORDER  BY sumsize 

DROP TABLE #orderdetail 

DROP TABLE #ordersummary 

DROP TABLE #paulwhitetruck 

Вы можете проверить результат CTE1, у него есть все возможное Permutation and Combination of order along with their size.

Если мой подход верен до сих пор, то мне нужна помощь.

Задача в ожидании:

фильтруйте и делите результат CTE1на 3 части ( Truck count) так, что они Orderidуникальны для каждой группы, и каждая часть Т ruckOrderSizeнаходится вблизи дельты.