English

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

• • 上一篇    

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

孙文娟1,2, 宫华1,2,†, 许可1,2, 申爱红3   

  1. 1. 沈阳理工大学理学院辽宁省兵器工业智能优化与控制重点实验室, 辽宁沈阳 110159;
    2. 沈阳工业大学管理学院, 辽宁沈阳 110870;
    3. 中国刑事警察学院基础部, 辽宁沈阳 110854
  • 收稿日期:2022-06-22 发布日期:2025-12-11
  • 通讯作者: 宫华 E-mail:gonghua@sylu.edu.cn
  • 基金资助:
    辽宁省教育厅科学研究经费项目(No.LG202025),辽宁省“兴辽英才计划”项目(No.XLYC2006017),中国刑事警察学院科研项目(No.D2020045)

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

SUN Wenjuan1,2, GONG Hua1,2,†, XU Ke1,2, SHEN Aihong3   

  1. 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 Published:2025-12-11

PDF

2

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

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

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, $\beta$ rule, core allocation

中图分类号: