Tantangan kueri: Membuat ember berukuran rata, berdasarkan ukuran bukan jumlah baris

Saya akan menjelaskan masalah dalam hal memuat sejumlah truk dengan pesanan, serata mungkin.

Input:

@TruckCount - the number of empty trucks to fill

Satu set:

OrderId, 
OrderDetailId, 
OrderDetailSize, 
TruckId (initially null)

Ordersterdiri dari satu atau lebih OrderDetails.

Tantangannya di sini adalah untuk menetapkan a TruckIduntuk setiap catatan.

Satu pesanan tidak dapat dibagi di truk.

Truk harus sama rata * dimuat sebanyak mungkin, diukur dengan sum(OrderDetailSize).

* Merata: Delta terkecil yang dapat dicapai antara truk dengan muatan paling sedikit dan truk dengan muatan terbanyak. Dengan definisi ini, 1,2,3 lebih merata daripada 1,1,4. Jika itu membantu, anggaplah Anda adalah algoritma statistik, buat bahkan histogram ketinggian.

Tidak ada pertimbangan untuk muatan truk maksimum. Ini adalah truk elastis ajaib. Namun jumlah truk sudah diperbaiki.

Jelas ada solusi yang berulang - round robin mengalokasikan pesanan.

Tetapi dapatkah hal itu dilakukan sebagai logika berbasis set?

Minat utama saya adalah untuk SQL Server 2014 atau lebih baru. Tetapi menetapkan solusi berbasis untuk platform lain juga bisa menarik.

Ini terasa seperti wilayah Itzik Ben-Gan :)

Aplikasi dunia nyata saya mendistribusikan beban kerja pemrosesan ke sejumlah ember agar sesuai dengan jumlah CPU logis. Karenanya setiap ember tidak memiliki ukuran maksimum. Statistik pembaruan, khususnya. Saya hanya berpikir lebih menyenangkan untuk mengabstraksi masalah menjadi truk sebagai cara membingkai tantangan.

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

Pikiran pertama saya adalah

select
    <best solution>
from
    <all possible combinations>

Bagian "solusi terbaik" didefinisikan dalam pertanyaan - perbedaan terkecil antara truk paling banyak dimuat dan paling sedikit dimuat. Bit lain - semua kombinasi - membuat saya berhenti untuk berpikir.

Pertimbangkan situasi di mana kami memiliki tiga pesanan A, B dan C dan tiga truk. Kemungkinannya adalah

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.

Banyak dari ini simetris. Enam baris pertama, misalnya, hanya berbeda di mana truk setiap pesanan ditempatkan. Karena truk dapat difungsikan, pengaturan ini akan menghasilkan hasil yang sama. Saya akan mengabaikan ini untuk saat ini.

Ada pertanyaan yang diketahui untuk menghasilkan permutasi dan kombinasi. Namun, ini akan menghasilkan pengaturan dalam satu ember. Untuk masalah ini saya perlu pengaturan lintas beberapa ember.

Melihat output dari kueri "semua kombinasi" standar

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

Saya mencatat hasil membentuk pola yang sama seperti Tabel A. Dengan membuat lompatan kongnitif dengan mempertimbangkan setiap kolom sebagai Pesanan ¹ , nilai - nilai untuk mengatakan truk mana yang akan memegang Pesanan itu, dan baris untuk menjadi pengaturan Pesanan dalam truk. Kueri kemudian menjadi

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.

Membentang ini untuk mencakup empat belas Pesanan dalam data contoh, dan menyederhanakan nama-nama yang kita dapatkan ini:

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

Saya memilih untuk menyimpan hasil antara dalam tabel sementara untuk kenyamanan.

Langkah-langkah selanjutnya akan jauh lebih mudah jika data tersebut terlebih dahulu 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.

Bobot dapat diperkenalkan dengan bergabung ke tabel Pesanan.

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

Pertanyaannya sekarang dapat dijawab dengan menemukan pengaturan yang memiliki perbedaan terkecil antara truk yang paling banyak memuat dan yang paling sedikit memuat

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

