Scheduling system and work order scheduling protocol for such a system

• US 7,848,836 B2
• Filed: 11/21/2005
• Issued: 12/07/2010
• Est. Priority Date: 11/19/2004
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Paolucci, Massimo, Gozzi, Andrea
• Primary Examiner(s): Patel; Ramesh B
• Application Number:
  US11/666,114
• Publication Number:
  US 20080091289A1
• Time in Patent Office: 1,842 Days
• Field of Search: 700 95- 97, 700 99-103, 705/8
• US Class Current: 700/100
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06313 Resource planning in a project environment
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 10/0633 Workflow analysis

Abstract

In a scheduling system for planning and scheduling production in an industrial production system, which scheduled production is to be executed by the production system under control of a manufacturing execution system, the scheduling system is a multi-agent scheduling system. At least a part of the behavior of the agents in the multi-agent system is customizable by visually defined scheduling rules. The scheduling system and manufacturing execution system share a definition and execution environment having an editor that visually defines both the scheduling rules and control rules of the manufacturing execution system, and an execution engine for executing the scheduling rules and control rules and making scheduling decisions based on an execution of the scheduling rules and control rules.

Claims

1. A scheduling system for planning and scheduling production in an industrial production system, which scheduled production is to be executed by the production system under control of a manufacturing execution system, the scheduling system comprising:

a multi-agent scheduling system;

at least a part of a behavior of agents in said multi-agent scheduling system being customizable by visually defined scheduling rules;

a definition and execution environment, shared by the scheduling system and manufacturing execution system, the definition and execution environment including;

an editor operable to visually define both said scheduling rules and control rules of the manufacturing execution system, and

an execution engine for executing said scheduling rules and control rules and making scheduling decisions based on an execution of said scheduling rules and control rules.

2. The scheduling system of claim 1, wherein interaction rules between said agents are established by a scheduling protocol adapted to the production system by at least a part of the customizable agent behavior.

3. The scheduling system of claim 1, wherein a definition of said scheduling and control rules is based on a given set of graphical items.

4. The scheduling system of claim 1, wherein said visually defined scheduling rules are selected from the group consisting of scheduling constraints, scheduling criteria, interactions among scheduling and production control activities.

5. The scheduling system of claim 1, wherein said scheduling rules are visually defined by using an implementation of a visual language including items selected from the group consisting of modules for:

real time acquisition allowing a definition of rules to detect an occurrence of events;

output of data to external destinations;

allowing function calls;

storing local data within a rule scope;

conditional statements;

providing entry points for sub-rules invocation; and

graphical links connecting modules and defining the rule computation flow.

6. The scheduling system of claim 1, wherein said agents are selected from the group consisting of:

agents associated with physical assets;

agents associated with information;

agents associated with functions; and

agents associated with scheduling decision activities.

7. The scheduling system of claim 1, wherein said agents are arranged in classes with different behaviors selected from the group consisting of:

asking other agents for services or information;

replying to requests for service; and

synchronizing with other agents'"'"' activity.

8. The scheduling system of claim 1, wherein said agents are arranged in a hierarchy, said hierarchy including entities selected from the group consisting of:

an agent site,

a set of agent areas related to said agent site in a decision hierarchy relationship,

a set of agent cells related to at least one of said agent areas in a decision hierarchy relationship, and

a set of agent units related to at least one of said agent areas and said agent cells in a decision hierarchy relationship.

9. A work order scheduling protocol for an agent-based scheduling system for scheduling processing of incoming work orders in a plant through operations performed by physical entities available in the plant, wherein agents in said scheduling system comprise a tree-like hierarchy including branches, said protocol ruling interactions between said agents in assigning operations requested by said incoming work orders to said physical entities, said protocol comprising:

a first main section, wherein the protocol identifies in said hierarchy a plurality of branches, each branch thus identified including physical entities adapted to process a given work order, and

a second main section, wherein processing of said given work order is scheduled for each one of said identified branches of physical entities, whereby one of said scheduled branches is adapted to be selected for processing said given work order.

10. The protocol of claim 9, wherein said protocol involves agents of said system acting as product segments agents to select a physical entity to contact for starting said negotiation protocol.

11. The protocol of claim 10, wherein said protocol is based on the following rules:

a physical entity to contact is a lowest level entity able to perform all activities listed in related product segments; and

if more than one entity at the same level is available, then a parent entity is selected.

12. The protocol of claim 9, wherein said protocol is based on scheduling rules customizable as visual rules.

13. The protocol of claim 9, wherein sections are selected from the group consisting of:

an initialization section,

said first main section requesting work order service by activating new instances of the section itself,

said second main section including a set of scheduling operations executed iteratively, and

a finishing section.

14. The protocol of claim 13, further comprising a work order scheduling conversation by agents acting as work order agents applying said first main section of the protocol.

15. The protocol of claim 13, wherein said first main section involves a first step wherein a work order agent sends to a physical entity agent a request message including information about required operations, and the physical entity agent that receives said request message is configured for acting by indicating any of:

i) the work order being unable to be processed by the respective resource, directly or via any of its child re-sources;

ii) all the operations requested by said work order being able to be processed by any of said child resources, thus allowing a scheduling criterion aiming at containing all the operations of the same work order in one branch only;

iii) all operations requested by said work order being able to be processed by a set of said child resources, thus allowing a scheduling criterion spreading said operations of said work order over different branches in said system; and

iv) the operations requested by said work order being able to be processed by a set including said respective resource and its child resources, while no sub-branch exists in said system able to process the whole set of the operations requested by said work order.

16. The protocol of claim 14, wherein said first main section involves a second step including operations selected out of the sequence wherein:

having received a list of possible complete schedules for a related work order, said work order agent marks the received whole work order schedules with its own preferences and it sends to a physical entity agent a message containing schedule proposals and related preference values;

said physical entity agent selects a sub-set of possible schedules to save and replies to said work order agent by providing a list of selected schedules in the form of proposed slots;

said work order agent forwards this list to a set of operation agents related to its work order operations by sending a confirm message;

each said operation agent informs the physical entity agent that made the slot proposals about the slot to confirm and the slots to be canceled by sending a confirmation message containing the list of slots to be saved;

said physical entity agent acknowledges said slot confirmation/cancellation by a reply message; and

said operation agent replies to the work order agent by indicating that slot confirmation was concluded.

17. The protocol of claim 16, wherein said second main section includes said work order agent activating a related operation agent by sending an activation message containing a list of physical entity agents that can be contacted by said related operation agent for acquiring service.

18. The protocol of claim 14, wherein said work order agents are configured for applying a scheduling protocol more than once when a scheduling attempt fails because of unfeasibility in assigning one or more operations to resources.

19. The protocol of claim 17, wherein said second main section includes the operations of:

said operation agents sending announcing messages to announce themselves to the physical entity agents able to be contacted for acquiring service;

said physical entity agents replying to said operation agents with acknowledge messages; and

said operation agents replying to said work order agents with acknowledge messages, whereby all said physical entity agents become knowledgeable of the operations that will be released later.

20. The protocol of claim 17, further comprising operations of:

said work order agents checking dependencies and constraints of operations by detecting operations able to be scheduled and sending release messages to the related operation agents, said release messages containing information about release time, due date and deadline for the operation schedule;

each operation agent receiving one said release message sending a request message to the physical entity agents listed in the activation message it has received, said request message containing data for allocating a best slot for the operation;

said physical entity agents receiving said request messages and determining one or more slots for the operation; and

said physical entity agents replying to the operation agent with the list of proposed slots for service.