单机不相容双目标最优批排序研究

李小衬

（武汉生物工程学院计算机与信息工程系，湖北 武汉430415）

2个代理在同一台机器上加工，每个代理都有各自的目标，即顾客的任务不同，就会有不同的目标，总目标是尽可能使每个顾客满意。

平行分批不相容排序是指把任务分成几个子集，每个子集作为一批，不相容的任务不能放在同一批中加工，每批的完工时间就是这批中最后一个任务的完工时间，并且该批中每个任务的完工时间是相同的。常用“p－batch”表示平行分批处理机。

目前关于多目标多代理排序的文献不断涌现。文献［1］讨论的是为了实现顾客的目标要求，如何通过有效的方法找到相应的非支配序；文献［2］讨论的是2个客户类的双目标排序问题：第1类客户的目标函数是在假设其他客户的目标函数有界的情况下寻找最优排序；文献［3］讨论的是一个多代理排序问题，3个共同的目标函数是：极小化任务的完工时间、极小化最大延迟、极小化加权总完工时间，并且以最大延迟和加权总完工时间为目标函数的排序模型是NP－完全的。

1 有关符号

设有m个无关的工件X1，X2，…，Xm，并假设处理机的容量是无限的，设工件Xj的加工时间为pj（j＝1，2，…，m）。一个批序列记为σ＝（A1，A2，…，Ar），其中，Ak（k＝1，2，…，r）是一个工件集合。记批Ak的完工时间，易知，在一个序σ中，对每一个工件

用∑Cj表示所有工件的加工总完工时间，Cmax为所有工件的时间表长。用三参数法：

表示以F为目标函数的双代理单机无界平行分批不相容排序问题。其中，b≥m表示每批的容量是无限的，IG表示任务集的不相容，mul－cuts表示双代理。

2 Cmax和∑Cj的组合函数

在一台无界平行分批处理机上，要加工2个任务集C1和C2，其中任务集C1的目标函数为R1，任务集C2的目标函数为R2，这2个任务集是不相容的。用：

Y＝R1＋θR2（θ＞0，θ代表R1和R2这2个不同目标函数之间的权因子）代表这个模型总的目标函数。笔者研究的目标是极小化组合函数Y。

该模型可描述为：在一台无界平行分批处理机上，加工2类不相容的任务集，目标是极小化Cmax和∑Cj的组合函数：________

用三参数法表示为：

式中，F就是组合函数Y＝R1＋θR2（θ＞0），F关于分量R1和R2是正则的。下面设m1为C1中工件数，m2为C2中工件数，m1＋m2＝m。

3 批排序的最优化

下面给出在最优化Y的过程中要用到的几个性质。

性质1［4］模型（2）的所有批排序中，C1中的任务一定是放在同一批是最优的。

性质2［4］1｜p－batch b≥m｜∑Cj的最优批排序一定是按SPT－分批序排列。

性质3［4］1｜p－batch b≥m｜∑Cj的最优序为（A1，A2，…，Ar）的充要条件是：

下面利用DP算法（动态规划算法）找到1｜p－batch b≥m｜∑Cj中任务C2的最优批排序。假设C2中任务已按SPT标号，即p1≤p2≤…≤pm2。假设C2中包含最后m2－j＋1个任务Xj，Xj＋1，…，Xm2的SPT－分批序的最小总完工时间为Gj，并且第一批是从0时刻开始加工。求任务C2最优序的DP算法如下：

步骤1 在当前序的前面放入新的一批。不妨设在当前序｛Xk，…，Xm2｝的前面放入新的一批｛Xj，…，Xk－1｝（其中pk－1是｛Xj，…，Xk－1｝的加工时间），则∑Cj增加了pk－1（m2－j）。

步骤2 求出这个算法的递归方程。设Gm2＋1＝0为递归的初始条件，对j＝m2，m2－1，…，1，则递归方程为：

G1就是最后的最优值。

为了求得模型（2）的最优序σ＊，由性质1知，只须在任务集C2的批之间找到放批Atotal的最好位置即可。用r个大任务X1，X2，…，Xr代表C2中的r个批，其中P（Xi）＝P（Ai）；把Atotal当作任务X0，其中P（X0）＝P。在求∑Cj时，X0的权重为W0＝1，Xi的权重是Wi＝｜Ai｜（1≤i≤r）。则极化目标函数：

等价于极小化r＋1个任务X0，X1，X2，…，Xr的加权总完工时间：

式中，序σ＊中任务Xi的完工时间为C（Xi），X0的权为1，Xi的权转化为θ｜Ai｜（1≤i≤r）。

由性质3及 WSPT规则［5］有：如果就在C2的批Ak与Ak＋1之间安插批是模型（2）的最优序，并且：

其中，在最优批排序σ＝（A1，A2，…，Ar）中，批Ai的完工时间为C（Ai）。

4 计算复杂性分析

由上面的求解过程可以得到下面2个定理：

［1］Agnetis A，Mirchandani P B，Pacciarelli D，et al.Nondominated schedules for a job－shop with t wo competing users［J］.Computational ＆Mathematical Organization Theory，2000，6（2）：191－217.

［2］Agnetis A，Mirchandani P B，Pacciarelli D.Scheduling pr oblems wit h t wo co mpeting agents［J］.Oper Res，2004，52（2）：229－242.

［3］Lee C Y，Uzsoy R.Mini mizing makespan on a single batch processing machine wit h dynamic job arrivals［J］.Inter national Jour nal of Production Research，1999，37：219－236.

［4］Baker K R，Smit h J C.A multiple－criterion model f or machine scheduling［J］.Jour nal of scheduling，2003，6：7－16.

［5］Yaalzdani Sabouni M T，Jola i F.Opti mal methods for batch processing problem with makespan and maxi mum lateness objectives［J］.Applied Mathematical Modelling，2010，34：314－324.