Algorithmus - teilt Ordner Gruppen

Question

ich für einen Algorithmus bin auf der Suche um eine optimale Lösung für das folgende Problem zu finden:

I N Ordner mit Dateien in ihnen.

Ich möchte sie in Y-Gruppen so arrangieren, dass der Unterschied in der Anzahl der Dateien zwischen den Gruppen minimal ist.

Zum Beispiel:

• folder1: 1 Datei
• folder2: 1 Datei
• Ordner3: 4 Dateien
• Folder4: 7 Dateien.

für 2 Gruppen, die optimale Lösung ist:

• Konzern1: folder1, folder2, Folder3 (insgesamt 6-Dateien)
• Group2: Folder4 (insgesamt 7 Dateien)

Answer 1

Anscheinend ist das Problem, das Sie beschreiben, makespan minimization on identical parallel machines, wobei Y die Nummer m der Maschinen ist und die Anzahl der Dateien in einem Ordner die Bearbeitungszeit p_i für jeden darstellen i in {1,...,n} Dabei steht n für die Anzahl der Ordner. Es ist bekannt, dass das Problem NP-hard ist, aber several approximation algorithms wurde gefunden. Unter Verwendung der three-field-notation wird dieses Problem als P || Cmax bezeichnet, wenn m Teil der Eingabe ist und Pm || Cmax, wenn m eine Konstante ist.