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.