Flower Pollination Algorithm Based on Block Structure Properties for Reentrant Job Shop Scheduling Problem

Abstract

Flower pollination algorithm based on block structure properties (FPA_BSP) is presented to minimize the total weighted tardiness (TWT) for reentrant job shop scheduling problem (RJSSP). Firstly, the mathematical model of RJSSP based on the disjunctive graph is established, and then its duality model is proved to be the model of maximum cost flow problem after it being determined the direction of the disjunctive arcs. Secondly, the extended reentrant-smallest-order-value (RSOV) encoding rule is designed to transform FPA’s individuals from real vectors to job permutations so that flower pollination algorithm (FPA) can be used to perform global search for finding high-quality solutions or regions in the solution space. Thirdly, eight kinds of neighborhood structures are defined, and the inner properties of block structures are analyzed based upon the properties of the maximum cost flow problem. The determination conditions of the four former neighborhood structures for improving TWT are obtained by the block structures’ analyses, which can be used to avoid search in the invalid regions. Then, a high-efficient local search integrating multiple neighborhoods with the obtained determination conditions is proposed to execute a thorough search from the promising regions found by the global search. Computational experiments and comparisons manifest the effectiveness of the presented FPA_BSP. The properties of RJSSP’s block structures and incorporates them with FPA are proposed to obtain an effective FPA_BSP for solving RJSSP. It is also the first time that FPA is used to address scheduling problem.

Zaixing Sun

PhD Candidate

I am currently pursuing a PhD degree in computer science and technology with the School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen, China. I am also a visiting student with the Evolutionary Computation Research Group, Centre for Data Science and Artificial Intelligence & School of Engineering and Computer Science, Victoria University of Wellington, Wellington, New Zealand. My research interests include cloud computing, intelligent optimisation and scheduling.