Multi-Agent Techniques for Scheduling

In general, scheduling is deciding which job or task is to be processed on which machine. Obvious examples of scheduling include creating timetables for nurses in a hospital or teaching activities in schools, allocating processor time to computer jobs, and allocating assembly lines or machines to produce different goods. All scheduling problems include some constraints, like: a machine can handle at most one job at a time. When all constraints are satisfied, you have a feasible schedule. Many feasible schedules may exist, however, some are preferred to others. For example, the sooner all jobs are finished, the better.

For relatively easy instances of these problems, algorithms exist that are guaranteed to find the optimal solution in a reasonable amount of time. For others, approximation techniques or heuristics exist which give reasonably good schedules.

More difficult scheduling problems arise when uncertainty is added. For example, it could be uncertain what the exact processing time is of a given job. It could be that a machine breaks down and a technician needs to intervene. Another type of uncertainty lies in the arrivalrate of new jobs.

For these harder scheduling problems we currently explore decentralised decision making, i.e. multi-agent learning.

• Literature study of scheduling. An extensive overview is provide in the book “Scheduling: Scheduling Theory, Algorithms, and Systems” by M. Pinedo (2008).
• For a specific class of scheduling problems, propose a new or improved (reinforcement learning) algorithm.
• Implement the technique and evaluate by doing computer simulations.
• Analyse and compare with existing solutions.
• Report on the results and draw conclusions.

Interested students should contact David Catteeuw (dcatteeu@vub.ac.be) for more information.

Promotor: Ann Nowé