Search code examples
mathmathematical-optimization

Optimization production list order

I have an optimization problem. The situation is the following: Imagine many boxes (box 1, box 2, box 3, box 4 …). Each one of these boxes needs to be filled with a different combination of items 

Ex:
Box 1 : item B + E
Box 2 : item A + C
Box 3 : item E
Box 4 : item B + C + E + F
….

Each one of these boxes may content up to 6 products. There are around 100 boxes to fill and about 45 different products.

• When an item is treated, all the boxes with this item are filled with it.

• Each item type is treated once only :

• When a box contains one or more items it is “Open”

• When a box contains all of its items, it is “Closed”.

We must find the treatment order that minimizes the average number of open boxes. Ex: 

1.  Items B
2.  Items D
3.  Items A
4.  …

Would give 11 open boxes on average. Sadly, testing all possibilities is not an option. ( 40! = a lot) so we’re looking for a way to formalize the problem and solve it. Any ideas?

I would like to get a list which show me the item productions order

Solution

  • One option would be to address this problem through constraint programming. Below a simple MiniZinc (https://www.minizinc.org) model with a small data set:

    include "globals.mzn";

int: items = 5;
set of int: ITEM = 1..items;
set of int: TIME = 1..items;

int: boxes = 8;
set of int: BOX = 1..boxes;

array[BOX] of set of ITEM: content = [{1}, {1,3}, {1,3,4}, {2,4}, {1,2}, {4}, {1,2,5}, {4,5}];

array[ITEM] of var TIME: time; % which item to treat at which time instant 
array[TIME] of var ITEM: item; % which time instant to treat each item

array[BOX] of var TIME: open = [min([time[i] | i in content[b]]) | b in BOX]; 
array[BOX] of var TIME: close = [max([time[i] | i in content[b]]) | b in BOX]; 

constraint inverse(time, item);

var int: obj = sum(b in BOX)(close[b] - open[b]);

solve minimize obj;

output ["obj = \(obj)\n"] ++ ["item = \(item)\n"] ++ ["open = \(open)\n"] ++ ["close = \(close)\n"]

    This model minimizes the cumulative open time of all the boxes. If you instead want to minimize the maximum time any box is open then change the objective to var int: obj = max(b in BOX)(close[b] - open[b]).

    Edit: To minimize the maximum number of boxes open at any time instant use the following:

    % number of open boxes after each step
array[TIME] of var int: nopen = [sum(b in BOX)(close[b] > t /\ open[b] <= t) | t in TIME];

var int: obj = max(nopen);

    I hope this model can be adapted for you data and that it scales well enough.

    Edit:

    To scale to larger instances you could use a LNS (Large Neighbourhood Search) configuration with the default Gecode solver.

    To do so replace the solve minimize obj; item with:

    % Gecode        
annotation relax_and_reconstruct(array[int] of var int,int);

solve 
:: int_search(item, dom_w_deg, indomain_random, complete) 
:: restart_luby(50)
:: relax_and_reconstruct(item, 80)
minimize obj;

    Another option would be to try another solver. For this model the or-tools-solver (https://developers.google.com/optimization/) seems to work particularly well, especially if configured with more threads (e.g. 8).

    You could also switch to the OsiCbc-solver (provided with the MiniZinc-distribution) and use the following MIP-model:

    include "globals.mzn";

int: items;
set of int: ITEM = 1..items;
set of int: TIME = 1..items;

int: boxes;
set of int: BOX = 1..boxes;

array[BOX] of set of ITEM: content;

array[ITEM, TIME] of var 0..1: x;

array[BOX] of var TIME: open;
array[BOX] of var TIME: close;

constraint forall(i in ITEM)
    (sum(t in TIME)(x[i,t]) = 1);

constraint forall(t in TIME)
    (sum(i in ITEM)(x[i,t]) = 1);

constraint forall(b in BOX, i in content[b])
    (open[b] <= sum(t in TIME)(t*x[i,t]) /\ close[b] >= sum(t in TIME)(t*x[i,t]));

array[BOX] of int: v = [card(content[b]) - 1 | b in BOX];

constraint forall(b in BOX) % redundant constraints
    (close[b] >= open[b] + v[b]);   

var int: obj = sum([close[b] - open[b] | b in BOX]);

solve
minimize obj;

output ["obj = \(obj)\n"] ++ ["item = \([sum(i in ITEM)(i * x[i,t]) | t in TIME])\n"] ++ ["open = \(open)\n"] ++ ["close = \(close)\n"] ++ ["nopen = \([fix(sum(b in BOX)(close[b] > t /\ open[b] <= t)) | t in TIME])\n"];