Granted Patent B2

US 7,230,736 · App. 10/284,561 · Granted Jun 12, 2007

Abstract

Claims (71)

1. A computer controlled system for planning and scheduling the work flow, received in the form of work units, for reconfigurable production systems having a plurality of modules with a plurality of alternative capabilities, the system comprising:

a system controller for integrating resource constraints and time constraints to identify optimal work flow schedules, wherein said controller receives descriptions of at least one work unit with its desired attributes, capability models from each of the plurality of modules, and the current state of the system, including operations currently being performed by the modules and capabilities previously planned and scheduled, wherein said capability models include timing constraints, feature constraints, and commands, wherein said timing constraints include the duration of execution of a capability, the time during which a module is occupied, or the reservation of a module, wherein said feature constraints include limits on the size of the work units being processed and transformation of the work units, and wherein said commands include the names or identifications of the operations corresponding to the capabilities, together with timing information;

at least one planning function, wherein said planning function uses said capability models to determine how to produce the said desired attributes of the work units; and

at least one scheduling function, wherein said scheduling function utilizes global optimization to schedule selected capabilities and provide a set of scheduled capabilities in the form of commands to the plurality of modules.

2. The system for planning and scheduling reconfigurable production systems according to claim 1 , wherein said planning function comprises;

means for selecting at least one work unit to be planned;

means for determining capabilities to produce said work unit;

means for modifying constraints using selection variables;

means for posting constraints on selection variables and common modules to memory;

means for posting timing and precedence constraints to memory; and

means for reserving a selected resource if only part of a job is being scheduled.

3. The system for planning and scheduling reconfigurable production systems according to claim 2 , wherein selecting a work unit to be planned is based on an input job description.

4. The system for planning and scheduling reconfigurable production systems according to claim 2 , wherein determining capabilities to produce said work unit further comprises considering all reconfigurable production system module capabilities.

5. The system for planning and scheduling reconfigurable production systems according to claim 4 , further comprising selecting alternative capabilities from the reconfigurable production system modules.

6. The system for planning and scheduling reconfigurable production systems according to claim 2 , wherein said selection variables are created automatically for each capability.

7. The system for planning and scheduling reconfigurable production systems according to claim 2 , wherein said selection variables comprise Boolean variables.

8. The system for planning and scheduling reconfigurable production systems according to claim 2 , wherein said modified constraints comprise timing constraints.

9. The system for planning and scheduling reconfigurable production systems according to claim 2 , wherein said modified constraints comprise the reservation of resources during intervals in which reconfigurable production system modules are occupied.

10. The system for planning and scheduling reconfigurable production systems according to claim 2 , wherein posting timing and precedence constraints comprises connecting variables of all alternative capabilities to a single time variable.

11. The system for planning and scheduling reconfigurable production systems according to claim 1 , wherein said scheduling function comprises:

means for selecting capabilities to be scheduled;

means for reserving exit resources for planned capabilities; and

means for solving for timing and selection variables.

12. The system for planning and scheduling reconfigurable production systems according to claim 2 , further comprising means for acquiring at least one capability model from at least one machine module.

13. The system for planning and scheduling reconfigurable production systems according to claim 1 , wherein said machine module comprises a print engine module.

14. The system for planning and scheduling reconfigurable production systems according to claim 1 , wherein said machine module comprises and analysis module.

15. The system for planning and scheduling reconfigurable production systems according to claim 1 , wherein said machine module comprises a manufacturing fine module.

16. The system for planning and scheduling reconfigurable production systems according to claim 1 , wherein said machine module comprises a packaging line module.

17. A method for planning and scheduling the work flow for reconfigurable production systems having a plurality of modules and including a system controller, comprising:

utilizing the system controller to integrate resource constraints and time constraints to identify optimal work flow schedules, wherein said controller receives descriptions of at least one work unit with its desired attributes, capability models from each of the plurality of modules, and the current state of the system, including operations currently being performed by the modules and capabilities previously planned and scheduled, wherein said capability models include timing constraints, feature constraints, and commands, wherein said timing constraints include the duration of execution of a capability, the time during which a module is occupied, or the reservation of a module, wherein said feature constraints include limits on the size of the work units being processed and transformation of the work units, and wherein said commands include the names or identifications of the operations corresponding to the capabilities, together with timing information;

