提前/拖延调度问题最优解的结构.pdf_大学文库

D0I:10.13374/j.issn1001-053x.2000.03.026 第22卷第3期北京科技大学学报 Vol,22 No.3 2000年6月 Journal of University of Science and Technology Beijing June 2000 提前/拖延调度问题最优解的结构谢铁军”程涛)刘任平) 1)H北京科技大学应用科学学院，北京1000832)北京航空航天大学动力工程系，北京1000833)清华大学计算机系，北京100084 摘要讨论了带有4项惩罚指标的提前/拖延调度问题，目的是确定最优公共交货期和确定最优排序.给出了最优公共交货期的确定方法，提出了联合惩罚因子的概念，并讨论了最优解的结构，关键词提前/拖延调度；完工时间：交货期：惩罚因子分类号TB114.1 调度问题是生产实际中的一个非常重要的工顺序，我们的目的是确定最优公共交货期d和研究课题，提前/拖延(Earliness/Tardiness)调度最优加工顺序π，使目标函数最小，是其中重要的一类，随着just-in-time(JIT)生产思 2最优公共交货期想在生产中的广泛应用，提前/拖延调度问题的研究越来越受到重视，成为研究的热点之一). 在上述模型中，每个工件J《i=1,2,…n)都有所谓提前/拖延调度就是要确定工件在机器上自己的交货期d,把这些交货期统一成一个交的最优加工顺序，使工件尽可能按交货期交货，货期d,便得到公共交货期，即d=d(i=1,2,… 工件提前或拖延都会使费用增加，要受到惩罚， ).下面将讨论公共交货期的性质，进而得到最目前，对ET调度问题的研究仍然是把对优公共交货期d. 提前和拖延的惩罚作为主要指标，)，这种指标定理1若≥B,则对任一加工顺序π最优公规定，工件的完工时间早于或晚于交货期都将共交货期d=0. 受到惩罚，但是，在某些实际生产中，由于多种证明设公共交货期为d,则止d以=1,2，…，因素的影响，不仅要考虑对提前和拖延这两项 n),设dCw,此时，所有工件拖延期指标的惩罚，还要考虑对交货期和工件完工时 T0=Cm-d0,提前期Ew=0,(i=1,2,…,m). 间的限制).鉴于此，在本文讨论的问题中，把惩目标函数F(π，d=[BaCw-d+ad+nCl. 罚指标扩展为4项：提前期、拖延期、交货期和工件的完工时间. 把d向右移动，移至d',分2种情况讨论. (I)d<d”<C移动后目标函数为： 1问题描述及目标函数的确定形式 F(π，d')EItCw-d'Hhod'+nCnl. 设n个工件，，…，Jn在一台机器上加移动后目标函数的改变量为：工，每个工件J的加工时间为P,完工时间为C, △F,-F(π，d')-F(π，d0=[B(d-d't 交货期为d,公共交货期为d.每个工件提前期为E,=max(0,d-C),拖延期T=max(0,C-d).a 高ald'-d2-pd"-≥0，为提前期E的惩罚因子，B为拖延期T:的惩罚说明移动后目标函数值增加，因子，Y,为交货期d的惩罚因子，8，为完工时间 (2)d<Cw≤d',设C≤d'<Cw+,Cw为某个 C的惩罚因子，a,B,,8都大于零. 工件完工时刻，(1≤h<),此时，目标函数确定为如下形式： F(xd')=au(d'-Cu)+Bu(Cu-d')+ Fπ，d=2(auEu-BuTin+Yo+nCm. 高测d+2a.Cm 其中，π={小，[2]，，[}为n个工件的一个加移动后目标函数改变量： 199910-21收稿谢铁军男，37岁，讲师，顾士 △F,=F(π，d')-F(π，dD=ad'-Ca)

第卷第期侧】年月北京科技大学学报介】哪口、提前拖延调度问题最优解的结构谢铁军 ” 程涛 ” 刘任平 ” 北京科技大学应用科学学院，北京北京航空航天大学动力工程系，北京清华大学计算机系，北京摘要讨论了带有项惩罚指标的提前拖延调度问题，目的是确定最优公共交货期和确定最优排序给出了最优公共交货期的确定方法，提出了联合惩罚因子的概念，并讨论了最优解的结构关键词提前拖延调度完工时间交货期惩罚因子分类号调度问题是生产实际中的一个非常重要的研究课题，提前拖延门厄调度是其中重要的一类随着一一而生产思想在生产中的广泛应用，提前拖延调度问题的研究越来越受到重视，成为研究的热点之一〔所谓提前拖延调度就是要确定工件在机器上的最优加工顺序，使工件尽可能按交货期交货工件提前或拖延都会使费用增加，要受到惩罚目前，对汀调度问题的研究仍然是把对提前和拖延的惩罚作为主要指标〔，，，，这种指标规定，工件的完工时间早于或晚于交货期都将受到惩罚但是，在某些实际生产中，由于多种因素的影响，不仅要考虑对提前和拖延这两项指标的惩罚，还要考虑对交货期和工件完工时间的限制口，鉴于此，在本文讨论的问题中，把惩罚指标扩展为项提前期、拖延期、交货期和工件的完工时间问题描述及目标函数的确定形式工顺序，我们的目的是确定最优公共交货期 ’和最优加工顺序矿，使目标函数最小最优公共交货期在上述模型中，每个工件双，， … 都有自己的交货期端，把这些交货期统一成一个交货期，便得到公共交货期，即试卜，， … 下面将讨论公共交货期的性质，进而得到最优公共交货期 ’ 定理若艺” 艺尽，则对任一加工顺序二最优公共交货期 ‘ 证明设公共交货期为，则击以件，，… ，，设」，此时，所有工件拖延期几。一户，提前期。，户，， … ，目标函数凡的二艺肠一试叶叭，今把向右移动，移至，分种情况讨论 ’ ，移动后目标函数为设个工件汤，人，一，去在一台机器上加工，每个工件诱的加工时间为只，完工时间为，交货期为试，公共交货期为每个工件提前期为三，一，拖延期不，一动为提前期云的惩罚因子，尽为拖延期不的惩罚因子币为交货期试的惩罚因子，叹为完工时间的惩罚因子，，声，笋，叹都大于零目标函数确定为如下形式爪卜艺呱，一勺袱 ‘ ，，移动后目标函数的改变量为 △只二，留一兀，刃【艺八成一 ‘ 燕词’ 一介【勤一蓦越一刃说明移动后目标函数值增加〕毛，设。〕蕊留晰，为某个工件完工时刻，蕊，此时，几 ‘ 艺闭，一公艺一留兀刃艺碑切饥诚。，。十。其中，二【，〔， … ，【为个工件的一个加臾珍】仆收稿谢铁军男，岁，讲师，硕士移动后目标函数改变量 △凡兀，一兀，的艺为，一一 DOI ：10．13374／j ．issn1001－053x．2000．03．026

VoL22 No.3 谢铁军等：提前/拖延调度问题最优解的结构 ·285 pCa-d三Bd-dr+含d-功 F元d=2a(d”-Ca)+00+空B(Ca- 注意到， d"y+ihwd"+Σ8Cw. d'-Cm≥0,0≤C0-dkd'-d(i=1,2,…,h). 移动后，目标函数增量：故得到： k1 Eax(d-Cu)z0.EBd(Ca-d)=Bdd-d). AF;=F(z,d")-F(,d)=San(d"- 因此， d)-on(d-Cu)+Br(d-d")+ AF;z-B(d'-d)+B(d-d)+Ead'-d)- 三w(d"-d0. [ξr-2p]d-a0--d-020. 设d-d"=d-Cw=6, 因此，d向右移动后，目标函数值增加.同理可则△F=-eEMt2a-三m=-eG(). 证，d向左移动后，目标函数值会减少.因此，当G(s)+0(s=0,1,2,…,n)时，由于e>0,>0, 最优公共交货期d*=0,证毕. 故△F,和△F?中必有且只有一个小于零，当在以下的讨论中，均假设含0. 定理3对于某一加工顺序π，当G(s)+0 容易验证：Gs)严格递增，即G(s+1)>Gs). (s=0,1,2,,n)时，必存在某一个工件J使最优事实上，G)-G+10=2a-三Al-2a- 公共交货期d◆在C闲处到达，其中k满足含-anB0 G(k-1)0:当存在一点k,使G(k)=0 因此，至多存在一点m,使G(m)=0. 时最优公共交货期取区间[C,C]中任意值. 定理2对任意一加工顺序π，当G(s)+0, 证明当G(s)≠0s=0,1,2,,n)时，设最优公 (s=0,1,2,…,n)时，最优公共交货期等于某个工件共交货期*在C处到达，C为某个工件的完的完工时刻，即d=C;当G(k)=0时，最优公共工时刻，则目标函数为：交货期取区间[C,C]中任意值. F(rd)-au(d-Cu)0++B(C- 证明设CxdBn(Cn- +2 d向右移动，移至C+处，即d'=C,此时， d')+2ad+20Ch. 目标函数：目标函数增量： Fzd)-au(d-C)+0+0+po(Ca-d)+ △R=F(a,d')-F元，d0=2a(d"-0+ 含%d+空a.cn. am(d'-Cu)-Bu (Cu-d)+ d移动后，目标函数增量：含d-dr+(d-. △F,=F(x,d')-F(x,d0=a4(d'-d0- 注意到： Ba(Cu-d')+Bn(d-d')+Ey(d'-d). d'-d=Cwj-d=d'-Cu=Cu)-Cu=Pun. + 设d'-d=Cn-d=6, 所以，△F=Pum[+aa-三Bn]=PnGw. 则△R=e宫ut8a-京pAl=eGh. 再把d向左移动，移至Cw-处，即d”=C-1,此再把d向左移动，移至C四处，即d”=C,此时目标函数：时，目标函数： F(.d)-Ean(d"-Cg)+O+O+B(Cu-d)+ 2 t

谢铁军等提前拖延调度问题最优解的结构艺戏成。一的儿 ‘ 艺 ’ 一刃凡 ‘今艺。 ‘】，，一么，〕小艺几〕〕一卜户注意到，一七， ‘ 月一水口 ‘ 一，，… ，故得到，’ 艺叭月即艺叹月拌俘儿艺〕 ’ 一之，艺戏，一 ‘ 一司‘ 艺戏成一 ‘ 因此，月 △凡之一艺两〕 ‘ 一的几一 ‘ 扮，户卜嗯灿一酬 ’ 一的一〔勤篮、，一刃 ‘ 因此，向右移动后，目标函数值增加一的之同理可移动后，目标函数增量 △凡兀，才，一兀，动艺 ‘ 即一的一一。艺几〕一 ’ ，户卜至丢” 。 ” 一的设一 ” 一负，，曰泪艺︺代尸口花、卜产艺间证，向左移动后，目标函数值会减少因此，最优公共交货期尹，证毕在以下的讨论中，均假设艺” 艺尽为了讨论方便，设函数以艺艺一艺凡，，，，… ，产勺规定试卜三一酬，试一三蓦嘶，显然，以卜，以容易验证以‘ 严格递增，即以事实上，以‘ 一以〔艺〔，一艺几一咚一卜，时卜艺刀。〕一〔，，〕一儿〕产时因此，至多存在一点，使定理对任意一加工顺序二，当羊，，，，… ，时，最优公共交货期等于某个工件的完工时刻，即了。当时，最优公共交货期取区间【、，口〕』中任意值证明设、，、为某个工件的完工时刻，，，… ，，此时，目标函数为月 ” 则 △凡一城丢三操和〕一价当以羊，，，… ，时，由于局，几习，故 △只和 △凡中必有且只有一个小于零，当 △名时，移至处可使目标函数值减少当△凡时，移至口。处可使目标函数值减少，因此，最优公共交货期必在某个工件完工时刻达到当以幻时， △只巴 △凡二刁移至。处或移至处，目标函数值不改变，因此，最优公共交货期取区间【，口卜〕」中任意值定理对于某一加工顺序二，当羊，，，… ，时，必存在某一个工件。使最优公共交货期在处到达，其中满足一，当存在一点，使时最优公共交货期取区间【、，〕」中任意值证明当羊，，，，二，时，设最优公共交货期尹在处到达，为某个工件的完工时刻，则目标函数为爪刃艺。一，艺刀、。一的艺〕决艺。口小户卜联爪介蓦一 ’嚎八一的向右移动，移至处，即留，此时目标函数为艺热。毋艺门户户】向右移动，移至处，即 ‘ 二口，此时，目标函数爪兀卜、一门艺几〕一今十艺，氏小凡介蓦匈 “ ‘ 一 ’均嚎尸明了艺知’ 艺门目标函数增量 △凡二， ‘ 一二，刃艺，〕 ‘ 一的俘户。。 ‘ 一〕一刀一的移动后，目标函数增量 △名兀，一兀，的刀一 ‘ 艺叭月 ‘ 一的艺 ‘ ，一动一儿〕 ‘ “一 “ ’ 嗜户一 “ ‘ 十酗 “ “ ’ 一办设沪一卜〕一。，，注意到，一，厂一。一〕一。二则 △只〔艺〔艺〔，〕一艺几」。，户卜再把向左移动，时，目标函数少叫卜移至划处，即’ ‘ ，此月介所以，△兀一，艺，【。艺〔，一艺几】」淤，〔。 · 户卜产卜再把向左移动，移至卜】处，即’ 任一，此时目标函数兀 ‘今艺。】 ’ ‘一十风】一留，卜户止

·286● 北京科技大学学报 2000年第3期 2xd"n+26,C. 3.1E。中工件的最优排序移动后，目标函数增量：引理1对于部分工件集E={J,aJ}, -2 互换某两个相邻工件JM,J!的位置，其余工件 △F=F(π，d")-F(π，d)=Σau(d"-d)- 不变，则目标函数的改变量为： ad-C)+Bx(Cx-d")+ △F=(-aa)P1-(n-arn)P 三(d-d)+(d"-d. 证明E。中工件按原加工顺序J,Ja, 由于d-d"=d-Ck-y=Ck-d”=Cy-C-:=Px,所 J,J4,…,J加工时，每个工件提前期以，△B=-Px+2a-B,-PuG(k-I). Eu=d-cn=1,2,,k),拖延期Tn=0. l 由于d是最优公共交货期，因此，△F=P1 此时目标函数F(π，d)=Σ(amEa+hd*+OnCw)+ Gk)20,△F=-PGk-1)20,即k应满足 (BuT+d+0uC). G(k)≥0，G(k-1)≤0，当G(s)+0s=0,1,2,…,m) 三t+ 互换工件J,#,的位置，其余工件不变，得时，有且只有一点k,使G(k-1)0.此新加工顺序π'=，“JM,…,在此顺时，最优公共交货期在C￡处达到.当G(k)=0时，序π'之下，目标函数为： G(k-1)<0,最优公共交货期取区间[C,C]中任意值. Fx',d)=[EanEuH+anE'utanE'[anEu]+ +2 定理3的结论与加工顺序π有关，在特殊情 nd*+f0.Cul+0.CC 况下定理3的结论与加工顺序无关 [5QuC.]+BuT+ynd*+0uCu). 任+2 推论当目标函数中的惩罚系数a=a,B=B, 改变加工顺序后目标函数的增量为： =%,0=0,(i=1,2,,)时，即目标函数为： △F=F(π'，d*)-F(π，d*)=a(E'M-Ea)+ F(π，d=(aEa+Te+yD+0Ca)时，对任何 (E'-Et)+0C'-Cu)+ 加工顺序π，必存在一个，使最优公共交货期 a-1(C'-0-C-）. d*=C.其中k为大于或等于n(B-)/(a+)的最注意到CW=C-+P, 小整数， Ctn=Ci+Ptn=Cu-n+Pu+Pe 证明当a=a,p=B,%=,8=武i=1,2,,n)时， C(=Cu-1+Pu 函数G=+a三B:=m叶a- C'=C'tu+P=Cu-+Ptmir+Pui (n-s)B=n(y-B)+s(a+B). E'm-Et=(d*-C'm)-(d-Ct)=Cu-C't= 此函数对任意加工顺序都成立. (Cn+Pi-(Cu-n+Pu+Pu)=-Pu, 由定理3，必存在J:,使最优公共交货期 E'-Et=(d*-C')-(d-Cum:)=Ct- d*=C阳.其中k满足G(k-1)≤0，G(k)≥0 C=(Ctn+Pw+PtD)-(Cu-n+P)=Pu. 即 Gk)=y-B+ka+)20: 所以得： Gk-1)=ny-+(k-1)(a+B)s0. △F=a（-Pir）+anPt0PH+ 所以得：n(B-y)/(a+)≤k≤n(B-y)/(a+B)+1. +(-Pd)=(0g-an)P-(0-am)Pa. k为大于或等于n(B-y)/(a+)的最小正整数. 由引理可知，△F由2个惩罚因子0u和aw 由本文讨论假设P,可得B-P0. 共同决定定义6=-a称为工件J的关于d*的联合 3最优解的结构左惩罚因子=1,2，…，n),上述△F可表示为： △F=dwPl-di+Pm 定理3给出了最优公共交货期*的确定方下面将用联合惩罚因子来讨论E:的最优加法.对某一加工顺序π，相应可确定最优公共交工顺序.以下性质15中均假设只改变E:中某货期d*.d*确定后便可把n个工件分成两部分： 2个相邻工件JM,J的位置，其余工件的位置不在*之前工件集合Ea={,J…,Jx}和d之后变的工件集合T={J,Jx,Jm}.下面的结论将性质1对于某2个相邻工件J,J,若对说明E,T,工件的加工顺序做适当调整能使目应的联合左惩罚因子d=+=0,则Ja,J)位置标函数达到局部最优. 状态不改变目标函数值

