单机资源分配效率及机制研究——考虑单位订单异构客户

摘要

如何将一段调度时域内的有限资源在多个需求个体之间进行有效分配是一类基础问题。传统上，常假设资源提供方为全局决策者，提供方按照自身性能指标分配有限资源，需求个体的诉求往往并不被关注。而现实中，独立个体的个性化要求不仅是客观存在的，而且日益呈现出多样化趋势。因此，具有独立目标的资源提供方和自私且异构(Heterogeneous)的需求个体之间的冲突就不可避免。一方面，为深入研究这一冲突程度，有学者提出无秩序代价(Price of Anarchy,POA)的概念，定量描述由于个体自利性(Selfishness)而导致的最差全局结果和资源提供方所期望的最优全局结果之间的差距。此后，无秩序代价的概念被引申到资源分配效率的研究中。另一方面，这一冲突问题也促使资源提供方设计更为有效的资源分配机制，满足日益多样化的客户需求。这也意味着，从资源分配优化的角度来说，资源提供方不能仅仅关注自身的性能指标，而需要更多的综合考虑多方利益目标。
　　本文将上述问题抽象为制造环境中，面向自利订单的单机资源分配效率及分配机制研究。其中，具有相同处理长度(identical processing length)的单位订单(single-unit product)有不同的正规型(regular)和非正规型(non-regular)时效要求，资源提供方也具有独立的优化目标。本文首先描述了单机下异构任务调度的基本模型，而后逐层递进的深入分析了Nash均衡调度与Pareto调度的关系，后又探讨了N人Pareto调度与N+1人Pareto调度解集合的关系。在此基础上定量分析了Pareto调度可能导致资源提供方性能指标的最大恶化程度，即无秩序代价。由此揭露资源分配问题中自利异构客户方与资源提供方之间的冲突机理。在资源分配效率研究的基础上，为反映博弈各方的诉求和不对等关系，本文利用多人Nash讨价还价模型来描述这一问题，建立了基于Nash讨价还价理论的资源分配机制。对于构造出的带约束非线性整数规划模型，本文基于拉格朗日松弛法给出了三种可行化调度方案进行求解。与此同时，为衡量拉格朗日松弛法的有效性，本文采用商业软件 LocalSolver对原问题直接进行求解。仿真实验验证了本文Nash讨价还价机制的可行性。
　　本文的主要研究内容和研究结论如下：
　　(1)基于单机下异构任务调度的基本模型和Nash均衡调度与Pareto调度的概念，证明出Pareto调度集合为Nash均衡调度集合的子集这一定理。在此基础上，深入探讨了异构客户的任意型订单按 EDD规则排序产生的NE调度与任意NE调度，这两种调度下导致的最差POA之间的联系。对于静态单机下，具有单位订单的异构任务，且资源提供方的性能指标为完成时间之和或最大完成时间的问题背景下，通过研究相继证明出如下定理：1)存在按 EDD规则排序的 Nash均衡调度。2)存在按 EDD规则排序的Nash均衡调度是使得资源提供方性能指标最差的 Nash均衡调度。3)按EDD规则排序的Nash均衡调度必定是Pareto调度。4)存在按EDD规则排序的Pareto调度是使得资源提供方性能指标最差的调度。在对N人解集合相关性质研究的基础上，后又针对资源提供方和客户方的整体性能指标，探讨了N人Pareto调度与N+1人Pareto调度解集合的关系，分析表明：1)一定存在按EDD规则排序且使得整体性能指标最优的Nash均衡调度。2)存在使得整体性能指标最优的调度不仅属于N+1人Pareto解集合，而且属于N人Pareto解集合。
　　(2)基于上述的相关性质定理，继而推导且紧界验证了具有任意型时效指标的单位订单，按照EDD规则排序的Pareto调度产生的最差调度结果和资源提供方期望的最优调度结果之间的差距(即 POA)，并且深入探讨了自利异构的客户群体的组成对 POA的影响。研究表明：1)不论资源提供方的性能指标为完成时间之和还是最大完成时间，一方面由于调度时域的限制，POA不会无止境的被恶化；另一方面在固定的调度时域内，资源提供方面对的客户越多，则POA越小，资源提供方的资源分配效率越高，并且当资源提供方面对的客户都是正规型客户时，任意的Nash均衡调度都是使得资源提供方性能指标最优的调度。2)当资源提供方的性能指标为完成时间之和时，如果正规型客户数目为某一固定值，那么随着非正规客户数目的增加，POA先恶化至最差值后又得到优化。3)当资源提供方的性能指标为最大完成时间时，客户群体中非正规型客户的比率越大，则资源提供方的性能指标就越早的被恶化。
　　(3)基于上述有关资源分配效率的研究结论，资源提供方亟须设计出更为有效的资源分配机制，在考虑了自身性能指标的同时，也能够满足客户的多样性需求。本文为反映博弈各方的复杂自利性和不对等关系，建立了基于多人Nash讨价还价理论的资源分配机制。对于构造出的带约束非线性整数规划模型，采用拉格朗日松弛法设计了基于次梯度法、变量轮换法的资源分配机制，并给出了三种可行化调度方案。后为评价拉格朗日松弛算法，本文采用商业软件LocalSolver直接求解原问题，得到LocalSolver调度方案，也为资源提供方实际运作过程中提供了衡量绩效的基准。
　　(4)本文深入分析了各参与方讨价还价能力系数、资源提供方的调度时域、三种可行化调度方案对最终调度结果的影响。仿真分析发现：1)随着调度时域的增大，三种可行化调度方案皆使得客户都更有可能占据靠近期望交期的位置。且调度时域愈大，三种可行化方案得到的调度结果与LocalSolver结果愈接近。2)三种可行化方案虽在某些算例的计算中有优劣之分，但三种方案的调度结果与LocalSolver结果相差都不大，能够有效的解决相关问题。3)随着资源提供方讨价还价能力系数的增大，资源提供方的性能指标逐渐得到优化，客户方的性能指标逐渐被恶化，Nash讨价还价模型的目标函数值逐渐增大。4)当Nash讨价还价模型达到LocalSolver解时，调度方案可能不唯一；当资源提供方性能指标与客户方性能指标之和达到稳定时，拉格朗日松弛法得到的结果未必能达到LocalSolver结果。5)若资源提供方特别强势，则在可行化调度时，会更多的关注资源提供方诉求，极少的关注客户诉求，严重恶化了客户的性能指标，进而导致可行化调度结果与LocalSolver结果的偏差。6)对于拥有相同期望交期的客户，讨价还价能力系数较大的个体往往具有更多优势，其能够占据对自己更有利的资源段来优化自身性能指标。
　　本文的创新点在于：综合考虑了具有正规型和非正规型指标的自利客户，分析了Nash均衡调度与Pareto调度之间的联系，给出了Pareto调度可导致的POA界。运用Nash讨价还价理论构建出反映各方复杂自利性和不对等关系、资源提供方保留收益与POA内在联系的资源分配模型，得到了满足Pareto最优的Nash均衡解，并对供给体系更好的适应多样性需求提出了一些管理见解。

