Fusionner des tâches sans chevauchement

Question

Dans mon cas d'utilisation, j'ai différentes séries de tâches qui doivent être accomplies dans un ordre spécifique en fonction de la situation. Supposons que j'aie trois cas à traiter. Au lieu de répéter le même travail pour chaque cas, je devrais pouvoir intégrer les tâches communes à tous les cas et ne les exécuter qu'une seule fois. La fusion doit se faire sans empiéter sur les tâches déjà fusionnées. Mon cas d'utilisation et le résultat escompté sont décrits dans le diagramme ci-dessous.

Entrée

Résultats attendus

Les tâches A, B et C sont communes à tous les cas de ce diagramme. La tâche B, en revanche, ne sera pas fusionnée car elle chevauchera la tâche A, qui est déjà fusionnée. Quelqu'un pourrait-il suggérer un algorithme pour implémenter ceci dans un projet Java ?

Answer 1

Ce billet sera long, mais j'essaierai de le rendre aussi facile à comprendre que possible. N'hésitez pas à me faire savoir dans les commentaires si vous souhaitez que je corrige ou clarifie quelque chose.

Code source : https://github.com/asinkxcoswt/stackoverflow-merge-task-lcs

Analyse du problème

Selon votre explication, nous avons 3 séquences de tâches non répétitives et non ordonnées. Les séquences peuvent être "fusionnées" de manière à ce que certaines tâches communes puissent être exécutées ensemble afin de réduire le temps et les ressources. Mais en général, il y a plusieurs façons de fusionner. Il s'agit de trouver la méthode qui donne les meilleurs résultats en termes de

• Points de fusion maximums possibles
• Exécution parallèle maximale possible
• Le plus petit nombre d'étapes à exécuter au total

Cela peut être considéré comme un problème d'optimisation dans lequel vous essayez de minimiser la coût de ressources y durée .

• ressources (étapes) : le nombre d'étapes doit être le plus faible possible, ce qui a la même signification que le "nombre maximal de points de fusion" (car plus vous fusionnez de tâches, moins vous avez d'étapes). Il peut s'agir du nombre de cases carrées dans l'image lorsque chaque tâche est utilisée. resources = 1 .

• durée Je pense que vous voulez une "exécution parallèle maximale", mais je trouve que la façon de la mesurer n'est pas très claire. Je suppose donc que vous voulez que les tâches soient effectuées aussi rapidement que possible, ce qui signifie que vous voulez minimiser la durée totale, qui peut être le nombre de lignes horizontales dans l'image lorsque chaque ligne représente duration = 1 .

Vous pouvez observer que l'état de l'entrée (avant la fusion) est celui où vous avez déjà le minimum de durée (exécution parallèle maximale), mais un maximum de ressources . Cela signifie que notre algorithme de fusion ne peut faire que deux choses.

1. (Mauvais) Faire le durée d'augmenter ou de rester inchangée.
2. (Bon) Faire le ressources diminuer ou rester identiques.

En d'autres termes, nous allons réduire la ressources au prix d'un allongement de la durée des tâches. Nous ne pouvons pas déterminer quelle est la meilleure solution tant que nous n'avons pas défini l'objectif final. coût en fonction de ces deux facteurs. Par exemple, certains préfèrent disposer d'un minimum de ressources, quelle que soit la durée, tandis que d'autres ont des préférences différentes.

• coût Pour des raisons de simplicité, j'utiliserai ici, à titre d'exemple, la définition suivante cost = resources * duration qui peut être considéré comme l'argent que vous payez pour resources nombre de travailleurs par la duration ils fonctionnent.

• objectif : Le but de cette optimisation est donc de trouver la manière de fusionner 3 séquences de tâches qui donne le coût minimum = resources * duration

Aperçu de la solution

