I'll describe the problem in terms of loading a fixed number of trucks with orders, as evenly as possible.

Inputs:

@TruckCount - the number of empty trucks to fill

A set:

OrderId, 
OrderDetailId, 
OrderDetailSize, 
TruckId (initially null)

Orders are composed of one or more OrderDetails.

The challenge here is to assign a TruckId to each record.

A single order cannot be split across trucks.

Trucks should be as evenly* loaded as possible, measured by sum(OrderDetailSize).

* Evenly: The smallest achievable delta between the least loaded truck and most loaded truck. By this definition, 1,2,3 is more evenly distributed than 1,1,4. If it helps, pretend you are stats algorithm, creating even height histograms.

There is no consideration for maximum truck load. These are magic elastic trucks. The number of trucks however is fixed.

There’s an obviously solution which is iterative - round robin allocate orders.

But can it be done as set based logic?

My main interest is for SQL Server 2014 or later. But set based solutions for other platforms could also be interesting.

This feels like Itzik Ben-Gan territory :)

My real world application is distributing a processing workload into a number of buckets to match the number of logical CPUs. Hence each bucket has no maximum size. Stats updates, specifically. I just thought it was more fun to abstract the problem into trucks as a way of framing the challenge.

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
  • 7
    This looks to be the classic bin packing problem. – Dan Guzman Jul 6 at 11:05
  • 1
    Hugo Kornelis has a good work up on it as well. – sp_BlitzErik Jul 6 at 13:56
  • Will all OrderDetailSize values be equal for a given OrderId or is that just co-incidence in your sample data? – youcantryreachingme Sep 17 at 5:41
  • @youcantryreachingme Ah, good spot... no that's just co-incidence in the sample data. – Paul Holmes Sep 18 at 15:36

My first thought was

select
    <best solution>
from
    <all possible combinations>

The "best solution" part is defined in the question - the smallest difference between the most loaded and least loaded trucks. The other bit - all combinations - caused me pause for thought.

Consider a situation where we have three orders A, B and C and three trucks. The possibilities are

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.

Many of these are symmetric. The first six rows, for example, differ only in which truck each order is placed. Since the trucks are fungible these arrangemets will produce the same outcome. I shall ignore this for now.

There are known queries for producing permutations and combinations. However, these will produce arrangements within a single bucket. For this problem I need arrangements across multiple buckets.

Looking at the output from the standard "all combinations" query

;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.

I noted the results formed the same pattern as Table A. By making the congnitive leap of considering each column to be an Order1, the values to say which truck will hold that Order, and a row to be an arrangement of Orders within trucks. The query then becomes

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.

Expaning this to cover the fourteen Orders in the example data, and simplifying the names we get this:

;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.

I choose to hold the intermediate results in temporary tables for convenience.

Subsequent steps will be much easier if the data is first UNPIVOTED.

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.

Weights can be introduced by joining to the Orders table.

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

The question can now be answered by finding the arrangement(s) which have the smallest difference between most-loaded and least-loaded trucks

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

Discussion

There are a great many problems with this. First it is a brute-force algorithm. The number of rows in the working tables is exponential in the number of trucks and orders. The number of rows in #Arrangements is (number of trucks)^(number of orders). This will not scale well.

Second is that the SQL queries have the number of Orders embedded in them. The only way around this is to use dynamic SQL, which has problems of its own. If the number of orders is in the thousands there may come a time when the generated SQL becomes too long.

Third is the redundancy in the arrangements. This bloats the intermediate tables increasing runtime hugely.

Fourth, many rows in #Arrangements leave one or more trucks empty. This cannot possibly be the optimum configuration. It would be easy to filter out these rows upon creation. I've chosen not to do so to keep the code simpler and focused.

On the up side this handles negative weights, should your enterprise ever start shipping filled helium baloons!

Thoughts

If there were a way to populate #FilledTrucks directly from the list of trucks and Orders I think the worst of these concerns would be managable. Sadly my immagination stumbled on that hurdle. My hope is some future contributor may be able to supply that which eluded me.




1 You say all items for an order must be on the same truck. This means the atom of assignment is the Order, not the OrderDetail. I have generated these from your test data thus:

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

It makes no difference, though, whether we label the items in question 'Order' or 'OrderDetail', the solution remains the same.

