Open Stacks

From CometPublic

Contents 1 Problem 1.1 Example 2 Model 3 Search 3.1 Basic search 3.2 getSwapDelta method 3.3 Improved search 4 GUI 4.1 Initialisation 4.2 Refreshing 4.3 getSwapDelta modification 5 Results 6 Links

[edit] Problem

A manufacturer has a number of orders from customers to satisfy; each order is for a number of different products, and only one product can be made at a time. Once a customer's order is started (i.e. the first product in the order has been made) a stack is created for that customer. When all the products that a customer requires have been made, the order is sent to the customer, so that the stack is closed. Because of limited space in the production area, the number of stacks that are in use simultaneously i.e. the number of customer orders that are in simultaneous production, should be minimized.

More formally: we are given a Boolean matrix in which the columns correspond to the products required by the customers and each row corresponds to the order of a particular customer. The entry c_ij = 1 iff customer i has ordered some quantity of product j (the quantity ordered is irrelevant). The objective is to find a permutation of the products such that the maximum number of open orders at any point in the sequence is minimized: order i is open at point k in the production sequence if there is a product required in order i that appears at or before position k in the sequence and also a product that appears at or after position k in the sequence.

[edit] Example

	Slot1	Slot2	Slot3	Slot4
	P1	P2	P3	P4
O1	1	0	1	1
O2	0	1	0	1
O3	1	0	1	0

On this example, we can see that the maximum number of open stacks is 3. Indeed, the stack of order 1 opens in slot 1 and closes in slot 4; the stack of order 2 opens in slot 2 and closes in slot 4; the stack of order 3 opens in slot 1 and closes in slot 3. We have 2 open stacks in slot 1 and slot 4, and 3 open stacks in slot 2 and slot 3, so the maximum number of open stacks is 3.

	Slot1	Slot2	Slot3	Slot4
	P4	P2	P3	P1
O1	1	0	1	1
O2	1	1	0	0
O3	0	0	1	1

Assume now that we swap product 1 and product 4. In this configuration, the stack of order 1 opens in slot 1 and closes in slot 4; the stack of order 2 opens in slot 1 and closes in slot 2; the stack of order 3 opens in slot 3 and closes in slot 4. At each slot, 2 stacks are open, so the maximum number of open stacks is 2, which is the optimum. [P4, P2, P3, P1] is thus one of the possible optimal solutions.

[edit] Model

// products's variables that contain positions
var{int}[] prodVars;
// opening positions of the stack of each order
var{int}[] openedStacks;
// closing positions of the stack of each order
var{int}[] closedStacks;
// number of open stacks for each position
var{int}[] nbOpenStacks;
// maximum number of open stacks
var{int} maxNbOpenStacks
// iterator for the search
var{int} it;

m = new LocalSolver();
RandomPermutation perm(Slots);
prodVars = new var{int}[Products](m, Slots) := perm.get();

openedStacks = new var{int}[o in Orders](m) <- min(p in Products: requires[o, p]) (prodVars[p]);
closedStacks = new var{int}[o in Orders](m) <- max(p in Products: requires[o, p]) (prodVars[p]);
nbOpenStacks = new var{int}[p in Products](m) <- sum(o in Orders) (openedStacks[o] <= prodVars[p] && closedStacks[o] >= prodVars[p]);
maxNbOpenStacks = new var{int}(m) <- max(p in Products) (nbOpenStacks[p]);

it = new var{int}(m) := 0;

m.close();

The prodVars table contains the decision variables : each variable is a product such that prodVars[i] represents the ith product. The values contained in these variables are the positions of the products, that are randomly assigned the first time.

The three following tables contains variables to obtain useful information on the problem at each moment. They are moreover assigned by invariants such that the three table are always consistent with the prodVars variables.

openedStacks contains the opening positions of the stack of each order. More formally : for an order o, openedStacks[o] contains the minimum position of a set of product p such o requires p.

openedStacks contains the closing positions of the stack of each order. More formally : for an order o, openedStacks[o] contains the maximum position of a set of product p such o requires p.

nbOpenStacks contains the number of open stacks for each position in the production sequence. maxNbOpenStacks is just the maximum of this table, which the value that we want minimize.

Finally, "it" is not useful for the problem itself. It's only declared as integer variable for graphical purpose (see graphical section for more details).

[edit] Search

[edit] Basic search

