提前/拖延调度问题最优解的结构

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?中必有且只有一个小于零，当 在以下的讨论中，均假设含<B。 △F<O时，d移至C,处可使目标函数值减少； 当△F<0时，d移至C处可使目标函数值减少， 为了讨论方便，设函数Gs)=m+2aM- 因此，最优公共交货期必在某个工件完工时刻 三pa,(012m). 达到.当G()=0时，△F,=△F2=0,d移至C处或 规定G0三G=w+空a，显然， 移至C处，目标函数值不改变，因此，最优公 共交货期取区间[C因，Cwn]中任意值. G00,Gn>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,G(k)>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- 证明设Cxd<C,C为某个工件的完工时 d①+hwtΣ8uCe. 刻，(k=1,2,,n),此时，目标函数为： d向右移动，移至处C+,即d'=C,此时 Fr,d亦an(d-C)+三Ba(Ci-d①+ 目标函数为： 含d+g0,ca… t*1 F(r,d)-Ea(d'-Cu)+O+O+>Bn(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,G(k)>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)位置 标函数达到局部最优. 状态不改变目标函数值

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

Vol.22 No.3 谢铁军等：提前/拖延调度问题最优解的结构 ·287· 证明由引理，无论J,J)哪个在先，都有证明第1步：若S为空集，则S不必讨论.设 △F=dP一dPn=0,目标函数值不变. S非空，S中的工件可以通过与所有其他工件 性质2对于某2个相邻工件J,J1,若对 互换方法排在和S,之后，由性质13，这样换 应的联合左惩罚因子c≤0，d+20,则J1排在 序后目标函数值下降.再用同样的方法可将S J之前能使目标函数值下降. 工件换到S之后，由性质13，这样换序后目标 证明由引理，互换J山，J的位置后， 函数值下降.换序后E。顺序为S<S<S,违 △F=dP一dr-Pu≤0，因此，J-排在J之前能 反这个顺序将导至目标函数值会增加. 使目标函数值下降。 第2步：进一步调整S中的工件顺序使其 性质3对于某2个相邻工件Jx,J#,若对应 与{Pl6l}递减顺序一致，由性质5这样调整 的联合左惩罚因子d≥0，d≤0，则Jk排在J 后目标函数值下降， 之前能使目标函数值下降. 第3步：进一步调S.中的工件顺序使其与 证明由引理，互换a,J的位置后， {Pa/⊙}递增顺一致，由性质4这样调整后目标 △F=daPr-d-P之0，这说明互换Ja,J)的位 函数值下降， 置会使目标函数值增加，因此，按原顺序J排在 由性质15，任何违背上述排序的加工顺 J之前能使目标函数值下降. 序，必然使目标函数值会增加，故上述排序为最 性质4对于某2个相邻工件J,J,若对应 优排序. 的联合左惩罚因子dr>0,d0,且(P/6a)≤ 定理4的结论表明，Ea中的最优解依P6l (P/6),则W排在J:之前能使目标函数值下 具有形结构. 降. 3.2T,中工件的最优排序 证明由引理，互换J,J)的位置后，△F= 引理2对于部分工件集合Ta={J,J2…, dxPr-dP=drdr[(Pr1l/oiri)-(Plda)]≥0， J,互换某2个相邻工件J,J的位置，其 这说明互换J,J的位置会使目标函数值增 余工件不变，则目标函数的改变量为： 加，因此，按原顺序J排在J之前能使目标函 AF=(Bt+0)Pun-(B+0)Pun. 数值下降. 证明T4中，每个工件提前量En=0,拖延量 性质5对于某2个相邻工件a,J,若对 Tn=Cu-d0=k+1,k+2…,n),Ea中工件按原加 应的左联合惩罚因子d<0,6<0,且(Pullual)≥ 工顺序J+,…,,J,…,J加工时，目标 (P/6l),则Ja排在J之前能使目标函数值 函数： 下降. Fπ，d)=∑(a,Eo+hdH0Ca)+ 证明由引理互换J,Jr的位置后，△F= P-8mPu=-18Pm+tP= BiTinthud+0.Cu). |dall84l[-(P-/id+)+(P/八6l)]20, 互换工件J0,+的位置，其余工件不变， 这说明互换J,J的位置会使目标函数值增 得新加工顺序π'={U,J+…,J,,…, 加，因此，按原顺序排在J:之前能使目标函 J},在此顺序π'之下，目标函数为： 数值下降. r',d=三(aEt7e,Ca）+{3BanH 有了上述性质，通过对相邻工件的互换，可 BIa'+B-T'=nr[三ATH[三md+ 以得到E,的最优排序. [EOuCiHOwC'wC>0nCu]. 定理4把E中工件分成3个集合： S.={J6>0,J∈Ea}: 改变加工顺序后目标函数的增量为： S={Jlδ=0，J∈Ea}: △F=F(π'，d①-F(π，d)=Ba(T'M-Tm)+ S={Jl6<0,J∈Ea}. B(T'-T)+0t(C'-Ci)+ 把这3个集合排序：S.在左，S在中，S.在 0(C'-C). 右，再把S.中工件按{P/6a}递增顺序排序；S 由于，Cw=C-n+Pa, 中工件任意排序：S.中工件按{P/6l}减顺序 C=Cun+Pt=C-+Pu+PL, 排序，则所得Ea的排序为最优排序. C=Cu+Pu C'=Ct-+Pur+P

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

·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

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