Défi de requête: création de compartiments de taille égale, basés sur une mesure et non sur le nombre de lignes

Je décrirai le problème en termes de chargement d'un nombre fixe de camions avec des commandes, aussi uniformément que possible.

Contributions:

@TruckCount - the number of empty trucks to fill

Un ensemble:

OrderId, 
OrderDetailId, 
OrderDetailSize, 
TruckId (initially null)

Orderssont composés d'un ou plusieurs OrderDetails.

Le défi ici est d'attribuer un TruckIdà chaque enregistrement.

Une seule commande ne peut pas être répartie entre plusieurs camions.

Les camions doivent être aussi uniformément chargés que possible, mesurés par sum(OrderDetailSize).

* Également: le plus petit delta réalisable entre le camion le moins chargé et le camion le plus chargé. Selon cette définition, 1,2,3 est plus uniformément distribué que 1,1,4. Si cela vous aide, faites comme si vous étiez un algorithme de statistiques, créant des histogrammes de hauteur égale.

Il n'y a aucune considération pour la charge maximale du camion. Ce sont des camions élastiques magiques. Le nombre de camions est cependant fixe.

Il existe évidemment une solution itérative: le tournoi à la ronde alloue les commandes.

Mais peut-il être fait comme une logique basée sur un ensemble?

Mon intérêt principal est pour SQL Server 2014 ou version ultérieure. Mais des solutions basées sur des ensembles pour d'autres plates-formes pourraient également être intéressantes.

Cela ressemble au territoire d'Itzik Ben-Gan :)

Mon application réelle distribue une charge de travail de traitement dans un certain nombre de compartiments pour correspondre au nombre de CPU logiques. Par conséquent, chaque seau n'a pas de taille maximale. Mises à jour des statistiques, en particulier. Je pensais juste que c'était plus amusant de résumer le problème dans les camions comme un moyen de cadrer le défi.

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

Ma première pensée a été

select
    <best solution>
from
    <all possible combinations>

La partie «meilleure solution» est définie dans la question - la plus petite différence entre les camions les plus chargés et les moins chargés. L'autre morceau - toutes les combinaisons - m'a fait réfléchir.

Prenons une situation où nous avons trois commandes A, B et C et trois camions. Les possibilités sont

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.

Beaucoup d'entre eux sont symétriques. Les six premières lignes, par exemple, ne diffèrent que par le camion dans lequel chaque commande est passée. Étant donné que les camions sont fongibles, ces arrangements produiront le même résultat. Je vais ignorer cela pour l'instant.

Il existe des requêtes connues pour produire des permutations et des combinaisons. Cependant, ceux-ci produiront des arrangements dans un seul seau. Pour ce problème, j'ai besoin d'arrangements sur plusieurs compartiments.

Examen de la sortie de la requête standard "toutes combinaisons"

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

J'ai noté que les résultats formaient le même schéma que le tableau A. En faisant le saut congnitif de considérer chaque colonne comme un ordre ¹ , les valeurs pour dire quel camion contiendra cet ordre, et une ligne pour être un arrangement des ordres dans les camions. La requête devient alors

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.

En étendant cela pour couvrir les quatorze ordres dans les données d'exemple, et en simplifiant les noms, nous obtenons ceci:

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

Je choisis de conserver les résultats intermédiaires dans des tableaux temporaires pour plus de commodité.

Les étapes suivantes seront beaucoup plus faciles si les données sont d'abord 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.

Les poids peuvent être introduits en se joignant à la table Commandes.

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

Il est maintenant possible de répondre à la question en trouvant le ou les arrangements qui présentent la plus petite différence entre les camions les plus chargés et les moins chargés

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

Il y a beaucoup de problèmes avec cela. C'est d'abord un algorithme de force brute. Le nombre de lignes dans les tables de travail est exponentiel dans le nombre de camions et de commandes. Le nombre de lignes dans #Arrangements est (nombre de camions) ^ (nombre de commandes). Cela n'évolue pas bien.

Deuxièmement, les requêtes SQL contiennent le nombre de commandes incorporées. Le seul moyen de contourner ce problème est d'utiliser le SQL dynamique, qui a ses propres problèmes. Si le nombre de commandes est dans les milliers, il peut arriver un moment où le SQL généré devient trop long.

Troisièmement, la redondance des dispositions. Cela gonfle énormément les tables intermédiaires, ce qui augmente considérablement l'exécution.

Quatrièmement, de nombreuses lignes dans #Arrangements laissent un ou plusieurs camions vides. Cela ne peut pas être la configuration optimale. Il serait facile de filtrer ces lignes lors de la création. J'ai choisi de ne pas le faire pour garder le code plus simple et ciblé.

Du côté positif, cela gère les poids négatifs, si votre entreprise devait commencer à expédier des ballons d'hélium remplis!

Pensées

S'il y avait un moyen de remplir #FilledTrucks directement à partir de la liste des camions et des commandes, je pense que la pire de ces préoccupations serait gérable. Malheureusement, mon imagination a trébuché sur cet obstacle. J'espère qu'un futur contributeur pourra peut-être fournir ce qui m'a échappé.

¹ Vous dites que tous les articles d'une commande doivent se trouver sur le même camion. Cela signifie que l'atome d'affectation est l'Ordre, pas l'OrdreDétail. J'ai généré ceux-ci à partir de vos données de test ainsi:

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

Cela ne fait aucune différence, que nous étiquetions les articles en question «Commande» ou «CommandeDétail», la solution reste la même.

