基于并行机加工能力配置的多轮拍卖机制研究

朱倩倩, 王秀利, 耿苏杰

系统工程理论与实践 ›› 2020, Vol. 40 ›› Issue (5) : 1242-1254.

PDF(742 KB)
中国科学院数学与系统科学研究院期刊网
PDF(742 KB)
系统工程理论与实践 ›› 2020, Vol. 40 ›› Issue (5) : 1242-1254. DOI: 10.12011/1000-6788-2019-0489-13
论文

基于并行机加工能力配置的多轮拍卖机制研究

    朱倩倩, 王秀利, 耿苏杰
作者信息 +

A multi-round auction mechanism for parallel machine scheduling

    ZHU Qianqian, WANG Xiuli, GENG Sujie
Author information +
文章历史 +

摘要

在私有信息不公开的分散决策下，针对需要承诺交货期限的稀缺并行机加工能力配置问题，以改善分散系统无秩序代价为目标，设计了一种基于时间维度配置稀缺资源的多轮拍卖机制.具体地，该机制根据资源稀缺性受机器加工能力和订单交货期限双重影响的特点，设计线性歧视资源定价方式，既保证定价的公平性，合理性和有效性，又引导任务主体披露真实订单信息，实现分散系统下稀缺资源配置的高效率；该机制中的定标问题是具有NP难属性的组合优化问题，本文设计基于拉格朗日松弛技术的启发式算法，以提高该问题的计算效率和实际应用性.数值实验结果显示，该拍卖机制能显著改善分散决策下并行机加工能力配置的无秩序代价，拍卖机制下的系统总收益平均达全局系统总收益的93.9%.

Abstract

We consider the parallel machine scheduling problem in the decentralized decision-making environment, since the private information is not public, anarchistic competition without mechanism would cause price of anarchy. Hence, we design a multi-round auction mechanism to solve this problem. In this problem, the scarcity of resources is affected by machine processing capacity and order delivery deadline. So we propose a new linear discriminant price policy which based on the order's deadline to ensure fairness, rationality and effectiveness in pricing. The price policy can also guide the participants to disclose real order information so as to achieve the incentive compatibility; Next we present a heuristic algorithm which based on Lagrangian relaxation technique to solve the winner determination problem with NP-hard property. Simulation results show that the auction mechanism can reduce the price of anarchy of the production capability allocation problem significantly. On average, the auction mechanism provides 93.9% of the system value found by global decision-making problem.

关键词

分散决策 / 拍卖机制 / 并行机 / 订单接受与调度 / 拉格朗日松弛

Key words

decentralized decision / auction mechanism / parallel machines / order acceptance and scheduling / Lagrangian relaxation

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
朱倩倩 , 王秀利 , 耿苏杰. 基于并行机加工能力配置的多轮拍卖机制研究. 系统工程理论与实践, 2020, 40(5): 1242-1254 https://doi.org/10.12011/1000-6788-2019-0489-13
ZHU Qianqian , WANG Xiuli , GENG Sujie. A multi-round auction mechanism for parallel machine scheduling. Systems Engineering - Theory & Practice, 2020, 40(5): 1242-1254 https://doi.org/10.12011/1000-6788-2019-0489-13
中图分类号： F273   

参考文献

