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

• US 5,353,229 A
• Filed: 10/30/1992
• Issued: 10/04/1994
• Est. Priority Date: 12/26/1991
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Tanaka, Toshikazu
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): BROWN, THOMAS
• Application Number:
  US07/969,074
• Time in Patent Office: 704 Days
• Field of Search: 364/468, 364/153-156, 364/401-403, 395/55, 395/904, 395/926
• US Class Current: 700/103
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

In a system, utilized in, e.g., scheduling, for satisfying constraints by allowing relaxation of constraints, a constraint relaxation necessity detection section detects necessity of constraint relaxation in a problem solving cycle of a problem solving section. When the necessity of constraint relaxation is detected, a relaxation target constraint selection section is enabled to select a constraint to be relaxed from a constraint group. A constraint relaxation section searches a constraint relaxation knowledge management section in association with the selected constraint to check if a partial solution satisfies a relaxation permission condition. If the relaxation permission condition is satisfied, constraint relaxation is attempted according to a relaxation method recorded in correspondence with the relaxation permission condition. When the constraint relaxation is executed, the constraint relaxation necessity detection section checks if the constraint relaxation is successful, and the control returns to the problem solving cycle of the problem solving section.

Claims

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.

3. A system according to claim 1, wherein the possibility of relaxation comprises a relaxation permission condition corresponding to each constraint, and wherein said constraint relaxation means searches said constraint relaxation knowledge management means to check if the partial solution satisfies the relaxation permission condition corresponding to the selected constraint.

4. A system according to claim 3, wherein said constraint relaxation means executes relaxation of the selected constraint according to a method of relaxation corresponding to the relaxation permission condition.

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 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.