Zastosowanie teorii grafów do wyznaczania rozkładów zajęć

• Autorzy: Wojciech Sikora
• Języki publikacji: PL

Abstrakty

Jednym z wielu zagadnień organizacyjnych, dla których nie uzyskano dotychczas zadowalających wyników jest zagadnienie wyznaczania rozkładów zajęć dydaktycznych. Ma ono obszerną literaturę. Można wyróżnić trzy podejścia do rozwiązywania zagadnienia planowania zajęć. Pierwsze - najmniej efektywne, polega na formułowaniu tego problemu jako zadania programowania całkowitoliczbowego (binarnego), drugie - jako zadania kolorowania wierzchołków grafu, trzecie - najskuteczniejsze polega na bezpośrednim wyznaczaniu rozkładu zajęć za pomocą algorytmów heurystycznych. Prace nad zagadnieniem planowania zajęć podjęto w 1975 r. w Zakładzie Ekonometrii Akademii Ekonomicznej w Poznaniu. Od 1977 r. funkcjonuje Komputerowy System Planowania Zajęć (KSPZ), wykorzystujący trzecie podejście. Jakość wyznaczonych w ten sposób rozkładów zajęć nie jest jednak zadowalająca. Uzyskane wyniki wskazują na potrzebę doskonalenia algorytmów poprzez wykorzystanie np. teorii grafów. Dla bardzo uproszczonego zagadnienia algorytm ustalania rozkładu zajęć, sprowadzający się do odpowiedniego pokolorowania grafu, przedstawił Kreczmar. Ogólniejsze zagadnienie rozważał Burlaga, który podał algorytm ustalania rozkładu zajęć oparty na metodzie Maghout wyznaczania wszystkich antyklik (zbiorów wewnętrznie stabilnych) w grafie. W artykule przedstawiamy ogólne zagadnienie planowania zajęć. Zostanie ono sformułowane najpierw jako zadanie znajdowania najliczniejszego φ - skojarzenia w grafie dwudzielnym Koniga, a następnie jako zadanie znajdowania najliczniejszej antykliki w grafie sprzężonym. Przedstawiony zostanie ponadto algorytm znajdowania najliczniejszej antykliki. (fragment tekstu)

Słowa kluczowe

PL

Teoria grafów; Harmonogram; Dydaktyka

EN

Graph theory; Schedule; Didactics

• Czasopismo: Zeszyty Naukowe. Seria 1 / Akademia Ekonomiczna w Poznaniu
• Rocznik: 1981
• Numer: nr 94 Prace Instytutu Cybernetyki Ekonomicznej
• Strony: 165--178

Twórcy

autor

Wojciech Sikora

Bibliografia

• Henryk Burlaga: Planowanie zajęć jako problem wyznaczania zbioru wewnętrznie stabilnego w grafie zwykłym, w: "Problemy zastosowania metod matematycznych i elektronicznej techniki obliczeniowej w zarządzaniu", WAT, Warszawa 1972.
• Henryk Burlaga: Suboptymalne metody kolorowania grafów. Biuletyn WAT, rok XXII, nr 2, luty 1975.
• Andrzej Kreczmar: Kryterium istnienia i algorytm ustalania rozkładu zajęć. Wyd. Uniwersytetu Warszawskiego. Warszawa 1970.
• A. Kaufmann: Wwiedenije w prikładnuju kombinatoriku, Nauka, Moskwa 1975.