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

慕 迪, 刘培海

(华东理工大学数学系,上海 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为一个足够大的数。

目标函数为:

minZ=Cmax+W

同时式(1)保证任何接受工件jj的完工时间都不大于最大完工时间,即∀jj∈A,且Cj≤Cmax;约束式(2)即求出所有被拒绝工件的惩罚和;式(3)表示工件jj要么被拒绝,要么被加工。

为了更方便地求解此问题,构造n个子问题;在每个子问题(Pk)中,工件jk必须被接受(即xk=1),而jk之后的工件全部被拒绝。子问题(Pk)的数学模型可写为:

minZk=Cmax,k+Wk

其中Cmax,k、Wk分别表示子问题(Pk)的最大完工时间和所有拒绝工件的惩罚和。

显然,这n个子问题中一定存在某个问题(Pk)与原问题具有相同的最优解。从而对原问题的求解转换为求解这个这n个子问题。而对于每一个子问题(Pk),已经知道最后接受的工件,这方便了对问题的求解。

2.2 问题(P)的上下界

(4)

(5)

xj∈[0,1],j=1,…,k-1

(6)

Ak={j|rj≤rk,Pj≤wj};

Bk={j|rj≤rk,Pj>wj}.

(1) ∀i∈Ak,xi=1;

由式(4),假设在某个最优解中

由式(4)可得

(7)

(8)

所以必然有

不妨设j是使得式(9)成立的最大整数,即

(9)

其中1≤j≤i。

则由式(7),可以得到下面的式子:

从而必然存在某个y使得iy并且xy>0。那么保持式(9)成立的前提下增大xi至=xi+Δx,同时减小xy到=xy-Δxpi/py,这样可以得到松弛问题的一个新解且目标函数值不增加。

重复上述过程,总可以找到一个满足性质3的最优解。

例1：考虑一个4工件排序问题,求解这个问题的下界。首先将工件重新排序,工件的各项参数见表1。由于最后接受的工件一定满足pj/wj≤1(若最后加工的是pj/wj>1的工件,则拒绝这个工件得到一个新的时间表,新时间表的目标函数值一定比原时间表小),因此只要考虑k=1,3的情况。

表1 例1中各工件参数

设上述算法所得下界UB对应的排序为π1,显然这也是问题(P)的一个松弛解。

下面讨论问题(P)的上界。

对排序π1进行如下处理,得到问题(Pk)的一个可行排序π2:

步骤1 在排序π1中,

(1) 若(1-xi)pi≤wi,则在π2中令xi=1,即接受工件ji;

(2) 若(1-xi)pi>wi,则在π2中令xi=0,即拒绝工件ji;

步骤2 将所有满足xi=1的工件按照达到时间rj的顺序安排加工,拒绝其他工件,得到加工时间表π2。上述算法得到问题(P)的可行解,将这个解作为问题(P)的一个上界。

例2:同样是例1中的4工件问题,现在求解上界。由例1,xi=1,i=1,3;x2=1/2;x4=0;由于(1-xi)piw4;

则在π2中,令xi=1,i=1,2,3;x4=0;接受工件集合为A={j1,j2,j3},拒绝工件集合为R={j4},计算得到上界UB=Cmax+w4=8+2=10。

3 分支定界算法

需要先将所有工件按照到达时间rj从小到大重新排列,即r1≤r2≤…≤rn。在这里只要考虑拒绝还是接受pj/wj>1的工件,因为加工pj/wj≤1的工件不会使目标函数值增大。利用2.2节中的方法来计算各个节点处的上下界。在利用分支定界方法进行搜索时,定义下述变量:k表示当前加工工件集合中到达时间最大的工件;UB为问题(P)的一个上界;UBk表示r*=rk时的上界;LBk表示r*=rk时的下界;Sk:表示r*=rk时的目标函数值,其中S0表示初始解;Opt:最优排序的目标函数值。

分支定界算法的主要步骤如下所述:

步骤1 初始化:将Z0=UB作为问题的初始解和初始上界;

步骤2 分支:若LBkUBk,则更新上界UB=UBk;

步骤3 删除规则:若在某个节点有LBk>UB,则将这个节点删去;

步骤4 停止条件:若已经考虑了所有分支,则停止计算,此时得到局部最优解。

例3:为了更好地说明上述算法,考虑1个5工件的排序问题。每个工件的参数如表2所示。本文得到问题的初始上界S0=16。由于r*∈{rj|pj/wj≤1,j=1,…,5}={r1,r4,r5},因此考虑3种情况,得到的可行解分别为S1=14,S4=13,S5=10;

表2 例3中的各工件参数

因此,最优解为Opt=min{Z1,Z2,Z5}=min{14,13,10}=10;被接受工件集合为A={j1,j2,j4,j5},拒绝工件集合为R={j3}。以r*=r4为例,分支定界过程见图1。其中,Del表示Delete,即删除这个节点。

图1 分支定界过程 Fig.1 Procedure of branch-and-bound algorithm

4 数值模拟

首先利用Cplex软件对整数规划模型进行求解,并且用C++语言来编译分支定界算法,为以下参数的每种组合产生200个实例:

(1) 加工工件的个数为n∈{50,200,500,1 000};

(2) 工件的到达时间、加工时间和拒绝费用分别为[0,100×n×dc],[1,100]和[1,100×rc]上满足均匀分布的随机数,其中dc和rc为控制系数,n为工件个数;dc∈{0.2,0.5},rc∈{0.5,1,1.5}。用(dc,rc)的形式来表示每种参数的组合。

表3～表6分别示出了当dc∈{0.2,0.5},rc∈{0.5,1,1.5}时,整数规划(IP)的运行结果。可以看出,整数规划模型基本上能得出问题(P)的最优解,并且在1 000个工件内效率都比较高,但是运行时间平均比分支定界算法要长。

表3 n=50时整数规划运行结果

表4 n=200时整数规划运行结果

表5 n=500时整数规划运行结果

表6 n=1 000时整数规划运行结果

表7 分支定界算法运行结果

本文给出了带有拒绝工件的单机排序问题的整数规划模型和分支定界算法。数值模拟的结果说明在解决1 000个工件问题内,分支定界方法是非常有效的。在以后的工作中,如何把这个方法推广到多台机器上将会是非常值得研究的课题。

符号说明：

n——工件个数

J={j1,j2,…,jn}——工件集合

rj——工件jj的到达时间

pj——工件jj的加工时间

wj——工件jj的拒绝费用

Cj——工件jj的完工时间

R——拒绝工件集合

A——接受工件集合

Z(π)=Cmax(A)+W——时间表π的目标函数值

[1] BARTA Y,LEONARDI S,MARCHETTI-SPACCAMELA A,etal.Multi-processor scheduling with rejection[J].SIAM Journal on Discrete Mathematics,2000,13(1):64-78.

[2] SEIDEN S S.Preemptive multiprocessor scheduling with rejection[J].Theoretical Computer Science,2001,262(1):437-458.

[3] HOOGEVEEN H,SKUTELLA M,WOEGINGER G J.Preemptive scheduling with rejection[J].Mathematics Programming,2003,94(2-3):361-374.

[4] ENGELS D W,KARGER D,KOLLIOPOULOS S G,etal.Techniques for scheduling with rejection [J].Journal of Algorithms,2003,49(1):175-191.

[5] LU Lingfa,NG C T,ZHNG Liqi.Optimal algorithms for single-machine scheduling with rejection to minimize the makespan[J].International Journal of Production Economics,2011,130(2):153-158.

[6] ZHANG Liqi,LU Lingfa,YUAN Jinjiang.Single machine scheduling with release dates and rejection[J].European Journal of Operational Research,2009,198(3):975-978.

SingleMachineSchedulingwithJobRejectionandReleaseDates

MUDi,LIUPei-hai

(DepartmentofMathematics,EastChinaUniversityofScienceandTechology,Shanghai200237,China)

This paper considers the single machine scheduling problem with job rejection.The objective function is to minimize the sum of the maximum completion time of the job and the rejection lost of all rejected jobs.Firstly,the paper introduces a mixed integer programming model and some properties of the optimal solution.Finally,a branch-and-bound algorithm and a numerical simulation are presented.

scheduling; single machine; rejection; branch-and-bound

1006-3080(2017)06-0890-05

10.14135/j.cnki.1006-3080.2017.06.021

2016-06-23

慕 迪(1992-),女,安徽人,硕士生,研究方向为组合最优化。

刘培海,E-mail:pliu@ecust.edu.cn

O0221.7

A