基于组合拍卖的多Agent调度问题研究

摘要

随着制造业全球化趋势的不断加深，企业间的专业化分工日益深入和细化，制造资源的优化配置正在从企业内、区域内向整个地区、整个国家乃至全球范围延伸。信息技术的发展和各种先进制造技术的出现，为诸如应用服务提供商、敏捷制造、网络化制造、服务型制造、云制造等新型制造模式的出现提供了技术上的支持。这些新的制造模式强调企业间的协作和全社会范围内的资源共享和优化配置，以保证产品从设计到制造的低成本和高效率。由于价值链中的不同企业间存在着异构性、分布性和自治性等特点，如何将分散的制造资源有效地组织起来，实现“分散资源集中使用，集中资源分散服务”的目标，成为制造领域研究的热点。
　　本文采用多Agent技术，旨在从全局优化以及局部协调的角度对上述问题展开讨论。首先在分布式决策环境下研究多Agent之间的协商机制和调度模型;然后考虑多Agent环境中采用线性资源消耗函数的加工时间可控调度问题;最后，将资源消耗函数扩展为非线性凸函数形式。具体而言，本文的研究工作主要包括以下三个方面:
　　首先，考虑分布式环境中各Agent的异构性、分布性、自治性等特点，提出了一种多回合组合拍卖机制，采用基于需求的投标语言，将组合拍卖的一般形式与机器调度的建模技术相结合，建立了一种改进的竞胜标模型，该模型同时兼顾了系统收益与机器利用率。同时，通过投标策略的改进，激励未中标的投标者放宽对加工时间需求的约束来参与下一回合的竟标，为调度计划的制定提供了更加灵活的调度空间。数值实验的结果验证了机制的有效性，该机制在保证系统收益的同时，提高了资源的利用率，提升了客户服务水平。
　　第二，为了使加工资源得到更加充分的利用，将可控加工时间引入多Agent调度问题中，并将加工环境由单机扩展到并行机。在该问题中，资源拥有者可以根据实际需要，调整资源消耗量以控制工件的加工时间，形成了加工时间可控的多Agent调度问题。资源拥有者在进行中标决策时，既要决策中标工件、机器分配、加工顺序，还要决策为加工每个工件投入的资源量，其目标是使自身收益最大化。同时，为加快拍卖的收敛速度，提高拍卖的效率和求解质量，设计了一种基于次梯度方法的自适应价格更新方法。实验结果表明，与传统的“刚性”加工时间的调度模型相比，可控的加工时间可以增加调度的灵活性，能够使生产资源得到更加充分的利用，使资源拥有者的收益得到进一步提升。
　　最后，将加工时间可控调度问题中的资源消耗函数由线性函数扩展到非线性凸函数形式。为求解非线性混合整数规划竞胜标模型，设计了一个两阶段求解方法:先确定加工方案，再求解最优资源分配问题。在此基础上，设计了分支定界算法和遗传算法求解竞胜标模型。实验结果表明，对于中小规模问题，分支定界算法能够在合理时间内给出最优解或近优解;对于大规模问题，遗传算法能够在较短时间内给出次优解。