基于拉格朗日松弛的产能共享讨价还价研究

展开
  • 1. 滁州学院经济与管理学院, 安徽滁州 239000
    2. 东华大学旭日工商管理学院, 上海 200051
王长军  E-mail: cjwang@dhu.edu.cn

收稿日期: 2021-05-24

  网络出版日期: 2024-06-07

基金资助

国家自然科学基金重点项目(71832001);上海市自然科学基金面上项目(20ZR1401900);上海市社科规划一般课题(2019BGL036);安徽省社会科学创新发展研究攻关课题(2020CX058);滁州学院应用经济学重点学科研究课题(2021yyjjx07)

版权

运筹学学报编辑部, 2024, 版权所有,未经授权。

Production capacity sharing bargaining based on Lagrangian relaxation

Expand
  • 1. School of Economics and Management, Chuzhou University, Chuzhou 239000, Anhui, China
    2. Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, China

Received date: 2021-05-24

  Online published: 2024-06-07

Copyright

, 2024, All rights reserved, without authorization

摘要

以制造业产能共享为背景, 考虑自利的产能提供方与需求方诉求不一致和市场关系不对等因素, 采用Nash讨价还价理论研究共享产能分配策略。为此, 首先将传统调度模型与非对称Nash讨价还价模型相结合, 构建出本质为非线性整数规划的产能共享模型。继而, 设计了基于拉格朗日松弛的求解算法, 给出了产能共享的讨价还价分配结果。仿真分析表明, 本文方法在大部分情况下能够获得理想的讨价还价结果。当产能提供方目标为min-sum型, 其关注所有客户的自利且异质的时效要求, 其与客户方的冲突尤其显著; 随着其讨价还价能力的增强, 其改善是以牺牲客户时效要求为代价的。然而当其讨价还价能力再继续增加, 反而导致系统整体效益的波动。因此, 博弈各方需要保持合理的讨价还价强度。

本文引用格式

吴琼, 王长军 . 基于拉格朗日松弛的产能共享讨价还价研究[J]. 运筹学学报, 2024 , 28(2) : 93 -102 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.007

Abstract

The production capacity sharing problem was studied in this paper. Considering that the game is composed of a capacity provider and customers, in which the capacity provider and customers are self-interest, with different demands and different market relations. Nash bargaining theory was adopted to explore the sharing strategy of the production capacity. To be specific, the classic scheduling model and the asymmetric Nash bargaining model were combined to develop a production capacity sharing model, which was essentially a nonlinear integer program. To address the computational issue, a solving method based on Lagrangian relaxation was designed, and then, the bargaining results of production capacity sharing were given. Simulation analysis shows that the proposed algorithm performs well in most cases. It is found that when the capacity provider has a min-sum objective function, the capacity provider pays attention to the performance indicators of all customers, and the conflict between the capacity provider and customers are particularly significant. With the increase of bargaining power of the capacity provider, the capacity provider index is optimized, but the customer performance index becomes worse. However, when the bargaining power of the capacity provider is very strong, it will lead to the fluctuation of the overall efficiency of the system. Therefore, the game parties need to maintain a reasonable bargaining power.

参考文献

