Discussion :

[Student_Master]

Bonjour à tous,

Je sollicite votre aide pour résoudre un petit problème.
J'ai un tableau à une seule dimension :

Code :

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

nbtache_rebut[j]

; ce tableau contient le nombre total de tâches dans une tournée. Dans mon exemple le tableau contient 8 tâches qui sont stockés dans un tableau nommé :

Code :

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

Tournee_Rebut[j]

. Ces tâches portent les numéros :

Code :

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

30 31 32 33 34 35 36 37

.
Dans ce bout de code :

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
int f;
		int nbtache_rebut[maxR];
		if (j==oni)
		{
			nbtache_rebut[j] = nbnewtask;
			i=removednurse[j];
			fp  << " \n route "<< j << " tasks " <<nbtache_rebut[j] << " : " ;
			for (f=ont; f<=ont+nbnewtask+1; f++) 
			{
				int h = removedtask[f];
				Tournee_Rebut[j] = removedtask[f];
				if(h>=0)
				{
					fp << " " << Tournee_Rebut[j];
				}
			}
		}

La tournée que je nomme 'rebut' est la suivante :

Code :

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

route 2 tasks 8 :  30 31 32 33 34 35 36 37

==> ce code marche.
Dans mon exemple, j'ai une seule tournée (N°2) et deux périodes. Ce que je voulais faire est de partager les 8 tâches sur les deux périodes (aléatoirement) de telle sorte avoir une période qui contient 3 tâches et la deuxième contient 5 tâches (par exp). A condition de ne avoir deux tâches dans deux périodes différentes.
Pour faire cela, j'ai codé ce bout de code qui, malheureusement ne marche pas :

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
int nbrtache_rebut[maxR][maxT];
		int rand_periode ; //  valeur aléatoire
 
		// partage les taches sur toutes les periodes de la derniere tournee
 
		if (j==oni)  // parcourir la derniere tournee
		{
			for(t=0; t<ond; t++)
			{
				while(nbtache_rebut[j]>0 )  // si la somme de taches restants supérieur à zero 
				{
					rand_periode = rand()% (ond); // choisir une periode de la tournee i
					fp << " \n rand period : " << rand_periode;
					nbrtache_rebut[j][rand_periode] ++ ; // ajouter +1 au nombre de tache dans la periode choisie
					fp << " \n numero tache rebut : " << nbrtache_rebut[j][rand_periode];
					nbtache_rebut[j]--; // decrementer le nombre de tache restant
					fp << " \n nb tasks restantes : " << nbtache_rebut[j];
				}
				fp << "\n route " << j << " periode " << t << " tasks : " << nbrtache_rebut[j][rand_periode] ;
			}
		}

La sortie de ce bout de code :

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
rand period : 0 
 numero tache rebut : 31 
 nb tasks restantes : 7 
 rand period : 1 
 numero tache rebut : 32 
 nb tasks restantes : 6 
 rand period : 1 
 numero tache rebut : 33 
 nb tasks restantes : 5 
 rand period : 0 
 numero tache rebut : 32 
 nb tasks restantes : 4 
 rand period : 1 
 numero tache rebut : 34 
 nb tasks restantes : 3 
 rand period : 1 
 numero tache rebut : 35 
 nb tasks restantes : 2 
 rand period : 0 
 numero tache rebut : 33 
 nb tasks restantes : 1 
 rand period : 0 
 numero tache rebut : 34 
 nb tasks restantes : 0
 route 2 periode 0 tasks : 34
 route 2 periode 1 tasks : 34

Une dernière chose : je souhaiterai par la suite savoir quelles sont les tâches qui ont étés choisies (cad les identifier dans un tableau à trois dimensions :

Code :

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

int Tournee_Rebut_Period[maxR][maxA][maxT];

: cad j'aurais besoin de savoir par exp la tâche 32 est faite par la ressource 2 et à la période 1. ==> Tournee_Rebut_Period[2][32][1].

Je vous remercie pour votre aide.

Cordialement,

[Iradrille]

Dans mon exemple, j'ai une seule tournée (N°2) et deux périodes. Ce que je voulais faire est de partager les 8 tâches sur les deux périodes (aléatoirement) de telle sorte avoir une période qui contient 3 tâches et la deuxième contient 5 tâches (par exp). A condition de ne avoir deux tâches dans deux périodes différentes.

Hello,

Je ne suis pas sur de bien comprendre, mais à première vue c'est un problème NP-complet, et l'aléatoire risque de très vite poser des problèmes : tu auras des incompatibilités (une tache 'a' débute à 1h et finie à 2h10 -> assignée sur la 1ere période, une tache 'b' débute à 2h50 et finie à 3h30 -> assignée sur la 2eme période, une tache 'c' débutant à 2h05 et finissant à 2h55 ne pourra pas être assignée) et tu devras revenir en arrière. On se rapproche dans ce cas d'une méthode naïve par brute force.

A mon avi utiliser un tableau à 3 dimensions de bool est une mauvaise idée, tu devrais plutôt avoir des structures Periode, Tache etc..
La représentation des données dans ces problèmes est très importante et peu rendre le problème beaucoup plus simple à résoudre (ou beaucoup plus compliqué )

Avec un algo tabou ou génétique, ça devrait donner des résultats corrects assez rapidement.

[Student_Master]

Iradrille

Je te remercie pour ta réponse. En effet, je cherche juste à corriger le code qui ne donne pas les résultats que je souhaiterai avoir. Ce que j'ai mis comme code n'est juste qu'un petit extrait pour écrire l'instance dans un fichier texte et il n'a aucun rapport avec les méthodes que je suis entrain de développer.
Le deuxième code que j'ai cité celui qui marche pas et j'aimerai avoir un résultat comme celui ci :

Code :

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

route 2 tasks 8 :  30 31 32 33 34 35 36 37

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
rand period : 0 
 numero tache rebut : 30 
 nb tasks restantes : 7 
 rand period : 1 
 numero tache rebut : 31 
 nb tasks restantes : 6 
 rand period : 1 
 numero tache rebut : 32 
 nb tasks restantes : 5 
 rand period : 0 
 numero tache rebut : 33 
 nb tasks restantes : 4 
 rand period : 1 
 numero tache rebut : 34 
 nb tasks restantes : 3 
 rand period : 1 
 numero tache rebut : 35 
 nb tasks restantes : 2 
 rand period : 0 
 numero tache rebut : 36 
 nb tasks restantes : 1 
 rand period : 0 
 numero tache rebut : 37
 nb tasks restantes : 0
==> la construction de la tournée souhaitée avoir est la suivante (exp) :
 route 2 periode 0 tasks (4) : 30 33 36 37
 route 2 periode 1 tasks (4) : 31 32 34 35

Cordialement,