带服务器的具有固定序列的平行专用机排序

2022-08-23王超杰陈光亭

杭州电子科技大学学报(自然科学版) 2022年4期

王超杰，陈光亭，陈永，张安

(1.杭州电子科技大学理学院，浙江杭州 310018；2.台州学院电子与信息工程学院，浙江台州 318000)

0 引言

1 问题描述

带服务器的具有固定序列的平行专用机排序问题的定义如下：给定1台服务器，m台平行专用机{M1,M2,…,Mm}和m个不相交的工件集Jk={Jk,1,Jk,2,…,Jk,nk}。其中机器Mk(1≤k≤m)需按照Jk,1,Jk,2,…,Jk,nk的顺序加工工件集Jk。每个工件Jk,j(1≤j≤nk,1≤k≤m)由加载时间Sk,j和加工时间Pk,j组成，其中nk表示第k台机器的工件数，每个工件的加载时间均为1，即Sk,j=1，Pk,j为整数。服务器只对工件进行加载操作，且一次只能对1个工件进行加载。每个工件必须先在服务器加载完毕才能开始加工。对于任意一个可行排序，Ck,nk表示机器Mk上最后1个工件的完成时间，Cmax表示工件的最大完工时间，则Cmax=max{C1,n1,C2,n2,…,Cm,nm}。目标是寻找一个可行排序，使得工件最大完工时间尽可能小，即minCmax。

根据文献[7]的三参数表示法,带服务器的具有固定序列的平行专用机排序问题可表示为PD,S1|fixed-seq,sj=1|Cmax，其中PD表示平行专用机，S1表示一台服务器，fixed-seq表示每台平行专用机加工工件的顺序是固定的，sj=1表示每个工件的加载时间均为1。PD,S1|fixed-seq,sj=1|Cmax是强NP-难的。

2 算法设计与分析

对于问题PD,S1|fixed-seq,sj=1|Cmax，文献[7]提出了MLT算法和MRW算法，其中MRW算法是本文设计改进算法的基础，其基本步骤如下。

(1)对于每台机器Mk，计算当前时刻工件集Jk中未被服务器加载的所有工件的处理时间(包括剩余工件的加载时间和加工时间)，即剩余时间。

(2)服务器完成当前工件上的加载操作后，选择当前时刻最大剩余时间工件集Jk中可被选择的工件进行加载操作；按此规则，直至服务器完成所有工件的加载。

(3)每个工件加载完成后，立刻在机器上加工。

对于PD,S1|fixed-seq,sj=1|Cmax问题的算法设计，一方面要考虑每台机器上工件加工时间总和，另一方面还要兼顾服务器不能有非必要的空闲，从而保证服务器连续工作。为此，本文针对MRW算法进行改进，提出一种平行专用机总加工时间递减的算法(Maximum the Sum of Processing-Time，MSPT)，基本步骤如下。

(2)服务器在选择工件进行加载的优先级为J1>J2>…>Jm。零时刻，工件J1,1在服务器上加载。每个工件加载完毕后，服务器从当前剩余的工件序列中，挑选出允许加载的工件集，选择该工件集中优先级最高的工件加载。按此规则，直至服务器完成所有工件的加载。

(3)每个工件加载完成后，立即在机器上加工。

为了便于理解本文提出的MSPT算法，通过一个具体用例来阐述。

m=3时，每个工件的加载时间为Sk,j=1,每个工件的加工时间Pk,j如下：

M1∶P1,1=1;P1,2=1;P1,3=2
M2∶P2,1=1;P2,2=0;P2,3=1
M3∶P3,1=2;P3,2=0;P3,3=1

根据MSPT算法，将服务器加工的工件顺序进行排列并求出MSPT算法所得排序的目标值。

(1)令T1,T2,T3表示对应工件集的加工时间Pk,j之和，

T1=P1,1+P1,2+P1,3=1+1+2=4
T2=P2,1+P2,2+P2,3=1+0+1=2
T3=P3,1+P3,2+P3,3=2+0+1=3

(2)根据平行专用机总加工时间递减的原则，服务器在选择工件进行加载的优先级为J1>J3>J2。零时刻，服务器加载工件J1,1。1时刻，服务器允许加载的工件集为{J2,1,J3,1}，服务器选取J3,1加载；2时刻，服务器允许加载的工件集为{J1,2,J2,1}，服务器选取J1,2加载；重复以上步骤，直至所有工件加载完毕。

(3)每个工件加载完成后，立即在机器上加工。

MSPT算法执行完毕所得的排序，如图1所示。