Maximal Flexibility and Optimal Decoupling in Task Scheduling Problems

Maximal Flexibility and Optimal Decoupling in Task Scheduling Problems

Endhoven, L.A.M.

Aardal, K.I. (mentor)
Witteveen, C. (mentor)
Klos, T.B. (mentor)

Electrical Engineering, Mathematics and Computer Science

Applied mathematics

Optimization

2012-08-29

This thesis focuses on the properties of (multi-agent) task scheduling instances represented as Simple Temporal Problems (STP). By defining a subclass STP$_{\prec}$ of STPs that contain these task scheduling instances, existing algorithms for arbitrary STPs can be improved if applied to task scheduling STPs, allowing arbitrary schedules and temporal decouplings to be created more efficiently. With the introduction of a new flexibility metric in this thesis, a Linear Programming (LP) formulation as well as an alternative Maximum Flexibility Algorithm is given to create maximally flexible open schedules from which an optimal temporal decoupling can be derived. This thesis also contains a proof that in task scheduling instances, contrary to intuition, an optimal temporal decoupling does not reduce the flexibility of the system. In order to ensure fair decouplings or open schedules for either the tasks or the agents, three types of egalitarian flexibility problem formulations are presented including LP formulations to solve these problems.

scheduling
decoupling

http://resolver.tudelft.nl/uuid:c9a3e9fd-ec74-490a-a15c-c7f14e528a24

2012-08-24

Student theses

master thesis

(c) 2012 Endhoven, L.A.M.