Iterative repair optimization with particular application to scheduling for integrated capacity and inventory planning

• US 6,216,109 B1
• Filed: 10/09/1997
• Issued: 04/10/2001
• Est. Priority Date: 10/11/1994
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Peoplesoft (Oracle Corporation)
• Inventors: Zweben, Monte, Daun, Brian L., Deale, Michael J., Davis, Eugene D.
• Primary Examiner(s): Poinvil, Frantzy
• Application Number:
  US08/948,375
• Time in Patent Office: 1,279 Days
• Field of Search: 705/4, 705/6, 705/7-10, 364/468.05, 364/468-6-4
• US Class Current: 705/7.12
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: Y02P 90/80 Management or planning

Abstract

A schedule for a complex activity is obtained by a scheduling system using a method of constraint-based iterative repair. A predetermined initial schedule is iteratively repaired, repairs being made during each iteration only to portions of the schedule that produce a constraint violation, until an acceptable schedule is obtained. Since repairs are made to the schedule only to repair violated constraints, rather than to the entire schedule, schedule perturbations are minimized, thereby reducing problems with the dynamic performance of the scheduling system and minimizing disruption to the smooth operation of the activity. All constraints on the scheduling activity can be evaluated simultaneously to produce a solution that is near optimal with respect to all constraints. In particular, consumable resource constraints can be evaluated simultaneously with other constraints such as, for example, reusable resource constraints, temporal constraints, state constraints, milestone constraints and preemptive constraints. The scheduling system of the invention is much quicker than previous scheduling systems that use, for example, constructive scheduling method. The system of the invention can also be easily modified to add, delete or modify constraints. Because of the minimization of schedule perturbation, coupling of all constraints, speed of operation, and ease of modification, the scheduling system of the invention is particularly useful for scheduling applications that require frequent and rapid rescheduling.

Claims

1. A method for scheduling a complex activity that is governed by a set of pre-defined constraints including consumable resource constraints, wherein an unacceptable schedule exists for the activity, the method comprising the steps of:

establishing the unacceptable schedule as a current schedule;

calculating a score for the current schedule;

repairing one or more constraint violations of the current schedule by modifying the current schedule without relaxing the set of pre-defined constraints;

determining a revised schedule from the schedule modification or modifications made by the constraint violation repair or repairs;

calculating a score for the revised schedule;

selecting one of the revised schedule or the current schedule as a new current schedule based upon a comparison of the score of the revised schedule and the score of the current schedule;

repeating, until a predetermined condition is met, the steps of repairing one or more constraint violations of the current schedule, determining a revised schedule, calculating a score for the revised schedule, and selecting one of the revised schedule or the current schedule as the new current schedule; and

selecting one of the revised schedules as the final schedule.

2. A method as in claim 1, wherein the step of selecting a new current schedule further comprises the step of selecting as the new current schedule the schedule that has the better score.

3. A method as in claim 1, wherein the step of selecting a new current schedule further comprises the step of occasionally selecting as the new current schedule the schedule that has the worse score.

4. A method as in claim 1, wherein the step of selecting a final schedule further comprises the step of selecting the most recently determined current schedule as the final schedule.

5. A method as in claim 1, further comprising the step of storing the revised schedule having the best score, and wherein the step of selecting a final schedule further comprises the step of selecting the revised schedule having the best score as the final schedule.

6. A method as in claim 1, wherein the score is a function of the relative importance of each constraint and the degree of violation, if any, of each constraint.

7. A method as in claim 1, wherein:

the score is a function of a multiplicity of penalties and weights;

one penalty is associated with each constraint, each penalty representing the degree of violation, if any, of the constraint; and

one weight is associated with each constraint, each weight representing the relative importance of the constraint.

8. A method as in claim 1, wherein the constraint violations are repaired so that the repaired constraint violation or violations are less severe than before the repair.

9. A method as in claim 1, wherein the predetermined condition is obtaining a schedule having a score that is better than a predetermined threshold score.

10. A method as in claim 1, wherein:

the activity is a manufacturing operation; and

the consumable resources are inventory.

11. A method as in claim 1, wherein:

the activity is a maintenance and repair operation; and

the consumable resources are components or materials used to effect the maintenance or repair.

12. A method as in claim 1, wherein the set of pre-defined constraints further includes reusable resource constraints.

13. A system for scheduling a complex activity that is governed by a set of pre-defined constraints including consumable resource constraints, wherein an unacceptable schedule exists for the activity, comprising:

a memory device, wherein;

the memory device is capable of storing an unacceptable initial schedule that is supplied to the system;

the memory device stores information regarding each of the constraints; and

the memory device is capable of storing one or more revised schedules produced by the system; and

a processing device, wherein;

the processing device is capable of calculating a score for each schedule;

the processing device is capable of repairing one or more constraint violations for each schedule by modifying the schedule without relaxing the set of pre-defined constraints;

the processing device is capable of determining each revised schedule from the schedule modification or modifications made by the constraint violation repair or repairs;

the processing device is capable of selecting one of the revised schedule or the current schedule as a new current schedule based upon a comparison of the score of the revised schedule and the score of the current schedule; and

the processing device is capable of selecting one of the schedules as the final schedule determined by the system.

14. A system as in claim 13, wherein:

the memory device is capable of storing the revised schedule having the best score; and

the processing device is capable of selecting the revised schedule having the best score as the final schedule.

15. A system as in claim 13, wherein:

the constraint information stored by the memory device includes a description of the constraint, a penalty function, a constraint weight, and a repair method for the constraint;

the score calculated by the processing device for each schedule is a function of the penalty caused by the schedule for each constraint and the weight for each constraint; and

the repair performed by the processing device for each constraint violation is performed using the repair method associated with the constraint.

16. A system as in claim 13, further comprising a user input device.

17. A system as in claim 13, further comprising a display device.

18. A system as in claim 13, wherein:

the activity is a manufacturing operation; and

the consumable resources are inventory.

19. A system as in claim 13, wherein:

the activity is a maintenance and repair operation; and

the consumable resources are components or materials used to effect the maintenance or repair.

20. A computer readable medium encoded with one or more computer programs for enabling scheduling of a complex activity that is governed by a set of pre-defined constraints including consumable resource constraints, comprising:

instructions for establishing an unacceptable initial schedule as a current schedule;

instructions for calculating a score for the current schedule;

instructions for repairing one or more constraint violations of the current schedule by modifying the current schedule without relaxing the set of pre-defined constraints;

instructions for determining a revised schedule from the schedule modification or modifications made by the constraint violation repair or repairs;

instructions for calculating a score for the revised schedule;

instructions for selecting one of the revised schedule or the current schedule as a new current schedule based upon a comparison of the score of the revised schedule and the score of the current schedule;

instructions for causing repetition of, until a predetermined condition is met, the instructions for repairing one or more constraint violations of the current schedule, the instructions for determining a revised schedule, the instructions for calculating a score for the revised schedule, and the instructions for selecting one of the revised schedule or the current schedule as the new current schedule; and

instructions for selecting one of the revised schedules as the final schedule.