. Counter constraints are a naturalrepresentation of constraints on the finite capacity of resources in resource-allocation type problems. They are a generic family of non-binary constraints that limit the number of variables that may be assigned particular values. Counter constraints can be represented by binary constraints, at a cost. We analyse the cost, show how a counter can be represented as a linear number of binary constraints, and demonstrate empirically that even with the optimal reduction,an explicit representation of counters is preferable to their representation as a set of binary constraints. For counter constraints, value ordering is essential. An heuristic for value ordering on constraint satisfaction problems (CSP), based on the estimated likelihoodof a solution, is presented. The proposed value ordering heuristic is useful for counter constraints, as well as for binary CSPs, where it can be used to approximate the number of solutions consistent with a particular value assignment to a variable. The proposed value ordering heuristic integrates counter constraints with binary constraint networks in a novel manner. Counter constraints are problematic for most heuristics, which are local in scope, yet we demonstrated empirically that the proposed value ordering heuristic is significantly superior to heuristics used in previous work.

Employee Timetabling Problems (ETP) are all around us. One possible approach for solving ETPs is to use constraint processing techniques. Another approach is to model human knowledge which is commonly used for solving such problems into knowledge-based systems for timetabling. It is difficult to represent the complex constraints of timetabling explicitly in constraint networks. On the other hand, knowledge-based representations of constraints are implicit and cannot support most of the heuristics of constraint-based processing that have been developed over the last decade. The present article presents on approach to representing and processing employee timetabling problems by a combination of explicit representations of some constraints and rule-based processing with heuristics for generic ETP constraints. This mixed-mode approach has been implemented in the form of a software package for defining and solving real-word ETPs. A general description of the design and organization of this software tool is given. Results for solving a typical real-world employee timetabling problem are presented and a comparison with the use of standard CSP (Constraint Satisfaction Problems) techniques is made. © 1997 John Wiley & Sons, Inc.

A general language for specifying resource allocation and time-tabling problems is presented. The language is based on an expert system paradigm that was developed previously by the authors and that enables the solution of resource allocation problems by using experts' knowledge and heuristics. The language enables the specification of a problem in terms of resources, activities, allocation rules, and constraints, and thus provides a convenient knowledge acquisition tool. The language syntax is powerful and allows the specification of rules and constraints that are very difficult to formulate with traditional approaches, and it also supports the specification of various control and backtracking strategies. We constructed a generalized inference engine that runs compiled resource allocation problem specification language (RAPS) programs and provides all necessary control structures. This engine acts as an expert system shell and is called expert system for resource allocation (ESRA). The performance of RAPS combined with ESRA is demonstrated by analyzing its solution of a typical resource allocation problem.>