Scheduling, planning and timetabling


In general, scheduling and timetabling solve the problem of assigning jobs or tasks on the available resources in time. Moreover the overall profit of such assignment should be maximized, when these tasks or jobs are performed according to the prepared schedule or the timetable. Finding of suitable schedule is necessary in various real-life problems such as the nurse rostering, the university course timetabling or the job scheduling.

The main research areas of this group include

  • university timetabling,
  • scheduling of computational jobs,
  • scheduling of mobile robots,
  • transport planning,
  • scheduling in traffic control

which we are solving both as static as well as dynamic scheduling problems using methods of artificial intelligence and operations research such as various search algorithms, meta-heuristics, integer or constraint programming.

While in the classical scheduling the whole problem is known in advance, in the dynamic case the problem changes over time as the solution is created. Jobs, tasks, etc., as well as resources may appear and disappear (job arrivals, job completions or cancellations, machine failures and restarts) or the parameters of jobs or tasks may change. Typically, the execution time of a job may change. Therefore, in the dynamic scheduling problem an efficient construction of the schedule with appropriate reactions on dynamic changes is requested.

University course timetabling solves the problem of finding suitable timetable for courses taught at the university. Courses are assigned into time slots and available classrooms so that the students' requirements, preferences of teachers as well as the study requirements are all met. A long-term research in this area together with the collaboration with the Purdue University lead to the development of a unique timetabling system, that is able to solve many timetabling problems of a very large scale. This system, called UniTime, is also applied for timetabling at our university for several faculties including our Faculty of Informatics. We are also involved in organizing a new university course timetabling competition ITC 2019.

When scheduling computational jobs in grid or cloud computing environments, it is necessary to assign jobs of several users onto the suitable and available machines in large, heterogeneous and dynamic computing environment. Such process should satisfy several criteria such as the good machine utilization, the fairness or the non-trivial Quality of Service (QoS). Research in this area resulted in the plan-based Torque scheduler used in national e-infrastructure CERIT for scheduling of approximately 5,000 CPUs. Scheduling of computational jobs is related to data transfer planning where data transfers are needed to process jobs. Advance planning of data transfers as well as other related resources is related to network flows and transport planning problems.

We are working on various transport planning problems such as data transfer planning, scheduling of mobile robots or scheduling of traffic lights. Scheduling of mobile robots in factory involves transportation of robots, their processing of jobs as well as traditional machine scheduling. We explore intelligent traffic control using scheduling models and advanced search algorithms. Scheduling of traffic lights is processed for single intersection as well as distributed system of communicating intersections.

Information for students

The area of timetabling and scheduling provides several interesting topics, which can include both practical and theoretical research. You can join this group either through writing bachelor or master thesis or through the doctoral study. IS MUNI provides several available topics for the bachelor or master thesis. These topics are offered and supervised by the members of this research team. Moreover, based on the mutual agreement with the student, it is also possible to create a new topic in the area of our research.

Topics for doctoral students:

  • Scheduling of mobile robots
  • Educational timetabling
  • Distributed scheduling in computational environments
  • Distributed data processing in high energy physics

Selected topics of master and bachelor thesis:

  • Search algorithms for traffic lights scheduling
  • Scheduling for adventure travel agency
  • Employee scheduling for science center
  • Teacher-oriented fairness in course timetabling
  • Bachelor state examination timetabling at the Faculty of Informatics
  • Multimedia streams planning with transcoding using local search heuristics
  • Course timetabling at Masaryk University in the UniTime system
  • Grid scheduling with local search
  • Web interface of international timetabling competition

International and national collaboration

This group cooperates with several international institutions, including

On the national level, we cooperate with several teams. Those are especially

Research group

We are members of Sitola research laboratory.

Contact

doc. Mgr. Hana Rudová, PhD.
hanka@fi.muni.cz
http://www.fi.muni.cz/~hanka/