while(it < maxIterations) {
	// choose the product p1 such that its position contains the maximum number of open stacks
	select (p1 in Products: nbOpenStacks[p1] == maxNbOpenStacks) {
		// choose the product p2 such that the swap with p1 minimizes the maximum number of open stacks
		selectMin (p2 in Products: p1 != p2) (getSwapDelta(p1, p2))
			prodVars[p1] :=: prodVars[p2];
	++it;
}

The problem of open stacks is an optimization problem. The basis algorithm is very simple : a product such that its position contains the present maximum number of open stacks is firstly choosen. A second product such that the swap with the first one minimizes the number of open stacks (deltas are computed by the getSwapDelta method) is then choosen. The two products are finally swapped. This operation is repeated maxIterations times.

[edit] getSwapDelta method

int getSwapDelta (int p1, int p2) {
       // present number of maximum number of open stacks
       int max1 = maxNbOpenStacks;
       // expected number of maximum number of open stacks if the position of p1 and p2 are swapped
       int max2 = lookahead(m, maxNbOpenStacks) { prodVars[p1] :=: prodVars[p2]; };
       return max2 - max1;
}

The getSwapDelta function returns the difference between the present maximum number of open stacks (max1) and the expected maximum of open stacks if the positions of the products p1 and p2 were exchanged. A best solution would be to compute incrementally this result, but we unfortunately didn't found such an algorithm.

[edit] Improved search

// number of iterations during which the second product won't be choosen
int tabuLength = nbProducts/3;
// for each product, iteration number under which the product is forbidden
int tabu[Products] = 0;
// number of iterations since the maximum number of open stacks didn't change
int nbItOfSameMaxOpenStacks = 0;
// maximum number of open stacks considered during the previous iteration
int previousNbOpenStacks = nbOrders;

while(it < maxIterations && nbItOfSameMaxOpenStacks < maxItForSameMaxOpenStacks) {
   // choose the product p1 such that its position contains the maximum number of open stacks
   select (p1 in Products: nbOpenStacks[p1] == maxNbOpenStacks) {
      // refresh the stop criterion if the maximum number of open stacks changes
      if (nbOpenStacks[p1] != oldNbOpenStacks){
         itForSameMaxOpenOrdersNumber = 0;
         oldNbOpenStacks = nbOpenStacks[p1];
      }

      //choose the product such that the swap with p1 minimizes the maximum number of open stacks
      selectMin (p2 in Products: p1 != p2 && tabu[p2] <= it) (getSwapDelta(p1, p2)) {
         prodVars[p1] :=: prodVars[p2];
         tabu[p2] = it + tabuLength;
      }
   }
   ++nbItOfSameMaxOpenStacks;
   ++it;
}

Some features have been added to the original search algorithm.

Firstly the tabu component. Each product is associated with a tabu number that prevent the selectMin to choose a product if this one was already choosen during one of the last tabuLength iterations. It permits to avoid falling in local minimas.

Secondly a stop criterion. Because the optimal iterations number is not know at the beginning, the algorithm iterates maxIterations times. Unfortunately, it is often an unappropriate bound because the algorithm quickly converges to the minimum number of open stacks and then needlessly iterates during a long time. The variable nbItOfSameMaxOpenStacks is there to avoid this: this is a second iterator that iterates up to the maxItForSameMaxOpenStacks and that is set up to zero each time the maximum of open stacks changes. So it forces the algorithm to stop when maxItForSameMaxOpenStacks iterations are done for a same maximum number of open stacks.

Note that here the best solution during the search is not stored anywhere. See the entire source code for this.

[edit] GUI

You can take on a look on the graphical interface here. The meaning of the differents colors is explained below.

[edit] Initialisation

//gets the entire visualization window
CometVisualizer cv();  

//get the main component of the entire visualization window (that already contains buttons)
Visualizer visu = cv.getVisualizer();

//declaration of the first widget which contains the problem grid
VisualHBox hb1(visu,"Visualisation");
//declaration of the problem grid
VisualTextTable vtt = cv.getTextTable("vtt",0..nbOrders,0..nbProducts);
//adds the grid to the visualization widget
hb1.packStart(vtt);
//adds the visualisation widget to the upper part of the visualizer in a new tab
visu.addNotebookPage(hb1);

//declaration of the second widget which displays some useful data on the problem
VisualHBox hb2(visu,"Search");
//declaration of the board widget which is the component that contains the different labels
VisualVBox vba(visu,"Board"); 
//declaration of a final label displayed in the board
VisualLabel labelMaxNbOpenStacks(visu,"Maximum number of open stacks");
//declaration of a label that can be dynamically refreshed (displays the data)
VisualEntry entryMaxNbOpenStacks(visu,"");
//adds the 2 labels to the board
vba.packStart(labelMaxNbOpenStacks);
vba.packStart(entryMaxNbOpenStacks);
//adds the board to hb2
hb2.packStart(vba);
//adds hb2 to the bottom of the visualizer in a new tab
visu.addBottomNotebookPage(hb2); 

//declaration of the third widget which displays some useful statistics on the algorithm
VisualHBox hb3(visu,"Statistics");
//declaration of the board widget which is the component that contains the different labels
VisualVBox vbs(visu,"Board");
//declaration of a final label displayed in the board
VisualLabel labelIterations(visu,"Iterations")
//declaration of a label that can be dynamically refreshed (displays the statistics)
VisualEntry entryIterations(visu,"");
//adds the 2 labels to the board
vbs.packStart(labelIterations);
vbs.packStart(entryIterations);
//adds the board to hb3
hb3.packStart(vbs);
//adds hb3 to the bottom of the visulizer in a new tab
visu.addBottomNotebookPage(hb3);

//initialisation of the colors and the labels of the grid
forall(p in Products)
	vtt.setColor(0,p+1,"green");
forall(o in Orders) {
	vtt.setLabel(o+1,0,o+1);
	vtt.setColor(o+1,0,"green");
} 

The first part of the graphical interface is its declaration and initialisation. The GUI is composed by three tabs : the first one contains the grid that represents the open stacks problem; the second one contains a label which gives at each moment the maximum number of open stacks; the third one gives some statistics on the current iterations number.

To build this interface, the first thing to do is to import the "visu" class which contains a lot of interesting methods useful this purpose.

The GUI declaration begins to retrieve the main component of the visualization windows on which a lot of component will be added.

It builds then the first widget, in wich the grid representing the problem is added. The widget is finally added to the main visualization component in a new tab.

The two next widgets are builded in the same way : two labels are defined and added in a board component which is itself added to the widgets. The widgets are then added to the main component in new tabs.

The green column number represents the numbers of the orders. The green and yellow line numbers represents the numbers of products (with their position number just above in gray).

[edit] Refreshing

// at each iteration, the GUI is refreshed so that it is consistent with the search
whenever it@changes(int o, int n){
   // displays the current number of iterations in the expected label
   entryIterations.setInt(n);
   int maxNbOpenOrders = max(p in Products) (nbOpenStacks[p]);
   // displays the maximum number open stacks in the expected label
   entryMaxNbOpenStacks.setInt(maxNbOpenOrders);

   forall(p in Products) {
      // replace the old product number holded in the position of p by the number of p
      vtt.setLabel(0,prodVars[p]+1,p+1);
      // if the position of p contains the current maximum number of open stacks, the products p is colored in yellow, else in green
      if(nbOpenStacks[p] == maxNbOpenOrders)
         vtt.setColor(0,prodVars[p]+1,"yellow");
      else
         vtt.setColor(0,prodVars[p]+1,"green");  

      forall(o in Orders)
         if (requires[o,p])
            // recolor in red the intersection between o and the position of p if o requires p
            vtt.setColor(o+1,prodVars[p]+1,"red");			
         else
            //recolor in orange the intersection between o and the position of p if o the stack of o is opened at this position and that o doesn't require p else recolor the case in gray 
            if (openedStacks[o] <= prodVars[p] && closedStacks[o] >= prodVars[p]) 
               vtt.setColor(o+1,prodVars[p]+1,"orange");
            else
               vtt.setColor(o+1,prodVars[p]+1,"gray");
   }

   visu.getStatusBar().setColor("yellow");
   visu.getStatusBar().setText("Stepping...Click run to continue");
   // when the table is refreshed, wait for the click on the run button to continue
   sleepUntil visu.getRunButton()@clicked();
   visu.getStatusBar().pop();
}

// wait for each position change for all product
forall(p in Products)
   foreveron prodVars[p]@changes() {
      if(it>0) {
         // if a product's position change, it is colored in blue before the entire grid is refreshed
         vtt.setColor(0,prodVars[p]+1,"blue");
         visu.getStatusBar().setColor("yellow");
         visu.getStatusBar().setText("Stepping...Click run to continue");
         // when the table is refreshed, wait for the click on the run button to continue
         sleepUntil visu.getRunButton()@clicked();
         visu.getStatusBar().pop();
      }
   }

For practical reasons, we chose to implement an iterative mode for the graphical interface. That's to say that the algorithm stops between each execution step and wait for a user's action (click on the run button).

The GUI waits for two differents event types : an iterator change and a product's position change.

When the iterator changes, all the grid representing the problem is refreshed : the product's numbers are changed so that they corresponds to their new position. The product's cases are also colored in yellow for the products with a position which is correspond to a maximum number of open stack. The other product's cases are colored in green. The cases at the intersection of an order o and o product p such that o requires p are colored in red. The cases at the intersection of an order o and a product p such that o doesn't require p and such that the stack of o in opened at the position p are colored in orange. The oter cases are colored in gray. The new number of iterations and the new maximum number of open stacks are refreshed in their expected label.

When a product's position change, the GUI colors the case which contains the product's number in blue. It gives the possibility to observe which variables are chosen by the search to be swapped.

[edit] getSwapDelta modification

int getSwapDelta (int p1, int p2) {
	// present number of maximum number of open stacks
	int max1 = maxNbOpenStacks;

	// copy of the products variables
	int newProdVars[Products];
	forall(p in Products)
		newProdVars[p] = prodVars[p]; 

	// swap of the two positions of the products in the copy
	newProdVars[p1] = prodVars[p2];
	newProdVars[p2] = prodVars[p1];
	
	// recreation of the tables containing the opening and closing positions for each order
	int newOpenedStacks[o in Orders] = min(p in Products:requires[o, p]) (newProdVars[p]);
	int newClosedStacks[o in Orders] = max(p in Products:requires[o, p]) (newProdVars[p]); 

	// expected number of maximum number of open stacks if the position of p1 and p2 are swapped
	int max2 = max(p in Products) (sum(o in Orders) (newOpenedStacks[o] <= prodVars[p] && newClosedStacks[o] >= prodVars[p]) ); 

	return max2 - max1;
}

The getSwapDelta function previously introduced is unfortunately not appropriate when the GUI is launched. Indeed in the previous version, the evaluation of max2 by lookahead construct causes the swap of product's variables. It represents a problem for the GUI because as explained above, it waits for such an event to refresh the next product choosen by the algorithm (colored in blue). This effect is of course underisable because each variable will be colored one time during the evaluation of the best second product minimizing the maximum number of open stacks. To avoid this problem, the getSwapDelta function is changed such that it doesn't make any modification on the model's variables.

[edit] Results

The problems considered are available at the following links : problems_10_10_35, problems_10_20_35, challenge_set

Here are five tested instances. All final results are known thans to a constraint model.

The data are the following : each instance has been tested 10 times and for 2 different conditions, one with the tabu component (tabuLength=nbProducts/3) and another one whithout the tabu component; the maximum number of iterations for a same maximum number of open stacks needed can vary following the problem and is indicated. The results must be interpreted as following : firstly the number of iterations used to find the solution; secondly two different times : the first indicates the time used by the algorithm to converge to a first good solution, the second is the time of resolution for the final solution found.

• Random instance BMS, number 1 (10,10,35)
  • Tabu = yes, maxItForSameMaxOpenStacks = 50 : 56 iterations, 19/131 ms
  • Tabu = no, maxItForSameMaxOpenStacks = 50 : 52 iterations, 8/152 ms

• Random instance BMS, number 2 (10,10,35)
  • Tabu = yes, maxItForSameMaxOpenStacks = 50 : 72 iterations, 48/167 ms
  • Tabu = no, maxItForSameMaxOpenStacks = 50 : 61 iterations, 8/185 ms

• Random instance BMS, number 6 (10,20,35)
  • Tabu = yes, maxItForSameMaxOpenStacks = 50 : 108 iterations, 64/540 ms
  • Tabu = no, maxItForSameMaxOpenStacks = 50 : 57 iterations, 52/638 ms

• Random instance BMS, number 7 (10,20,35)
  • Tabu = yes, maxItForSameMaxOpenStacks = 100 : 134 iterations, 309/1170 ms
  • Tabu = no, maxItForSameMaxOpenStacks = 100 : 137 iterations, 414/1540 ms

• Warwick 311: balanced products (10,30)
  • Tabu = yes, maxItForSameMaxOpenStacks = 100 : 157 iterations, 1038/2803 ms
  • Tabu = no, maxItForSameMaxOpenStacks = 100 : 199 iterations, 2475/4966 ms

We can see that for little problems, the number of iterations and the time to converge to a first solution are better without tabu component. However this observation doesn't hold with bigger problems. The second observation that we can make is that the total time to find the final solution is always better when a tabu component is added.

[edit] Links

- The entire source code in Comet is available here: Open Stacks (source code)

- This problem was the subject of the first Constraint Modelling Challenge (2005): http://www.dcs.st-and.ac.uk/%7Eipg/challenge/