Research of Cellular Automata Model of Dockyard Ship Shifting Scheduling Problem and Its Ant Colony Algorithm

Abstract Shipyard ship shifting scheduling problem is a NP hard problem. By analyzing the characteristics of the problem, gradually present the general cellular automata model of the problem with the cellular automata theory, and explore the evolution rules of the CA model. Based on the evolution rules of the model, we proposal a general algorithm ideas and processes of the model. Finally, the Ant Colony Algorithm of the model is presented and the validity and convergence of the algorithm is proved. The topic of the paper is that provides an idea for shipyard shifting scheduling problem modeling.