Оптимизация производственного списка заказов

Question

У меня проблема с оптимизацией.Ситуация следующая: представьте себе много коробок (блок 1, блок 2, блок 3, блок 4…).Каждый из этих полей должен быть заполнен различными комбинациями элементов

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

Каждый из этих полей может содержать до 6 товаров.Есть около 100 коробок для заполнения и около 45 различных продуктов.

• Когда предмет обрабатывается, все ящики с этим предметом заполняются им.

• Каждый тип элемента обрабатывается только один раз:

• Если ящик содержит один или несколько элементов, он «открыт»

• Когда ящик содержит все свои элементы, это «Закрыто».

Мы должны найти порядок обработки, который минимизирует среднее количество открытых коробок.Например:

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

Дало бы в среднем 11 открытых коробок.К сожалению, тестирование всех возможностей не вариант.(40! = Много), поэтому мы ищем способ формализовать проблему и решить ее.Любые идеи?

Я хотел бы получить список, который показывает мне порядок производства предметов

Answer 1

Один из вариантов - решить эту проблему с помощью программирования ограничений.Ниже представлена ​​простая модель MiniZinc (https://www.minizinc.org) с небольшим набором данных:

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"]

. Эта модель минимизирует совокупное время открытия всех ящиков. Если вы вместо этого хотите минимизировать максимальное время любого ящикаоткрыт, затем измените цель на var int: obj = max(b in BOX)(close[b] - open[b]).

Редактировать: Чтобы свести к минимуму максимальное количество открытых ящиков в любое время, используйте следующее:

% 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);

Я надеюсь, что эта модель может быть адаптирована для ваших данных и что она достаточно хорошо масштабируется.

Редактировать:

Для масштабирования в более крупные экземпляры вы можете использовать LNS (Large Neighborhood)Поиск) в конфигурации с решателем по умолчанию Gecode.

Для этого замените элемент solve minimize obj; на:

% 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;

Другой вариант - использовать другой решатель. Для этой моделиor-tools -сольвер (https://developers.google.com/optimization/), кажется, работает особенно хорошо, особенно если сконфигурировано с большим количеством потоков (например, 8).

Вы также можете переключиться на OsiCbc -сольвер (поставляется сMiniZinc-дистрибутив) и используйте следующий MIP-модель:

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"];