带有交货期的一类柔性流水车间调度问题的合作博弈

doi:10.15960/j.cnki.issn.1007-6093.2025.04.007

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (4): 83-93.doi: 10.15960/j.cnki.issn.1007-6093.2025.04.007

带有交货期的一类柔性流水车间调度问题的合作博弈

孙文娟¹^,², 宫华¹^,²^,*(), 许可¹^,², 申爱红³

1. 沈阳理工大学理学院辽宁省兵器工业智能优化与控制重点实验室, 辽宁沈阳 110159
2. 沈阳工业大学管理学院, 辽宁沈阳 110870
3. 中国刑事警察学院基础部, 辽宁沈阳 110854

收稿日期:2022-06-22 出版日期:2025-12-15 发布日期:2025-12-11
通讯作者: 宫华 E-mail:gonghua@sylu.edu.cn
基金资助:
辽宁省教育厅科学研究经费项目(LG202025);辽宁省“兴辽英才计划”项目(XLYC2006017);中国刑事警察学院科研项目(D2020045)

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

Wenjuan SUN¹^,², Hua GONG¹^,²^,*(), Ke XU¹^,², Aihong SHEN³

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:2022-06-22 Online:2025-12-15 Published:2025-12-11
Contact: Hua GONG E-mail:gonghua@sylu.edu.cn

摘要/Abstract

摘要：

本文利用合作博弈理论研究了带有交货期的一类柔性流水车间调度问题。具有初始调度顺序的工件需要依次经过多道工序加工, 每道工序有多台同速并行机。工件所属客户的成本为工件完工时间的线性加权与拖期惩罚费用之和。考虑到客户可以通过合作结成联盟, 并在联盟内重新调度以节省成本, 以客户为博弈方, 以联盟最大成本节省为特征函数建立合作博弈模型。通过分析合作博弈性质, 寻求合理的成本节省分配方法以降低客户成本。当工件的加工时间与工序相关且具有公共交货期时, 证明了合作博弈为凸博弈, $\beta$规则和Shapley值均能得到一个核心分配, 并且给出了Shapley值的一种简单计算形式。数值算例验证了合作博弈模型的性质及成本分配方法的合理性。

关键词: 柔性流水车间, 合作博弈, 交货期, β 规则, 核心分配

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.

Key words: flexible flow-shop, cooperative games, due date, β rule, core allocation

中图分类号:

O225

孙文娟, 宫华, 许可, 申爱红. 带有交货期的一类柔性流水车间调度问题的合作博弈[J]. 运筹学学报（中英文）, 2025, 29(4): 83-93.

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.

图/表 3

参考文献 19

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. doi: 10.1016/S0377-2217(01)00070-4
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. doi: 10.1057/s41274-016-0010-9
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. doi: 10.1016/j.ejor.2019.04.046
12	Slikker M .Balancedness of sequencing games with multiple parallel machines[J].Annals of Operations Research,2005,137(1):177-189. doi: 10.1007/s10479-005-2253-8
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. doi: 10.1016/j.ejor.2021.02.030
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. doi: 10.1007/BF01753431
18	Curiel I , Potters J , Prasad R , et al.Sequencing and cooperation[J].Operations Research,1994,42(3):566-568. doi: 10.1287/opre.42.3.566
19	Shapley L S .A value for $n$-person games[J].Annals of Mathematics Studies,1953,28,307-317.

$ T $	$ \lambda_T $	$ v(T) $	$ T $	$ \lambda_T $	$ v(T) $	$ T $	$ \lambda_T $	$ v(T) $	$ T $	$ \lambda_T $	$ v(T) $
12	10	10	123	40	80	2 345	20	120	45 678	0	100
23	30	30	234	50	100	3 456	0	20	123 456	20	290
34	20	20	345	0	20	4 567	0	0	234 567	0	130
45	0	0	456	0	0	5 678	20	100	345 678	10	130
56	0	0	567	0	0	12 345	30	260	1 234 567	0	290
67	0	0	678	30	80	23 456	10	130	2 345 678	40	280
78	50	50	1 234	60	210	34 567	0	20	12 345 678	50	490

[1]	陈聪利, 杨辉, 杨光惠, 王春. 不确定参数下n人非合作博弈的逼近定理[J]. 运筹学学报（中英文）, 2025, 29(1): 105-113.
[2]	孙攀飞, 孙浩. 合作博弈两类组合解的社会可接受性[J]. 运筹学学报（中英文）, 2024, 28(3): 121-131.
[3]	李文忠, 徐根玖. 效用可转移合作博弈的Shapley值公理化研究进展综述[J]. 运筹学学报（中英文）, 2024, 28(3): 63-80.
[4]	袁先智. 共识博弈与区块链生态共识均衡[J]. 运筹学学报（中英文）, 2024, 28(3): 1-26.
[5]	陈泽融, 肖汉. 最短路博弈群体单调分配方案构造[J]. 运筹学学报, 2022, 26(2): 101-110.
[6]	张广, 肖文君, 邬冬华. 图博弈的过程比例解[J]. 运筹学学报, 2021, 25(4): 101-110.
[7]	徐晨, 徐寅峰, 郑斐峰. 考虑部分工件不可打扰的多任务调度问题研究[J]. 运筹学学报, 2021, 25(4): 91-100.
[8]	宣洪伟, 李振东, 盛舟山, 刘林冬. 灾后运输网络中的最短路修复合作博弈[J]. 运筹学学报, 2021, 25(3): 183-199.
[9]	于晓辉, 杜志平, 张强, 逄金辉. 基于T-联盟Shapley值的分配策略[J]. 运筹学学报, 2020, 24(4): 113-127.
[10]	于晓辉, 杜志平, 张强, 周珍, 逄金辉. 一种资源投入不确定情形下的合作博弈形式及收益分配策略[J]. 运筹学学报, 2019, 23(4): 71-85.
[11]	肖燕, 李登峰. 带策略约束的区间数双矩阵博弈的双线性规划求解方法[J]. 运筹学学报, 2019, 23(4): 59-70.
[12]	侯丽娜, 孙海琳. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式[J]. 运筹学学报, 2019, 23(3): 91-108.
[13]	张玉忠, 张龙. 优化交货期窗口的两阶段供应链排序问题[J]. 运筹学学报, 2016, 20(4): 30-38.
[14]	王斯琪, 谢政, 戴丽. 一种求解合作博弈最公平核心的非精确平行分裂算法[J]. 运筹学学报, 2016, 20(2): 105-112.
[15]	邓喜才，向淑文，左羽. 不确定性下强Berge均衡的存在性[J]. 运筹学学报, 2013, 17(3): 101-107.

带有交货期的一类柔性流水车间调度问题的合作博弈

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 19

相关文章 15

编辑推荐

Metrics

本文评价