Research On Dynamic Scheduling Of Tool Flow In FMS

Production efficiency and system flexibility of Flexible Manufacturing System (FMS) are mostly depend on reasonable planning for tool flow, whose schedule is one of important elements of FMS scheduling. But the state-of-the-art scheduling theory and algorithm of tools flow are not so advanced that the degree of automation of tools flow in job shop is comparatively low, which greatly restrain the production ability of FMS increasing. Hence, further research on proper planning and scheduling for tool flow is imperative from the view of theory and practice in order to improve the overall system production ability and make full of the advantage of FMS in flexibility.In the course of the thesis presented, the subject of research is tool flow scheduling in FMS environment. The necessity of tool flow dynamic scheduling research is stated, and the state of the art of tool flow scheduling theory is reviewed. Then tool flow scheduling in cases of procedure provisioning tools and working step provisioning tools are investigated, and the deadlock detecting and deadlock avoidance during the schedule of tool flow are deeply analyzed.Firstly, simulation models are developed respectively in cases of procedure provisioning tools and working step provisioning tools based on Petri net with the oriented-object technique. The models developed accurately and conveniently describe all the sections when FMS is running with not only considering the part flow but also focusing on the tool flow, and include the machine malfunction and tool failure as a component. This is basic for tool flow heuristic scheduling.Secondly, cutting tools life is considered as a factor to rich and enhance tool flow scheduling theory and technique based on tool flow deadlock-free scheduling on the condition of procedure provisioning tools. Extended tools applying allocation graph in relation to tool flow deadlock strategy is built up with the graph theory. The nature of tool flow deadlock is revealed profoundly from the view of graph theory. Tool flow deadlock decision theorem and non-deadlock graph property theorem are given based on extended tools applying allocation graph. Double-layer deadlock avoidance strategy is brought forth to prevent deadlock in two models of machine selection process and tools allocation.The effect of tool flow on part flow efficiency is fully considered in tools allocation decision, and the rule of earliest finish time for current operation is given. The experiment results show that the rule presented is able to decease the waiting time for tools effectively and improve the production efficiency of the system. Tool flow deadlock-free heuristic scheduling algorithm in case of procedure provisioning tools is built up with the method of combination double-layer deadlock avoidance strategy and scheduling rules, and the handling tactics of tools failure are given. The simulation results show that the algorithm is effective.Then tool flow deadlock-free scheduling in case of working step provisioning tools based on graph theory is researched deeply. The evolving model of tools flow state is built up, and the states of tools flow deadlock and tools flow deadlock-free unsafe are defined. The tools resource allocation graph and the definition of machine deadlock are given. Combined machine deadlock with tools flow deadlock-free unsafe state, a detection algorithm of tools flow deadlock-free unsafe state is designed, based on which the tools flow deadlock avoidance approach is developed. An example shows this approach is able to avoid the occurrence of tools flow deadlock.Tool flow deadlock-free heuristic scheduling algorithm in case of working step provisioning tools is developed based on the virtual machine queue idea and the deadlock avoidance approach in tools allocation decision, then the corresponding handling strategy of tools failure in the progress of scheduling is given. Thus, tool flow deadlock avoidance and tools allocation in real time are solved in case of working step provisioning tools.Tool flow scheduling is analyzed from the view of the global optimization, after research on tool flow deadlock-free heuristic scheduling. A mathematical model of integrated scheduling for part flow and tool flow is presented, in which the objective is to minimize system make-span. A double- layer genetic algorithm (GA) is proposed for global optimization of the model. The outer and inner layers of the GA are to search optimal and feasible operation sequences and tool assignment, respectively. A case study shows that the double- layer GA is effective and practicable. The Quasi-static optimal rescheduling base on double-layer GA is presented in order to deal with effectively emergencies such as machine malfunction and tools breakage.Finally, the scheduling simulation programs based on algorithms developed are given and the system performance index by means of the algorithms. The simulation results show that the heuristic scheduling and optimal scheduling algorithms in case of procedure provisioning tools and working step provisioning tools are feasible and effectively. The presented scheduling theory and algorithm provide a foundation for FMS design and running, and establish a basis for fully utilizing FMS performance in actual production.