# Bin Packing with CP Solver

[   [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)):
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.

• I'm not sure I understand your problem. (1) what does [time start, duration] in your data mean? Does this mean that you have a task that must start on some machine at the given start time? Or is it a release time, indicating that the task can start any time after its release and must run for the given duration? (2) when exactly do you need the cool down? After every task? Or after every 14 minutes? Please polish your problem description. Commented Aug 27, 2021 at 20:38
• @JorisKinable Could you please check now if I managed to ask my query more efficiently. Commented Aug 29, 2021 at 3:24

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.

• Yes, it is variant of Constrained Resource/ Job Shop but I was going through solution and founded that Bins are assigned tasks without completing task assigned to them earlier. There can only be 1 task/bin in time space. For Ex: Bin 1 is assigned Task2/7/13. Task2 starts at 00:01 and ends at (00:01+6 minutes) ie 00:07 whereas Task7 starts at 00:05 which violates precedence order(I guess that's what it's called when you can't work on task without finishing prior Task. So if Bin1 is assigned Task2[1,6] then without cooling it can be assigned Task9[7,3]. Commented Sep 1, 2021 at 5:06
• Also can you hint on how we can model this using OR or other tools because it creates Bins on fly and assign Tasks in accordance to constraints like checking for 14 minutes and providing cooldown and again search for Tasks to assign and so on. Commented Sep 1, 2021 at 5:19
• @user3237357, I think you have listed the tasks from $0$ till $13$ while I listed them from $1$ till $14$ and this is why you found a violation. Is it correct? Commented Sep 1, 2021 at 6:31
• @user3237357, for your second comment, I think if you can use a heuristic method you would have the flexibility and simplicity to model and optimize your problem. :) Commented Sep 1, 2021 at 6:35
• @user3237357, for the first one, I tried Mixed-integer programming and for the second I used a simple random selection heuristic. I hope it will be useful. :) Commented Sep 1, 2021 at 12:48