Looking at your real world requirement (which I'm assuming is at attempt to balance your workload across a set of cpus) ...

Is there a reason why you need to pre-assign processes to specific buckets/cpus? [Trying to understand your real requirements]

For your example of 'stats updates', how do you know how long a particular operation will take? What if a given operation runs into an unexpected delay (eg, more-than-planned/excessive fragmentation of table/index, long-running user txn blocks a 'stats update' operation)?


For load balancing purposes I typically generate the list of tasks (eg, list of tables to have stats updated) and place said list in a (temporary/scratch) table.

The structure of the table can be modified per your requirements, eg:

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
)

Next I kick off X number of concurrent processes to perform the actual 'stats updates' operations, with each process performing the following:

  • place exclusive lock on the tasks table (ensures no task is picked up by more than one process; should be relatively short-lived lock)
  • find 'first' row where start = NULL ('first' would be determined by you, eg, order by priority?)
  • update row set start = getdate(), thread = <process_number>
  • commit update (and release exclusive lock)
  • make note of id and target/command values
  • perform the desired operation against target (alterntaively, run command) and when done ...
  • update tasks with end = getdate() where id = <id>
  • repeat above until no more tasks to perform

With the above design I've now got a dynamically (mostly) balanced operation.

NOTES:

  • I try to provide some sort of prioritization method so I can kick off the longer running tasks up front; while a couple processes are working on the longer running tasks, the other processes can churn through the list of shorter running tasks
  • if a process runs into an unplanned delay (eg, long-running, blocking user txn), other processes can 'pick up the slack' by continuing to pull the 'next available' operation from tasks
  • the design of the tasks table should provide for other benefits, eg, a history of run times you can archive for future reference, a history of run times that can be used to modify priorities, provide a status of current operations, etc
  • while the 'exclusive lock' on tasks may seem a bit excessive, keep in mind we have to plan for the potential issue of 2 (or more) processes attempting to obtain a new task at the same exact time, so we need to guarantee a task is assigned to only one process (and yes, you can obtain the same results with a combo 'update/select' statement - depending on your RDBMS's SQL language capabilities); the step of obtaining a new 'task' should be quick, ie, the 'exclusive lock' should be short-lived and in reality, processes will be hitting tasks in a fairly random fashion so will be little blocking anyways

Personally, I find this tasks table driven process a bit easier to implement and maintain ... as opposed to a (usually) more complex process of trying to pre-assign task/process mappings ... ymmv.


Obviously for your make believe example you can't have your trucks going back to the distribution/warehouse for the next order, so you need to pre-assign your orders to various trucks (keeping in mind that UPS/Fedex/etc also have to assign based on delivery routes in order to reduce delivery times and gas usage).

However, in your real world example ('stats update') there's no reason why the task/process assignments can't be done dynamically thus ensuring a better chance of balancing out the workload (across cpus and in terms of reducing overall run time).

NOTE: I routinely see (IT) folks trying to pre-assign their tasks (as a form of load balancing) before actually running said tasks, and in every case s/he ends up having to constantly tweak the pre-assignment process to take into consideration constantly varying task issues (eg, level of fragmentation in table/index, concurrent user activity, etc).

  • Firstly, if we think of 'order' as table, and 'orderdetail' as a specific statistic on the table, then the reason for not splitting is to avoid lock waits between competing buckets. Traceflag 7471 is designed to eliminate this issue, but in my testing I still had locking issues. – Paul Holmes Sep 18 at 15:45
  • I'd originally hoped to make a very lightweight solution. Create the buckets as singular multistatement SQL blocks, and then 'fire and forget' each using self destructing SQL Agent jobs. i.e. no Queue management work. However, subsequently I found I couldn't easily measure the volume of work per statistic - number of rows didn't cut it. Not surprising really, given that rowcount doesn't map linearly to the amount of IO from one table, or indeed stastic, to the next. So yes, for this application, it could indeed self balance with addition of some active queue management as you suggest. – Paul Holmes Sep 18 at 15:46
  • To your first comment ... yeah, there's still the (obvious) decision on granularity of commands ... and concurrency issues like: can some commands be run in parallel and benefit from their combined disk reads, etc. But I still find a (somewhat light) dynamic queue management a bit more efficient than pre-assigning buckets :-) You've got a good set of answers/ideas to work with ... shouldn't be too hard to come up with a solution that provides some decent load balancing. – markp Sep 18 at 16:22

create and populate number table as you wish.This is one time creation only.

 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)

Created Truck table

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 )

I have created one OrderSummary Table

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

Please check my Delta value and let me know if it is wrong

,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

You can check the result of CTE1 , it has all possible Permutation and Combination of order along with their size.

If my approach is correct till here,then I need somebody help.

Pending Task :

filter and Divide result of CTE1 in to 3 part (Truck count) such that Orderid is unique among each group and each part TruckOrderSize is near to Delta.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.