1 工业和信息化部. 关于加快培育共享制造新模式新业态?促进制造业高质量发展的指导意见[EB/OL]. (2019-10-29)[2021-05-24]. https://www.miit.gov.cn/zwgk/zcwj/wjfb/zh/art/2020/art_8f82f9a4c4434ff79a5a9e4009cc4e68.html.
2 Pinedo M L . Scheduling: Theory, Algorithms, and Systems[M]. New York: Springer, 2012.
3 徐俊刚, 戴国忠, 王宏安. 生产调度理论和方法研究综述[J]. 计算机研究与发展, 2004, 2, 257- 267.
4 Baker K R , Smith J C . A multiple-criterion model for machine scheduling[J]. Journal of Scheduling, 2003, 6 (1): 7- 16.
5 Agnetis A , Mirchandani P B , Pacciarelli D , et al. Scheduling problems with two competing agents[J]. Operations Research, 2004, 52 (2): 229- 242.
6 Zhao Q L , Yuan J J . Bicriteria scheduling of equal length jobs on uniform parallel machines[J]. Journal of Combinatorial Optimization, 2020, 39 (3): 637- 661.
7 梁建恒, 薛含钰, 白丹宇, 等. 分支定界算法求解带有释放时间的单机双代理调度问题[J]. 运筹与管理, 2019, 28 (10): 83- 88.
8 Li H , Gajpal Y , Bector C R . A survey of due-date related single-machine with two-agent scheduling problem[J]. Journal of Industrial and Management Optimization, 2017, 13 (5): 1- 19.
9 Koutsoupias E, Papadimitriou C. Worst-case equilibria [C]//Annual Symposium on Theoretical Aspects of Computer Science, 1999: 404-413.
10 Qi X . A note on worst-case performance of heuristics for maintenance scheduling problems[J]. Discrete Applied Mathematics, 2007, 155 (3): 416- 422.
11 Nong Q Q , Guo S J , Miao L H . The shortest first coordination mechanism for a scheduling game with parallel-batching machines[J]. Journal of the Operations Research Society of China, 2016, 4 (4): 517- 527.
12 Bülbül K , ?en H . An exact extended formulation for the unrelated parallel machine total weighted completion time problem[J]. Journal of Scheduling, 2017, 20 (4): 373- 389.
13 Croce F D , Scatamacchia R , T'kindt V . A tight linear time $\frac{13}{12}$-approximation algorithm for the $P_2\|C_{\rm max}$ problem[J]. Journal of Combinatorial Optimization, 2019, 38 (1): 608- 617.
14 Kress D , Meiswinkel S , Pesch E . Mechanism design for machine scheduling problems: Classification and literature overview[J]. OR Spectrum, 2018, 40 (3): 583- 611.
15 王长军, 徐琪, 贾永基. 单机下异构任务调度的解性质研究[J]. 管理科学学报, 2015, 18 (7): 70- 81.
16 Cao Q , Jing Y , Zhao H V . Power allocation in multi-user wireless relay networks through bargaining[J]. IEEE Transactions on Wireless Communications, 2013, 12 (6): 2870- 2882.
17 Nasiri-Gheidari O , Marofi S , Adabi F . A robust multi-objective bargaining methodology for inter-basin water resource allocation: A case study[J]. Environmental Science and Pollution Research, 2018, 25 (3): 2726- 2737.
18 Dover O , Shabtay D . Single machine scheduling with two competing agents, arbitrary release dates and unit processing times[J]. Annals of Operations Research, 2016, 238 (1/2): 145- 178.
19 Xu Z J , Xu D H . Single-machine scheduling with workload-dependent tool change durations and equal processing time jobs to minimize total completion time[J]. Journal of Scheduling, 2018, 21 (4): 461- 482.
20 Hong J , Lee K , Pinedo M L . Scheduling equal length jobs with eligibility restrictions[J]. Annals of Operations Research, 2020, 285 (2): 295- 314.
21 王长军, 吴琼. 共享经济中基于排序博弈的单资源供需匹配效率研究[J]. 工业工程与管理, 2021, 26 (1): 165- 173.
22 Luh P B , Hoitomt D J , Max E , et al. Schedule generation and reconfiguration for parallel machines[J]. IEEE Transactions on Robotics and Automation, 2002, 6 (6): 687- 696.
23 Fonseca G B , Nogueira T H , Ravetti M G . A hybrid Lagrangian metaheuristic for the cross-docking flow shop scheduling problem[J]. European Journal of Operational Research, 2019, 275 (1): 139- 154.
24 轩华, 王薛苑, 李冰. 带批和离散机柔性流水车间问题的混合异步次梯度优化的拉格朗日松弛算法[J]. 计算机集成制造系统, 2020, 26 (4): 1001- 1010.
25 陶杰, 高岩. 疫情环境下价格导向的防护物资最优生产分配机制研究[J]. 运筹学学报, 2020, 24 (1): 13- 22.
文章导航

/