Discussion :

[Lockon Stratos]

Bonjour,
Je développe un logiciel permettant de générer des emplois du temps, mais le problème est que celui-ci prend plus de 30 minutes pour faire un seul jour, j'aurais donc besoin de pouvoir l'optimiser.
Voilà mon code

Les données :

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
professeur_matiere_classe1(Prof, Mat) :- Prof = 0, Mat = 0; Prof = 1, Mat = 1; Prof = 2, Mat = 2; Prof = 3, Mat = 3; Prof = 4, Mat = 4; Prof = 5, Mat = 5; Prof = 8, Mat = 8; Prof = 9, Mat = 9; Prof = 10, Mat = 10; Prof = 11, Mat = 11; Prof = 12, Mat = 12; Prof = 13, Mat = 13; Prof = 14, Mat = 14.
professeur_matiere_classe2(Prof, Mat) :- Prof = 0, Mat = 0; Prof = 1, Mat = 1; Prof = 2, Mat = 2; Prof = 3, Mat = 3; Prof = 6, Mat = 6; Prof = 7, Mat = 7; Prof = 14, Mat = 14.
professeur_matiere_classe3(Prof, Mat) :- Prof = 0, Mat = 0; Prof = 1, Mat = 1; Prof = 2, Mat = 2; Prof = 3, Mat = 3; Prof = 10, Mat = 10; Prof = 4, Mat = 4; Prof = 13, Mat = 13.
professeur_matiere_classe4(Prof, Mat) :- Prof = 0, Mat = 0; Prof = 1, Mat = 1; Prof = 2, Mat = 2; Prof = 3, Mat = 3; Prof = 9, Mat = 9; Prof = 8, Mat = 8.
professeur_matiere_classe5(Prof, Mat) :- Prof = 0, Mat = 0; Prof = 1, Mat = 1; Prof = 2, Mat = 2; Prof = 3, Mat = 3; Prof = 8, Mat = 8; Prof = 5, Mat = 5; Prof = 12, Mat = 12; Prof = 12, Mat = 15.
professeur_matiere_classe6(Prof, Mat) :- Prof = 0, Mat = 0; Prof = 1, Mat = 1; Prof = 2, Mat = 2; Prof = 3, Mat = 3; Prof = 10, Mat = 10; Prof = 4, Mat = 4; Prof = 13, Mat = 13.
professeur_matiere_classe7(Prof, Mat) :- Prof = 0, Mat = 0; Prof = 1, Mat = 1; Prof = 2, Mat = 2; Prof = 3, Mat = 3; Prof = 9, Mat = 9; Prof = 8, Mat = 8.
professeur_matiere_classe8(Prof, Mat) :- Prof = 0, Mat = 0; Prof = 1, Mat = 1; Prof = 2, Mat = 2; Prof = 3, Mat = 3; Prof = 8, Mat = 8; Prof = 5, Mat = 5; Prof = 12, Mat = 12; Prof = 12, Mat = 15.
 
 
 
disponibilites_heure1(Prof) :- Prof = 1; Prof = 2; Prof = 3; Prof = 6; Prof = 4; Prof = 7; Prof = 15; Prof = 9.%; Prof = 0.
disponibilites_heure2(Prof) :- Prof = 1; Prof = 5; Prof = 3; Prof = 8; Prof = 10; Prof = 13; Prof = 15; Prof = 11.%; Prof = 0.
disponibilites_heure3(Prof) :- Prof = 1; Prof = 2; Prof = 6; Prof = 9; Prof = 4; Prof = 14; Prof = 12; Prof = 15.%; Prof = 0.
disponibilites_heure4(Prof) :- Prof = 4; Prof = 2; Prof = 3; Prof = 4; Prof = 7; Prof = 9; Prof = 10; Prof = 11; Prof = 13; Prof = 15.%; Prof = 0.
disponibilites_heure5(Prof) :- Prof = 1; Prof = 2; Prof = 3; Prof = 6; Prof = 4; Prof = 7; Prof = 15; Prof = 9.%; Prof = 0.
disponibilites_heure6(Prof) :- Prof = 1; Prof = 5; Prof = 3; Prof = 8; Prof = 10; Prof = 13; Prof = 15; Prof = 11.%; Prof = 0.
disponibilites_heure7(Prof) :- Prof = 1; Prof = 2; Prof = 6; Prof = 9; Prof = 4; Prof = 14; Prof = 12; Prof = 15.%; Prof = 0.

professeur_matiere_classe(Prof, Mat) renseigne, pour chaque classe, la liste des profs et des matières qu'ils enseignent. Ici j'ai presque toujours associé le prof 1 à la matière 1 pour plus de clarté.

disponibilites_heure(Prof) donne, pour chaque heure de cours, la liste des profs disponibles.