En regardant vos besoins réels (qui, je suppose, visent à équilibrer votre charge de travail sur un ensemble de processeurs) ...

Y a-t-il une raison pour laquelle vous devez pré-affecter des processus à des compartiments / processeurs spécifiques? [Essayer de comprendre vos besoins réels ]

Pour votre exemple de «mise à jour des statistiques», comment savez-vous combien de temps prendra une opération particulière? Que se passe-t-il si une opération donnée rencontre un retard inattendu (par exemple, une fragmentation de la table / de l'index plus que prévu / excessive, l'utilisateur txn de longue durée bloque une opération de «mise à jour des statistiques»)?

À des fins d'équilibrage de charge, je génère généralement la liste des tâches (par exemple, la liste des tables pour lesquelles les statistiques sont mises à jour) et je place cette liste dans une table (temporaire / temporaire).

La structure de la table peut être modifiée selon vos besoins, par exemple:

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
)

Ensuite, je lance X nombre de processus simultanés pour effectuer les opérations de mise à jour des statistiques, chaque processus effectuant les opérations suivantes:

• placer un verrou exclusif sur la taskstable (garantit qu'aucune tâche n'est récupérée par plus d'un processus; devrait être un verrou de courte durée)
• trouver la «première» ligne où start = NULL(«la première» serait déterminée par vous, par exemple, commander par priority?)
• mettre à jour l'ensemble de lignes start = getdate(), thread = <process_number>
• valider la mise à jour (et libérer le verrou exclusif)
• noter idet target/commandvaleurs
• effectuer l'opération souhaitée contre target(alternativement, exécuter command) et une fois terminé ...
• mettre tasksà jour avecend = getdate() where id = <id>
• répéter ci-dessus jusqu'à ce qu'il n'y ait plus de tâches à effectuer

Avec la conception ci-dessus, j'ai maintenant une opération équilibrée dynamiquement (principalement).

REMARQUES:

• J'essaie de fournir une sorte de méthode de priorisation afin de pouvoir lancer les tâches les plus longues à l'avance; tandis que quelques processus travaillent sur les tâches les plus longues, les autres processus peuvent parcourir la liste des tâches plus courtes
• si un processus rencontre un retard imprévu (par exemple, un long terme, bloquant l'utilisateur txn), d'autres processus peuvent «prendre le relais» en continuant à tirer l'opération «prochaine disponible» de tasks
• la conception de la taskstable doit fournir d'autres avantages, par exemple, un historique des temps d'exécution que vous pouvez archiver pour référence future, un historique des temps d'exécution qui peut être utilisé pour modifier les priorités, fournir un état des opérations en cours, etc.
• Bien que le `` verrouillage exclusif '' taskspuisse sembler un peu excessif, gardez à l'esprit que nous devons planifier le problème potentiel de 2 (ou plus) processus tentant d'obtenir une nouvelle tâche en même temps , nous devons donc garantir une tâche est affecté à un seul processus (et oui, vous pouvez obtenir les mêmes résultats avec une instruction combinée «mise à jour / sélection» - selon les capacités du langage SQL de votre SGBDR); l'étape d'obtention d'une nouvelle «tâche» devrait être rapide, c'est-à-dire que le «verrou exclusif» devrait être de courte durée et en réalité, les processus se produiront tasksde manière assez aléatoire et seront donc peu bloquants de toute façon

Personnellement, je trouve ce tasksprocessus piloté par table un peu plus facile à mettre en œuvre et à maintenir ... par opposition à un processus (généralement) plus complexe d'essayer de pré-assigner des mappages de tâches / processus ... ymmv.

Évidemment, pour votre exemple imaginaire, vous ne pouvez pas faire revenir vos camions à la distribution / entrepôt pour la prochaine commande, vous devez donc pré-affecter vos commandes à divers camions (en gardant à l'esprit qu'UPS / Fedex / etc. doivent également attribution en fonction des itinéraires de livraison afin de réduire les délais de livraison et la consommation de gaz).

Cependant, dans votre exemple réel (`` mise à jour des statistiques ''), il n'y a aucune raison pour que les affectations de tâches / processus ne puissent pas être effectuées de manière dynamique, ce qui garantit une meilleure chance d'équilibrer la charge de travail (sur tous les processeurs et en termes de réduction du temps d'exécution global) .

REMARQUE: je vois régulièrement des personnes (IT) essayer de pré-assigner leurs tâches (comme une forme d'équilibrage de charge) avant d'exécuter lesdites tâches, et dans tous les cas, il / elle finit par devoir constamment ajuster le processus de pré-affectation pour prendre en tenant compte des problèmes de tâches qui varient constamment (par exemple, le niveau de fragmentation dans la table / l'index, l'activité simultanée des utilisateurs, etc.).

créer et remplir la table des nombres comme vous le souhaitez. Il s'agit d'une création unique.

 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)

Table de camion créée

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 )

J'ai créé une OrderSummarytable

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

Veuillez vérifier ma valeur Delta et faites-moi savoir si elle est erronée

;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 

Vous pouvez vérifier le résultat de CTE1, tout est possible Permutation and Combination of order along with their size.

Si mon approche est correcte jusqu'ici, alors j'ai besoin de l'aide de quelqu'un.

Tâche en attente:

filtrer et diviser le résultat de CTE1dans à 3 parties ( Truck count) de telle sorte qu'elles Orderidsoient uniques parmi chaque groupe et chaque partie T ruckOrderSizeest proche de Delta.