两台平行机排序博弈问题的协调机制

排序理论是组合最优化理论的重要组成部分,如果在排序过程中有一个系统管理员来安排相应任务,那么往往会得到比较理想的解。但是,随着互联网的发展,在许多排序过程中由系统管理员来强加控制是不可行的,因为互联网的用户具有独立性和自利性,他们"自私"地追求自身的利益最优,而不在乎是否造成社会资源的浪费。若没有合理的资源使用机制,这种自利性往往会使结果与理论最优值偏差巨大。因此设计合理的机制以影响、引导独立和"自私"的用户的选择从而减少社会资源的浪费将具有重大的理论意义。本文针对如下排序博弈模型:具有2台平行机,工件是局中人,工件的策略是对机器的选择,工件的目标是最小化它的完工时间,全局目标是最小化最大完工时间,探讨SPT-LPT机制(SPT-LPT机制是指一台机器按工件加工时间的不减顺序排序,另一台机器按工件加工时间的不增顺序排序),首先研究了SPT-LPT机制下相应排序博弈问题的纳什均衡解的情况,其次证明了当工件数不小于4时,SPT-LPT机制下的无秩序代价为4/3。

考虑维护且加工时间可变的单机调度问题研究

解决了考虑多阶段时间窗(Time-window)[u,v]周期性维护的情况下,因工件加工存在学习效应,加工时间可变时目标函数为最小makespan的单机调度问题。证明了维护次数θ的上界θUB,首次提出虚拟维护的概念,在此基础上给出了两阶段模型来描述该问题。然后,本文给出了多项式时间复杂度的启发式算法,LPT-SPT算法;以及将初始解群和接受概率等概念引入变领域搜索算法(Variable Neighborhood Search,VNS),提出了改进的VNS算法,基于群的变领域搜索(Populated Variable Neighborhood Search,P-VNS)。最后,大量的实例验证了LPT-SPT算法和P-VNS有着较高的时间效率和很好的解精度。