MODELING AND MANAGING DISJUNCTIONS IN SCHEDULING PROBLEMS

In this paper is presented a method for modelling and managing various constraints encountered in task scheduling problems. The approach aim s at characterizing feasible schedules through the analysis of the set of constraints and their interaction, regardless of any optimization criteria. This analysis is achieved by a constraint propagation proces s on a constraint graph and produces both restricted domains for the d ecision variables and an updated formulation of the initial constraint s. The graphs usually used to model temporal constraints seem to be li mited because they only allow the representation of strict precedence relations between two tasks. In order to model a larger variety of tem poral constraints, particularly any constraint that connects two event s (start- or finish-time of a task), a model called a time-bound-on-no de (TBON) graph is proposed in which each task is featured by two node s. Then it becomes possible to handle constraints on task durations, d ue for example to flexibilities in resource utilization. This kind of graph is not new and has already been investigated in related works on project planning and Constraint Satisfaction Problems. But its proces sing and interpretation deserved to be developed, particularly for the present purpose, which is the search for the necessary conditions of feasibility. With respect to conjunctive temporal constraints, the ana lysis is achieved with a polynomial algorithm based on the longest pat h search on a conjunctive TBON graph, yielding the necessary and suffi cient conditions of feasibility. Taking account of resource constraint s leads to defining disjunctive constraints. To this end, disjunctive sets of arcs are introduced, making the TBON graph nonconjunctive. In this case, a complete characterization of feasibility cannot reasonabl y be faced, due to the combinatorial feature. Nevertheless, a polynomi al algorithm that applies reduction and deletion rules on the nonconju nctive part of the graph is proposed to restart new propagations on th e conjunctive part until all deductions have been made.