Research And Simulation On Dynamic Job-shop Scheduling Problem Based On Hybrid Ant Colony Algorithm

In the new century, competition between manufacturing enterprises is getting more and more fierce, modem production is moving towards four directions:variety of species, small-scale quantity, punctual delivery and less stocks. Workshop is the material and information center of manufacturing enterprise. Workshop scheduling is a key point for enterprises to meet market needs quickly. Job-shop scheduling problem(JSP) is not only an important issue in actual production, but also a typical NP-hard problem in theoretical study. Ant colony algortithm(ACA) is a suitable way to solve such problem. Efficient optimization scheduling method can significantly improve utilization of equipments, reduce inventory and costs and strengthen responsiveness to the market. In this paper, hybrid ant colony algorithm that combines the artificial immune algorithm(AIA) into ACA is used to solve JSP, its main contents are as follows:1) The first chapter introduces the source, background, purpose and significance of the subject, emphasizing the importance of job-shop scheduling in manufacturing enterprise.2) First, this chapter describes the basic ACA and A1A in detail and shows their characteristics. Then, the basic ACA and AIA are combined together to form hybrid ant colony algorithm. Finally, the fusion strategy and realization steps of hybrid ACA is designed.3) The properties of static JSP is defined, the mathematical and disjunctive graph model of it are also established. Then, the model is corresponded with hybrid ACA exactly, which make the problem a suitable and natural expression for the algorithm. According to the model, the node visiting rules are designed and a detailed algorithmic process is given. Finally, an example from the literature verifies the feasibility and effectiveness of hybrid ACA.4) This chapter describes the basic concept and properties of dynamic JSP. defines the essential differences between static and dynamic JSP and establishes its simulation model based on event-driven principle after analyzing the key issue. An example from the literature is solved, the output is compared with the literature's. The comparison results shows that hybrid ACA has better optimization ability in solving dynamic JSP.5) This chapter summarizes the paper and prospects further research.