System and process for job scheduling using limited discrepancy search
First Claim
1. A computer-implemented system for producing a schedule for a project by assigning attributes to elements in accordance with given constraints, the system comprising:
- a systematic engine including;
a schedule developer adapted to generate an intermediate assignment of a subset of the attributes to a subset of the elements;
a pruning processor operatively coupled to the schedule developer and adapted to generate an error signal responsive to violation of a subset of predetermined discrepancy limits by the intermediate assignment, the error signal being applied to the schedule developer and causing the schedule developer to modify the intermediate assignment; and
a bound selector operatively coupled to the schedule developer and adapted to store and modify the discrepancy limits in response to operation of the schedule developer and the pruning processor; and
a nonsystematic engine, including;
a schedule packer operatively coupled to the systematic engine, adapted to accept as input the intermediate assignment and to produce therefrom an improvement thereof by a right-justify operation and a left-justify operation; and
an evaluator, operatively coupled to the schedule packer, adapted to estimate an overall resource utilization of the improvement, to generate as output a violation signal in response to the improvement violating a subset of the constraints, the violation signal being applied as an input to the systematic engine and causing the schedule developer to generate a new intermediate assignment, and to generate as output the improvement as the schedule for the project responsive to the improvement not violating the constraints.
2 Assignments
0 Petitions
Accused Products
Abstract
Assignment of attributes to elements subject to constraints is achieved using a system that has a systematic engine and a nonsystematic engine. The systematic engine includes a schedule developer for producing partial proposed assignments, a pruning processor for determining violations of discrepancy limits by a partial proposed assignment, and a bound selector for relaxing discrepancy limits as needed. The non-systematic engine includes a schedule packer for modifying assignments proposed by the systematic engine and an evaluator for comparing the modified assignments with the constraints.
63 Citations
19 Claims
-
1. A computer-implemented system for producing a schedule for a project by assigning attributes to elements in accordance with given constraints, the system comprising:
-
a systematic engine including; a schedule developer adapted to generate an intermediate assignment of a subset of the attributes to a subset of the elements; a pruning processor operatively coupled to the schedule developer and adapted to generate an error signal responsive to violation of a subset of predetermined discrepancy limits by the intermediate assignment, the error signal being applied to the schedule developer and causing the schedule developer to modify the intermediate assignment; and a bound selector operatively coupled to the schedule developer and adapted to store and modify the discrepancy limits in response to operation of the schedule developer and the pruning processor; and a nonsystematic engine, including; a schedule packer operatively coupled to the systematic engine, adapted to accept as input the intermediate assignment and to produce therefrom an improvement thereof by a right-justify operation and a left-justify operation; and an evaluator, operatively coupled to the schedule packer, adapted to estimate an overall resource utilization of the improvement, to generate as output a violation signal in response to the improvement violating a subset of the constraints, the violation signal being applied as an input to the systematic engine and causing the schedule developer to generate a new intermediate assignment, and to generate as output the improvement as the schedule for the project responsive to the improvement not violating the constraints. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A computer-implemented process for producing a schedule for a project by assigning attributes to elements, subject to a set of constraints, the process comprising:
-
a) generating a partial proposed assignment; b) determining whether the partial proposed assignment violates a predetermined discrepancy limit; c) modifying the partial proposed assignment responsive to violation of the predetermined discrepancy limit; d) iterating b) and c) responsive to continued violation of the predetermined discrepancy limit and responsive to existence of additional possible proposed assignments for which violation of the predetermined discrepancy limit is not established; e) altering the predetermined discrepancy limit and iterating a)-d) responsive to the non-existence of additional possible proposed assignments for which violation of the predetermined discrepancy limit is not established; f) forming an intermediate assignment responsive to the partial proposed assignment; g) modifying the intermediate assignment to produce an improvement of the intermediate assignment, using a right-justify operation and a left-justify operation; h) evaluating the improvement with respect to the constraints; i) iterating a)-h) responsive to the improvement violating a subset of the constraints; and j) producing the schedule for the project from the improvement responsive to the improvement not violating the constraints. - View Dependent Claims (7, 8, 9, 10)
-
-
11. A computer-implemented system for producing a schedule for a project by assigning attributes to elements in accordance with given constraints, the system comprising:
-
a systematic engine including; a schedule developer adapted to generate an intermediate assignment of a subset of the attributes to a subset of the elements; a pruning processor operatively coupled to the schedule developer and adapted to generate an error signal responsive to violation of a subset of predetermined discrepancy limits by the intermediate assignment, the error signal being applied to the schedule developer and causing the schedule developer to modify the intermediate assignment; and a bound selector operatively coupled to the schedule developer and adapted to store and modify the discrepancy limits in response to operation of the schedule developer and the pruning processor; and a nonsystematic engine, including; a schedule packer operatively coupled to the systematic engine, adapted to accept as input the intermediate assignment and to produce therefrom an improvement thereof; and an evaluator, operatively coupled to the schedule packer, adapted to estimate an overall resource utilization of the improvement, to generate as output a violation signal in response to the improvement violating a subset of the constraints, the violation signal being applied as an input to the systematic engine and causing the schedule developer to generate a new intermediate assignment, and to generate as output the improvement as the schedule for the project. - View Dependent Claims (12, 13, 14, 15)
-
-
16. A computer-implemented process for producing a schedule for a project by assigning attributes to elements, subject to a set of constraints, the process comprising:
-
a) generating a partial proposed assignment; b) determining whether the partial proposed assignment violates a predetermined discrepancy limit; c) modifying the partial proposed assignment responsive to violation of the predetermined discrepancy limit; d) iterating b) and c) responsive to continued violation of the predetermined discrepancy limit and responsive to existence of additional possible proposed assignments for which violation of the predetermined discrepancy limit is not established; e) altering the predetermined discrepancy limit and iterating a)-d) responsive to the non-existence of additional possible proposed assignments for which violation of the predetermined discrepancy limit is not established; f) forming an intermediate assignment responsive to the partial proposed assignment; g) modifying the intermediate assignment to produce an improvement of the intermediate assignment; h) evaluating the improvement with respect to the constraints; i) iterating a)-h) responsive to the improvement violating a subset of the constraints; and j) producing the schedule for the project from the improvement responsive to the improvement not violating the constraints. - View Dependent Claims (17, 18, 19)
-
Specification