分批排序源于诸如半导体制造业、金属冶炼工业、航空工业、制鞋业等大规模的生产流水作业线和工业生产中.作为经典排序的推广,分批排序具有很强的应用背景和现实意义.根据批加工方式的不同,分批排序模型又可以分为平行分批和继列分批两大类.在平行分批模型中,机器在任何时刻可以在同一批内同时加工多个工件,每一批的加工时间就等于该批中所有工件的加工时间最长者.而在继列分批模型中,工件是按照一个接一个串联的方式形成一批加工的,每一批的加工时间就等于该批中所有工件的加工时间之和.对于分批排序问题来说,管理者关注的重点是如何将给定的工件(订单、任务)划分成批以及如何安排这些批的加工生产,即决策者要首先确定如何将给定的工件划分成相应的批,然后确定这些批在机器上的开工时间及先后加工顺序.　　 在加工生产以及成品运输的过程中,工件常常由于其物理特征、化学特性、加工要求等的差异性而事先被划分成不同的工件组(族、类),这些不同工件组中的工件往往需要不同的操作方法和运作方式.在本学位论文中,我们主要研究含有多个工件组(或者说工件具有不相容性质)的机器排序模型.依据所考虑问题的不同,工件的不相容性在文中往往呈现不同的形式:(1)在分批排序中,我们要求不同工件组中的工件不能放在一个加工批中进行加工,也不能放在一个运输批中进行运送;(2)在成组技术(GT)加工限制下,我们要求同一工件组中的工件必须在机器上连续加工;(3)在工件允许拒绝的排序中,基于机器负载的限制以及资源的有限性,部分工件需要外包给其它的生产商进行加工,从而使得那些外包的工件和被加工的工件也形成两个不同的工件组;(4)在具有多个代理的排序中,每个代理中的工件就形成一个单独的工件组,同时每个代理具有各自需要优化的目标函数.　　 第二章研究具有不相容工件组的加工生产和车辆运输的两阶段排序问题.我们假定不同工件组中的工件不能放入同一批中进行加工,也不能放入同一个运输批中被车辆运送.目标是寻求一个加工和运输方案使得车辆运输完所有在机器上加工完成的工件到各自的顾客并最终返回到机器的时问达到最小.在成组加工技术限制下,我们给出了一个运行时间为O(nlogn)的最优算法.在没有成组加工技术限制时,我们首先证明了该问题是NP-困难的,然后给出了一个最坏执行比为3/2的启发式算法.同时,我们对工件组的个数为常数的情形给出了一个最优的多项式时间算法.　　 第三章研究含有多重工件组的平行批生产和车辆运输的两阶段排序问题.所有工件首先在一台批容量无界的平行批机器上加工处理,然后加工完成的工件被一辆容量有限制的汽车运输到各自的终点.我们假定不同工件组中的工件不能放入同一批中进行加工处理,也不能放入同一个运输批中被车辆运送.目标是寻求一个加工和运输方案使得车辆运输完所有在机器上加工完成的工件到各自的顾客并最终返回到机器的时间达到最小.当工件组个数F为1时,Lu和Yuan[101]给出了一个运行时间为O(n2)的最优算法.当工件组个数F为任意时,我们首先证明了该问题是NP-困难的,然后我们利用Lu和Yuan解决单工件组的最优算法,构造了一个最坏执行比为3/2的启发式算法.当工件组个数F为常数时,我们给出了一个拟多项式时间算法和一个运行时间为O(nF+3/ε)的全多项式时间近似方案.　　 第四章研究在成组加工技术限制下交货期可分配的单机排序问题.我们要求同一工件组中的工件必须连续加工,即在加工过程中不同工件组之间的工件不允许交织.交货期分配策略是由下面的三种分配策略之一决定:FML-CON,FML-SLK以及DIF.在这里,FML-CON意味着同一工件组中的工件可分配一个公共交货期;FML-SLK意味着同一组中的工件可分配一个相同的松弛日期;DIF意味着每个工件可分配一个独立的交货期.目标为寻求一个最优的工期分配策略和一个工件排序使得包含提前、延误、工期分配以及时间流费用的总和达到最小.我们构造了一个对这三种交货期分配策略都适用的统一优化算法,其时间复杂性为O(nlogn).　　 基于每个工件具有各自的到达时间并且工件的加工时间是其开工时间的简单线性增长函数的假设,第五章研究目标为最小化时间表长的单机平行批排序问题.当批容量无界时,我们给出了一个O(nlogn)一时间的动态规划算法.当批容量有界时,我们首先证明了即使只含有两个不同到达时间的排序问题也是NP-困难的,然后对工件加工顺序预先确定和不同退化率的个数为常数的两种特殊情形分别给出了多项式时间算法,最后对不同到达时间的个数为常数的情形给出了一个全多项式时间近似方案.　　 基于工件的加工时间是其开工时间的(简单)线性增长函数的假设,第六章研究几个允许拒绝部分工件的平行机排序问题.目标是寻求一个最优解使得接受工件的排序费用以及拒绝工件的总惩罚费用之和达到最小.当工件加工时间是其开工时间的线性增长函数并且排序费用为时间表长时,我们给出了一个全多项式时间近似方案.当工件加工时间是其开工时间的简单线性增长函数并且排序费用为总加权完工时间之和时,我们也给出了一个全多项式时间近似方案.当工件加工时间是其开工时间的线性增长函数(所有工件具有相同的退化率)并且排序费用为总完工时间之和时,我们设计了一个运行时间为O(n2)的最优动态规划算法.　　 第七章研究平行批处理机上关于两个代理的限制最优化排序问题.所考虑的问题分为两大类:在不相容的情形下,我们假定不同代理中的工件不能放在同一批中加工;在相容的情形下,我们假定两个代理中的工件都可以放在同一个批中加工.当要求第二个代理中所有工件的最大完工费用或者总误工工件个数不超过某个门槛值的限制,而使得第一个代理的目标为最小化所有工件的最大完工费用或者总误工工件个数时,我们分别给出了最优的多项式时间算法.当要求第二个代理中所有工件的最大完工费用或者总完工费用之和不超过某个门槛值的限制,而使得第一个代理的目标为最小化所有工件的最大完工费用或者总完工费用之和时,我们分别给出了拟多项式时间算法.当要求第二个代理中所有工件的时间表长或者总完工时间之和不超过某个门槛值的限制,而使得第一个代理的目标为最小化所有工件的总加权完工时间之和时,我们证明了这些问题都是一般NP-困难的.　　 第八章研究继列批处理机上关于两个代理的限制最优化排序问题.限制第二个代理中所有工件的最大完工费用不超过某个门槛值,对第一个代理的目标为最小化所有工件的最大完工费用、总完工时间之和或者总误工工件个数的情形,我们分别给出了最优的多项式时间算法.限制第二个代理中所有工件的总完工时间之和或者总误工工件个数不超过某个门槛值,对第一个代理的目标为最小化所有工件的总完工时间之和的情形,我们证明了这些问题都是一般NP-困难的,并分别给出了拟多项式时间算法.当两个代理的目标都为最小化总加权误工工件个数时,我们对该问题给出了一个拟多项式时间算法.该算法也表明不加权的排序问题是多项式可解的.