problem planu zajęć

Problemy matematyczne "ubrane" w życiowe problemy.
Awatar użytkownika
Chewbacca97
Użytkownik
Użytkownik
Posty: 464
Rejestracja: 9 lis 2013, o 22:09
Płeć: Mężczyzna
Podziękował: 33 razy
Pomógł: 120 razy

problem planu zajęć

Post autor: Chewbacca97 »

Problem porządnego planu lekcji dotyka wszystkich na każdym etapie edukacji. Jest to problem dość stymulujący i coraz bardziej popularny. W 2019 odbyła się czwarta, kolejna już edycja Międzynarodowego Turnieju w Planowaniu Zajęć (

Kod: Zaznacz cały

https://www.itc2019.org/home
). Ja natomiast chcę rozwiązać problem podobny do tego z 2-go Międzynarodowego Turnieju w Planowaniu Zajęć z 2007 roku. :D

Curriculum jest to zbiór przedmiotów, które uczniowie mają wspólnych. Każdy przedmiot ma jednego nauczyciela, ilość zajęć (lekcji) tygodniowo, minimalną ilość dni tak by zajęcia było rozłożone w tygodniu oraz ilość uczniów uczęszczających na ten przedmiot. Celem jest przyporządkowanie czasu (para dzień tygodnia i pora dnia) do pokojów tak, aby spełnione były poniższe ograniczenia.

1. Jeden nauczyciel może nauczać tylko jednego przedmiotu o danym czasie (parze, dzień - pora dnia).
2. W jednym pokoju nauczany może być tylko jeden przedmiot o danym czasie.
3. Jeden przedmiot w danym curriculum może być nauczany o danym czasie.
4. Dodatkowo istnieje lista ograniczeń: pary (dzień i pora dnia) kiedy dany przedmiot nie może być nauczany (z jakiegoś powodu...).

Celem jest znalezienie planu lekcji tak, aby te ograniczenia były spełnione oraz aby zminimalizować "karę" za poniższe sytuacje.

5. Jeżeli ilość uczniów na danym przedmiocie jest większa od ilości miejsc na sali, do której przedmiot został dopasowany - kara 1pkt.
6. Jeżeli nie jesteśmy w stanie rozciągnąć zajęć (lekcji) z danego przedmiotu na minimalną ilość dni - kara 5pkt.

Moim początkowym pomysłem jest wprowadzenie zmiennej:
\(\displaystyle{ x_{c,r,d,t}= \begin{cases} 1 \;\; \mathrm{jeżeli \; przedmiot \; c \; przypisany \; jest \; to \; pokoju \; r \; dnia \; d \; i \; porze \; dnia \; t}\\ 0 \;\; \mathrm{w \; przeciwnym \; wypadku} \end{cases} }\)

Ale tutaj się zacinam trochę. :? Wszelkie pomysły mile widziane!
ODPOWIEDZ