Optimisation of block erection scheduling based on a Petri net and discrete PSO

Abstract

The shipyard block erection system (SBES) is a typical discrete-event dynamic system. To model multiprocessing paths and a concurrent assembly procedure, a timed Petri net (TPN) is proposed. The definition of a Petri net is extended to accord with the real-world SBES organisation. The basic TPN modules are presented to model the corresponding variable structures in the SBES, and then the scheduling model of the whole SBES is easily constructed. A modified discrete particle swarm optimisation (PSO) based on the reachability analysis of Petri nets is developed for scheduling of the SBES. In the proposed algorithm, particles are coded by welding transitions and selecting places of the TPN model, and then the collaboration and competition of particle individuals is simulated by crossover and mutation operators in a genetic algorithm. Numerical simulation suggests that the proposed TPN–PSO scheduler can provide an improvement over the conventional scheduling method. Finally, a case study of the optimisation of a back block erection process is provided to illustrate the effectiveness of the method.

Keywords:

• Petri nets
• particle swarm optimisation
• modelling
• scheduling
• shipyard block erection system

Acknowledgements

This work is supported by the Fundamental Research Funds for the Central Universities (No. HEUCF100701) and, in part, by the research fund of China HeiLongJiang government (No. LRB06-167). The authors would like to thank Prof. Qiu Chang-hua of Harbin Engineering University for discussions during the course of the study.