Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Health care management
Reexamination Certificate
1997-10-09
2001-04-10
Poinvil, Frantzy (Department: 2768)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Health care management
Reexamination Certificate
active
06216109
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a system and method for scheduling a complex activity that includes performance of a multiplicity of tasks, the completion of which necessitates the use of a multiplicity of resources and adherence to state requirements of a multiplicity of attributes. The tasks, resources and attributes are related by a multiplicity of constraints. At least some of the resources are consumable resources. In particular, the invention relates to such a system and method that combine the techniques of constraint-based iterative repair with the techniques of material requirements planning.
2. Related Art
Management of a complex activity, such as operation of a manufacturing facility, or maintenance and repair of a complex system such as the Space Shuttle, necessitates scheduling of many tasks, the completion of which may conflict with each other for a variety of reasons. Further, each of the tasks uses resources (which can be either consumable or reusable) of finite extent. Development of a schedule that resolves the many possible conflicts that may arise during conduct of the activity is a complex problem. The problem is further compounded by the probability that unforeseen events will, from time to time, necessitate modification of any determined schedule.
“Scheduling” is the process of assigning times and resources to the tasks of an operation. Scheduling assignments must satisfy a set of constraints. Constraints include, for example, temporal constraints, milestone constraints, resource constraints, state constraints and preemptive constraints.
Constructive scheduling is one method that has been used to develop schedules for complex activities. In constructive scheduling, a partial schedule is developed from scratch so that the partial schedule does not violate any of the constraints (or violates the constraints to a predefined acceptable degree). The partial schedule is then incrementally extended through a series of successive partial schedules, each successive partial schedule conforming to the constraints (again, to a predefined degree), until a final, complete schedule is developed. In some constructive scheduling methods, failure of any of the partial schedules to adequately satisfy the constraints necessitates backtracking to an earlier partial schedule and reconstructing a series of partial schedules from that point. Construction of partial schedules and backtracking continue until an acceptable final schedule is developed. In other constructive scheduling methods, when a partial schedule fails to satisfy a constraint, the schedule meets the constraint as best it can, and the constraint is relaxed to the degree necessary to eliminate the constraint violation.
Constraint-based iterative repair is another method that has been used to develop schedules for complex activities. In constraint-based iterative repair, a complete schedule that does not adequately satisfy the constraints is iteratively modified to obtain a series of complete schedules until one of the modified schedules adequately satisfies the constraints. Unlike constructive methods, only constraints that have been violated are repaired during each iteration.
The above-described techniques have been used to solve “scheduling problems.” A “scheduling problem” is a problem in which all of the items, e.g., tasks and resources, to be scheduled to accomplish an operation are known at the beginning of development of the schedule. Establishment of a schedule consists of assigning a time and allocating resources to each task such that the constraints are satisfied to the degree desired. An example of a scheduling problem is the assignment of classrooms, teachers and students for all of the courses offered at a university during a semester.
In contrast to a scheduling problem, with its pre-established set of tasks and resources, a “planning problem” is more open-ended. In a planning problem, any of a number of sets of tasks and resources can be chosen to accomplish an operation, subject only to the satisfaction of certain conditions during the scheduled set of activities. Thus, typically, while scheduling for a planning problem will begin with a defined set of tasks and resources, additional tasks and resources are added to the schedule as the final schedule is developed. (It is also possible to delete some tasks and resources during development of the final schedule.) Therefore, scheduling for “planning problems” is generally more complex than scheduling for “scheduling problems.” Scheduling a manufacturing operation is a good example of a planning problem.
There are two primary types of planning problems: i) consumable resource planning, e.g., inventory planning such as planning for finished goods, raw material, and/or work-in-progress in a manufacturing operation, and ii) reusable resource planning, e.g., capacity planning such as planning for machine and labor usage in a manufacturing operation. Previously, these two planning problems have been addressed separately. Below, previous methods of addressing these problems are discussed in the manufacturing context.
In manufacturing, master production scheduling (MPS) has been used to address the inventory planning problem. MPS operates at a macrocosmic level and is used to develop a build schedule for the supply of finished goods, e.g., goods sold directly to a consumer. MPS accepts demand requirements as input, i.e., the quantity of finished goods needed at particular times. The demand requirements are forecasted and/or actual needs netted against existing inventory. MPS develops a schedule for the replenishment of the finished goods inventory by scheduling the production and/or procurement of batches of finished goods to meet the demand requirements. For example, MPS could be used to develop a build schedule for a particular model of computer made by a manufacturer.
Rough cut capacity planning has been used in the manufacturing context to address the capacity planning problem at the macrocosmic level. Typically, rough cut capacity planning evaluates capacity constraints at some level between the factory and machine levels, e.g., at the production line level. A build schedule, as developed by a MPS system for example, is input into the rough cut capacity planning system and a determination is made as to whether sufficient resources exist to implement the build schedule. If not, a planner must either direct that additional capacity be added, or develop a new build schedule using MPS techniques. For example, rough cut capacity planning can determine whether there are an adequate number of assembly lines and workers to produce a sufficient number of computers according to a build schedule established by an MPS system.
Typically, MPS and rough cut capacity scheduling are successively performed at least several times before a satisfactory build schedule is developed, one that accommodates both demand (inventory) requirements and capacity constraints. Inventory planning and capacity planning are not coupled, other than to supply the inventory planning (i.e., MPS) output as the capacity planning (i.e., rough cut capacity planning) input, and to use the capacity planning output to evaluate the efficacy of the inventory planning output. Solution of the combined inventory and capacity problem in this manner frequently takes a rather long time and does not lend itself to easy rescheduling once an acceptable build schedule has been established.
Once MPS and rough cut capacity planning have been used to develop a satisfactory build schedule for the supply of finished goods, the production requirements of the build schedule are supplied to a material requirements planning (MRP) system. MRP operates at a microcosmic level and is used to develop a schedule for the production of finished goods. As input, the MRP system accepts the production requirements of the build schedule, subassembly and raw materials inventory levels (to net production requirements against existing inventory), bills of materials (BOMs) associated w
Daun Brian L.
Davis Eugene D.
Deale Michael J.
Zweben Monte
Graham David R.
PeopleSoft, Inc.
Poinvil Frantzy
LandOfFree
Iterative repair optimization with particular application to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Iterative repair optimization with particular application to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Iterative repair optimization with particular application to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2506548