La nature de ce problème est très similaire à celle du problème bien connu des Plus longue séquence commune (LCS) . Nous pouvons dire que chaque résultat de fusion possible correspond à une sous-séquence commune des trois listes de tâches. Mais contrairement au problème LCS, nous ne pouvons pas dire que la plus longue est la meilleure pour nous. Au lieu de cela, nous devons trouver toutes les sous-séquences communes possibles et calculer leur cost puis choisir celui qui a le moins de cost .

Implémentation

Infrastructure du code

Avant de parler en détail du LCS, traduisons d'abord le problème en code.

Tâche

Une tâche est une unité qui contient le duration y resources que nous allons optimiser. Il s'agit généralement d'un run() pour définir ce qu'elle est censée faire. La méthode id est là parce que nous devons les identifier et les mettre sur un pied d'égalité. Ici, si 2 tâches ont la même id Je les traiterai comme une seule et même tâche.

abstract class Task {
    public abstract String id();
    public abstract void run();
    public abstract int duration();
    public abstract int resources();
    public int cost() {
        return this.duration() * this.resources();
    };

     /**
     * Just a convenient method to create a task with a one-liner
     */
    static Task of(String id, int duration, int resource, Runnable execution) {
        return new Task() {
            @Override
            public void run() {
                execution.run();
            }

            @Override
            public int duration() {
                return duration;
            }

            @Override
            public int resources() {
                return resource;
            }

            @Override
            public String id() {
                return id;
            }
        };
    }
}

C'est ainsi que les tâches sont préparées. Veuillez noter que chaque tâche est créée avec resources=1 y duration=1 mais vous pouvez les modifier à votre guise.

    public static void main(String[] args) {
        Task A = Task.of("A",1, 1, () -> System.out.println("I'm task A"));
        Task B = Task.of("B",1, 1, () -> System.out.println("I'm task B"));
        Task C = Task.of("C",1, 1, () -> System.out.println("I'm task C"));
        Task D = Task.of("D",1, 1, () -> System.out.println("I'm task D"));
        Task E = Task.of("E",1, 1, () -> System.out.println("I'm task E"));
        Task U = Task.of("U",1, 1, () -> System.out.println("I'm task U"));
        Task W = Task.of("W",1, 1, () -> System.out.println("I'm task W"));
        Task X = Task.of("X",1, 1, () -> System.out.println("I'm task X"));
        Task Y = Task.of("Y",1, 1, () -> System.out.println("I'm task Y"));
        Task Z = Task.of("Z",1, 1, () -> System.out.println("I'm task Z"));

        Task[] case1 = new Task[] {A,B,C,D,E};
        Task[] case2 = new Task[] {W,B,A,U,C,E};
        Task[] case3 = new Task[] {B,X,Y,Z,E,A,C};
    }

ParallelTask

A ParallelTask prend des listes de tâches en nombre arbitraire. Ses run() exécute toutes les listes de tâches en parallèle. Mais chaque tâche d'une liste spécifique est toujours exécutée dans l'ordre. Elle agrège également les duration y resources de ses tâches sous-jacentes. Les duration d'une tâche parallèle sera égale à la duration de la liste la plus longue. Alors que les resources est la simple somme de toutes les tâches resources .

class ParallelTask extends Task {
    private final String id;
    private final Task[][] taskSequences;
    ParallelTask(String id, Task[] ... taskSequences) {
        this.id = id;
        this.taskSequences = taskSequences;
    }

    @Override
    public void run() {
        Arrays.stream(this.taskSequences).parallel().forEach(taskSeq -> {
            Arrays.stream(taskSeq).forEach(Task::run);
        });
    }

    @Override
    public int duration() {
        IntStream eachSequenceTotalDuration = Arrays.stream(this.taskSequences).mapToInt(
                taskSeq -> Arrays.stream(taskSeq).mapToInt(Task::duration).sum()
        );

        return eachSequenceTotalDuration.max().orElse(0);
    }

    @Override
    public int resources() {
        IntStream eachSequenceTotalResources = Arrays.stream(this.taskSequences).mapToInt(
                taskSeq -> Arrays.stream(taskSeq).mapToInt(Task::resources).sum()
        );

        return eachSequenceTotalResources.sum();
    }

