SQL Oracle - Multiprocessor Scheduling: Greedy Number Partitioning

Question

Is there an SQL statement to perform greedy number partitioning? (Oracle 19c)

I want to divide jobs among N processors.

Example,

Given the following workload data set:

job
---
4
60
50
1
100
6

Expected result set (assuming just N=2 where ties go to the processor with the fewest number of jobs assigned to it):

job  processor
---  ---------
100  1
 60  2
 50  2
  6  1
  4  1
  1  2 

The following table may help clarify how those processors were assigned.

job  processor  length  count
---  ---------  ------  -----
100  1          100     1
 60  2           60     1
 50  2          110     2
  6  1          106     2
  4  1          110     3
  1  2          111     3

Some combination of analytic functions and hierarchical queries seems like it could make this happen without having to resort to procedural code. Thanks in advance for your thoughts and assistance.

Answer 1

You can use a recursive CTE:

with tt as (
      select job, row_number() over (order by job desc) as seqnum
      from t
     ),
     cte(job, seqnum, processor, proc1, proc2, lev) as (
      select job, seqnum, 1, job as proc1, 0 as proc2, 1
      from tt
      where seqnum = 1
      union all
      select tt.job, tt.seqnum,
             (case when cte.proc1 > cte.proc2 then 2 else 1 end),
             (case when cte.proc1 > cte.proc2 then cte.proc1 else cte.proc1 + tt.job end),
             (case when cte.proc1 > cte.proc2 then cte.proc2 + tt.job else cte.proc2 end),
             lev + 1
      from cte join
           tt
           on tt.seqnum = cte.seqnum + 1
     )
select *
from cte
order by seqnum;

Here is a db<>fiddle.