wpait

kolorowanie totalne (procesory)

kolorowanie listowe (choosability) moze miec to sens dla ukladania harmonogramów

open shop model - szeregowanie zadan dedykowanych
zadania podzielone naa operacje, operacje przypisane do konkretnych procesorow
operacji ejst tyle co procesorow, procesor wykonuje dane zadanie, kolejnosc dowolna, ozadanie nie moze vbyc wykonywane jednoczesnie, procesor na raz mieli jedno zadanie
diagram ganta, uszeregowanie w czasie
kryterium cmax - moment zakoncenia ostatniego z zadan
kryteitum sumy czasow zakonczenia suma cj (bo jak sa przestoje to jest dluzej i gorzej)
mozna wziasc sredni czas zakonczenia jako parametr harmonogramu

model sumacyjny
szeregowanie zadan dedykowanych na procesorach rownoleglych
kryterium sumacyjne

kolorowanie sprawiedliwe
kazdry procesor po rowni wykorzystywany




Kolorowanie krawędziowe grafów.
Szeregowanie zadań na procesorach dedykowanych (open-shop).
Układanie harmonogramów (planów zajęć). Harmonogramów bez "okienek" (klasy, nauczyciele, godziny, bez przestojów w klasach oraz okienek u nauczycieli)

Układanie harmonogramów
Rzeczywiste
Jednym ze sposobów rozwiązywania tego typu problemów jest użycie algorytmu genetycznego

Bardzo prosty przykład
Mamy czterech nauczycieli
Pan Andrzej, nauczyciel matematyki
Pani Beata, nauczycielka historii
Pan Czesław, nauczyciel muzyki
Pan Dezydery, nauczyciel obrony przed czarną magią

I cztery klasy: Ia, IIa, IIIa, Ib

Ia ma trzy godziny matematki, dwie historii i trzy obrony przed czarną magią
II a ma dwie godziny matematki, dwie historii i obrony przed czarną magią
Ia ma trzy godziny matematki, dwie historii i trzy obrony przed czarną magią
http://www.cs.ucsb.edu/~teo/papers/OSHand.pdf
http://en.wikipedia.org/wiki/School_timetable
http://alexandria.tue.nl/extra2/200211248.pdf
http://www.cs.qub.ac.uk/itc2007/index.htm
http://www.intechopen.com/books/greedy_algorithms/solving_the_high_school_scheduling_problem_modelled_with_constraints_satisfaction_using_hybrid_heuri
http://cdn.intechopen.com/pdfs/5830.pdf
open-shop scheduling problem
http://en.wikipedia.org/wiki/Open-shop_scheduling
http://constellation.uqac.ca/2322/