慕 迪, 刘培海

(华东理工大学数学系,上海 200237)

带拒绝和到达时间的单机排序问题

慕 迪, 刘培海

(华东理工大学数学系,上海 200237)

研究了一个单机带拒绝的排序问题,目标函数是最小化接受工件的最大完工时间与所有被拒绝工件的拒绝费用之和。首先给出了此问题的混合整数规划模型,并得到了最优解的一些性质。最后给出了一个分支定界算法,并给出了数值模拟的结果。

排序; 单机; 拒绝; 分支定界

1 最优解的性质

性质1若工件ji和工件jj满足ri≤rj,pi/wi≤1,则

(1) 若在π*中接受工件jj,则工件ji也一定被接受;

(2) 若在π*中拒绝工件ji,则工件jj也一定被拒绝。

证明 (1)假设在最优排序π*中ji被拒绝,并且ji满足ri≤rj,pi/wi≤1,因为π*接受了工件jj,若在Cmax(π*)时刻开始加工ji,则目标函数值不会增加,这与π*的最优性矛盾,因此ji在π*中也一定被接受;

(2) 同理可证。

性质2若工件jj和工件ji满足:rj≥ri,pj≥pi,wj

(1)若在π*中接受工件jj,则工件ji一定也被接受;

(2)若在π*中拒绝工件ji,则工件jj一定也被拒绝。

(2) 同理可证。

性质3若一段序列{jh,jh+1,…,jh+k}(k>0)满足:∀ji∈{jh,jh+1,…,jh+k},pi/wi≤1,工件jh前和jh+k后分别都是一段空闲,且jh和jh+k之间无空闲,则在最优时间表π*中,{jh,jh+1,…,jh+k}总是同时被接受,或者同时被拒绝。

证明 若jk被接受,则∀ji∈{jh,jh+1,…,jh+k-1},有pi/wi≤1,且显然有ri≤rk,由性质1,ji一定被接受;同理,若工件jh被拒绝,则∀jj∈{jh+1,jh+2,…,jh+k}一定也被拒绝。

性质4在最优时间表π*中,设最后加工工件开始加工的时间为tmax,则∀t

(1) 机器在t时刻忙碌,即在加工某个工件;

(2) 任何满足rj≤t,pj/wj≤1的工件均已完工。

2 目标问题的上下界

2.1 整数规划模型

假设所有工件已经按照到达时间的先后顺序重新编号,即

r1≤r2≤…≤rn:

(1)

(2)

xj∈{0,1},j=1,…,n

(3)

其中,

Cmax为最大完工时间;W为所有被拒绝工件的拒绝费用和;M为一个足够大的数。