Discussion :

[CedricMocquillon]

Bonjour à tous,

J'ai un problème algorithmique qui peut s'enoncer comme un problème de production: j'ai n tâches à exéctuer sur m machines (m=n). Chaque tâche a une date de début et une date de fin connue. Mon but est de les affecter aux machines de sorte à minimiser le nombre de machines utilisées. Mon algo actuel consite à trier les tâches par date de début d'exécution croissante et à les placer sur la machine compatible (qui est disponible avant la date de début de la tâche courante) disponible au plus tard. J'ai l'impression que ce problème est polynomial mais je n'arrive pas à le ramener à un problème "classique". Si vous avez des idées de pistes... je suis preneur

[pseudocode]

A mon avis, ton problème doit être un "Job Shop Scheduling" mais de la manière dont tu l'as expliqué, je ne comprend pas: si les dates de début et de fin des tâches sont imposées, je ne vois pas trop comment on peut minimiser quoi que ce soit.

[CedricMocquillon]

Justement, le truc c'est qu'ici je ne cherche pas à minimiser la date de fin de la dernière tâche mais le nombre de machines utilisées: si par exemple j'ai n tâches unitaires telles que la tâche i se commence en i et se termine en i+1, je peux très bien décider d'affecter chaque tâche à chaque machine (j'ai donc utilisé n machines) mais dans mon cas je préfèrerais qu'elles soient toutes affectées à la première machine (j'aurais donc utilisé une seule machine). Avec cet exemple c'est effectivement possible de toutes les affecter à la machine 1 mais si j'ai une tâche k qui commence en k et se termine en k+3, je serai alors obligé d'utiliser deux machines. Et je voudrais donc déterminer un algo optimal (si le problème est polynomial ou pseudo-polynomial) ou alors une bonne heuristique (si le problème est NP-difficile) pour le cas général où on connait pour chaque tâche sa date de début et sa date de fin.

[pseudocode]

... Je comprend toujours pas.

Si la date de début de la tâche est est imposée, il faut nécessairement affecter cette tâche à une machine disponible. N'importe laquelle.

[CedricMocquillon]

Ben... non... pas n'importe laquelle, je pense qu'un exemple vaut mieux qu'un long discours:
n = 3 (le nombre de tâches)
T1 [0,1], T2 [1,2], T3[2,3] (les dates de début et de fin des tâches)
Première possibilité d'affectation:
M1 |[T1][T2][T3]
M2 |___________
M3 |___________
Nombre de machines utilisées : 1

Deuxième possibilité d'affectation:
M1 |[T1]________
M2 |____[T2]____
M3 |________[T3]
Nombre de machines utilisées : 3

Donc il faut pas affecter une tâche à n'importe quelle machine puisque je veux minimiser le nombre de machines utilisées (et donc avec l'exemple être dans le cas de la première possibilité). Voilà, je sais pas si c'est plus clair maintenant. En fait il faudrait donc un algorithme pour le cas général et si possible que j'arrive à identifier quel type de problème c'est (genre si j'arrive à dire "c'est un problème de recherche de plus court chemin dans un graphe" c'est cool c'est polynomial ou encore "c'est un problème de sac à dos" bon c'est moins cool c'est pseudo polynomial ou enfin "c'est un problème de voyageur de commerce" et là c'est NP-Difficile mais au moins j'aurais accès à de bonnes heuristiques)

[pseudocode]

Ahhhhh.... je comprend mieux.

Tu veux minimiser le nombre de machines différentes nécessaires au scheduling.

Dans ce cas, au lieu de prendre "n'importe quelle" machine, il faut prendre en priorité celles qui ont déjà été utilisées. non ?

[Alikendarfen]

Bonjour,

Je pense que ce lien peut t'aider : http://www.enseignement.polytechniqu...00000000000000

Ce qu'il explique est un algo glouton permettant d'affecter le plus de tâches possible sur une (unique) ressource, en connaissant les dates de début fin des tâches. Cela se fait très simplement avec une petite démonstration à l'appui.

