Planning, scheduling, and transportation


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 an assignment should be maximized when these tasks or jobs are performed according to the prepared schedule or the timetable. The finding of a suitable schedule is necessary for various real-life problems such as the nurse rostering, the university course timetabling, or job scheduling. Scheduling is often necessary for combination with an assignment of resources for transportation in problems such as vehicle routing, logistics, or rail transportation. Here, it is essential to consider the assignment of resources in time as well as network infrastructure defined by a graph.

The main research areas of this group include

  • vehicle routing and logistics,
  • rail transportation,
  • intelligent trasportation systems,
  • university timetabling,
  • scheduling of mobile robots,
  • scheduling of computational jobs

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.

We are working on various transportation problems such as freight transportation, optimization for railways, data transfer planning, scheduling of mobile robots, or scheduling of traffic lights. Freight transportation is related to logistics problems with backgrounds in vehicle routing. Our work in optimization for railways is concerned about capacity planning, network design, as well as timetable construction. Scheduling of mobile robots in the factory involves transportation of robots, their processing of jobs as well as traditional machine scheduling. We have explored intelligent traffic control using scheduling models and advanced search algorithms. Scheduling of traffic lights is processed for a single intersection as well as a distributed system of communicating intersections.

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 university course timetabling competition ITC 2019 with almost 200 registered users from more than 50 countries.

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.

Information for students

The areas of scheduling and trasportation provide 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 and routing of vehicles
  • Educational timetabling
  • Distributed scheduling in computational environments
  • Distributed data processing in high energy physics

Selected topics of master and bachelor thesis:

  • Vehicle routing using large neighborhood search
  • Minimal perturbations for vehicle routing problems
  • Clustering for large-scale vehicle routing problems
  • 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
https://www.fi.muni.cz/~hanka/