Planning and scheduling reconfigurable systems around off-line resources

• US 8,315,898 B2
• Filed: 10/30/2002
• Issued: 11/20/2012
• Est. Priority Date: 10/30/2002
• Status: Expired due to Fees

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Fromherz, Markus P. J.
• Primary Examiner(s): MANSFIELD, THOMAS L
• Application Number:
  US10/284,514
• Publication Number:
  US 20040088207A1
• Time in Patent Office: 3,674 Days
• Field of Search: 705/7.12, 705/7.11
• US Class Current: 705/7.12
• CPC Class Codes: G06Q 10/06314 Calendaring for a resource
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

A system is provided to allow for planning and scheduling the work flow for reconfigurable production systems having a plurality of modules, which may have alternative capabilities. The system includes a system controller, at least one planning function for planning the production of work units without utilizing off-line modules, and at least one scheduling function for scheduling the production of work units without utilizing off-line modules.

Claims

1. A computer controlled system for planning and scheduling the work flow for a reconfigurable production system, the computer controlled system comprising:

a plurality of modules, the reconfigurable production system comprising the plurality of modules, the plurality of modules having a plurality of alternative capabilities, the work flow comprising one or more jobs to be performed on the reconfigurable production system, each job comprising one or more work units to be produced on the reconfigurable production system;

a system controller;

a computer-readable memory that stores computer-executable instructions for execution by the system controller, the computer-readable instructions comprising instructions for;

planning the production of work units of the one or more jobs without utilizing off-line modules, the planning comprising;

selecting one or more work units to be planned,

determining one or more system capabilities to produce the one or more work units, such that the off-line modules are not utilized,

determining whether the system capabilities to produce the one or more work units are available without utilizing the off-line modules, and

if the system capabilities to produce a work unit are not available without utilizing the off-line modules,

prior to the work unit reaching the off-line modules, tagging, by the system controller, the work unit with the system capabilities needed for the work unit which are not available,

prior to the work unit reaching the off-line modules, removing, by the system controller, the work unit and all subsequent work units of the same job from consideration, and

reinserting, by the system controller, the work unit and all subsequent work units when the system capabilities needed by the work unit become available, and

scheduling the production of the one or more work units without utilizing the off-line modules, wherein

the off-line modules are modules of the reconfigurable production system that are temporarily unavailable to produce work units,

the reconfigurable production system continues to produce work units while the work unit is removed from consideration, and

the work units of each job are produced in order, wherein

the system capabilities are operations that accept the work unit at an entry port, process the work unit, and move the work unit to an exit port.

2. The system according to claim 1, wherein said planning further comprises:

modifying one or more of timing constraints, interval constraints, and precedence constraints using selection variables so that the work units can be produced;

posting one or more selection variable constraints on selection variables and the plurality of modules to memory so that the work units can be produced;

posting the timing, interval, and precedence constraints to memory so that the work units can be produced; and

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

3. The system according to claim 2, wherein selecting one or more work units to be planned is based on an input job description.

4. The system according to claim 2, wherein the determining of the system capabilities to produce said one or more work units further comprises specifying a desired exit port and itinerary.

5. The system according to claim 4, further comprising instructions for selecting at least one alternative one of the system capabilities from the reconfigurable production system modules.

6. The system according to claim 2, wherein said selection variables are created automatically for each system capability.

7. The system according to claim 2, wherein said selection variables comprise Boolean variables.

8. The system according to claim 2, wherein said constraints modified by said modifying instruction comprise the reservation of one or more resources during intervals in which reconfigurable production system modules are occupied.

9. The system according to claim 2, wherein posting the timing, interval, and precedence constraints comprises connecting variables of all alternative capabilities between successive ones of the work units to a single time variable.

10. The system according to claim 1, wherein said scheduling comprises:

selecting one or more capabilities to be scheduled;

reserving one or more exit resources of the plurality of modules for the selected capabilities, each exit resource being a resource that relates to the exit of work units from the corresponding one of the modules; and

solving for one or more of timing and selection variables.

11. The system according to claim 2, further comprising instructions for acquiring at least one capability model from at least one of the plurality of modules.

12. The system according to claim 1, wherein said plurality of modules comprises a print engine module.

13. The system according to claim 1, wherein said plurality of modules comprise an analysis module.

14. The system according to claim 1, wherein said plurality of modules comprise a manufacturing line module.

15. The system according to claim 1, wherein said plurality of modules comprise a packaging line module.

16. A method for planning and scheduling the work flow for a computer controlled reconfigurable production system having a plurality of modules with a plurality of alternative capabilities, the work flow comprising one or more jobs for production on the reconfigurable production system, each job comprising one or more work units to be produced on the reconfigurable production system, the method comprising:

planning the work flow for the reconfigurable production system, without utilizing off-line modules, the planning the work flow comprising;

acquiring a description of one or more work units of the one or more jobs to be produced,

selecting at least one of the work units to be planned,

