Permutation Flow Shop Scheduling Optimization Method Based on Cooperative Games

Abstract

This paper proposes a cooperative games model for the permutation flow shop scheduling problem (PFSP) with multiple customer tasks. Here, customers create alliances through cooperation in the case of delayed and early delivery penalty constraints, and tasks in the alliance are rescheduled to seek maximum cost savings. A new $\beta $ rule allocation method is proposed considering the variability in the delay penalty factor of different ordered tasks. Additionally, it is proven that the cost-saving allocation resulting from this allocation method is a core allocation of the PFSP cooperative games. A hybrid particle swarm optimization algorithm is proposed to obtain the optimal scheduling of each coalition. The algorithm uses a particle swarm as the main body, maintains the advantage of fast convergence of particle swarm optimization, increases the diversity among the population, and improves the optimization performance of the algorithm. Finally, the effectiveness of the algorithm, model, and allocation method is verified via experiments. The total cost for all customers under the optimal scheduling sequence is 5595.8, compared to 6689.8 for the initial scheduling order. The proposed cooperative games model can be applied to various enterprises to better satisfy the diverse needs of the market and customers.

Keywords

• Permutation flow shop scheduling
• cooperative games
• hybrid particle swarm optimization
• xcost allocation
• core