北京科技大学学报年第期移动后，艺为 ’ 艺氏小目标函数增量 △凡， ‘，一汀，的一艺矜， ’ ‘一刃一，〕一卜，谓、、一 “ 艺几户卜一 ‘，艺艺 “ 一动由于一 “ 一一卜，尸二一留，二一卜，以， △凡二一尸〔艺为艺、一艺几二」一厂尸二，所一由于是最优公共交货期，因此， △名〕以七， △只二一、以一全，即应满足全此，一 ‘ ，当羊，，，… ，，有且只有一点，使一，，最优公共交货期在处达到当时，瓦中工件的最优排序引理对于部分工件集凡而，，无 … 廷，互换某两个相邻工件沂。，试的位置，其余工件不变，则目标函数的改变量为 △ 叹，〕一。〕一什〕一〔只证明凡中工件按原加工顺序丙。，无 … ，丙〕，试。〕， … ，人加工时，每个工件提前期凡尹一叨叮，，… ，，拖延期兀此时目标函数月兀，刃二艺禹、翔尹，艺帆，〕兀〕尹〕〕互换工件试，沂。的位置，其余工件不变，得新加工顺序兀 ‘ 弄，亦〕… 从，弄， … 从。，在此顺序二 ‘ 之下，目标函数为月二 ‘ ，刃艺禹〕〔，万 ’ 〔，〕〔刃 ‘ 〔什，〕【艺，禹，时一，最优公共交货期取区间【、，中任意值定理的结论与加工顺序二有关，在特殊情况下定理的结论与加工顺序无关推论 ‘，当目标函数中的惩罚系数产刀朋，笋二夕，已，，，… ，时，即目标函数为瓜刃艺兹〔 ‘ 兀勺乃沙时，对任何加工顺序，必存在一个人，使最优公共交货期尹、其中为大于或等于刀一谓的最小整数证明当 ‘ 君戏 ‘ 二夕，叹二厌，，… ，时，函数以习艺入艺」一艺几对一产扮户十一刀少一户切此函数对任意加工顺序都成立由定理，必存在、，使最优公共交货期尹、其中满足一蕊，即以二一户十权“ 切之一夕一刀一仪切 ‘ 所以得谓一夕切 ‘ ‘ 谓一夕仅切为大于或等于谓一力切的最小正整数艺夕〔，尹〔艺，】」 ‘ 〔、叹 ‘ 。二」户产由本文讨论假设艺少艺” ，可得刀一户户】卜最优解的结构定理给出了最优公共交货期尹的确定方法对某一加工顺序二，相应可确定最优公共交货期尹尹确定后便可把个工件分成两部分在之前工件集合瓦丙， … ，、和之后的工件集合兀二，， … ，几〕下面的结论将说明凡兀工件的加工顺序做适当调整能使目标函数达到局部最优月艺司」艺渭。，不，，〕尹，，〕户矛，，七丰改变加工顺序后目标函数的增量为 △ 兀 ‘ ，尹一兀尹， ‘ 一 ‘〕。，〕 ‘ 〕一，〕凰， ‘ ‘ 一。，〕 ‘ 〔，〕一口，〕注意到一一。，，〕〔，卜，〕〔，尸，小 ‘ 〔。〕卜〕〕， ‘ ， ‘ ，苟一〕【〕尸〔，， ‘ 「‘ 一，尹一 ’ 。 ‘ 一尹一，灼一 ‘ 〔，卜〔，一 ‘一〕〔，〕尸〔一〔〕， ‘ 〔、〕一尹一 ‘ 〔，一尹一、、。一 ‘ ，暇，】一卜，〕十尸，〕只小所以得 △ 〔 ‘ 一〔。〕〔，， ‘〕 ‘ ，〕一〔，〕，〕一〔。几一从二，一。、〕〔小由引理可知， △ 由个惩罚因子，和共同决定定义落一称为工件涛的关于尹的联合左惩罚因子叮，， … ，，上述△ 可表示为 △ 氏只叫一占。乃小下面将用联合惩罚因子来讨论几的最优加工顺序以下性质一中均假设只改变凡中某个相邻工件而，曰的位置，其余工件的位置不变性质对于某个相邻工件而，试〕，若对应的联合左惩罚因子氏。成。，则弄，巩位置状态不改变目标函数值

