任务如何分配是生产生活中经常会出现的问题。从简单的安排员工完成任务,到复杂的大型项目规划实施,任务分配都在其中发挥出了重要的作用。在任务分配中,分配的效率、资源利用率、参与者的收益等都是评价一个任务分配机制优劣的重要因素。一个合理的任务分配机制,既可以提高分配效率,也能保障分配的公平,更重要的是使得分配方案的社会效用最大化。当任务的要求变得更加详细具体,如何准确而精简的进行表示?当任务间有了先后次序的约束,我们如何去发现这些任务的先后次序关系?当任务自身有了时间约束,如何才能保证任务的最终完成?这些问题都大大增加了任务分配问题的复杂度。针对上述问题,本文的主要工作与贡献如下:1.提出了基于拍卖理论的任务分配方法。本文将任务视为一个独有的、有价值的资源(商品)进行拍卖,参与竞拍的人就是商品分配的对象。针对不同类型的任务分配,设计适用的拍卖机制。2.设计了任务分配中的第二低价拍卖机制。在基本的任务分配问题中,本文给出一种通用分配方法,并采取单边拍卖的机制去模型化任务分配问题。通过采取最低价胜出,但支付的是第二低价。本文证明了该机制的个体理性、预算平衡、真实性,并给出了计算效率。实验证明,这种机制能有效提高社会福利。3.设计了职位分配中的贪婪双边拍卖机制。职位分配是任务分配的一种特殊形式,本文将职位——任务的直接分配对象。视为特殊的资源,利用贪婪机制,快速得出职位的最佳分配,将之与时序双边拍卖机制做比较。证明了机制的个体理性、预算平衡和真实性,并给出了相应算法时间复杂度。4.提出一种时间约束的多任务协同规划机制。在这个机制中,任务的先后次序是给出的。拍卖人有着明确的输入集合和目标输出集合的,竞价人可以自由的进行任务、任务的执行方案的组合并提出竞价,而每个竞价都有着严格时间约束。使用混合多元组合拍卖机制来进行任务的组合,找出全部有效解。有效解既可以满足总的目标,也可以保证在任务执行过程中不会发生商品的短缺。在众多的有效解中,本文找出一个最佳的解,实现拍卖人收益的最大化和完成时间的最小化。