TABLE OF CONTENTS In this section, the general framework of the agent-based approach for scheduling in an agile manufacturing environment is presented. The successful implementation of agent-based approach strongly depends on how the system is decomposed into interrelated subsystems so that the integrity of the system is not violated. The digraph representation of product assembly sequence allows successful decomposition of large size scheduling problems into sub-problems, so that the integrity of original problem is not violated.
The digraph decomposition procedure described by [KUS 89] is used for decomposing the overall scheduling problem into sub-problems. The decomposition procedure consists in the following; a complex digraph is decomposed into simple sub-digraphs by removing root node A i ( A 3 in example presented by Figure 2(b)) from it. Then, moving forward we remove all the assembly nodes until the digraph is decomposed to the level where all resulting sub-digraphs have simple structure. Products with simple digraph representation have linear assembly structure and their optimal scheduling can be achieved by polynomial algorithms (see [HE 02]). As a result of decomposition, a set of sub-digraphs and single nodes (machining and assembly operations) is generated. Each decomposed sub-digraph, generated during the decomposition process, is an individual job that needs to be scheduled according to its precedence relationships with other jobs. For each sub-digraph an agent is assigned as an entity of the system that is responsible and authorised only for scheduling his job in the system. If a single assembly node generated...