    @Override
    public String id() {
        return this.id;
    }
}

Coût initial

Vous pouvez exécuter le code de suivi et constater que le coût initial (avant fusion) est de 126 .

public static void main(String[] args) {

    ... init tasks ...

    Task[] case1 = new Task[] {A,B,C,D,E};
    Task[] case2 = new Task[] {W,B,A,U,C,E};
    Task[] case3 = new Task[] {B,X,Y,Z,E,A,C};

    Task p = new ParallelTask("INITIAL_SOLUTION", case1, case2, case3);
    // p.run(); // <-- try this if you want
    System.out.println(p.cost()); // <-- 126
}

Rapport complet

Pour plus de commodité, ajoutons une méthode permettant d'imprimer le rapport complet afin d'afficher les éléments suivants cost , duration , resources et la manière dont les tâches sont organisées.

class ParallelTask extends Task {
    ... other methods ...

    public void report(boolean showSummary) {
        if (showSummary) {
            System.out.println("------------------------");
            System.out.println("TASK " + this.id() + " (COST " + this.cost() + ", DURATION " + this.duration() + ", RESOURCES " + this.resources() + ")");
            System.out.println("------------------------");
        }

        int l = Arrays.stream(this.taskSequences).mapToInt(taskSeq -> taskSeq.length).max().orElse(0);
        for (int j = 0; j < l; j ++) {
            for (int i = 0; i < this.taskSequences.length; i++) {
                if (this.taskSequences[i].length - 1 < j) {
                    System.out.print("  ");
                    continue;
                }
                Task task = this.taskSequences[i][j];
                if (task instanceof ParallelTask p) {
                    p.report(false);
                } else if (task instanceof MergedTask m) {
                    System.out.println(task.id());
                } else {
                    System.out.print(task.id() + " ");
                }
            }
            System.out.println("");
        }
    }
}

La course à pied p.report(true) imprimera quelque chose comme ceci.

------------------------
TASK INITIAL_SOLUTION (COST 126, DURATION 7, RESOURCES 18)
------------------------
A W B 
B B X 
C A Y 
D U Z 
E C E 
  E A 
    C 

Tâche fusionnée

