Preference-Based Search for Scheduling

Abstract

Preference-based search (PBS) is a new search procedure for solving combinatorial optimization problems. Given a set of preferences between search decisions, PBS searches through a space of preferred solutions, which is tighter than the space of all solutions. The definition of preferred solutions is based on work in non-monotonic reasoning (Brewka 1989; Geffner & Pearl 1992; Grosof 1991) on priorities between defaults. The basic idea of PBS is quite simple: Always pick a locally best decision α. Either make the decision α or make other locally best decisions that allow to deduce ¬α and thus represent a counterargument for α. If there is no possible counterargument then PBS does not explore the subtree of ¬α. This pruning of the search space is obtained by non-monotonic inference rules that are inspired by Doyle’s TMS and that detect decisions belonging to all or no preferred so-lution. We show that PBS can optimally solve various impor-tant scheduling problems.