Actuellement le professeur et la matière 0 correspondent à un vide dans l'emploi du temps. J'ai retiré la prof 0 dans les disponibilités sinon il me sort des emplois du temps quasi vides (remarque c'est pas si mal pour les élèves).


Les traitements :

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
differents([]).
differents([0|R]) :- differents(R). % On peut avoir plusieurs classe sans cours
differents([T|R]) :- outlist(T, R), differents(R).
 
 
jour([[PC1H1, MC1H1], [PC1H2, MC1H2], [PC1H3, MC1H3], [PC1H4, MC1H4], [PC1H4, MC1H4], [PC1H4, MC1H4], [PC1H4, MC1H4]],
[[PC2H1, MC2H1], [PC2H2, MC2H2], [PC2H3, MC2H3], [PC2H4, MC2H4], [PC2H5, MC2H5], [PC2H6, MC2H6], [PC2H7, MC2H7]],
[[PC3H1, MC3H1], [PC3H2, MC3H2], [PC3H3, MC3H3], [PC3H4, MC3H4], [PC3H5, MC3H5], [PC3H6, MC3H6], [PC3H7, MC3H7]],
[[PC4H1, MC4H1], [PC4H2, MC4H2], [PC4H3, MC4H3], [PC4H4, MC4H4], [PC4H5, MC4H5], [PC4H6, MC4H6], [PC4H7, MC4H7]],
[[PC5H1, MC5H1], [PC5H2, MC5H2], [PC5H3, MC5H3], [PC5H4, MC5H4], [PC5H5, MC5H5], [PC5H6, MC5H6], [PC5H7, MC5H7]],
[[PC6H1, MC6H1], [PC6H2, MC6H2], [PC6H3, MC6H3], [PC6H4, MC6H4], [PC6H5, MC6H5], [PC6H6, MC6H6], [PC6H7, MC6H7]],
[[PC7H1, MC7H1], [PC7H2, MC7H2], [PC7H3, MC7H3], [PC7H4, MC7H4], [PC7H5, MC7H5], [PC7H6, MC7H6], [PC7H7, MC7H7]],
[[PC8H1, MC8H1], [PC8H2, MC8H2], [PC8H3, MC8H3], [PC8H4, MC8H4], [PC8H5, MC8H5], [PC8H6, MC8H6], [PC8H7, MC8H7]]) :- 
differents([PC1H1,PC2H1,PC3H1,PC4H1,PC5H1,PC6H1,PC7H1,PC8H1]),
differents([PC1H2,PC2H2,PC3H2,PC4H2,PC5H2,PC6H2,PC7H2,PC8H2]),
differents([PC1H3,PC2H3,PC3H3,PC4H3,PC5H3,PC6H3,PC7H3,PC8H3]),
differents([PC1H4,PC2H4,PC3H4,PC4H4,PC5H4,PC6H4,PC7H4,PC8H4]),
dispoH1(PC1H1), dispoH1(PC2H1), dispoH1(PC3H1), dispoH1(PC4H1), dispoH1(PC5H1), dispoH1(PC6H1), dispoH1(PC7H1), dispoH1(PC8H1), 
dispoH2(PC1H2), dispoH2(PC2H2), dispoH2(PC3H2), dispoH2(PC4H2), dispoH2(PC5H2), dispoH2(PC6H2), dispoH2(PC7H2), dispoH2(PC8H2), 
dispoH3(PC1H3), dispoH3(PC2H3), dispoH3(PC3H3), dispoH3(PC4H3), dispoH3(PC5H3), dispoH3(PC6H3), dispoH3(PC7H3), dispoH3(PC8H3), 
dispoH4(PC1H4), dispoH4(PC2H4), dispoH4(PC3H4), dispoH4(PC4H4), dispoH4(PC5H4), dispoH4(PC6H4), dispoH4(PC7H4), dispoH4(PC8H4),
dispoH5(PC1H5), dispoH5(PC2H5), dispoH5(PC3H5), dispoH5(PC4H5), dispoH5(PC5H5), dispoH5(PC6H5), dispoH5(PC7H5), dispoH5(PC8H5),
dispoH6(PC1H6), dispoH6(PC2H6), dispoH6(PC3H6), dispoH6(PC4H6), dispoH6(PC5H6), dispoH6(PC6H6), dispoH6(PC7H6), dispoH6(PC8H6),
dispoH7(PC1H7), dispoH7(PC2H7), dispoH7(PC3H7), dispoH7(PC4H7), dispoH6(PC5H7), dispoH6(PC6H7), dispoH6(PC7H7), dispoH6(PC8H7),
profmatc1(PC1H1,MC1H1), profmatc1(PC1H2,MC1H2), profmatc1(PC1H3,MC1H3), profmatc1(PC1H4,MC1H4), profmatc1(PC1H5,MC1H5), profmatc1(PC1H6,MC1H6), profmatc1(PC1H7,MC1H7),
profmatc2(PC2H1,MC2H1), profmatc2(PC2H2,MC2H2), profmatc2(PC2H3,MC2H3), profmatc2(PC2H4,MC2H4), profmatc2(PC2H5,MC2H5), profmatc2(PC2H6,MC2H6), profmatc2(PC2H4,MC2H7),
profmatc3(PC3H1,MC3H1), profmatc3(PC3H2,MC3H2), profmatc3(PC3H3,MC3H3), profmatc3(PC3H4,MC3H4), profmatc3(PC3H5,MC3H5), profmatc3(PC3H6,MC3H6), profmatc3(PC3H4,MC3H7),
profmatc4(PC4H1,MC4H1), profmatc4(PC4H2,MC4H2), profmatc4(PC4H3,MC4H3), profmatc4(PC4H4,MC4H4), profmatc4(PC4H5,MC4H5), profmatc4(PC4H6,MC4H6), profmatc4(PC4H4,MC4H7),
profmatc5(PC5H1,MC5H1), profmatc5(PC5H2,MC5H2), profmatc5(PC5H3,MC5H3), profmatc5(PC5H4,MC5H4), profmatc5(PC5H5,MC5H5), profmatc5(PC5H6,MC5H6), profmatc5(PC5H4,MC5H7),
profmatc6(PC6H1,MC6H1), profmatc6(PC6H2,MC6H2), profmatc6(PC6H3,MC6H3), profmatc6(PC6H4,MC6H4), profmatc6(PC6H5,MC6H5), profmatc6(PC6H6,MC6H6), profmatc6(PC6H4,MC6H7),
profmatc7(PC7H1,MC7H1), profmatc7(PC7H2,MC7H2), profmatc7(PC7H3,MC7H3), profmatc7(PC7H4,MC7H4), profmatc7(PC7H5,MC7H5), profmatc7(PC7H6,MC7H6), profmatc7(PC7H4,MC7H7),
profmatc8(PC8H1,MC8H1), profmatc8(PC8H2,MC8H2), profmatc8(PC8H3,MC8H3), profmatc8(PC8H4,MC8H4), profmatc8(PC8H5,MC8H5), profmatc8(PC8H6,MC8H6), profmatc8(PC8H4,MC8H7).

Les contraintes sont donc :
1 prof ne peux pas être dans 2 classes en même temps (differents(Liste)).
1 prof doit être disponible pour être assigné à une classe(dispoH(Prof)).
1 prof doit avoir une matière à enseigner dans une classe pour y être mis(profmat(Prof, Mat)).


Les problèmes de ce script sont donc qu'il est beaucoup trop lent à trouver des solutions (j'admet qu'il y a beaucoup de calculs à faire).
Je ne l'utilise actuellement qu'avec 4 classes car il n'y a pas assez de jeu de données pour en utiliser plus mais là n'est pas le problème.
De plus quand "j'active" la possibilité d'avoir des heures sans cours (en mettant dans dispos le prof 0) il me sort des emplois du temps avec 3 ou 4 heures de cours pour les 4 classes réunies (1 heure par classe).

Le mieux serait donc de pouvoir dire au prolog : "essaye de placer le plus de prof possible sans prendre trop de temps, et là où les possibilités de placement sont plus restreintes (donc plus de calculs à faire) t'as le droit de mettre des trous" mais il ne comprend pas .

Par la suite je devrait également ajouter des durées minimales à certains cours : Un tp de physique c'est pas 1 heure mais bien 2 si on veux faire quelque chose de correct, etc .... Pour ça je ne vois pas trop comment m'y prendre, et je n'essaye pas non plus pour l'instant car si il faut qu'il me mette 3 heures pour générer un seul jour d'emploi du temps sa va pas aller.

Désolé pour ce pavé mais je pense qu'il vaut mieux bien expliquer sont problème pour être bien aidé que de rester trop vague.

Merci de votre aide.

[Trap D]

Bonjour

Tout d'abord, le problème des emplois du temps est un problème compliqué.

Quand je vois le code du predicat jour je n'ai même pas envie de le lire ! Je pense qu'il faudrait revoir la conception du programme.

Un programme Prolog comporte des faits et des regles qui agissent à partir des faits.
Ici les faits pourraient être

• les prof (nom, matiere, plage horaires diponibles)
• les salles (numero, specialisation)
• les heures de cours(prof, salle)
• les matieres (nombre d'heures par niveaux, obligation de salle specialisée, necessite d'heures consecutives)
• les classes(heures)
• etc, on peut imaginer d'autres faits

Ensuite, on peut définir les regles pour constituer une heure de cours, prof disponible, classe disponible, salle disponibles, matieres possible, puis définir des regles pour constituer un EDT. définir le nombre de jours et le nombre d'heures par jour pour une classe.
Ceci dit, c'est un simple avis, on peut surement faire autrement, et on est là pour répondre aux questions.

Bon courage.