Solved

# How to write a constraint to process all the items in a box

• 58 views

+2
• Enthusiast

Dear Team,

I am facing one problem while writing a constraint. Let's say, I have three boxes with several items. Say box 1 has 4 items, box 2 has 6 items and box 3 has 9 items. I am processing the items day wise considering time as a constraint. I want that, if I am selecting a particular box, I will process all the items of that box 1st then will move to the next box. What I am getting that

Day1-box1- 2 items

Day1-box2-3 items

Day1-box3-2 items

Day2-box1-2 items.

I do not want it. I want, choose a box on day 1, process all the 4 items based on the available time. I have written a constraint to handle it, which is like

sum[d, v(d, boxnumber)] >= p_items(boxnumber) - v_Penalty(boxnumber)

It means, I am trying to get the item number in a box while minimizing the penalty in the objective function.

Kindly help if I am doing anything wrong.

icon

Best answer by Toine 18 April 2024, 11:13

View original

Hi RwitamJ,

The problem you are describing can be modeled as a single-machine scheduling problem.

Basically, you are scheduling the processing of the boxes, where the processing time is the sum of the processing times of the items in the box.

b(i,a) := processing time of item a in box i [note: it could be that in your model each item has the same processing time, the given formulation is more general]
p(i)    := processing time of box i, this is equal to sum[a, b(i,a)]
t(i)     := non-negative starting time of box i [for example, time measured in hours from the beginning of the first day]
d(i,j)  := binary variable, d(i,j) = 1 if box i is processsed before box j

You could use one of the following formulations:

Formulation 1
Indicator constraint t(j) - t(i) >= p(i), with Activating condition d(i,j) = 1
d(i,j) + d(j,i) = 1

Formulation 2
t(j) >= sum[i | i <> j, p(i) * d(i,j)]
d(i,j) + d(j,i) = 1
d(i,j) + d(j,k) + d(k,i) <= 2

Formulation 1 has the advantage that it contains less constraints than formulation 2. The advantage of the second formulation is that it has a better LP-relaxation.

To find out on which day a certain item a is processed:
Take the starting time t(i) of a box and add to that the processing times items of all items in the box that come before item a. Then, we can calculate on which day this starting time occurs and we will know on which day the item is processed.

Some questions:
How many items can be processed on a day? Is this different depending on the box/day?

I hope this helps. Kind regards,

Toine