US6070144A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and process for job scheduling using limited discrepancy search
Assignee: University of Oregon
•
Filing: 1998-08-27
•
Granted: 2000-05-30
•
Expires: 2018-08-27
Abstract
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.
Inventors
- 👤 Matthew L. Ginsberg
- 👤 William D. Harvey
- 👤 James M. Crawford
- 👤 Ari K. Jonsson
- 👤 Joseph C. Pemberton
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 10:37
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/06; G06Q10/063; G06Q10/0631; G06Q10/06311; G06Q10/063118; G06Q10/06312; G06Q10/06313
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
246 words
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.
Claim 2
Dependent Claim
246 words
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.
Claim 3
Dependent Claim
80 words
A computer-implemented system as in claim 1, wherein the intermediate assignment includes an intermediate assignment start and an intermediate assignment end, and wherein: (i) the left-justify operation includes choosing a left-justification start preceding the intermediate assignment start sufficiently to avoid overlap of assignments between a left-justification assignment and the intermediate assignment; and (ii) the right-justify operation includes choosing a right-justification end succeeding the intermediate assignment end sufficiently to avoid overlap of assignments between a right-justification assignment and the intermediate assignment.
Claim 4
Dependent Claim
17 words
A computer-implemented system as in claim 1, wherein the right-justify operation and the left-justify operation are iterated.
Claim 5
Dependent Claim
44 words
A computer-implemented system as in claim 1, wherein the intermediate assignment includes an intermediate assignment end having a particular relationship to a cycle of shifts, the right-justify operation including selection of a right-justify end also having the particular relationship to the cycle of shifts.
Claim 6
Dependent Claim
43 words
A computer-implemented system as in claim 1, wherein the intermediate assignment includes an intermediate assignment end having a particular relationship to a cycle of shifts, the right-justify operation including selection of a right-justify end having a random relationship to the cycle of shifts.
Claim 7
Dependent Claim
192 words
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.
Claim 8
Dependent Claim
192 words
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.
Claim 9
Dependent Claim
76 words
A computer-implemented process as in claim 6, wherein the intermediate assignment includes an intermediate assignment start and an intermediate assignment end, and wherein: (i) the left-justify operation includes choosing a left-justification start preceding the intermediate assignment start sufficiently to avoid overlap between a left-justification assignment and the intermediate assignment; and (ii) the right-justify operation includes choosing a right-justification end succeeding the intermediate assignment end sufficiently to avoid overlap between a right-justification assignment and the intermediate assignment.
Claim 10
Dependent Claim
17 words
A computer-implemented process as in claim 6, wherein the right-justify operation and the left-justify operation are iterated.
Claim 11
Dependent Claim
44 words
A computer-implemented process as in claim 6, wherein the intermediate assignment includes an intermediate assignment end having a particular relationship to a cycle of shifts, the right-justify operation including selection of a right-justify end also having the particular relationship to the cycle of shifts.
Claim 12
Dependent Claim
43 words
A computer-implemented process as in claim 6, wherein the intermediate assignment includes an intermediate assignment end having a particular relationship to a cycle of shifts, the right-justify operation including selection of a right-justify end having a random relationship to the cycle of shifts.
Claim 13
Dependent Claim
230 words
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.
Claim 14
Dependent Claim
230 words
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.
Claim 15
Dependent Claim
34 words
A computer-implemented system as in claim 11, wherein the bound selector modifies the discrepancy limits in response to detected inability of the systematic engine to generate new intermediate assignments without violating the discrepancy limits.
Claim 16
Dependent Claim
61 words
A computer-implemented system as in claim 11, wherein the schedule developer and the pruning processor iteratively operate together to generate partial assignments, and wherein each iteration of intermediate assignment generation results in addition of a new assignment of one of the attributes of one of the elements, in response to a previous iteration not resulting in generation of the error signal.
Claim 17
Dependent Claim
19 words
A computer-implemented system as in claim 11, wherein the constraints include a required deadline for completion of the project.
Claim 18
Dependent Claim
21 words
A computer-implemented system as in claim 11, wherein the discrepancy limits include a threshold number of violations of a predetermined heuristic.
Claim 19
Dependent Claim
184 words
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.
Claim 20
Dependent Claim
184 words
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.
Claim 21
Dependent Claim
18 words
A computer-implemented process as in claim 16, wherein the generating a partial proposed assignment includes following a heuristic.
Claim 22
Dependent Claim
21 words
A computer-implemented process as in claim 16, wherein the discrepancy limits include a threshold number of violations of a predetermined heuristic.
Claim 23
Dependent Claim
19 words
A computer-implemented process as in claim 16, wherein the constraints include a required deadline for completion of the project.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-30 | 2003-11-29 | 2004-05-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-30 | 2007-11-29 | 2008-05-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-30 | 2011-11-29 | 2012-05-30 | $7700.00 | Window Closed / Lapsed |