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

Question

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 itemsDay1-box2-3 itemsDay1-box3-2 itemsDay2-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.

Toine · Accepted Answer

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 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 jYou could use one of the following formulations:Formulation 1Indicator constraint t(j) - t(i) >= p(i), with Activating condition d(i,j) = 1d(i,j) + d(j,i) = 1Formulation 2t(j) >= sumd(i,j) + d(j,i) = 1d(i,j) + d(j,k) + d(k,i) <= 2Formulation 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

Reply

Sign up

Login to the community

Scanning file for viruses.

This file cannot be downloaded