determining the capabilities needed to produce the at least one of the work units without utilizing the off-line modules,

determining whether the capabilities needed to produce the at least one of the work units without utilizing the off-line modules are available, and

if the capabilities to produce a work unit are not available without utilizing the off-line modules;

prior to the work unit reaching the off-line modules, tagging, by the reconfigurable production system, the work unit with the capabilities needed for the work unit which are not available,

prior to the work unit reaching the off-line modules, removing, by the reconfigurable production system, the work unit and all subsequent work units of the same job from consideration; and

reinserting, by the reconfigurable production system, the work unit and all subsequent work units when the capabilities needed by the work unit become available, and

scheduling the work flow for the plurality of modules in the reconfigurable production system, without utilizing the off-line modules, wherein

the off-line modules are modules of the reconfigurable production system that are temporarily unavailable to produce work units,

the reconfigurable production system continues to produce work units while the work unit is removed from consideration, and

the work units of each job are produced in order, wherein the system capabilities are operations that accept the work unit at an entry port, process the work unit, and move the work unit to an exit port.

17. A method according to claim 16, wherein planning aid work flow further comprises:

modifying one or more of timing, interval, and precedence constraints using election variables;

posting one or more selection variable constraints on selection variables and common modules to a memory; and

posting the timing, interval, and precedence constraints to the memory.

18. A method according to claim 17, wherein determining the capabilities needed to produce at least one of the work units comprises selecting alternative capabilities from the capabilities of the reconfigurable production system modules.

19. A method according to claim 17, wherein said modified constraints comprise the reservation of resources during the intervals in which reconfigurable production system modules are occupied.

20. A method according to claim 17, wherein said selection variables are created automatically for each capability.

21. A method according to claim 17, wherein said selection variables comprise Boolean variables.

22. A method according to claim 17, wherein said precedence constraints comprise connecting the output variables of all alternative capabilities between successive ones of the work units to a single time variable.

23. A method according to claim 17, further comprising reserving a selected resource if only part of a job is being scheduled.

24. A method according to claim 16, wherein scheduling the work flow for the plurality of modules in the reconfigurable production system comprises:

selecting one or more capabilities to be scheduled;

reserving one or more exit resources for the selected capabilities within the same jobs; and

solving for one or more timing and selection variables of the selected capabilities.

25. A method according to claim 24, wherein said selected capabilities include a subset of capabilities needed to produce the at least one of the work units.

26. A method according to claim 24, wherein said selected capabilities include all of the capabilities needed to produce the at least one of the work units.

27. A method according to claim 17, wherein said capabilities comprise capability models for at least one of the plurality of modules.

28. A method according to claim 17, wherein said capabilities comprise feature constraints.

29. A method according to claim 17, wherein said capabilities comprise timing constraints.

30. An article of manufacture comprising a computer-readable recording medium having computer readable program code embodied in the medium which, when the program code is executed by a computer causes the computer to perform a method for planning and scheduling for a computer controlled reconfigurable production system, the method comprising:

planning the work flow for the reconfigurable production system without utilizing off-line modules, the work flow comprising one or more jobs for production on the reconfigurable production system, each job comprising one or more work units to be produced on the reconfigurable production system, wherein the planning the work flow comprises;

acquiring a description of one or more work units of the one or more jobs to be produced,

selecting at least one of the work units to be planned,

determining the capabilities needed to produce the at least one of the work units without utilizing the off-line modules,

determining whether the capabilities needed to produce the at least one of the work units without utilizing the off-line modules are available,

if a work unit cannot be produced without utilizing the off-line modules,

prior to the work unit reaching the off-line modules, tagging, by the reconfigurable production system, the work unit with the capabilities needed for the work unit which are not available,

prior to the work unit reaching the off-line modules, removing, by the reconfigurable production system, the work unit and all subsequent work units of the same job from further consideration, and

reinserting, by the reconfigurable production system, the work unit and all subsequent work units when the capabilities needed by the work unit become available,

modifying one or more of timing, interval, and precedence constraints using selection variables,

posting one or more selection variable constraints on selection variables and common modules to a memory,

posting the timing, interval, and precedence constraints to the memory; and

scheduling the work flow for the plurality of modules in the reconfigurable production system without utilizing the off-line modules, wherein

the off-line modules are modules of the reconfigurable production system that are temporarily unavailable to produce work units,

the reconfigurable production system continues to produce work units while the work unit is removed from consideration, and

the work units of each job are produced in order, wherein the system capabilities are operations that accept the work unit at an entry port, process the work unit, and move the work unit to an exit port.

31. An article of manufacture comprising a computer-readable recording medium having computer readable program code embodied in said medium which, when said program code is executed by said computer causes said computer to perform a method for planning and scheduling computer controlled reconfigurable production systems according to claim 30, wherein scheduling said work flow comprises:

selecting one or more capabilities to be scheduled;

reserving one or more exit resources for the selected capabilities within the same jobs; and

solving for one or more timing and selection variables of the selected capabilities.