Foire algorithme de distribution des produits

Question

Voici mon problème:

• Il y a n entreprises de distribution produits.
• Tous les produits doivent être distribués dans les jours k
• Acheminer des produits de la société Ci devraient être consécutifs - cela signifie qu'il peut être distribué sur les jours 2,3,4,5 mais pas 2,3,6,7
• nombre de produits distribués par société Ci le jour j devrait être inférieur (ou égal) le jour J-1 (s'il y en avait le jour j-1)
• différence entre les produits distribués entre les jours i et j ne doit pas être supérieure à 1

Exemple:

Nous avons 3 jours pour distribuer des produits. Produits de la société A: a, a, a, a, a. Produits de la société B: b, b, b. Produits de la société C: c, c

Distribution équitable: [AAB, AABC, abc]

Distribution non valide: [AABC, AABC, ab] parce que le 1er jour il y a 4 produits, le 3 jour 2 produits (différence> 1)

Distribution non valide: [abc, AABC, AAB] parce que le 1er jour il y a un produit A, et le 2ème jour il y a 2 produits A, si la distribution du produit A ne pas en baisse

EDIT s'il y a un cas qui rend impossible une répartition équitable s'il vous plaît fournir avec brève description, je vais accepter la réponse

Answer 1

commentaire de Gareth Rees sur la réponse de djna est juste - le contre qui suit est impossible à résoudre:

• 3 jours, 7 articles de la société A et 5 articles de la société B

J'ai testé cela avec le programme Perl de force brute le plus stupide qui soit (qui prend bien moins d'une seconde , En dépit d'être très inefficace):

my ($na, $nb) = (7, 5); 
for (my $a1 = 0; $a1 <= $na; ++$a1) { 
    for (my $a2 = 0; $a2 <= $na - $a1; ++$a2) { 
     my $a3 = $na - $a1 - $a2; 
     for (my $b1 = 0; $b1 <= $nb; ++$b1) { 
      for (my $b2 = 0; $b2 <= $nb - $b1; ++$b2) { 
       my $b3 = $nb - $b1 - $b2; 
       if ($a1 >= $a2 && $a2 >= $a3 || $a1 == 0 && $a2 >= $a3 || $a1 == 0 && $a2 == 0) { 
        if ($b1 >= $b2 && $b2 >= $b3 || $b1 == 0 && $b2 >= $b3 || $b1 == 0 && $b2 == 0) { 
         if (max($a1 + $b1, $a2 + $b2, $a3 + $b3) - min($a1 + $b1, $a2 + $b2, $a3 + $b3) <= 1) { 
          print "Success! ($a1,$a2,$a3), ($b1,$b2,$b3)\n"; 
         } 
        } 
       } 
      } 
     } 
    } 
} 

S'il vous plaît un coup d'oeil et vérifier que je ne l'ai pas fait d'erreurs stupides. (J'ai omis max() et min() pour la brièveté - ils font juste ce que vous attendez.)

Answer 2

Je ne Je pense que vous pouvez toujours répondre à vos exigences.

Tenir compte 4 jours et 6 articles de fournisseur A et 6 articles de fournisseur B.

Answer 3

Il a été démontré que les points 4 et 5 étaient incompatibles:

• 4: Pour tout j jour, pour toute entreprise A, C (j, A) == 0 ou C (j, A)> = C (j + 1, A)
• 5: Pour les jours i et j, |C(i) - C(j)| <= 1

Vous avez besoin ainsi de détente soit contrainte. Honnêtement, alors que j'ai une idée de pourquoi 4 a été mis en place (pour éviter de retarder indéfiniment la distribution d'une entreprise) je pense qu'il pourrait être exprimé autrement de considérer le premier et dernier jour de distribution comme spécial (puisque le premier jour , vous prenez généralement ce qui reste de l'entreprise précédente et le dernier jour vous distribuez ce qui reste).

Le point 3 force la contiguïté.

Mathématiquement:

Pour toute entreprise A, qui a des produits, il existe deux jours i et j tels que:

• C (i, A)> 0 et C (j, A) > 0
• pour chaque jour x tel que x < i ou x> j, C (x, A) = 0
• pour chaque jour x tel que i < x < j, C (x, A) = C (x)

Certes, le problème devient alors trivial à résoudre :)

Answer 4

Depuis que je pensais que le problème était amusant, je l'ai fait un modèle pour trouver des solutions utilisant MiniZinc. Avec le backend Gecode, l'exemple initial montre 20 solutions en environ 1,6 ms.

include "globals.mzn"; 

%%% Data 
% Number of companies 
int: n = 3; 
% Number of products per company 
array[1..n] of int: np = [5, 3, 2]; 
% Number of days 
int: k = 3; 

%%% Computed values 
% Total number of products 
int: totalnp = sum(np); 
% Offsets into products array to get single companys products 
% (shifted cumulative sum). 
array[1..n] of int: offset = [sum([np[j] | j in 1..i-1]) 
          | i in 1..n]; 

%%% Predicates 
predicate fair(array[int] of var int: x) = 
     let { var int: low, 
      var int: high 
     } in 
     minimum(low, x) /\ 
     maximum(high, x) /\ 
     high-low <= 1; 
predicate decreasing_except_0(array[int] of var int: x) = 
     forall(i in 1..length(x)-1) (
       (x[i] == 0) \/ 
       (x[i] >= x[i+1]) 
     ); 
predicate consecutive(array[int] of var int: x) = 
     forall(i in 1..length(x)-1) (
      (x[i] == x[i+1]) \/ 
      (x[i] == x[i+1]-1) 
     ); 

%%% Variables 
% Day of production for all products from all companies 
array[1..totalnp] of var 1..k: products 
      :: is_output; 
% total number of products per day 
array[1..k] of var 1..totalnp: productsperday 
     :: is_output; 

%%% Constraints 
constraint global_cardinality(products, productsperday); 
constraint fair(productsperday); 
constraint 
    forall(i in 1..n) (
     let { 
      % Products produced by company i 
      array[1..np[i]] of var int: pi 
       = [products[j] | 
       j in 1+offset[i]..1+offset[i]+np[i]-1], 
      % Products per day by company i 
      array[1..k] of var 0..np[i]: ppdi 
     } in 
      consecutive(pi) /\ 
      global_cardinality(pi, ppdi) /\ 
      decreasing_except_0(ppdi) 
    ); 

%%% Find a solution, default search strategy 
solve satisfy; 

Les prédicats decreasing_except_0 et consecutive sont à la fois très naïf, et ont de grandes décompositions. Pour résoudre des instances plus grandes, il faut probablement les remplacer par des variantes plus intelligentes (par exemple en utilisant la contrainte normale).