Wrocław 30 maja 2006
Marta Kaczmarek, numer indeksu 127801

Raport z ‘dużego’ projektu wykonanego w ramach pracowni z przedmiotu Sztuczna Inteligencja.

Układanie planu zajęć dla gimnazjum


1.Opis zadania.

Celem projektu było ułożenie planu zajęć dla Gimnazjum na podstawie przydziału przedmiotów i godzin lekcyjnych nauczycielom w roku szkolnym 2005/2006.

Definicja problemu.

Utworzenie planu zajęć polega na znalezieniu zbioru czwórek: 'n', 'h', 'k', 's', to znaczy 'n'-ty nauczyciel ma o godzinie 'h'-tej lekcje z klasą 'k' w sali 's', tak żeby:
- żadni dwaj nauczyciele nie uczyli tej samej klasy w tym samym czasie,
- żadne dwie klasy nie miały lekcji z tym samym nauczycielem w tym samym czasie,
- żadne dwie sale nie były wykorzystywane o tej samej porze przez tą samą klasę,
- w ciągu dnia żadna klasa nie miała więcej niż osiem godzin lekcyjnych,
- żadna klasa nie miała więcej niż dwie godziny pod rząd zajęć z tego samego przedmiotu,
- żadna klasa nie miała okienek między takim samym przedmiotem tego samego dnia,
- specyficzne typy zajęć np. W-F, języki obce, informatyka odbywały się w salach dla nich przeznaczonych.

Należy podkreślić, że w przypadku posiadania gotowego planu zajęć można w łatwy sposób (złożoność wielomianowa) sprawdzić, czy wszystkie założenia zostały spełnione. Natomiast sprawdzenie przy znanym układzie danych, czy istnieje takie ułożenie planu by wszystkie reguły były respektowane należy do problemów NP-trudnych. Nie jest znany żaden algorytm rozwiązujący ten problem w czasie wielomianowym.


2.Przykładowe dane.

Dane wejściowe pobierane są z pliku. Forma ich zapisu przedstawiona jest tutaj: dane

Nauczycielom odpowiadają indeksy od 1 do 20.
Przedmiotom odpowiadają indeksy od 1 do 15.
Klasom indeksy od 1 do 9.
Dni tygodnia to liczby od 1 do 5.
Godziny to indeksy od 1 do 8.

Ułatwia to analizowanie i rozwiązywanie problemu.

W celu ułożenia planu lekcji dla szkoły, stworzyłam kilka zmiennych:
nauczyciel - by ułożyć plan dla nauczycieli, ale również dysponować informacją czy o danej godzinie nauczyciel nie ma już innej lekcji,
gabinet - by ułożyć plan ze względu na zajęte gabinety, co da nam informację kto i z kim ma zajęcia w danej sali o ustalonej godzinie, jak również uchroni nas przed zajmowaniem sali w której już są zajęcia,
klasa - by ułożyć plan dla danej klasy bez i z podziałem na grupy, dysponować informacją czy klasa ma w ustalonej chwili dane zajęcia, z danym nauczycielem, lub w danym gabinecie,
lekcja - tworzy zbiór wszystkich zajęć (jedno lub dwugodzinnych) odbywających się w szkole w trakcie tygodnia,
kolejka - by pobrać i utworzyć listę godzin które będą umieszczane w planie, umożliwić losowe generowanie przedmiotu który będzie wpisany w plan.

Tab.1 Tabela przedstawia informację co znajduje się na odpowiednich polach danej zmiennej (np. zmienna[1][2][1][2]).
pole w tab. [ ] [ ] [ ] [ ] [ ]
nauczyciel nr nauczyciela dzień (np. 1) godzina (np.1) [0] - przedmiot
[1] - klasa
[2] - gabinet
[3] - 0 (cała klasa),
1 (1 grupa),
2 (2 grupa) 		-
gabinet nr sali dzień godzina (np.1) [0] - przedmiot
[1] - klasa
[2] - nauczyciel
[3] - 0 (cała klasa),
1 (1 grupa),
2 (2 grupa)
 -
klasa nr klasy dzień godzina (np.1) [0] - cała klasa
[1] - 1 grupa
[2] - 2 grupa
 [0] - przedmiot
[1] - nauczyciel
[2] - gabinet
lekcja nr lekcji (uwaga nie przedmiotu!) [0] - przedmiot
[1] - klasa
[2] - liczba godzin pod rząd
[3] - nr grupy
[4] - nr nauczyciela
 - - -
kolejka nr lekcji (uwaga nie przedmiotu!) - - - -


3.Opis metody rozwiązania.

