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

A multi-round auction mechanism for parallel machine scheduling

作　　者：朱倩倩 王秀利[1] 耿苏杰 ZHU Qianqian;WANG Xiuli;GENG Sujie(School of Economics and Management,Nanjing University of Science and Technology,Nanjing 210094,China)

机构地区：[1]南京理工大学经济管理学院,南京210094

出　　处：《系统工程理论与实践》2020年第5期1242-1254,共13页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71571101,71871118)。

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

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

分 类 号：F273[经济管理—企业管理]