Scheduling Multi-Capacitated Resources under Complex Temporal Constraints

Abstract

In this paper we develop and analyse CSP-based procedures for solving scheduling problems with metric temporal constraints (e.g. jobs’ deadlines or separation constraints between couple of consecutive activities in a job) and multiple capacitated resources, referred to formally as the Multiple Capacitated Metric Scheduling Problem (MCM-SP). This work follows two different solution approaches used to identify resource capacity conflicts. (1) Proffle-based approaches (e.g. [1]) - They consist of characterizing a resource demand as a function of time, identifying periods of overallocation in this demand proffle, and incrementally performing “eveling actions” to (hopefully) ensure that resource usage peaks fall below the total capacity of the resource. (2) Clique-based approaches [3, 2] - Given a current schedule, this approach builds up a conflicts graph whose nodes are activities and whose edges represent overlapping resource capacity requests of the connected activities. Fully connected subgraphs (cliques) are identiffed and if the number of nodes in the clique is greater than resource capacity a conflict is detected Clique-based approaches perform more global analysis and offer greater accuracy in conflict detection in comparison with local pairwise proffle-based analysis, but at a potentially much higher computational cost. In a previous paper [1], several proffle-based solution procedures were developed and evaluated (in particular the ESTA algorithm), some of them descending from an approach proposed in the planning literature.