The paper is concerned with the role that anytime algorithms can play in the domain of maximal constraint satisfaction. The goal is to find a solution that satisfies as many constraints as possible within a given time limit. Anytime algorithms are a new approach, in real-time systems, which trade solution quality for time. They were applied successfully to many different real-time applications such as robot planning, real-time sensing and acting, on-line learning, and knowledge based anytime computations. We propose to apply them to job-shop scheduling. Three algorithms are presented to various versions of the problem. The results are presented and compared.
展开▼
