Fuzzy constraints in job-shop scheduling

Didier Dubois (1, 2) , Henri Prade (1, 2)

1 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage
2 CNRS - Centre National de la Recherche Scientifique

This paper proposes an extension of the constraint-based approach to job-shop scheduling, that accounts for the flexibility of temporal constraints and the uncertainty of operation durations. The set of solutions to a problem is viewed as a fuzzy set whose membership function reflects preference. This membership function is obtained by an egalitarist aggregation of local constraint-satisfaction levels. Uncertainty is qualitatively described in terms of possibility distributions. The paper formulates a simple mathematical model of job-shop scheduling under preference and uncertainty, relating it to the formal framework of constraint-satisfaction problems in artificial intelligence. A combinatorial search method that solves the problem is outlined, including fuzzy extensions of well-known look-ahead schemes.

Domaines: Intelligence artificielle [cs.AI]

Didier Dubois, Henri Prade. Fuzzy constraints in job-shop scheduling. Journal of Intelligent Manufacturing, 1995, 6 (4), pp.215--234. ⟨10.1007/BF00128646⟩. ⟨hal-04049238⟩