一谢铁军等提前拖延调度问题最优解的结构一证明由引理，无论而，哪个在先，都有 △ 氏。一沐只。一，目标函数值不变性质对于某个相邻工件么，，若对应的联合左惩罚因子氏‘ ，成。〕七，则沂。排在禹之前能使目标函数值下降证明由引理，互换弄，。的位置后， △ 氏。一成。丹， ‘ ，因此，排在去之前能使目标函数值下降性质对于某个相邻工件人，，若对应的联合左惩罚因子氏全，成。， ‘ ，则丙排在试二之前能使目标函数值下降证明由引理，互换弄〕，、的位置后， △ 氏禹。一成曰丹之，这说明互换，的位置会使目标函数值增加，因此，按原顺序丙排在之前能使目标函数值下降性质对于某个相邻工件去，，若对应的联合左惩罚因子氏一汤。，户，且几〕户‘ 、从、，则丙排在。，之前能使目标函数值下降证明由引理，互换大〕，、的位置后， △ 二成、产。一遥、只成疾【尸，总一尸总、〕全，这说明互换去，巩的位置会使目标函数值增加，因此，按原顺序弄排在试。之前能使目标函数值下降性质对于某个相邻工件，，、，若对应的左联合惩罚因子衡，成、，且几氏〕之乃了占阳〕，则丙排在、之前能使目标函数值下降证明由引理互换，，。的位置后， △尸氏只。〕一苏 ‘ 一民尸成尸、占〔 ‘了日占「一俨占〔占，」全，这说明互换人，去的位置会使目标函数值增加，因此，按原顺序冻排在〕之前能使目标函数值下降有了上述性质，通过对相邻工件的互换，可以得到凡的最优排序定理把凡中工件分成个集合及二沂。么，工〕任凡 ‘〕咨 ‘ ，试 ‘ 任凡巩山，人凡把这个集合排序及在左，在中，一在右，再把中工件按，俄，递增顺序排序中工件任意排序中工件按几了民减顺序排序，则所得凡的排序为最优排序证明第步若为空集，则不必讨论设非空，中的工件可以通过与所有其他工件互换方法排在和之后，由性质一，这样换序后目标函数值下降再用同样的方法可将工件换到之后，由性质一，这样换序后目标函数值下降换序后凡顺序为，违反这个顺序将导至目标函数值会增加第步进一步调整中的工件顺序使其与了氏〕递减顺序一致，由性质这样调整后目标函数值下降第步进一步调中的工件顺序使其与。。递增顺一致，由性质这样调整后目标函数值下降由性质一，任何违背上述排序的加工顺序，必然使目标函数值会增加，故上述排序为最优排序定理的结论表明几中的最优解依八了氏具有八形结构兀中工件的最优排序引理对于部分工件集合兀沂，巩 … ，几，互换某个相邻工件丙〕，沂的位置，其余工件不变，则目标函数的改变量为 △ 二凡十氏。〕一、。小证明兀中，每个工件提前量场，拖延量几二一以，二，，凡中工件按原加工顺序沂，沂 … ，丙，试， … ，几加工时，目标函数爪风刃艺几勺闭〕，〕系，八，】不，】，「互换工件沂。，沂的位置，其余工件不变，得新加工顺序丫沂」， · … ，城〕，弄。， … ，巩。〕，在此顺序二 ‘ 之下，目标函数为全侧“ ，刃一互、几〕夕〔 · · 〕口〕暴声〔月不。八， ‘ ‘ ‘ 〔 ‘· 〔，护，〕不 ‘ 〕〕通，〕司「艺。， ‘ 〕 ‘ 【艺已们卜卜扫改变加工顺序后目标函数的增量为 △ 二 ‘ ，司一瓦动戏 ‘ ‘ 。一不刀〔〕 ‘ 〔什一不，，〕， ’ 。，〕一，〕 ‘ 〔，一，由于，二，一尸〔、，门尸卜，尸。尸。， ‘ ‘一〕十尸， ‘ ，〕，一，〕尸，。。

