System, utilized in scheduling, or the like, for satisfying constraints by allowing relaxation of constraints

Claim 1

A system, utilized in scheduling, for satisfying constraints by allowing relaxation of constraints, comprising: means for obtaining a final solution which specifies values that all variables can assume by repeating a problem solving cycle consisting of generation of a partial solution which refines values that some or all constraints of a constraint group can assume, and a test of checking whether or not the generated solution satisfies each of the constraints; constraint relaxation necessity detection means for detecting necessity of relaxation of some constraints during execution of the problem solving cycle; constraint relaxation knowledge management means for managing stored information associated with a possibility of relaxation and a method of relaxation, and a procedure to be enabled to know a relaxation condition from an external source in correspondence with each of the constraints; relaxation target constraint selection means for, when said constraint relaxation necessity detection means detects the necessity of relaxation of some constraint, selecting a constraint to be relaxed from the constraint group; and constraint relaxation means for checking the possibility of relaxation of the constraint selected by said relaxation target constraint selection means upon reception of information stored in said constraint relaxation knowledge management means, and for, when it is determined that relaxation is possible, executing relaxation of the constraint.

Claim 2

A system, utilized in scheduling, for satisfying constraints by allowing relaxation of constraints, comprising: means for obtaining a final solution which specifies values that all variables can assume by repeating a problem solving cycle consisting of generation of a partial solution which refines values that some or all constraints of a constraint group can assume, and a test of checking whether or not the generated solution satisfies each of the constraints; constraint relaxation necessity detection means for detecting necessity of relaxation of some constraints during execution of the problem solving cycle; constraint relaxation knowledge management means for managing stored information associated with a possibility of relaxation and a method of relaxation, and a procedure to be enabled to know a relaxation condition from an external source in correspondence with each of the constraints; relaxation target constraint selection means for, when said constraint relaxation necessity detection means detects the necessity of relaxation of some constraint, selecting a constraint to be relaxed from the constraint group; and constraint relaxation means for checking the possibility of relaxation of the constraint selected by said relaxation target constraint selection means upon reception of information stored in said constraint relaxation knowledge management means, and for, when it is determined that relaxation is possible, executing relaxation of the constraint.

Claim 3

A system, utilized in scheduling, for satisfying constraints by allowing relaxation of constraints, comprising: means for obtaining a final solution which specifies values that all variables can assume by repeating a problem solving cycle consisting of generation of a partial solution which refines values that some or all constraints of a constraint group can assume, and a test of checking whether or not the generated solution satisfies each of the constraints; constraint relaxation necessity detection means for detecting necessity of relaxation of some constraint during execution of the problem solving cycle; constraint relaxation knowledge management means for managing stored information associated with a possibility of relaxation and a method of relaxation, and a procedure to be enabled to know a relaxation condition from an external source in correspondence with each of the constraints; relaxation target constraint selection means for, when said constraint relaxation necessity detection means detects the necessity of relaxation of some constraint, selecting a constraint to be relaxed from the constraint group; constraint relaxation means for checking the possibility of relaxation of the constraint selected by said relaxation target constraint selection means upon reception of information stored in said constraint relaxation knowledge management means, and for, when it is determined that relaxation is possible, executing relaxation of the constraint; relaxation reason acquisition means for, when said constraint relaxation means executes the procedure according to the information associated with the procedure to be enabled to know a relaxation condition from the external source, which information is stored in said constraint relaxation knowledge management means, and knows the relaxation condition from the external source, acquiring a relaxation reason; relaxation knowledge generation means for analyzing the relaxation reason input from said relaxation reason acquisition means, and generating a determination condition for determining possibility of relaxation of a constraint and a relaxation method; and relaxation knowledge addition means for adding the determination condition information and the relaxation method information generated by said relaxation knowledge generation means to said constraint relaxation knowledge management means.

Claim 4

A system, utilized in scheduling, for satisfying constraints by allowing relaxation of constraints, comprising: means for obtaining a final solution which specifies values that all variables can assume by repeating a problem solving cycle consisting of generation of a partial solution which refines values that some or all constraints of a constraint group can assume, and a test of checking whether or not the generated solution satisfies each of the constraints; constraint relaxation necessity detection means for detecting necessity of relaxation of some constraint during execution of the problem solving cycle; constraint relaxation knowledge management means for managing stored information associated with a possibility of relaxation and a method of relaxation, and a procedure to be enabled to know a relaxation condition from an external source in correspondence with each of the constraints; relaxation target constraint selection means for, when said constraint relaxation necessity detection means detects the necessity of relaxation of some constraint, selecting a constraint to be relaxed from the constraint group; constraint relaxation means for checking the possibility of relaxation of the constraint selected by said relaxation target constraint selection means upon reception of information stored in said constraint relaxation knowledge management means, and for, when it is determined that relaxation is possible, executing relaxation of the constraint; relaxation reason acquisition means for, when said constraint relaxation means executes the procedure according to the information associated with the procedure to be enabled to know a relaxation condition from the external source, which information is stored in said constraint relaxation knowledge management means, and knows the relaxation condition from the external source, acquiring a relaxation reason; relaxation knowledge generation means for analyzing the relaxation reason input from said relaxation reason acquisition means, and generating a determination condition for determining possibility of relaxation of a constraint and a relaxation method; and relaxation knowledge addition means for adding the determination condition information and the relaxation method information generated by said relaxation knowledge generation means to said constraint relaxation knowledge management means.