planning the work flow for at least one reconfigurable production system, wherein said planning utilizes said capability models to determine how to produce the said desired attributes of the work units; and

scheduling the work flow for the plurality of modules in the reconfigurable production system, wherein said scheduling utilizes global optimization to schedule selected capabilities and provide a set of scheduled capabilities in the form of commands to the plurality of modules.

18. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 17 , wherein planning the work flow comprises:

acquiring a description of work units to be produced;

selecting at least one of said work units to be planned;

determining the capabilities needed to produce said work unit;

modifying constraints using selection variables;

posting constraints on selection variables and common modules to memory; and

posting timing and precedence constraints to memory.

19. A method for planning and scheduling reconfigurable production systems having a plurality of modules according to claim 18 , wherein determining the capabilities needed to produce said work unit comprises considering all possible reconfigurable production system module capabilities.

20. A method for planning and scheduling reconfigurable production systems having a plurality of modules according to claim 18 , wherein determining the capabilities needed to produce said work unit comprises selecting alternative capabilities from the reconfigurable production system modules capabilities.

21. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 18 , wherein said modified constraints comprise timing constraints.

22. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 18 , wherein said modified constraints comprise the reservation of resources during the intervals in which reconfigurable production system modules are occupied.

23. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 18 , wherein said selection variables are created automatically for each capability.

24. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 18 , wherein said selection variables comprise Boolean variables.

25. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 18 , wherein said precedence constraints comprise connecting the output variables of all alternative capabilities to a single time variable.

26. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 18 , further comprising reserving a selected resource if only part of a job is being scheduled.

27. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 17 , wherein scheduling the work flow for the plurality of modules in the reconfigurable production system comprises:

selecting capabilities to be scheduled;

reserving exit resources for planned capabilities within the same jobs; and

solving for timing and selection variables of planned capabilities.

28. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 27 , wherein said selected capabilities include a subset of capabilities needed to produce said work unit.

29. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 27 , wherein said selected capabilities include all of the capabilities needed to produce said work unit.

30. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 18 , wherein said capabilities comprise capability models for at least one machine module.

31. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 18 , wherein said capabilities comprise feature constraints.

32. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 18 , wherein said capabilities comprise timing constraints.

33. An article of manufacture comprising a computer usable medium having computer readable program code embodied in said medium which, when said program code is executed by a computer causes said computer to perform method steps for planning and scheduling reconfigurable systems having a plurality of modules, said method comprising:

utilizing the system controller for integrating resource constraints and time constraints to identify optimal work flow schedules, wherein said controller receives descriptions of at least one work unit with its desired attributes, capability models from each of the plurality of modules, and the current state of the system, including operations currently being performed by the modules and capabilities previously planned and scheduled, wherein said capability models include timing constraints, feature constraints, and commands, wherein said timing constraints include the duration of execution of a capability, the time during which a module is occupied, or the reservation of a module, wherein said feature constraints include limits on the size of the work units being processed and transformation of the work units, and wherein said commands include the names or identifications of the operations corresponding to the capabilities, together with timing information;

planning the work flow for at least one reconfigurable production system, wherein said planning utilizes said capability models to determine how to produce the said desired attributes of the work units; and

scheduling the work flow for the plurality of modules in the reconfigurable production system, wherein said scheduling utilizes global optimization to schedule selected capabilities and provide a set of scheduled capabilities in the form of commands to the plurality of modules.

34. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 33 , wherein planning the work flow comprises:

acquiring a description of work units to be produced;

selecting at least one of said work units to be planned;

determining the capabilities needed to produce said work unit;

modifying constraints using selection variables;

posting constraints on selection variables and common modules to memory; and

posting timing and precedence constraints to memory.

35. A method for planning and scheduling the work flow for reconfigurable production systems according to claim 33 , wherein scheduling the work flow comprises:

selecting capabilities to be scheduled;

reserving exit resources for planned capabilities within the same jobs; and

solving for timing and selection variables of planned capabilities.

Assignments (9)