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 timetable. Finding a suitable schedule is necessary for various real-life problems such as nurse rostering, university course timetabling, or job scheduling. Scheduling is often necessary for combination with allocating 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 and network infrastructure defined by a graph.
The main research areas of this group include
- vehicle routing and logistics,
- rail transportation,
- university timetabling,
- scheduling in distributed environments
which we are solving both static as well as dynamic scheduling problems using methods of artificial intelligence and operations research such as various search algorithms, metaheuristics, integer, or constraint programming. While in 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, transfer requests, as well as resources may appear and disappear (job or request arrivals, machine failures, or vehicle breakdowns) or the parameters of jobs or tasks may change (capacity or travel time changes). Therefore, efficient construction of the schedule and routes with appropriate reactions to dynamic changes is requested in the dynamic scheduling or routing problem.
We are working on various transportation problems such as freight transportation, optimization for railways, data transfer planning, or scheduling of mobile robots. Freight transportation is related to logistics problems with backgrounds in vehicle routing. We aim to solve the problems from practice, considering large-scale routing problems with rich characteristics. Our work on vehicle routing problems in freight transportation led to the construction of the software which is nowadays used by Wereldo company. In cooperation with the Institute for Transport Economics, Geography and Policy, we work on optimization for railways which is concerned with capacity planning, network design, as well as timetable construction. Scheduling of mobile robots in the factory involves the transportation of robots, their processing of jobs, and traditional machine scheduling.
University course timetabling solves the problem of finding a suitable timetable for courses taught at the university. Courses are assigned to time slots and available classrooms so that the student's 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 led to the development of a unique timetabling system, that can solve many timetabling problems of a very large scale. This system, called UniTime, is also applied for timetabling at our university for most of the faculties, including our Faculty of Informatics. We have been also involved in organizing a university course timetabling competition ITC 2019 with more than 350 registered users from about 60 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 a large, heterogeneous, and dynamic computing environment. Such a process should satisfy several criteria such as good machine utilization, 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. We have developed the Alea job scheduling simulator which is applied by many researchers over the world. Scheduling of computational jobs is related to data transfer planning where data transfers are needed to process jobs. Advance planning of data transfers and other related resources is related to network flows and transport planning problems.
Information for students
The areas of scheduling and transportation provide several interesting topics, including both practical and theoretical research. You can join this group by writing a bachelor's or master's thesis or doctoral study. IS MUNI provides topics for the bachelor's or master's thesis. These topics are offered and supervised by the members of this research team. More than that, 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:
- Vehicle routing and logistics
- Rail transportation
- Educational timetabling
- Distributed scheduling in computational environments
Selected topics of master and bachelor thesis:
- Vehicle routing competition
- Vehicle routing with transfers
- Dynamic vehicle routing with rich problem characteristics
- Vehicle routing with metaheuristics
- Planning for high-speed railways
- Dynamic vehicle routing problems
- Resource scheduling in OpenStack
- Visualization of tree search algorithms
- Scheduling of mobile robots using constraint programming
- 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
CollaborationsWe cooperate with various teams. Those are especially
- MetaCentrum and CESNET, Czech Republic
- CERIT Scientific Cloud, Institute of Computer Science, Masaryk University
- Institute for Transport Economics, Geography and Policy at Masaryk University
- Wereldo.com, Brno, Czech Republic
Research groupWe are members of Sitola research laboratory.
doc. Mgr. Hana Rudová, PhD.