W pracy rozważany jest problem układania rozkładów zajęć dla szkoły wyższej. Do rozwiązania tego zagadnienia wykorzystane zostały następujące metody lokalnego i globalnego przeszukiwania przestrzeni możliwych rozwiązań: symulowane wyżarzanie, przeszukiwanie tabu oraz algorytmy genetyczne. Zaproponowano rozwiązanie polegające na przekształceniu problemu harmonogramowania zajęć w problem kolorowania grafów, który rozwiązywany jest za pomocą każdej z wymienionych metod. W pracy opisane są głównie doświadczenia komputerowe zaprojektowane i wykonane dla rozwiązania problemu układania rozkładów zajęć, mające na celu zarówno gruntowną analizę badanych metod jak i wskazanie tej, której zastosowanie daje najlepsze rezultaty. Doświadczenia te zostały przeprowadzone na danych generowanych w sposób losowy oraz na danych rzeczywistych pobranych z systemu wspomagającego układanie rozkładów zajęć dla Wydziału Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej.
EN
In paper we consider a university timetabling problem. The following methods of local and global search of a solution space are used: simulated annealing, tabu search and genetic algorithms. We propose an approach based on a transformation of the basic problem to a graph coloring problem which is then solved with each of the methods. Mainly, computational tests, which were designed to analyze all methods in depth, are described. We use both randomly generated and real data obtained from a timetabling system used in Electronics Telecommunications and Informatics Faculty at Gdansk University of Technology.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W niniejszej pracy przedstawiono warianty adaptacji przeszukiwania tabu wraz z wynikami eksperymentów obliczeniowych do układania szkolnych harmonogramów zajęć. W modelu teoretycznym uwzględniono zarówno ograniczenia krytyczne, np. konflikty czasowe uczestników zajęć (nauczyciele i uczniowie) oraz brak przerw w zajęciach (eliminacja okienek) wybranych uczestników, jak również niekrytyczne składniki funkcji celu, np. równomierne rozłożenie zajęć w tygodniu i możliwie mała rozpiętość czasowa harmonogramu w każdym dniu.
EN
In this paper we present variants of tabu search implementation for computing school timetables together with computational results. In the theoretical model critical conditions as for example participant's time conflicts and consecutive class's schedule, as well as not critical conditions as for example even distribution of lessons and short span in each day are considered.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W pracy zostaną opisane najnowsze trendy dotyczące rozwiązywania problemu układania harmonogramów zajęć. Przedmiotem rozważań będą techniki używane w ostatnich latach na Zachodzie do rozwiązywania problemu. Pokrótce zostaną opisane charakterystyczne cechy pakietów komercyjnych spotykanych na tamtejszym rynku. Na zakończenie przedstawione będą perspektywy rozwoju oprogramowania związanego z układaniem rozkładów zajęć.
EN
In this paper the newest trends in automatic timetabling are described. We focus on techniques used for this problem during last years in North America and Western Europe. Besides, we describe characteristic features of commercial software. Finally, we present some ideas for future of automatic timetabling.
W pracy rozważamy szeregowanie zadań w rozrzedzonym systemie otwartym bez obustronnych przestojów o jednostkowym czasie wykonania operacji. Problem ten modelujemy za pomocą zwartego kolorowania krawędziowego grafów dwudzielnych. Stopień rozrzedzenia systemu otwartego mierzymy za pomocą liczby cyklomatycznej odpowiadającego mu grafu. Praca opisuje w skrócie przebieg eksperymentu komputerowego weryfikującego hipotezę dotyczącą zwartego kolorowania grafów o liczbie cyklomatycznej nie większej niż 8.
EN
In the paper we consider compact scheduling of tasks in sparse open shop with zero-one execution time of operations. We model this problem with consecutive edge coloring of bipartite graphs. Sparse factor of open shop is measured as cyclomatic number of corresponding graph. We shortly describe computer experiments which verify hypotheses that concern consecutive coloring of graphs with cyclomatic number not greater than 8.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.