·288· 北京科技大学学报 2000年第3期 T':-Tn=(C't-d)-(Cu-d)=C':-Cli]= 增顺序排序为最优排序， (C:+P+P)-(Ci-+P)=P 定理5的结论表明，T。中的最优解依P/e T'4-T=(C'*-d)-(C--d)=C'n:- 具有形结构. C=(Cu-1:+P)-(Cm+P+Pm)=-Pi. 所以得： 4小结 △F=BP-+f-(-P+OPt 本文讨论了带有4项惩罚指标的提前/拖延 0(-PU)=(B+0)P:-(Bu+)Pn. 调度问题，给出了最优公共交货期的确定方法，由上可知，△F由2个惩罚因子u和0，共同并讨论了最优解的结构，使得最优解的搜索范决定. 围大幅度缩小，为寻找最优解或近优解提供了定义G=+8称为工件J的关于d的联合搜索范围.对此类问题的进一步研究是寻找确右惩罚因子=1,2，…，n). 定最优解的有效算法，定理5T:中工件按序列{Pe}递增顺序排序为最优排序.证明：设Jk,J,J为T。中工参考文献件按序列{P/e}递增顺序的排序，互换某2个相 1 Baker K R.Sequencing with Earliness and Tardness Penal- 邻工件J,J)的位置，其余工件不变，则由引 ties.A Review Oper Res,1990,38,22 2 Panwalker S S,Smith ML.Common due Date Assignment 理，目标函数的改变量为： to Minimize Total Penalty for the One Machine Scheduling AF=eP-mPu=Bem(Ptye-(Puleu]. Problem.Oper Res,1982,30(2):319 由于{P/em}是递增的，即(Paen)≤(P/er),3 Cheng TCE,OgzC,QiXD.Due-date Assignment and 所以，△F≥0，目标函数值增加. Single Machine Scheduling with Compressible Processing 互换某2个不相邻工件JM,J的位置，可 Time.Int J Pro Eco,1996,43:29 以通过互换一系列相邻工件完成，也会使目标 4吴悦，汪定伟.用遗传/禁忌搜索混合算法求解可变加工时间的调度问题.控制与决策，1998,13（增）：428 函数值增加，因此，T:中工件按序列{Pe}递 Structure of Optimal Solution for E/T Scheduling XIE Tiejun",CHENG Tao,LIU Tenping 1)Applied Science School,UST Beijing.Beijing100083,China 2)Beijing University of AeronauticsAstronautics,Beijing100083,China 3)DepLof Computer Science and Engineering,Tsinghua University Beijing10084,China ABSTRACT A kind of E/T scheduling problem with four penalty factor is discussed in order to determine the optimal sequences and optimal common due date.A method about how to determine common due date is presented,the concept of combinative penalty factor is proposed,and the structure of optimal solution is discussed. KEY WORDS E/T scheduling;completion time;due date;penalty factor

北京科技大学学报年第期 ’ 到一，一界 ’ ‘ 一’ 一一 ’ 二 ’ 一「习 ‘ 一，尸，户一一，力月、〕， ’ 一。 ‘ 一了一一了二 ‘ 。一。一、一。十尸、一只。所以得 △ 二戏尹尹，。一几卜叹、十又一二俩沙氏、一俩。〕班由上可知， △ 由个惩罚因子刀 ‘ 和氏〕共同决定定义局份称为工件必的关于的联合右惩罚因子以，， … ，定理兀中工件按序列尸沙介价递增顺序排序为最优排序证明设试，城 … ，人为兀中工件按序列尸。两〕递增顺序的排序，互换某个相邻工件人〕，试。的位置，其余工件不变，则由引理，目标函数的改变量为 △ ￡【 ‘ 。一。，， ‘ 〔，声，【，，介】一〔冰【 ‘ 」由于几向是递增的，即。，介〔，。 ‘ 〔，介〔，〕，所以， △ 全，目标函数值增加互换某个不相邻工件试。，巩。的位置，可以通过互换一系列相邻工件完成，也会使目标函数值增加，因此，兀中工件按序列尸切低〕递增顺序排序为最优排序定理的结论表明，兀中的最优解依，抵月具有形结构小结本文讨论了带有项惩罚指标的提前拖延调度问题，给出了最优公共交货期的确定方法，并讨论了最优解的结构，使得最优解的搜索范围大幅度缩小，为寻找最优解或近优解提供了搜索范围对此类问题的进一步研究是寻找确定最优解的有效算法参考文献于时称，，，，而叭阵助，，，，刀七即汕，，吴悦，汪定伟用遗传禁忌搜索混合算法求解可变加工时间的调度问题控制与决策，，增刀乃，扩，，，仕卫，。印，，汀加加上，汀而