Définissons une autre tâche spéciale. A MergedTask enveloppe une tâche normale et réduit sa durée de vie. resources par 3 fois (parce qu'il fusionne 3 boîtes en 1).

class MergedTask extends Task {

    private final Task originalTask;
    MergedTask(Task originalTask) {
        this.originalTask = originalTask;
    }

    @Override
    public void run() {
        originalTask.run();
    }

    @Override
    public int duration() {
        return originalTask.duration();
    }

    @Override
    public int resources() {
        return originalTask.resources()/3;
    }

    @Override
    public String id() {
        return "MERGED(" + originalTask.id() + ")";
    }
}

Solution du manuel

Voyons à quoi ressemblera le code si nous essayons de résoudre le problème à la main (sans utiliser d'algorithme pour l'instant).

public static void main(String[] args) {
    Task p1 = new ParallelTask(
            "p1",
            new Task[] {A},
            new Task[] {W}
    );
    Task m1 = new MergedTask(B);
    Task p2 = new ParallelTask(
            "p2",
            new Task[] {C, D},
            new Task[] {A, U, C},
            new Task[] {X, Y, Z}
    );
    Task m2 = new MergedTask(E);
    Task p3 = new ParallelTask(
            "p3",
            new Task[] {A, C}
    );

    new ParallelTask("MANUAL_MERGED_TASK", new Task[] {p1, m1, p2, m2, p3}).report(true);
}

Ici, je construis manuellement le cas où nous fusionnons à B y E . Comme vous pouvez le constater dans le rapport suivant, son coût est de 96 même si le duration = 8 est pire, le coût est nettement supérieur au coût initial. Mais est-ce le meilleur ? Il faut trouver toutes les solutions possibles pour le dire.

------------------------
TASK MANUAL_MERGED_TASK (COST 96, DURATION 8, RESOURCES 12)
------------------------
A W 

MERGED(B)

C A X 
D U Y 
  C Z 

MERGED(E)

A 
C 

LCS

Nous modifierons l'algorithme LCS pour trouver toutes les sous-séquences communes possibles des trois listes de tâches. case1 , case2 et case3 . Je vais omettre l'implémentation complète de ce LCS modifié car cela serait trop long pour ce billet, vous pouvez trouver le code source sur mon site web Github .

Set<List<Cell>> findAllCommonSubsequences(List<Task> case1, List<Task> case2, List<Task> case3, String axisOrder) {
    ... see that full implemation on my Github ...
}

Cette fonction vous donnera un Set de sous-séquences communes possibles. List<Cell> est une sous-séquence, désolé ce n'est pas une notation intuitive, j'espère que vous pourrez comprendre à partir de l'exemple ci-dessous.

[
  [Cell(xyz=136,ref=025,common=true,tasks=A)], 
  [Cell(xyz=221,ref=110,common=true,tasks=B), Cell(xyz=357,ref=246,common=true,tasks=C)], 
  [Cell(xyz=221,ref=110,common=true,tasks=B), Cell(xyz=565,ref=454,common=true,tasks=E)], 
  [Cell(xyz=136,ref=025,common=true,tasks=A), Cell(xyz=357,ref=246,common=true,tasks=C)], 
  [Cell(xyz=221,ref=110,common=true,tasks=B)]
]

Il s'agit de toutes les sous-séquences communes possibles des listes de tâches d'entrée suivantes.

Task[] case1 = new Task[] {A,B,C,D,E};
Task[] case2 = new Task[] {W,B,A,U,C,E};
Task[] case3 = new Task[] {B,X,Y,Z,E,A,C};

Prenons un exemple de séquence [Cell(xyz=136,ref=025,common=true,tasks=A)] . Cette séquence n'a qu'un seul élément commun (tâche A ). Le nombre de xyz=136 indique la position de A dans chaque liste d'entrée case1 , case2 y case3 respectivement. Les ref=025 fait partie des détails de l'implémentation de LCS, vous savez ce que cela signifie si vous connaissez LCS, espérons-le. En résumé, toutes les sous-séquences communes sont A , B . BC , BE et AC .

Fusionner les tâches

Vous l'avez peut-être remarqué en lisant le Solution du manuel que le résultat final que nous voulons réellement sera toujours de la forme

new ParallelTask("SOLUTION", new Task[] {p1, m1, p2, m2, p3, m4, p4, ...})

En d'autres termes, nous allons utiliser une sous-séquence commune, telle que B E pour diviser les 3 listes de tâches d'entrée en n ParallelTask s ( p1, p2, p3, ..., pn ) et n-1 MergedTask s ( m1, m2, m3, ..., m{n-1} ), puis les regrouper dans un seul ParallelTask . Chacun MergedTask correspond à chaque élément de la sous-séquence commune.

Voici une méthode qui permet de le faire. Elle n'est pas élégante, mais j'espère que vous avez compris.

ParallelTask merge(List<Cell> commonSubsequence, List<Task> case1, List<Task> case2, List<Task> case3) {

        // pad cell index to prevent confusion, because the original cells will have indices = taskList's index - 1 due to LCS algorithm
        List<Cell> commonSubsequencePadded = commonSubsequence.stream()
                .map(cell -> new Cell(cell.value, cell.x - 1, cell.y - 1, cell.z -1, 0, 0, 0, true, cell.taskX, cell.taskY, cell.taskZ))
                .toList();
        System.out.println(commonSubsequencePadded);

        Cell prevCell = null;
        int taskNameIndex = 1;
        StringBuilder finalResultTaskName = new StringBuilder("MERGED_TASK(");
        List<Task> merged = new ArrayList<>();
        for (Cell cell : commonSubsequencePadded) {
            int startL1 = prevCell == null ? 0 : prevCell.x + 1;
            int startL2 = prevCell == null ? 0 : prevCell.y + 1;
            int startL3 = prevCell == null ? 0 : prevCell.z + 1;
            Task[] l1 = cell.x == startL1 ? new Task[0] : case1.subList(startL1, cell.x).toArray(new Task[0]);
            Task[] l2 = cell.y == startL2 ? new Task[0] : case2.subList(startL2, cell.y).toArray(new Task[0]);
            Task[] l3 = cell.z == startL3 ? new Task[0] : case3.subList(startL3, cell.z).toArray(new Task[0]);
            Task p = new ParallelTask("p" + taskNameIndex, l1, l2, l3);
            Task m = new MergedTask(cell.taskX);
            merged.add(p);
            merged.add(m);

            prevCell = cell;
            taskNameIndex++;
            finalResultTaskName.append(cell.taskX.id());
        }

        // if there are some remaining tasks after the last merge point
        if (prevCell != null && (prevCell.x + 1 < case1.size() || prevCell.y + 1 < case2.size() || prevCell.z + 1 < case3.size())) {
            Task[] l1 = prevCell.x + 1 < case1.size() ? case1.subList(prevCell.x + 1, case1.size()).toArray(new Task[0]) : new Task[0];
            Task[] l2 = prevCell.y + 1 < case2.size() ? case2.subList(prevCell.y + 1, case2.size()).toArray(new Task[0]) : new Task[0];
            Task[] l3 = prevCell.z + 1 < case3.size() ? case3.subList(prevCell.z + 1, case3.size()).toArray(new Task[0]) : new Task[0];
            Task p = new ParallelTask("p" + taskNameIndex, l1, l2, l3);
            merged.add(p);
        }

        return new ParallelTask(finalResultTaskName.append(")").toString(), merged.toArray(new Task[0]));
    }

Voyons le résultat

Les câbler tous ensemble.

Set<List<Cell>> allCommonSubsequenceList = findAllCommonSubsequences(List.of(case1), List.of(case2), List.of(case3), "XYZ");
        List<ParallelTask> allPossibleMergeList = allCommonSubsequenceList.stream().map(commonSubsequence -> merge(commonSubsequence, List.of(case1), List.of(case2), List.of(case3))).toList();

        allPossibleMergeList.forEach(t -> t.report(true));

Voici les résultats pour les 5 sous-séquences communes possibles A , B , BC , BE et AC . Et la solution la plus optimale est BE au prix coûtant 96 .

------------------------
TASK MERGED_TASK(A) (COST 150, DURATION 10, RESOURCES 15)
------------------------
  W B 
  B X 
    Y 
    Z 
    E 

MERGED(A)

B U C 
C C   
D E   
E     

------------------------
TASK MERGED_TASK(BC) (COST 120, DURATION 10, RESOURCES 12)
------------------------
A W   

MERGED(B)

  A X 
  U Y 
    Z 
    E 
    A 

MERGED(C)

D E   
E     

------------------------
TASK MERGED_TASK(BE) (COST 96, DURATION 8, RESOURCES 12)
------------------------
A W   

MERGED(B)

C A X 
D U Y 
  C Z 

MERGED(E)

    A 
    C 

------------------------
TASK MERGED_TASK(AC) (COST 120, DURATION 10, RESOURCES 12)
------------------------
  W B 
  B X 
    Y 
    Z 
    E 

MERGED(A)

B U   

MERGED(C)

D E   
E     

------------------------
TASK MERGED_TASK(B) (COST 120, DURATION 8, RESOURCES 15)
------------------------
A W   

MERGED(B)

C A X 
D U Y 
E C Z 
  E E 
    A 
    C 

Amélioration

Cette section traite de la possibilité d'étendre la solution pour prendre en charge les éléments suivants N nombre de listes au lieu de 3 listes seulement.

Dans la mise en œuvre ci-dessus, je modifie l'algorithme LCS, qui à l'origine prenait en charge 2 listes, pour prendre en charge le cas de 3 listes en ajoutant une autre boucle for au code. Il sera donc encore plus difficile d'écrire un code capable de gérer des listes de 3 listes. N liste.

Mais je pense que nous pouvons peut-être utiliser une autre méthode. Nous pouvons d'abord trouver toutes les sous-séquences communes des deux premières listes. Puis combiner le résultat avec le reste N-2 et trouver leurs sous-séquences communes de manière récursive.

J'ai ajouté un exemple de code pour cette idée dans la section /improved du code original sur mon Github.

J'ai créé une classe CommonSubsequenceFinder comme ceci

public class CommonSubsequenceFinder {
    public <T> Set<List<T>> findAllIn2Lists(List<T> l1, List<T> l2) {
        ...
    }

    public <T> Set<List<T>> findAllInNList(List<T> ... listArray) {
        if (listArray.length <= 1) {
            return new HashSet<>();
        }

        List<List<T>> lists = Arrays.asList(listArray);

        List<T> firstList = lists.get(0);
        List<T> secondList = lists.get(1);

        Set<List<T>> commonSubsequences = findAllIn2Lists(firstList, secondList);

        if (commonSubsequences.isEmpty()) {
            return commonSubsequences;
        }

        if (lists.size() == 2) {
            return commonSubsequences;
        }

        System.out.println(commonSubsequences);

        Set<List<T>> commonSubsequencesEx = new HashSet<>();
        List<List<T>> theRest = lists.subList(2, lists.size());
        for (List<T> subSeq : commonSubsequences) {
            List<List<T>> l = new ArrayList<>();
            l.add(subSeq);
            l.addAll(theRest);
            commonSubsequencesEx.addAll(findAllInNList(l.toArray(new List[l.size()])));
        }

        return commonSubsequencesEx;
    }
}

Dans la classe, vous trouverez deux méthodes publiques findAllIn2Lists(...) y findAllInNList(...) .

En findAllIn2Lists(...) peut trouver toutes les sous-séquences communes de 2 listes. Je l'ai fait pour supporter un type générique, vous pouvez mettre la liste de tout ce qui n'est pas limité à seulement un Task mais en précisant que la classe doit implémenter la méthode equals(...) y hashCode(...) correctement. Par exemple, j'ai ajouté les méthodes dans Task comme ci-dessous, qui nous permettent alors de comparer l'égalité de 2 tâches telles que t1.equals(t2) et il renverra true si t1 y t2 ont les mêmes id .

abstract class Task {
    public abstract String id();
    public abstract void run();
    public abstract int duration();
    public abstract int resources();
    public int cost() {
        return this.duration() * this.resources();
    };

    @Override
    public String toString() {
        return this.id();
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null) return false;
        if (o instanceof Task t) {
            return id().equals(t.id());
        }
        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id());
    }
}

Une autre méthode en CommonSubsequenceFinder est findAllInNList(...) . Il s'agit de la méthode récursive susmentionnée. Vous pouvez placer le code suivant dans la méthode principale pour voir le résultat.

Set<List<Task>> allCommonSubsequences = new CommonSubsequenceFinder().findAllInNList(List.of(case1), List.of(case2), List.of(case3));
System.out.println(allCommonSubsequences);

Résultat :

[[B], [B, C], [A, C], [E], [B, E], [A]]

Le seul problème restant est de savoir comment utiliser une sous-séquence commune pour fusionner N liste des tâches. Il s'agira essentiellement de la même chose que dans le cas des 3 listes. Vous devez faire une boucle pour chaque élément de la sous-séquence, utiliser l'élément pour diviser les listes sous la forme p1, m1, p2, m2, ... et les placer dans un ParallelTask . N'hésitez pas à me contacter si vous avez besoin d'aide supplémentaire à ce sujet.

Il se peut que vous souhaitiez modifier le calcul dans MergedTask.resources(...) à diviser par N au lieu de 3.