Diskusi

Ada banyak masalah dengan ini. Pertama adalah algoritma brute-force. Jumlah baris dalam tabel kerja eksponensial dalam jumlah truk dan pesanan. Jumlah baris dalam #Arrangements adalah (jumlah truk) ^ (jumlah pesanan). Ini tidak akan skala dengan baik.

Kedua adalah bahwa kueri SQL memiliki jumlah Pesanan yang tertanam di dalamnya. Satu-satunya cara untuk mengatasi ini adalah dengan menggunakan SQL dinamis, yang memiliki masalah sendiri. Jika jumlah pesanan dalam ribuan mungkin ada saatnya ketika SQL yang dihasilkan menjadi terlalu panjang.

Ketiga adalah redundansi dalam pengaturan. Ini menggembungkan tabel perantara meningkatkan runtime sangat.

Keempat, banyak baris di #Arrangements membiarkan satu atau lebih truk kosong. Ini tidak mungkin konfigurasi optimal. Akan mudah untuk menyaring baris-baris ini pada saat penciptaan. Saya memilih untuk tidak melakukannya agar kode lebih sederhana dan fokus.

Di sisi atas ini menangani bobot negatif, jika perusahaan Anda pernah mulai mengirim balon helium diisi!

Pikiran

Jika ada cara untuk mengisi #FilledTrucks langsung dari daftar truk dan Pesanan, saya pikir yang terburuk dari masalah ini adalah dapat dikelola. Sayangnya imaginasi saya tersandung pada rintangan itu. Harapan saya adalah beberapa kontributor di masa depan mungkin dapat memasok apa yang luput dari saya.

¹ Anda mengatakan semua item untuk pesanan harus di truk yang sama. Ini berarti atom penugasan adalah Orde, bukan OrderDetail. Saya telah menghasilkan ini dari data pengujian Anda sebagai berikut:

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

Namun, tidak ada bedanya, apakah kita memberi label pada item yang dimaksud 'Pesanan' atau 'PesananDetail', solusinya tetap sama.

Melihat kebutuhan dunia nyata Anda (yang saya asumsikan adalah upaya untuk menyeimbangkan beban kerja Anda di satu set CPU) ...

Apakah ada alasan mengapa Anda perlu menetapkan proses ke bucket / cpus tertentu? [Mencoba untuk memahami Anda nyata kebutuhan ]

Sebagai contoh Anda 'pembaruan statistik', bagaimana Anda tahu berapa lama operasi tertentu akan memakan waktu? Bagaimana jika operasi tertentu mengalami keterlambatan yang tak terduga (misalnya, fragmentasi tabel / indeks yang lebih dari yang direncanakan / berlebihan, pengguna yang sudah berjalan lama dapat memblokir operasi 'pembaruan statistik')?

Untuk tujuan penyeimbangan beban, saya biasanya membuat daftar tugas (misalnya, daftar tabel agar statistik diperbarui) dan menempatkan daftar kata dalam tabel (sementara / awal).

Struktur tabel dapat dimodifikasi sesuai kebutuhan Anda, misalnya:

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
)

Selanjutnya saya memulai sejumlah X proses bersamaan untuk melakukan operasi 'pembaruan statistik' yang sebenarnya, dengan setiap proses melakukan hal berikut:

• letakkan kunci eksklusif di jendela tasks meja (memastikan tidak ada tugas yang diambil oleh lebih dari satu proses; harus berupa kunci yang berumur pendek)
• temukan baris 'pertama' di mana start = NULL('pertama' akan ditentukan oleh Anda, mis. dipesan oleh priority?)
• perbarui set baris start = getdate(), thread = <process_number>
• melakukan pembaruan (dan melepaskan kunci eksklusif)
• membuat catatan iddan target/commandnilai - nilai
• melakukan operasi yang diinginkan terhadap target(secara alternatif, jalankan command) dan ketika selesai ...
• perbarui tasksdenganend = getdate() where id = <id>
• ulangi di atas sampai tidak ada lagi tugas yang harus dilakukan

