Bin Packing with CP Solver

Question

[   [0,5],
    [0,4],
    [1,6],
    [2,4],
    [3,6],
    [3,2],
    [4,5],
    [5,5],
    [6,4],
    [7,3],
    [8,2],
    [8,3],
    [9,5],
    [10,3]]

Representation of Data is as Follows: [Time Start(minutes_of_day),Time Duration(minutes)] These are daily tasks that needs to be assigned to machines. Once we have kind of roster so as which machine will perform which tasks, we'll schedule these tasks and our job is done. We just need best roster that how many machines will be utilized and which task will be performed by which machine. For that I'm RnDing a model. Here Time Start depicts time that is 0 considered as first minute of day(00:00) and so on and Time Duration is duration of task from time it starts so [0,5] means task will start at 0th minute of day that is at 00:00 and will end at 00:05.

I have n-number of machines which only works 30 minutes max a day and when their run time starts when they start first task assigned to them, One machine can continue for 14 minutes at stretch needs 3 minutes cooldown break. 14 minutes is a limit and machine can not exceed 14 minutes. It's like IntVar(0,14) if I'm not wrong. But since we have discrete tasks we need to assign multiple tasks in continuation and for that I need arc which store tasks assigned to machine and check for cumulative duration of these tasks as total duration should not exceed 14 minutes. For cooldown assignment, if say we assign two tasks in an arc that totals to 10 minutes, we'll give cooldown after both tasks end and next set of tasks will be assigned after minimum of 3 minutes, this cooldown timer can extend to any length/duration but 3 is minimum.

So how can I create bin of 30 minutes and within bin arc of 14 minutes and assign tasks and provide cooldown whenever machine finishes tasks assigned. Tasks that needs to be assigned should have no break between them, they should be continuous. For ex, if machine-1 is assigned [0,5] then next task can only be [5,5] and it can continue for [10,3] too if feasible but we want balanced works to be assigned to machines.

There are such thousands of tasks and enough machines to complete work but we need feasible solution that is balanced out without giving major portion of work to few machines and rest machines sitting idle.

One method I thought was making one bin per task as our variable. Then looping through each bin and assign tasks and when tasks are emptied discarding remaining bins.

I need help in modelling using CP-Solver and not Bin-Packing(MPsolver). I've gone through OR-Tools examples but I'm lost so if anyone could help..!

EDIT----------

from ortools.linear_solver import pywraplp

# Creates the model.
model = cp_model.CpModel()

data =[[0,5],
    [0,4],
    [1,6],
    [2,4],
    [3,6],
    [3,2],
    [4,5],
    [5,5],
    [6,4],
    [7,3],
    [8,2],
    [8,3],
    [9,5],
    [10,3]]

# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')
    
# Creates the variables
i=0
bins = []
total = 0
binused = 0
for d in data:
    bins.append([d[0],d[0]+30])
    i=i+1
    

# Variables
# x[b, d] = 1 if item d is packed in bin b.
x = {}
for b in range(len(bins)):
    for d in range(len(data)):
        x[(b, d)] = solver.IntVar(0, 1, 'x_%i_%i' % (b, d))
        
# y[b] = 1 if bin b is used.
y = {}
for b in range(len(bins)):
    y[b] = solver.IntVar(0, 1, 'y[%i]' % b)
 

# Constraints
# Each item must be in exactly one bin.
for d in range(len(data)):
    solver.Add(sum(x[b, d] for b in range(len(bins))) == 1)

# The amount packed in each bin cannot exceed its capacity.
for b in range(len(bins)):
    solver.Add(
        sum(x[(b, d)] * data[d][1] for d in range(len(data))) <= y[b] *
        14)

for b in range(len(bins)):
    for d in range(len(data)):
        solver.Add(x[b,d] * data[d][0]  <= bins[b][0] )

    
# Objective: minimize the number of bins used.
solver.Minimize(solver.Sum([y[b] for b in range(len(bins))]))


status = solver.Solve()

if (status == pywraplp.Solver.OPTIMAL) or (status == pywraplp.Solver.FEASIBLE)  :
    num_bins = 0
    for b in range(len(bins)):
        if y[b].solution_value() == 1:
            bin_items = []
            bin_weight = 0
            for d in range(len(data)):
                if x[b, d].solution_value() > 0:
                    bin_items.append(data[d])
                    bin_weight += data[d][1]
            if bin_weight > 0:
                num_bins += 1
                print('Bin number', b)
                print('Bin',bins[b])
                print('  Items packed:', bin_items)
                print('  Total weight:', bin_weight)
                print()
    print()
    print('Number of bins used:', num_bins)
    print('Time = ', solver.WallTime(), ' milliseconds')
else:
    print('The problem does not have an optimal solution.')

OUTPUT-----

Bin number 0
Bin [0, 30]
  Items packed: [[0, 5], [0, 4]]
  Total weight: 9

Bin number 5
Bin [3, 33]
  Items packed: [[1, 6], [2, 4]]
  Total weight: 10

Bin number 6
Bin [4, 34]
  Items packed: [[3, 6], [3, 2], [4, 5]]
  Total weight: 13

Bin number 9
Bin [7, 37]
  Items packed: [[5, 5], [6, 4], [7, 3]]
  Total weight: 12

Bin number 13
Bin [10, 40]
  Items packed: [[8, 2], [8, 3], [9, 5], [10, 3]]
  Total weight: 13


Number of bins used: 5
Time =  49  milliseconds

I've modelled this much after seeing some examples and lil bit RnD. Now how I model tasks to be continuous and non-overlapping in nature. Secondly, solver.Add(x[b,d] * data[d][0] <= bins[b][0] ) this constraint is working but logically it should be >= bins[b][0] but with this constraint it can't find optimal/feasible solution. And lastly how to model for cooldown.

Answer 1

If I understand the problem correctly, it might be modeled as a variant of the resource-constrained project schedule in which you have some parallel machines and the tasks should be performed with some limitation. From the above-given data, some noisy things should be considered.

• First, limiting the start time of a task by being started from the same point in the planning horizon would cause overlap between the tasks. it means finding a feasible solution by any kind of solvers, (MILP, CP, etc), would be challenging work.
• Second, executing the tasks far from the planning horizon beginning point might decrease resource efficiency.
• Third, you would need to recalculate a specific number of resources by a bit change in the data that lead to manipulating the final solution. That is not suitable.

As a solution for the above problem please, see the following picture:

In this case, we need almost six bins/resources. The efficiency of resources number $4$, $5$, and $6$ are very low. Also, there is an overlap between tasks $11$ and $12$ on the last resource which comes from the noisy data.

Indeed, another way might be using a heuristic algorithm but, I doubt it can produce a better solution. The result of the naive one is as follows:

• Resource $1$: $\text{\{j1, j8, j14, cooling}\}$
• Resource $2$: $\text{\{j2, j7, j13}\}$
• Resource $3$: $\text{\{j3, j10}\}$
• Resource $4$: $\text{\{j4, j9}\}$
• Resource $5$: $\text{\{j5}\}$
• Resource $6$: $\text{\{j6, j11}\}$
• Resource $7$: $\text{\{j12}\}$

I hope it will be helpful.