1. Wczytanie lekcji (1 lub 2 godzin*).
|
|
2. Losowe ułożenie lekcji w kolejce do uzupełniania planu.
|
|
3. Pobranie lekcji, dni=0, godz=0
|
|
4. Ustawienie dni = dni+1, godz =godz+1.
(Jeśli dni>5 i godz>8 to zablokowanie planu)
|
|
5. Sprawdzenie czy nauczyciel nie jest zajęty.
- zajęty -> skok do 4
-wolny
|
|
6. Sprawdzenie czy klasa bądź grupa nie są zajęte
- zajęta -> skok do 4
-wolna
|
|
7. Szukanie wolnego gabinetu odpowiadającego przedmiotowi.
- znaleziono 1 godz -> przejście do do 8
- nie znaleziono 1 godz -> skok do 4
- znaleziono 2 godz -> skok do 9
- nie znaleziono 2 godz -> skok do 4
|
|
8. Wpisanie danych do planów. (**), skok do 3
|
|
9. Sprawdzenie czy wszyscy i wszystko jest wolne na następną godz.
- nie -> skok do 4
- tak -> przejście do 10
|
|
10. Wpisanie danych. (**), skok do 3



* - jeżeli klasa ma np. 5 godzin matematyki, to lekcje do wpisania pobierane są jako lekcja 2 godzinna, lekcja 2 godzinna i ostatnia lekcja jedno godzinna, stanowi to 3 pobrane lekcje.

** - wpisanie danych do planu może odbywać się w dwóch systemach, albo od pierwszej do ostatniej godziny w dniu, albo od pierwszego dnia do ostatniego dnia w danej godzinie.

4.Przykłady działania programu i omówienie wyników.

Przykładowy plik zawierający otrzymane wyniki znajduje się tutaj: wyniki

Jeśli chodzi o odczytanie planów, metoda jest następująca:

Klasa Ia (1)  PONIEDZIAŁEK
godz 1 2 3 4 5 6 7 8
 cała klasa   7 17 10   0 0 0   0 0 0   9 14 13   4 4 13   6 3 10   0 0 0   0 0 0 
 grupa 1   0 0 0   9 1 14   0 0 0   0 0 0   0 0 0   0 0 0   4 13 4   13 4 1 
 grupa 2   0 0 0   13 4 2   13 4 2   0 0 0   0 0 0    0 0 0   0 0 0   4 13 4 

Jeśli chodzi o kolejność wpisywanych danych to jest to tak jak dla np. 7 17 10 jest to 7 przedmiot, 17 nauczyciel i 10 gabinet. Sprawdźmy zatem jaki plan jest dla nauczyciela 17 i gabinetu 10 tego samego dnia.

Nauczyciel 17  PONIEDZIAŁEK
 zajęcia   7 1 10 0   0 0 0 0   7 4 11 0   0 0 0 0   7 3 7 0   0 0 0 0   0 0 0 0   0 0 0 0 

Jeśli spojrzymy na tabelę 1. zauważymy, że na pierwszym polu wpisany jest przedmiot, następnie klasa, numer sali oraz czy to podział na grupy czy nie.

Gabinet 10  PONIEDZIAŁEK
 zajęcia   7 1 17 0   9 9 14 0   8 8 6 0   11 2 10 0   0 0 0 0   6 1 3 0   15 2 12 0   6 4 3 0 

6.Wnioski.

Jeśli chodzi o rozwiązanie tego problemu jest kilka bardzo ważnych rzeczy które mają na to wpływ.
Jest to:
• Przyjęcie pewnych założeń (podział na grupy, przydział sal do przedmiotu).
• Pobieranie losowe lekcji i umieszczanie jej w planie.
• Odpowiednie pobieranie godzin z planu (np. dla 3 jest to 2 +1, itd.).
• Ustalenie metody, w jaki sposób plan będzie uzupełniany (po godzinach czy po dniach).

Przyjęcie sposobu uzupełniania planu po dniach prowadzi do sytuacji, w której w pierwszych dniach tygodnia odbywa się większość zajęć, natomiast w czwartek i piątek jest ich o wiele mniej.
Uniknięcie nierównomierności rozkładu zajęć można uzyskać uzupełniając plan po godzinach, zaczynając od pierwszej każdego dnia, potem drugiej itd.. Można też powiedzieć, że plan jest układany ze względu na klasy to one mają plany bez okienek, nauczyciele za to nie. Tak jest, jeśli chodzi o metodę układania planu po godzinach. Przy drugiej metodzie jest mniejsze prawdopodobieństwo, że będą okienka.

7.Żródła.

• Materiały do wykładu Sztuczna Inteligencja (w szczególności Metody przeszukiwania – wykład 5 i 6),
• informacje na temat metod przeszukiwania ze strony Romana Bartáka.