The Design And Implementation Of Constraint-Based Scheduler

Scheduling problems arise in areas as diverse as production planning, personnel planning, computer design, and time tabling.Over time, the theory and application of Scheduling problems has grown into an important field of research. Roughly speaking,the traditional research on the Scheduling problems has grown into two main branch,one is operation research(OR), the other is artificial intelligence(AI).A lot of the attention in OR has been paid to scheduling problems that are based on relatively simple mathematical models.The intensive research on the mathematical models has led OR achieve a high level of efficiency in its algorithms,however, when modeling a practical scheduling problem and using these classical models,OR becomes relatively poor.Forcing model has to disgard many degrees of freedom and side constraints that exist in the practical scheduling situation.Disgarding some degrees of freedom would result in the loss of some solutions, while disgarding side constraints would result in the deviation from the orginal solutions.In contrast,AI research focuses on the more general scheduling models and tries to solve the problems by using general problem solving paradigms, while too much attention on the general attributes leads the lower efficiency than OR.Obviously,we want a general model provided by the high efficiency algorithm.The emergence of Constraint programming(CP) integrated with OR algorithms satisfies the request. Generally speaking,Constraint programming pays attention to solving an instance of CSP which includes a set of variables, the domain assigned to every variable, and a set of constraints on the variables.Constraint denotes the relation between one variable or several variables,for example:if x is an integer variable,x<10 is the constraint on the variable x.Solving an instance of CSP is a process of assigning a value to every variable from its domain synchronously satisfying all the constraints.In CP, the existing of constraint is for reducing the amount of computation of the problem to be solved.Concretely,we use constraints to reduce the domains of the problems and checking the inconsistency, the process of deduction is called constraint propagation.The symbols + - * > < = are the primary constraints of general Slover based on constraints,the temporal constraint and the resource constraint are the primary constraints of general Scheduler based on constraints. Constraint-based Scheduling is using the thought of the constraint programming to solve the combination optimization problems especially all kinds of scheduling problems.One of main characteristic is describing the problem naturely, intuitionisticly and intensively,so the description of the problem serves as the definition of the problem.The concordance of the description and definition guarantee that the solution of constraints must be the solution of the problem defined by us.The merit of the modeling separating from the solving is embedded in the Scheduling system based on constraints.CP make the system accurate,efficient,flexible and extendable.The constraint-based Scheduler system developed by us is the object oriented and CP's system based on the general constraint Solver which integrates the constraints into the object oriented languages(C++), takes constraints, variables and solver as entities, based on constraint programming, uses predefined constraint sets and general solver to resolve combinatorial optimization and scheduling problems.It makes easier to develop the application of scheduling and resource allocation based on constraints.It provides some mechanisms to solve these problems.we creat some classes to describe the problem itself such as activities, resources,temporal constraint,at the same time,it can use the variable ,constraint provided by Solver to describe some other special constraints to realize the solving strategy to special problem.The target of our system is to simplify the development of the application of industrial scheduling. By expending the original Solver, we design and realize the alg...