Abstract: | This thesis is concerned with the role that partial constraint satisfaction can play in the problem of single machine scheduling. Partial constraint satisfaction is a new process which combines branch and bound search with constraint satisfaction techniques. An algorithm is presented for applying partial constraint satisfaction to the single machine scheduling problem. Heuristics to direct this algorithm are described, and compared in terms of their efficiency and the quality of the resulting schedules.
|