Preference-Based Search for Scheduling

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 17

Search

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 nonmonotonic reasoning (Brewka 1989; Geffner 1990; Grosof 1991) on priorities between defaults. The basic idea of PBS is quite simple: Always pick a locally best decision alpha. Either make this decision alpha or make other locally best decisions that allow to deduce not alpha and thus represent a counterargument for alpha. If there is no possible counterargument then PBS does not explore the subtree of not alpha. Further pruning of the search space is obtained by nonmonotonic inference rules that are inspired by Doyle’s TMS and that detect decisions belonging to all or none preferred solution. We show that PBS can optimally solve various important scheduling problems. First experimental results for job-shop scheduling problems such as MT20 are encouraging.