论文摘要
排序（SCheduling）就是在一定的约束条件下对工件和机器按时间进行分配和安排加工次序，使一个或多个目标达到最优．排序论作为运筹学的一个重要分支，目前受到国内外学者的广泛关注．本文主要对于等长工件平行批排序模型进行了研究，作了以下两方面的工作：（1）具有优先约束、到达时间、等长工件的单机平行批排序问题；（2）具有到达时间、加工时间相同，极小化加权总误工的单机平行批排序问题．一个批机器或批加工机器是指可同时将几个工件作为一批进行加工的机器，每一批的加工时间等于这批工件中最长的加工时间．一旦一批工件开始加工就不能被中断，其他工件也不能加入该批．本文中研究的问题可描述如下：假设有n个工件J1，J2，…Jn，一台在给定的时间内只能加工一批工件的机器．工件之间具有优先约束关系，每个工件Jj有加工时间pj和到达时间rj（其中pj，rj都为整数）．工件是成批被加工处理的，这里的一批是指工件的一个子集，这些批（子集）构成了工件集的一个划分．一个批的加工时间等于这批工件中最大的加工时间，即px=maX{pj∶Jj∈Bx}．如果工件Ji，Jj有优先约束Jj（?）Jj，则要求Jj一定要在Jj真完工后加工．这意味着Ji真和Jj不能在同一批中被加工．一批的完工时间定义为该批所有工件的完工时间，即Cx=sx+max{pj∶Jj∈Bx}．参照文献[1]，[2]，我们称这个排序模型为平行批排序问题，记为1|prec；p-batch；rj|f这里f是要优化的目标函数．主要结果如下：（1）具有优先约束、到达时间、等长工件的单机平行批排序问题。我们对于具有优先约束，k个不同到达时间，等长工件的最大延迟极小化单机平行批排序问题进行了研究．首先，对于有固定k个不同到达时间ri（1≤i≤k）的平行批排序模型，给出块的概念．进而证明在最优排序中所有块的构形是这样的时间序列(r（1），r（2），…，r（nb）)（1≤nb≤k），其中r（i）∈{r（1），r<sub>（2），…，r（k）}．其次，对于所有可能的构形进行枚举，并给出一个O（2kn log kn2）时间的算法求解Lmax最优值．最后对于问题1|prec；p-batch；pj=p；r(（i），i∈{1，2，…，k}|f，当f为和函数∑fj形式，即f∈{∑ωjCj，∑Cj，∑Uj，∑ωjUj，∑Tj，∑ωjTj}时，给出了一个O（2kn）时间算法．当k为一固定值时，这两个问题是多项式可解的．（2）具有到达时间，加工时间相同极小化加权总误工的单机平行批排序问题．Baptiste在[5]中给出了问题1|p-batch；b＜n；pj=p；rj|f，f∈{∑ωjUj，∑ωjCj，∑Tj}的一个O（n8）时间的动态规划算法，并指出对于目标函数∑ωjTj，平行批等长工件问题的计算复杂性仍是未解的。本文中，我们将讨论问题1|p-batch；b＜n；pj=p；rj|∑ωjTj，首先，我们假设ω1≥ω2≥…≥ωn，且d1≤d2≤…≤dn，即工件的权数与工期是反一致的．此时，通过适当的修正，∑ωjTj就为一个有序的目标函数，这使得我们的排序问题具有特定的优势性质．其次，建立动态规划参数及方程，给出一个O（b2n7）（b＜n）的时间动态规划算法求解最优值．