[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publications: [PUBLink] [PUBLink])

A task constraint manages a set of temporal relations between a job's tasks (see figure below). Each relation involves links to two decision variables V1 and V2, a constant c and a comparator ¤ {<,=,>}, such that V1 ¤ V2 + c. The inconsistency of a relation is given by the minimal shift distance for one of the variables required to satisfy the relation. The TC's total inconsistency is the sum of the relations' inconsistencies.

The basic improvement heuristic of the task constraint (TC-H1) selects an inconsistent relation with a choice probability for a relation that is proportional to its inconsistency (see figure below). One of the involved variables is selected randomly, and a minimal shift of this variable is performed such that the relation is fulfilled.

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek