Heuristic Methods for Solving Job-Shop Scheduling Problems.
Antonio Garrido Tejero, Miguel Á. Salido, Federico Barber, Montserrat Abril López · 2000
Solving scheduling problems with Constraint Satisfaction Problems (CSP’s) techniques implies a wide space search with a large number of variables, each one of them with a wide interpretation domain. This paper discusses the application of CSP heuristic techniques (based on the concept of slack of activities) for variable and value ordering on a special type of job-shop scheduling problems in which the operations must schedule inside of temporal windows. These techniques are improved by introducing the concepts of slack probability and the find-hole method. Thus, a more flexible heuristic technique is obtained, which improves empirical efficiency and allows early detection of unfeasible problems.