Agent-based manufacturing systems scheduling

This work presents a methodology of agent-based manufacturing system scheduling incorporating game theoretic analysis of agent interaction. The developed methodology is universal and applicable to any manufacturing system structure as long as the assembly structure of the products can be modeled and represented by a digraph. The features of the developed agent-based scheduling methodology include: (i) the developed methodology takes manufacturing system structure and digraph representation of the product assembly structure as inputs and automatically generates agents as entities in the system that are ultimate participants in the scheduling process; (ii) the agents in the system correspond to the decomposed subdigraphs of the original digraph and each agent is responsible for solving the corresponding subdigraph; and (iii) the coordination among agents in the scheduling systems is carried out by solution concepts developed in the cooperative game theory: at each stage of the scheduling the winning agent, who is eligible for scheduling his/her job in the system, is the one who has the largest power index, Shapley value, from cooperating with the coalition that has already scheduled his/her job on the system. The overall scheduling process is modeled as execution of outer and inner games.; To evaluate the performance of the agent-based scheduling approach developed in this dissertation, computational experiments were conducted. The agent-based manufacturing system scheduling approach was coded in C++ and the program was run to test 70 randomly generated problems. The scheduling of the tasks was performed on a manufacturing system consisting of machining and assembly stages. Each stage of the system consists of number of parallel identical machines. The objective of the scheduling was minimization of maximum completion time of the overall task. The analysis of experiments indicates a performance of methodology within 2 times of the developed lower bounds. To compare the performance of the developed methodology for the scheduling problems reported in the literature, 1200 randomly generated n-job 3-stage flexible flowshop scheduling problems were tested. The analysis of results indicate that agent-based scheduling outperformed the best-reported results for almost all of the tested problems. For those underperformed problems, the results are statistically compatible.