Dengan desain di atas, saya sekarang memiliki operasi yang seimbang (sebagian besar) secara dinamis.

CATATAN:

• Saya mencoba memberikan semacam metode prioritas sehingga saya dapat memulai tugas yang lebih lama berjalan di depan; sementara beberapa proses bekerja pada tugas yang berjalan lebih lama, proses lainnya dapat mengaduk daftar tugas yang berjalan lebih pendek
• jika suatu proses mengalami penundaan yang tidak direncanakan (mis. berjalan lama, memblokir pengguna txn), proses lain dapat 'mengambil kelonggaran' dengan terus menarik operasi 'berikutnya yang tersedia' dari tasks
• desain taskstabel harus memberikan manfaat lain, misalnya, sejarah waktu proses yang dapat Anda arsipkan untuk referensi di masa mendatang, riwayat waktu proses yang dapat digunakan untuk memodifikasi prioritas, memberikan status operasi saat ini, dll.
• sementara 'penguncian eksklusif' tasksmungkin tampak sedikit berlebihan, perlu diingat bahwa kami harus merencanakan kemungkinan masalah 2 (atau lebih) proses yang berusaha untuk mendapatkan tugas baru pada waktu yang sama , jadi kami perlu menjamin tugas ditugaskan hanya untuk satu proses (dan ya, Anda dapat memperoleh hasil yang sama dengan pernyataan 'pembaruan / pilih' kombo - tergantung pada kemampuan bahasa SQL RDBMS Anda); langkah mendapatkan 'tugas' baru harus cepat, yaitu, 'kunci eksklusif' harus berumur pendek dan dalam kenyataannya, proses akan memukul taskssecara acak sehingga akan sedikit menghalangi lagian

Secara pribadi, saya menemukan tasksproses yang didorong tabel ini sedikit lebih mudah untuk diimplementasikan dan dipertahankan ... sebagai lawan dari proses (biasanya) yang lebih kompleks dalam mencoba untuk menetapkan tugas / pemetaan proses ... ymmv.

Tentunya untuk contoh percaya Anda, Anda tidak dapat meminta truk Anda kembali ke distribusi / gudang untuk pesanan berikutnya, jadi Anda perlu menetapkan pesanan terlebih dahulu ke berbagai truk (perlu diingat bahwa UPS / Fedex / dll juga harus menetapkan berdasarkan rute pengiriman untuk mengurangi waktu pengiriman dan penggunaan gas).

Namun, dalam contoh dunia nyata Anda ('pembaruan statistik') tidak ada alasan mengapa tugas / proses tugas tidak dapat dilakukan secara dinamis sehingga memastikan peluang yang lebih baik untuk menyeimbangkan beban kerja (lintas CPU dan dalam hal mengurangi waktu berjalan keseluruhan) .

CATATAN: Saya secara rutin melihat (IT) orang-orang yang mencoba melakukan pra-penugasan tugas-tugas mereka (sebagai bentuk load balancing) sebelum benar-benar menjalankan tugas-tugas tersebut, dan dalam setiap kasus ia akhirnya harus terus-menerus mengubah proses pra-penugasan untuk mengambil mempertimbangkan berbagai masalah tugas yang terus-menerus (mis., tingkat fragmentasi dalam tabel / indeks, aktivitas pengguna bersamaan, dll).

buat dan isi tabel angka sesuai keinginan. Ini hanya satu kali pembuatan.

 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)

Meja truk dibuat

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 )

Saya telah membuat satu OrderSummaryTabel

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

Silakan periksa nilai Delta saya dan beri tahu saya jika itu salah

;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 

Anda dapat memeriksa hasil CTE1, semuanya memungkinkan Permutation and Combination of order along with their size.

Jika pendekatan saya benar sampai di sini, maka saya butuh bantuan seseorang.

Tugas Tertunda:

saring dan Bagi hasil CTE1menjadi 3 bagian ( Truck count) sedemikian rupa sehingga Orderidunik di antara setiap kelompok dan setiap bagian T ruckOrderSizedekat dengan Delta.