分批排序问题是排序论的一个重要分支,它是一类具有很强应用背景的最优化问题,其研究结果被广泛应用于大规模的现代化生产的各个领域,如半导体生产、钢铁铸造、制鞋业等。因此,分批排序问题各种模型的算法和机制设计研究具有重要的理论和实际意义。分批排序的算法研究主要有两部分内容,一是寻求整体最优的算法设计,二是考虑具有多个理性局中人的排序博弈的机制设计。　　本论文所涉及的模型和问题如下：　　(一)对具有中控系统的并行分批排序问题设计最好可能的近似算法：本文所研究的在线并行分批排序问题可以描述为：有n个相互独立的工件J={J1,...,Jn}要在m台批处理机M={M1,...,Mm}上加工；工件Jj(1≤j≤n)的到达时间记为rj,加工时间记为pj；批处理机每次可同时加工至多B(机器的批容量)个工件；加工时间不同的工件可作为一批来加工,同一批中工件同时开工、同时完工。在线是指工件的信息是随着排序过程逐个释放的,即其到达时间只有它到达时系统才能获取。工件加工过程不允许中断,不允许从已确定的批中移走或加入新工件。研究任务是设计一个工件的加工方式,包括每个工件分配在哪个机器上加工、分配同一台机器上的工件如何进行分批和排序等,使得给定的某个整体目标达到最优。　　(二)对无中控系统、工件具有自主选择权的并行分批排序博弈问题设计“好”的协调机制：本文研究的排序博弈问题可以描述为：协调机制是由每台机器所确定的加工排序规则所构成的集合；每个工件对应一个局中人,局中人为工件选择一台机器进行加工,局中人的策略集是具有各自排序规则的机器集合,每个局中人都是“理性”的,即希望根据系统给定的协调机制来选择机器而到达自身目标的最优。整个排序系统有整体的优化目标。对于给定的的协调机制,理性的工件局中人会选择达到一个相应的纳什均衡,从而确定了这种协调机制下相应的整体成本或收益。因此协调机制的设计目标是,确定一个“好”的协调机制使得理性局中人所达到的纳什均衡也能够尽可能保证整体成本或收益的最优。　　本论文主要研究两类并行分批排序问题的算法和协调机制设计。主要研究内容有：首先,研究具有m台批容量有界的并行分批处理机、各工件加工时间相等、其全局目标函数为最小化最大完工时间的具有中控系统的在线排序问题。设计了两个竞争比均为1+α的在线算法-Unified算法和Greedy算法Aα,并证明了这一竞争比达到了最好可能。其次,研究具有m台批容量有界的并行分批处理机、各工件加工时间相等、其全局目标函数为最小化最大完工时间的无中控系统、工件具有自主选择权的半在线并行分批排序博弈问题。该模型中要求工件总数n的上界N已知,工件Jj(1≤j≤n)的到达时间rj是有理数且min{|ri-rj|:ri≠rj,1≤i,j≤n}已知。设计了该模型的一个协调机制：延迟机制,通过设计一个算法构造出了该机制的一个纳什均衡,证明了该机制下纳什均衡的唯一性；进而给出了该机制的无秩序代价PoA值(纳什均衡下的整体目标值与最优整体目标值之间的比较),从理论上证明了该协调机制的有效性。