Maximal Flexibility and Optimal Decoupling in Task Scheduling Problems

Abstract

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.