Algorytm do obliczania harmonogramu z podanymi ograniczeniami

Question

Rozważam hipotetyczny problem i szukam wskazówek, jak podejść do rozwiązania problemu, z algorytmicznego punktu widzenia.

Problem:

Rozważmy uniwersytet. Masz następujące obiekty:

• Nauczanie personelu. Każdy członek personelu uczy jednego lub więcej artykułów.
• Studenci. Każdy uczeń bierze jeden lub więcej artykułów.
• Pokoje. Pokoje mieszczą pewną liczbę studentów i zawierają określone rodzaje urządzeń.
• Artykuły. Wymagaj pewnego rodzaju sprzętu i pewnej ilości czasu w każdym tygodniu.

Biorąc pod uwagę informacje na temat zapisów (ie- ile studenci są zapisani w każdym papierze, a co pracownicy są przydzielane uczyć każdy papier), jak mogę obliczyć harmonogram, który jest zgodny z następującą ograniczenia:

1. Personel może uczyć tylko jednej rzeczy naraz.
2. Uczniowie mogą uczestniczyć tylko w jednym dokumencie naraz.
3. Pokoje mogą pomieścić tylko określoną liczbę studentów.
4. Papiery, które wymagają określonego rodzaju sprzętu, mogą być przechowywane tylko w pomieszczeniu, które zapewnia tego typu urządzenia.
5. Godziny pracy są od poniedziałku do piątku, od 8 do 12 i od 1 do 5.

Dyskusja:

W rzeczywistości nie jestem zbyt zaniepokojony sytuacją opisaną powyżej - to ogólna klasa problemu, że jestem ciekaw. Na pierwszy rzut oka wydaje mi się, że dobrze pasuje do algorytmu genetycznego, ale funkcja przydatności dla takiego algorytmu byłaby niezwykle złożona.

Jakie jest dobre podejście do próby rozwiązania tego rodzaju problemu spełniającego ograniczenia?

Myślę, że prawdopodobnie nie da się tego idealnie rozwiązać, ponieważ studenci mogą wziąć kombinację papierów, która prowadzi do sytuacji niemożliwych, zwłaszcza, że ​​liczba studentów wzrasta.

Answer 1

Pozostając przy algorytmach genetycznych, nie sądzę, aby funkcja fitness była bardzo złożona, wręcz przeciwnie.

Po prostu po prostu sprawdź rozwiązanie kandydata (bez względu na kodowanie) dla każdego z więzów (masz tylko 5) i przypisz im wagę, aby po spełnieniu ograniczenia wagę dodano do całkowitego wyniku, może reprezentować sprawność fizyczną.

W takim scenariuszu wystarczy zminimalizować funkcję fitness (ponieważ najlepsza możliwa poprawa to 0, co oznacza, że ​​wszystkie ograniczenia są spełnione) i pozwól GA zliczyć liczby.

Kodowanie zajmie trochę na zastanawianie się, ale raz, że zrobił to powinno być proste, chyba że ja czegoś brakuje, oczywiście :)

Answer 2

Bardzo ograniczoną wersją tego problemu jest NP-Complete.

Weź pod uwagę przypadek, gdy dokładnie jeden student może wziąć papier.

Teraz dla danego przedziału czasowego (powiedzmy, że papier uczy się przez cały dzień), możesz utworzyć trójczęściowy wykres z pokojami, dokumentami i uczniami, z krawędzią między papierem a uczniem, jeśli ten uczeń chce Weź to. Należy również dodać krawędzie między papierem i możliwymi pomieszczeniami.

Teraz widzimy, że 3 Dimensional matching problem jest instancją twojego problemu: musisz wybrać kombinację non-overlapping (student, paper, room) dla tej konkretnej szczeliny czasowej.

Prawdopodobnie lepiej poradzisz sobie z pewną heurystyką dotyczącą ogólnego problemu. Przepraszam, nie mogę ci tam pomóc.

Nadzieję, że pomaga.