Here we consider representing Job-Shop Scheduling Problems (JSSPs) as Constraint-Satisfaction Problems (CSPs) and employing constraint-directed search to find optimal or near optimal solutions. A CSP is a problem with a finite set of variables (each with a finite domain of values) and a set of constraints that restrict the possible assignments of values to variables. Scheduling a sequence of jobs involves assigning start times to each job subject to certain constraints. Usually a schedule is sought that minimizes cost and/or some measure of time, like the completion time or makespan.
展开▼