Dans ton problème, ce ne sera pas une solution optimale (appliquer cet algo sur chaque machine jusqu'à ce que toutes les tâches soient placées), mais peut être une base à partir de laquelle elle peut être trouvée, par permutation par exemple.

[souviron34]

en fait, il faut commencer par faire un tri et stocker successivement les taches ne se recoupant pas et les plus proches...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Tri (taches de 0 à N) : par ordre de debut croissant
 
intiailisation de i = 1 à i = N 
    machine(i) = -1
 
izero = 0
machine(0) = 0
fini = Faux
ilast = 0
inext = 0
 
tant que Fini = FAUX
   Fini = Vrai
 
   pour tache i = 1 a tache i = N
         si machine(i)  < 0
               si date de fin (tache(izero)) > date debut (tache(i))
                    machine(i) =  machine(izero)
               sinon
                   si Fini = Vrai
                        inext = i
                   fin si
                   Fini = Faux 
               fin si
         fin si
   fin pour
 
   si Fini = FAUX
        ilast = izero
        izero = inext
        machine(izero)= machine(ilast)+1
   fin si
 
Fin Tant que

[Alikendarfen]

En fait, je rejoints Pseudocode !

Si les dates de début et fin des tâches sont imposées, il faudra simplement autant de machines qu'il y a de tâches simultanées à un moment donné.

Donc effectivement pas de combinatoire la dedans. On trie par début croissant (ou l'inverse) et on affecte chaque tâche soit à une des machines utilisées s'il n'y a pas de recouvrement de cette tâche par rapport à une précédente, soit à une nouvelle machine. Et le tri n'est la que pour rendre plus simple le test du recouvrement.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
        void Affecter( List<Tache> taches, List<Machine> machines )
        {
            taches.Sort( delegate( Tache t1, Tache t2 ) { return t1.Debut.CompareTo( t2.Debut ); } );
 
            foreach ( Tache tache in taches )
            {
                foreach ( Machine machine in machines )
                {
                    if ( machine.Taches.Count == 0 )
                    {
                        machine.Taches.Add( tache );
                        break;
                    }
                    else if ( machine.Taches[machine.Taches.Count - 1].Fin <= tache.Debut )
                    {
                        machine.Taches.Add( tache );
                        break;
                    }
                }
            }
        }

Si je ne me trompe pas, la première machine aura le plus de tâches possible pour une machine (cf. le lien que j'ai indiqué au post d'avant).
La seconde machine le plus de tâches possible sur celles non affectées à la première.
Etc.

Par contre, peut on mieux faire en terme de complexité ?

Souviron, si j'ai bien compris ton algo, pour toi aussi, le pire cas est en O(n2), soit n * (n + 1) / 2 itérations ?

[Jean-Marc.Bourguet]

Si je ne me trompe pas, la première machine aura le plus de tâches possible pour une machine (cf. le lien que j'ai indiqué au post d'avant).
La seconde machine le plus de tâches possible sur celles non affectées à la première.

Tu te trompes. Par exemple 4 tâches sur deux machines:
1/ 0 -> 4
2/ 1 -> 2
3/ 2 -> 3
4/ 3 -> 200

La première machine fait une tâche pour une durée totale de 4, la deuxième fait trois tâches pour une durée totale de 199.

[Alikendarfen]

Exact ! Merci

Tu te trompes. Par exemple 4 tâches sur deux machines:
1/ 0 -> 4
2/ 1 -> 2
3/ 2 -> 3
4/ 3 -> 200

La première machine fait une tâche pour une durée totale de 4, la deuxième fait trois tâches pour une durée totale de 199.

Oui : il faut trier par date de fin et non pas par date de début.

[CedricMocquillon]

Merci à tous les deux!
Donc effectivement, ca confirme ce que je me disais sur le fait que c'est un problème polynomial, c'est cool
Par contre, mon problème a quelque peu évolué: j'ai un ordre sur les tâches en terme de disponibilité (quand elles commencent) mais j'ai également un ordre dans lequel je veux les classer à l'arrivée. En fait ca ressemble un peu au jeu du solitaire (celui avec les cartes sous windows): je connais l'ordre des cartes qui sont masquées (je connais donc leur date d'arrivée), j'ai m piles (mes m machines) sur lequelles je peux mettre mes cartes dans l'ordre dans lequel elles arrivent (je n'ai pas d'autre contraintes sur ces piles). Le but c'est de déterminer sur quelle pile je dois mettre les cartes cachées de sorte que je puisse dépiler les cartes de mes tas dans l'ordre (par exemple dans le cas des cartes: de l'as au roi). Le tout bien sur en minimisant le nombre de piles utilisées... (petite remarque: c'est pas vraiment des piles puisque je retire en premier la première carte insérée, First in First out).
Enfin, l'exemple avec le solitaire est une approximation puisque en fait mes tâches peuvent avoir des périodes de recouvrement mais bon c'est un peu l'idée.
En tout cas encore merci de vos réponses.

[Alikendarfen]

Je n'ai pas compris en quoi cela change le problème de départ ?

Tu souhaites ressortir tes tâches des piles dans le bon ordre, après les avoir rangées dans tes piles ?
Pour lancer l'exécution du traitement de chaque tâche par chaque machine ?

[CedricMocquillon]

Ben ça change énormément le problème de départ: imagines que l'on ait les tâches (dans l'ordre de leur date de début)
5 4 3 2 1
et que l'on souhaite les avoir dans l'ordre 1 2 3 4 5
La tache 5 va occuper une machine mais lorsque la tache 4 va "arriver", on ne pourra pas la mettre derrière la tache 5 sinon lorsque l'on va essayer de dépiler, la tache 5 "masquera" la tache 4
Exemple qui ne marche pas:
M1 T5 T4
M2 T3
M3 T2
M4 T1
M5
Lorsque l'on va dépiler on va avoir: T1 (accessible) T2 (accessible) T3 (accessible) mais pour "sortir" T4 (il faut respecter l'ordre 1 2 3 4 5) on est bloqué puisque la tâche T5 est "devant"
Donc dans mon exemple, y'a pas le choix, il faut faire:
M1 T5
M2 T4
M3 T3
M4 T2
M5 T1
Après il faut que je gère le cas général avec les dates d'arrivées et de fin. Mais bon je pense que j'ai une méthode qui doit résoudre pas trop mal le problème (même si je ne sais pas si ce problème est polynomial ou pas):
Je prend les taches dans l'ordre de sortie imposé et j'affecte chaque tâche à la machine disponible au plus tard dans l'ensemble des machines disponibles avant sa date d'arrivée et je met à jour la date de disponibilité de la machine en fonction de la date de fin de la tâche. Si je n'ai pas de machines disponibles avant sa date d'arrivée, c'est que le problème est infesable. Le fait de prendre la machine disponible au plus tard me permet d'essayer de minimiser le nombre de machines utilisées.

[Alikendarfen]

Donc on peut formuler tes contraintes comme ça ?

1/ Qu'on ne peut pas trier la liste initiale de tâches comme on veut, mais qu'on doit les placer sur les machines comme elles viennent.

2/ Qu'en plaçant les tâches sur une machine on est obligé de les mettre dans une file : par exemple si on place T5 sur M1 on sera obligé de placer toute autre tâche de M1 derrière T5 (et par conséquent seulement les tâches dont le début est après la fin de T5).

3/ Que cependant on connait toutes les tâches à l'avance.

C'est ça ?

[CedricMocquillon]

C'est à peu près ça:
1/ Les tâches initiales sont triées par date d'arrivée, si deux tâches ont la même date d'arrivée, on peu choisir laquelle des deux sera affectée à l'une des machines en premier.
2/ En fait, à chaque tâche t est associée deux valeurs: son numéro dans la liste triée par date d'arrivée (on note a_t ce numéro) et son numéro dans la liste souhaitée (on note s_t ce numéro) en sortie. Si la tache t est affectée à la machine M_i, alors on ne peut placer après t sur M_i que des tâches t' arrivant après a_t (donc avec a_t' > a_t) et étant après t dans la liste souhatée (donc avec s_t' > s_t).
3/ Le tout en cherchant à minimiser le nombre de machines (si on note x_{t,j} la variable binaire égale à 1 si la tache t est associée à la machine M_j, on cherche à maximiser le nombre de machines j pour lesquelles \sum_{t=1}^T x_{t,j} = 0)