Title: Multiple rules with game theoretic analysis for flexible flow shop scheduling problem with component altering times
Authors: Zhonghua Han; Yihang Zhu; Xiaofu Ma; Zhili Chen
Addresses: Faculty of Information and Control Engineering, Shenyang Jianzhu University, Shenyang, Liaoning, China; Department of Digital Factory, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang, Liaoning, China; Key Laboratory of Networked Control System, Chinese Academy of Sciences, Shenyang, Liaoning, China ' Faculty of Information and Control Engineering, Shenyang Jianzhu University, Shenyang, Liaoning, China ' Department of Electrical and Computer Engineering, Virginia Tech, Blacksburg, USA ' Faculty of Information and Control Engineering, Shenyang Jianzhu University, Shenyang, Liaoning, China
Abstract: This paper studies the flexible flow shop scheduling problem with component altering times (FFSP-CAT), which is a specific form of the flexible flow shop scheduling problem with sequence dependent setup times in the practical scenario. Dealing with FFSP-CAT includes the jobs' machine assignment determination and the globe optimisation. We develop six rules for jobs' machine assignment, and since these rules will easily conflict with one another if they are used with the same priorities, we construct a repeated cooperative model and provide a game theoretical analysis, then derive a Nash equilibrium machine assignment scheme (NEMAS) to effectively manage these rules for jobs' machines assignment at each stage. Furthermore, to achieve the global optimum, we design an advanced compact genetic algorithm (ACGA). By combining NEMAS and ACGA, an approach named advanced compact genetic algorithm with Nash equilibrium machine assignment scheme (ACGA-NEMAS) is used for minimising the makespan of FFSP-CAT. Through extensive comparison experiments with different scales of instances, we show that the algorithm with NEMAS acquires 56.85% improvement over the algorithm without NEMAS, and ACGA-NEMAS performs 80.28% better than genetic algorithm.
Keywords: repeated cooperative games; multiple rules; flexible flowshops; sequence dependent setup times; compact genetic algorithms; CGA; game theory; flowshop scheduling; component altering times; machine assignment; globe optimisation; Nash equilibrium.
International Journal of Modelling, Identification and Control, 2016 Vol.26 No.1, pp.1 - 18
Received: 20 Aug 2015
Accepted: 21 Oct 2015
Published online: 14 Jul 2016 *