带单服务器的流水作业排序问题的复杂性

时凌， 张琼， 龙彩燕

(广州工商学院 通识教育学院, 广东 广州 510850)

假设Ci,j为工件Jj在机器Mi上的完工时间.若在机器M1和机器M2上不存在空闲时间,则有:

C1,1=s1,1+p1,1,C2,1=s1,1+p1,1+s2,1+p2,1,

C1,j=C1,j -1+s1,j+p1,j,C2,j=max{C2,j -1,C1,j}+s2,j+p2,j, 其中j=2,…,n.

为了证明定理1,构造由下面7n个工件组成的工件组：

1)P-工件:s1,i=b,p1,i=b;s2,i=b+xi,p2,i=b(i=1,2,…,n).

2)Q-工件:s1,i=0,p1,i=b;s2,i=b+yi,p2,i=b(i=1,2,…,n).

3)R-工件:s1,i=0,p1,i=b;s2,i=b-zi,p2,i=b(i=1,2,…,n).

4)U-工件:s1,i=0,p1,i=b;s2,i=0,p2,i=b(i=1,2,…,n).

5)V-工件:s1,i=0,p1,i=b;s2,i=0,p2,i=b(i=1,2,…,n).

6)W-工件:s1,i=0,p1,i=b;s2,i=0,p2,i=b(i=1,2,…,n).

7)L-工件:s1,i=4b,p1,i=b;s2,i=b,p2,i=b(i=1,2,…,n).

假设数字匹配问题有解,机器在加工过程中无空闲时间，其中机器M1按工序σ(σ={σP1,1,σQ1,1,σR1,1,σU1,1,σV1,1,σW1,1,σL1,1,…,σP1,n,σQ1,n,σR1,n,σU1,n,σV1,n,σW1,n,σL1,n})加工工件，机器M2按工序τ(τ={τP2,1,τQ2,1,τR2,1,τU2,1,τV2,1,τW2,1,τL2,1,…,τP2,n,τQ2,n,τR2,n,τU2,n,τV2,n,τW2,n,τL2,n})加工工件，如图1所示.

图排序问题的甘特图

C(S)≥3b+x1+5b+x1+y1+7b+x1+y1-z1+8b+9b+10b+…+

(3+(n-1)11)b+x++(5+(n-1)11)b+xn+yn+(7+(n-1)11)b+…+

且使得C(S)=y.

由以上可知：如果加工顺序S存在这样的分解μ， 则完工时间等于y的加工顺序(如图1所示)；
如果加工顺序S不存在这样的分解μ， 即加工顺序S不是数字匹配问题的解,则xi+yi≠zi(i=1,2,…,n).令ξi=xi+yi-zi(i=1,2,…,n), 则ξi>0或者ξi<0 (对于ξi<0同理讨论).由上述可得：

该式与C(S)=y矛盾，证毕.

证明对于加工顺序S, 记Ii,j(S) (i=1,2;j=1,…,n)为工件Jj在机器Mi上的总空闲时间.如果在机器M1上的加工路径为1,…,j, 在机器M2上加工的工件为Jj, 则有:

(1)

如果在机器M1上的加工工件为J1, 在机器M2上的加工顺序为1,2,…,j, 则有:

(2)

如果在机器M1上的加工顺序为1,…,l, 在机器M2上的加工顺序为l,…,j, 则有:

(3)

由式(1)—式(3)有:

为了证明上界的紧性,本文构造了如下2种工件：

1)P-工件:s1,i=2b,p1,i=b,s2,i=2b,p2,i=b(i=1,2);

2)Q-工件:s1,i=0,p1,i=b,s2,i=0,p2,i=b(i=3,4).

图2 忙加工顺序S0的总完工时间 图3 最优加工顺序S*的总完工时间

猜你喜欢空闲排序工序120t转炉降低工序能耗生产实践昆钢科技(2022年2期)2022-07-08排序不等式中学生数理化·七年级数学人教版(2022年11期)2022-02-14大理石大板生产修补工序详解(二)石材(2020年4期)2020-05-25恐怖排序科普童话·学霸日记(2020年1期)2020-05-08“鸟”字谜小读者之友(2019年9期)2019-09-10土建工程中关键工序的技术质量控制建材发展导向(2019年10期)2019-08-24节日排序小天使·一年级语数英综合(2019年2期)2019-01-10西湾村采风东坡赤壁诗词(2018年6期)2018-12-22彪悍的“宠”生，不需要解释意林·少年版(2018年1期)2018-02-07WLAN和LTE交通规则CHIP新电脑(2016年3期)2016-03-10