[1] Pinedo M. 调度: 原理、算法和系统[M]. 北京: 清华大学出版社, 2007. Pinedo M. Scheduling: Theory, algorithms, and system[M]. Beijing: Tsinghua University Publishing House, 2007.
[2] Slotnick S A. Order acceptance and scheduling: A taxonomy and review[J]. European Journal of Operational Research, 2011, 212(1): 1-11.
[3] Wang X L, Zhu Q Q, Cheng T C E. Subcontracting price schemes for order acceptance and scheduling[J]. Omega, The International Journal of Management Science, 2015, 54: 1-10.
[4] Ou J W, Zhong X L. Order acceptance and scheduling with consideration of service level[J]. Annals of Operations Research, 2017, 248(1-2): 429-447.
[5] Wang X L, Geng S J, Cheng T C E. Negotiation mechanisms for an order subcontracting and scheduling problem[J]. Omega, the International Journal of Management Science, 2018, 77: 154-167.
[6] Koutsoupias E, Papadimitriou C. Worst-case equilibria[C]//Proceeding of the 16th International Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, 1999: 404-413.
[7] 王长军, 徐琪, 贾永基. 单机下异构任务调度的解性质研究[J]. 管理科学学报, 2015, 18(7): 70-81. Wang C J, Xu Q, Jia Y J. Properties of solution for heterogeneous tasks scheduling on single machine[J]. Journal of Management Sciences in China, 2015, 18(7): 70-81.
[8] 王长军, 贾永基, 徐琪, 等. 并行机下独立任务调度的无秩序代价分析[J]. 管理科学学报, 2010, 13(5): 44-50. Wang C J, Jia Y J, Xu Q, et al. Price of anarchy analysis for scheduling selfish tasks on parallel machines[J]. Journal of Management Sciences in China, 2010, 13(5): 44-50.
[9] McAfee R P, McMillan J. Auctions and bidding[J]. Journal of Economic Literature, 1987, 25(2): 699-738.
[10] Post D L, Coppinger S S, Sheble G B. Application of auctions as a pricing mechanism for the interchange of electric power[J]. IEEE Transactions on Power Systems, 1995, 10(3): 1580-1584.
[11] 王素凤, 杨善林. 考虑保留价影响报价策略的碳排放权拍卖模型[J]. 管理工程学报, 2016, 30(2): 181-187. Wang S F, Yang S L. Carbon emission rights auction considering the influence of reserve price on bidding strategies[J]. Journal of Industrial Engineering Management in China, 2016, 30(2): 181-187.
[12] 王明喜, 胡毅, 乔晗. 非对称环境下政府采购拍卖模型及配置效率研究[J]. 系统工程理论与实践, 2018, 38(9): 2277-2288. Wang M X, Hu Y, Qiao H. A government procurement auction model and its allocation efficiency in the asymmetric setting[J]. Systems Engineering—Theory & Practice in China, 2018, 38(9): 2277-2288.
[13] Chen R R, Roundy R O, Zhang R Q, el al. Efficient auction mechanisms for supply chain procurement[J]. Management Science, 2005, 51(3): 467-482.
[14] Karabati S, Yalçıin Z B. An auction mechanism for pricing and capacity allocation with multiple products[J]. Production and Operations Management, 2014, 23(1): 81-94.
[15] 赖明辉, 薛巍立, 田歆, 等. 整车运输协作问题迭代拍卖机制设计[J]. 系统工程理论与实践, 2018, 38(12): 3174-3186. Lai M H, Xue W L, Tian X, et al. Iterative auction design for truckload collaborative transportation[J]. Systems Engineering—Theory & Practice, 2018, 38(12): 3174-3186.
[16] 鞠永和, 朱俊武, 王静成, 等. 社交网络下基于个体技能的人力资源配置研究[J]. 系统工程理论与实践, 2018, 38(9): 2376-2389. Ju Y H, Zhu J W, Wang J C, et al. On human resource configuration based on individual skills in social network[J]. Systems Engineering—Theory & Practice, 2018, 38(9): 2376-2389.
[17] 王雅娟, 王先甲. 一种激励相容的多单位在线双边拍卖机制[J]. 管理科学学报, 2015, 18(8): 1-11. Wang Y J, Wang X J. Incentive compatible mechanism for multiunit online double auction[J]. Journal of Management Sciences in China, 2015, 18(8): 1-11.
[18] Kutanoglu E, Wu S D. On combinatorial auction and Lagrangean relaxation for distributed resource scheduling[J]. IIE Transactions, 1999, 31(9): 813-826.
[19] Dewan P, Joshi S. Auction-based distributed scheduling in a dynamic job shop environment[J]. International Journal of Production Research, 2002, 40(5): 1173-1191.
[20] Wurman P R, Wellman M P, Walsh W E. A parametrization of the auction design space[J]. Games and Economic Behavior, 2001, 35: 304-338.
[21] Hall G N, Liu Z X. On auction protocols for decentralized scheduling[J]. Games and Economic Behavior, 2011, 72: 583-585.
[22] Hall G N, Liu Z X. Market good flexibility in capacity auction[J]. Production and Operations Management, 2013, 22(2): 459-472.
[23] Ghosh J B. Job selection in a heavily loaded shop[J]. Computers and Operations Research, 1997, 24(2): 141-145.
[24] Talla N F, Leus R. Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment[J]. Computers and Operations Research, 2011, 38(1): 367-378.
[25] Cesaret B, Oğuz C, Salman F S. A tabu search algorithm for order acceptance and scheduling[J]. Computers and Operations Research, 2012, 39(6): 1197-1205.
[26] Mao K, Pan Q K, Pang X F, el at. A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process[J]. European Journal of Operational Research, 2014, 236(1): 51-60.
[27] Zandieh M, Roumani M. A biogeography-based optimization algorithm for order acceptance and scheduling[J]. Journal of Industrial and Production Engineering, 2017, 34(4): 312-321.
[28] Wang X L, Huang G D, Hu X W, el at. Order acceptance and scheduling on two identical parallel machines. Journal of the Operational Research Society, 2015, 66(10): 1755-1767.

基金

国家自然科学基金（71571101，71871118）
PDF(742 KB)

Accesses

Citation

Detail
段落导航
相关文章

/

〈 〉