Research Article

Cooperative games on a class of flexible flow-shop scheduling problem with due-dates

  • Wenjuan SUN ,
  • Hua GONG ,
  • Ke XU ,
  • Aihong SHEN
Expand
  • 1. Liaoning Key Laboratory of Intelligent Optimization and Control for Ordnance Industry, School of Science, Shenyang Ligong University, Shenyang 110159, Liaoning, China
    2. chool of Management, Shenyang University of Technology, Shenyang 110870, Liaoning, China
    3. Department of Basic Courses, Criminal Investigation Police University of China, Shenyang 110854, Liaoning, China

Received date: 2022-06-22

  Online published: 2025-12-11

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.

Abstract

A class of flexible flow-shop scheduling problem with due-dates is studied by using cooperative games theory. In this problem, jobs with an initial scheduling order need to be processed successively on multiple processes. There are multiple identical parallel machines at each processing stage. The cost of customer who owns one job is the sum of the job's weighted completion time and tardiness penalty. The scheduling objective is to minimize the sum of customers' costs. Considering that customers can collaborate to form coalitions and reschedule within coalitions to save costs, a cooperative game model is established. In this model, the customers can be seen as the players and the maximum cost savings obtained by rescheduling can be seen as the characteristic function. By analyzing the properties of cooperative games, the reasonable allocations of cost savings are used to reduce the customer's cost. When the jobs have identical processing time on the same processing stage and common due date, it is proved that the corresponding cooperative games are convex. Core allocations can be obtained by the $\beta$ rule and the Shapley value, and the Shapley value can be expressed in a simple form. Examples are given to verify the properties of the cooperative games and rationality of the cost allocation methods.

Cite this article

Wenjuan SUN , Hua GONG , Ke XU , Aihong SHEN . Cooperative games on a class of flexible flow-shop scheduling problem with due-dates[J]. Operations Research Transactions, 2025 , 29(4) : 83 -93 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.04.007

References

1 轩华, 张慧贤, 李冰.多阶段恶化柔性流水车间调度优化研究[J].系统工程,2020,38(3):52-63.
2 韩忠华, 张权, 史海波, 等.带准备时间的柔性流水车间多序列有限缓冲区排产优化问题[J].机械工程学报,2019,55(24):236-252.
3 王君妍, 王薛苑, 轩华.带批处理机的多阶段柔性流水车间调度优化[J].郑州大学学报(工学版),2017,38(5):86-90.
4 Curiel I , Pederzoli G , Tijs S .Sequencing games[J].European Journal of Operational Research,1989,40(3):616-634.
5 Borm P , Fiestras J G , Hamers H , et al.On the convexity of games corresponding to sequencing situations with due dates[J].European Journal of Operational Research,2002,136(3):616-634.
6 Zhou Y P , Gu X S .One machine sequencing game with lateness penalties[J].International Journal on Information,2012,15(11):4429-4434.
7 Ji M , Liu S , Zhang X L , et al.Sequencing games with slack due windows and group technology considerations[J].Journal of the Operational Research Society,2017,68(2):121-133.
8 Li F, Yang Y. Cooperation in a single-machine scheduling problem with job deterioration[C]//The $2016$ IEEE Information Technology, Networking, Electronic and Automation Control Conference, 2016: 79-82.
9 周意元, 张强, 王利明, 等.具有学习效应的排序对策[J].运筹与管理,2018,27(1):49-52.
10 Yang G J , Sun H , Uetz M .Cooperative sequencing games with position-dependent learning effect[J].Operations Research Letters,2020,48(4):428-434.
11 Yang G J , Sun H , Hou D S , et al.Games in sequencing situations with externalities[J].European Journal of Operational Research,2019,278(2):699-708.
12 Slikker M .Balancedness of sequencing games with multiple parallel machines[J].Annals of Operations Research,2005,137(1):177-189.
13 周艳平, 顾幸生.一类流水车间调度问题的合作博弈[J].化工学报,2010,61(8):1983-1987.
14 Ciftci B , Borm P , Hamers H , et al.Batch sequencing and cooperation[J].Journal of Scheduling,2008,16(4):405-415.
15 Atay A , Calleja P , Soteras S .Open shop scheduling games[J].European Journal of Operational Research,2021,295,12-21.
16 孙文娟, 宫华, 许可, 等.带有交货期的比例流水车间调度问题的合作博弈[J].控制与决策,2022,37(3):712-720.
17 Shapley L S .Cores of convex games[J].International Journal of Game Theory,1971,1(1):11-26.
18 Curiel I , Potters J , Prasad R , et al.Sequencing and cooperation[J].Operations Research,1994,42(3):566-568.
19 Shapley L S .A value for $n$-person games[J].Annals of Mathematics Studies,1953,28,307-317.
Outlines

/