目录

声明

第1章 绪论

1.1 研究背景及问题的提出

1.2 研究目标与研究意义

1.3 研究内容与论文框架

1.4 论文研究方法及创新点

第2章 相关理论基础及其文献综述

2.1 生产调度理论综述及研究现状

2.2 资源分配效率相关研究现状

2.3 资源分配机制相关研究现状

2.4 Nash讨价还价理论综述及相关研究现状

2.5 文献评述

第3章 单机下异构任务调度的解性质研究

3.1 变量定义与问题描述

3.2 解概念定义与关系分析

3.3 N人解集合相关性质研究

3.4 N+1人解集合与N人解集合关系研究

3.5 本章小结

第4章 单机下Pareto调度的POA分析

4.1 变量定义与模型假设

4.2 资源提供方性能指标为完成时间之和下的POA推导与紧界验证

4.3 资源提供方性能指标为最大完工时间下的POA推导与紧界验证

4.4 POA变化趋势分析

4.5 本章小结

第5章 基于Nash讨价还价的单机资源分配机制研究

5.1 多人Nash讨价还价问题背景

5.2 单机下Nash讨价还价模型建立与分析

5.3 Nash讨价还价模型的机制设计

5.4 本章小结

第6章 资源分配机制的仿真与分析

6.1 随机数据产生规则

6.2 仿真分析

第7章 研究结论与展望

参考文献

攻读学位期间发表的学术论文

致谢