（运筹学与控制论专业论文）加工时间非恒定的超前有奖延误受罚的排序问题.pdf

2 0 0 8 年上海大学硕士学位论文 摘要 排序问题是一类重要的组合最优化问题，也是运筹学研究的一个非常活跃的分 支随着研究者对排序问题越来越多的关注，各类新型排序也不断地涌现出来加工 时间非恒定的排序模型便是其中很重要的一个部分 本文考虑的是超前有奖延误受罚的排序问题：对所有的工件都定义一个共同的 交货期，当某一工件在交货期后完工，则给以一定的惩罚；而在交货期之前加工则给 以一定的奖励在目标函数为最小化加权超前有奖延误受罚总和中，引入了非恒定 的加工时间本文主要考虑了递减率与基本加工时间相关的、简单线性函数以及具有 学习效应的工件加工时间在每个问题中，给出了一些多项式时间可解的特例，并给 出了相应的分支定界算法另外，对递减率与基本加工时间相关的加工时间和简单线 性函数的加工时间模型，分别给出了一动态规划算法，并给出了算例 关键词单机排序；超前；延误；动态规划算法；分枝定界算法 2 0 0 8 年上海大学硕士学位论文 i i a b s t r a c t s c h e d u l i n gp r o b l e mi sa ni m p o r t a n tc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e ma n di s a l s oa s i g n i f i c a n tb r a n c ho fo p e r a t i o n a lr e s e a r c h t h e r ei sag r o w i n gi n t e r e s ti nt h el i t e r a t u r et os t u d ys c h e d u l i n gp r o b l e m s ，a n dv a r i o u sk i n d so fm o d e r ns c h e d u l i n gm o d e l s a r es p r i n g i n gu p n o n c o n s t a n tp r o c e s s i n gt i m es c h e d u l i n gm o d e l sa r ep a r to ft h e m w ec o n s i d e rs c h e d u l i n gp r o b l e m so ne a r l i n e s sa w a r da n dt a r d i n e s sp e n a l t yw i t h n o n c o n s t a n tp r o c e s s i n gt i m e s t h e r ei sag i v e nc o m m o nd u ed a t ef o ra l lt h ej o b s ， w h e naj o b sf i n i s h i n gt i m ei sa f t e rc o m m o nd u ed a t e ，ap e n a l t yi sg i v e n ，w h i l et h e f i n i s h i n gt i m ei sb e f o r ec o m m o nd u ed a t e ，a na w a r di sg i v e n w ei n t r o d u c en o n c o n - s t a n tp r o c e s s i n gt i m e si n t ot h ep r o b l e mo fm i n i m i z i n gt h ew e i g h t e ds u mo fe a r l i n e s s a w a r da n dt a r d i n e s sp e n a l t ys c h e d u l i n gm o d e l w em a i n l yc o n s i d e rd e c r e a s i n gr a t ei s i n d e p e n d e n to fi t sn o r m a lp r o c e s s i n gt i m e ，s i m p l yl i n e a rf u n c t i o na n dl e a r n i n ge f f e c t p r o c e s s i n gt i m e f o re a c hs c h e d u l i n gp r o b l e m ，w eg i v eab r a n c ha n db o u n da l g o r i t h m a n ds o m ep o l y n o m i a lt i m es o l v a b l ec a s e s ，r e s p e c t i v e l y f o rd e c r e a s i n gr a t ei si n d e p e n - d e n to fi t sn o r m a lp r o c e s s i n gt i m ea n ds i m p l yl i n e a rf u n c t i o np r o c e s s i n gt i m e ，w eg i v e ad y n a m i cp r o g r a m m i n ga l g o r i t h ma n dc o r r e s p o n d i n ge x a m p l e ，r e s p e c t i v e l y k e yw o r d ss c h e d u l i n g ，e a r l i n e s s ，t a r d i n e s s ，d y n a m i cp r o g r a m m i n ga l g o - r i t h m ，b r a n c ha n db o u n da l g o r i t h m 2 0 0 8 年上海大学硕士学位论文 4 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除 了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写 过的研究成果参与同一工作的其他同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意 签名余炙日期姗8 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有 权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论 文的全部或部分内容 ( 保密的论文在解密后应遵守此规定) 签名：微 导师豁钐陟期：碲易d 2 0 0 8 年上海大学硕士学位论文 1 1第一章前言 在本章中，我们首先简介排序问题的来源、发展及模型假设，接着对与本文有关 的基本概念进行阐述，最后简要讲述本文主要研究的排序问题 1 1排序问题简介 排序问题是一类重要的组合最优化问题，也是运筹学研究的一个非常活跃的分 支排序问题产生于上个世纪5 0 年代，产生的背景主要是机器制造，它广泛应用于 管理科学、计算机科学和工程技术等领域其实，在现实生活中排序无处不在：从普 通的生产部门的计划安排、人员调度、学科课程表的制定到宇宙飞船的复杂庞大的 飞行计划，都要用到排序的理论和算法 例如：在一个飞机场，有几十个登机门，每天有几百架飞机降落和起飞，登机门 的种类和大小是不同的，而班机的机型和大小也是不同的，如大登机门安放在能容 纳大型飞机的地方小登机门安放在只能容纳小型飞机的地方飞机按时刻表降落 和起飞，由于天气和机场的其他原因，时刻表也有很大的随机性当飞机占有登机门 时，到达的旅客下飞机，出发的旅客上飞机机场的调度人员需要制定一个可行的方 案，把登机门分配给降落的飞机，使机场的利用率最高或晚点起飞的飞机最少，这也 是一个排序问题，在这里飞机被看成是被处理的工件，登机门当作处理机，机场的规 定是约束条件 又如：在计算机多道程序操作系统中，并发执行多个进程，在宏观上同时执行 多个进程，在微观上在任何时刻c p u 只能执行一个进程进程的到达时间是不同的， 怎样调度这些进程才能使c p u 的利用率最高或者进程的平均周转时间最短? 这也是 个排序问题，其中进程被看成是要处理的工件，c p u 被当作是处理机，各进程之间 2 0 0 8 年上海大学硕士学位论文 2 的约束便是约束条件 由此可见，排序问题无处不在，研究排序的理论和算法对实际生产和生活有较 大的促进作用，对我们整个国民经济的发展也有不可忽略的意义 1 2 同本文相关的基本概念 一般来说，排序问题是由处理机的数量、种类、环境以及被处理的任务的性质 和目标函数所组成它是利用一些处理机最优地完成一批给定的任务，通常我们将 要处理的对象称为工件，且一般对由n 个工件组成的工件集合记为j = 以，厶) ， 其中乃o = 1 ，n ) 表示第歹个工件在不至于混淆的情况下，我们用工件易的 下标j 来表示第j 个工件将m 台机器组成的集合记为m = 尬，) 其中 坞，0 = l ，n ) 表示第j 台机器 在论文的后面部分都采用三参数表示法( g r a h a me ta 1 1 9 7 9 1 3 1 ) 来描述排序问 题，即：机器i 约束条件i 目标函数 排序问题中的机器表示的是机器的台数和机器的功能类型只有一台处理机的 排序问题称为单机排序问题，否则称为多机排序问题在多处理机排序问题中，如果 所有的机器都具有相同的功能，称它们为同类机或平行机( p a r a l l e lp r o c e s s o r s ) 同 类机又分为同速机、恒速机和变速机 排序问题中的约束条件，主要指工件或作业的性质以及工件在被加工过程中受 到的限制，在本文中同工件相关的一些变量常有。 1 、工件j 的实际加工时间功； 2 、工件j 的到达时间( a r r i v a lt i m e ) 或准备时间( r e a d yt i m e ) r 1 ：它表示工件j 可开始 被加工的时间，如果所有工件的准备时间相同，取= 0 ，j = 1 ，n ； 3 、工件歹的应交工时间( d u ed a t e ) d j ：当d j 三d ，j = 1 ，n 时，则d 是n 个工件的 共同应交工时间( c o m m o nd u ed a t e ，简记为c o n ) ； 4 、w j ：工件j 的权因子，表示歹的重要程度； 5 、g ：表示在序中工件歹的完工时间； 6 、易：e j = m a x 0 ，而一0 ) 表示在序中工件j 的超前； 2 0 0 8 年上海大学硕士学位论文 3 7 ，t j ：t j = m a x 0 ，g d a 表示在序中工件j 的延误； 8 、g ：表示序中工件的最大完工时间，它等于序中最后一个完工工件的完工时间 排序问题中的目标函数就是要最优化的函数在排序问题中，比较原始的目标 函数主要有时间表长、加权总完工时间、最大延误，加权误工任务数，此外还有些多 目标函数 本文主要考虑的是单处理机的排序问题，目标函数主要讨论极小化加权超前有 奖延误受罚总和，即譬1 ( q j t j 一岛e j ) 求解排序问题，其实质是构造算法以得到该问题的最优排序对于排序问题算法 的好与坏，我们常根据它的复杂性来判断由于绝大多数排序问题都是n p - h a r d 的， 其最优解往往很难找到，而且实际中只需找到满足一定要求的启发式解和近似解因 此排序问题的研究主要有两个方向一个是对可解的尸问题，寻找多项式时间优化算 法( 又称有效算法) 来得到问题的最优解或者对p h a r d 问题，在特殊情况下寻找 有效算法二是对求p h a r d 问题解有两种基本方法：一是用分支定界算法、动态 规划算法等巧妙的穷举法求出它的精确最优序；另一种方法是求出它的近似最优排 序，各种局部搜索算法和启发式算法都是很有效的为了知道所得到近似最优排序与 最优排序的近似程度，分析误差界是使用这类方法不可缺少的工作，也是最难的工作 1 3 相关问题的已有结果 在经典排序问题中，工件的加工时间通常是一个事先给定的常数但在有较强的 实际背景的排序问题中，工件的加工时间可能与其开始的加工时间有关系总体上， 与开工时间有关的加工时间的排序问题可以分为两大类一类是加工时间是其开工 时间的非减函数，另一类是加工时间是其开工时间的非增函数这些模型反映了在现 实生活中加工时间是其开工时间的线性或分段线性的模型第一种情况在炼钢过程， 塑料加工和医疗等方面具有广泛的应用如在炼钢过程中，如果工件在加工前需要等 待，则将引起加工工件的温度的下降，从而导致工件的加工时间的增加后一种情况 的实际背景常见于管理科学中，如工人在加工相同或相似的工件时，由于熟练程度 或掌握知识的增加，工件的加工时间将随着工作时间而缩短这两类情况通常称为工 件加工时间依赖开始加工时间的排序问题 2 0 0 8 年上海大学硕士学位论文4 第一种情况用如下集合来标识( d 】， q ) ， 幻) ， 呜) ) ，其中对每个工件歹有一个 交货期喀，一个正常加工时间和一个为大于。的常数( 称为工件歹的退化率) 工 件的实际加工时间通常用正常加工时间、加工的退化率和开始加工时间来描述，即 乃= n j + ，( j = 1 ，扎) ，其中t 为工件歹的开始加工时间线性加工时间的单 机排序问题1 i 乃= + 吗亡i 。最早由g u p t a 和g u p t a 1 9 8 8 1 7 提出，并且得出 工件按 关) 的非降序排列为该问题的最优序尽管极小化最大完工时间的单机问题 x l p j = a j + 引c m 娃存在多项式时间算法，但其它目标函数的问题却相当复杂对于 极小化加权完工时间和问题x l p j = a j + 芒i 努1 嘶c j ，b a c h m a n e ta 1 2 0 0 2 1 】证明 了该问题是p h a r d 的大多数文献均研究其特殊情况，对于工件退化率相同的情 况，m o s h e i o v 1 9 9 6 1 0 证明了问题l l p j = 吩+ b t ie j l l 哟c j 当取嘶= 6 ( 6 0 ) 时，其最优序具有关于正常加工时间的7 a 型性质( 即在最优序中，排在正常加工时间 最大的工件前面的工件按正常加工时间不减序排列，而排在其后的工件按正常加工时 间不增序排列) 在此基础上，给出了o ( n l o g n ) 的多项式时间算法m o s h e i o v 1 9 9 1 1 1 】 证明了排序问题1 i 殇= a + b t le j l l0 ，的最优序具有关于退化率的7 v 7 一型性质( 即 在最优序中，排在退化率最大的工件前面的工件按退化率不增序排列，而排在其后 的工件按退化率不减序排列) 对于另一类情况用如下集合来标识( d ) ， ) ， h a ， 呜) ) ，其中对每个工件j 有一 个交货期嘞，一个正常力n - f _ 时间和一个递减率( 其中，0 0 ，岛 0 其中和岛分别称为罚因子和奖因子 据我们所知，目前有两篇文献研究了对这种超前有奖延误受罚的排序模型，w - u 和s u n 2 0 0 2 1 1 4 】给出了一些多项式时间可解的特例及一个分枝定界算法s o n ge t a 1 2 0 0 2 1 1 2 6 】等人给出了一个动态规划算法同时在逆一致性条件下给出了一个伪多项 式时间的动态规划算法 1 4本文研究的主要问题及相关工作 最近，越来越多的学者开始研究加工时间非恒定的排序模型对于我们的模型 1 1 ie j - ( 乃一岛易) 也可以引入非恒定的加工时间在第二章中，我们主要研究在 工件的加工时间的递减率是与基本加工时间相关的超前有奖延误受罚问题 。 n 1 i 殇= 哟( n u ) l 哪n ( 乃一z j e j ) ( r ) j = l 在第三章中，我们主要研究在工件的加工时间为简单线性函数的超前有奖延误 受罚问题 n 1 l 功= 引吵n ( a j 乃一p j e j ) ( 尼) j = 1 在第四章主要研究工件具有学习效应的超前有奖延误受罚的排序问题 n 1 i 功= 矿- 1 ii 雩n ( 乃一z j e j ) j = l ( b ) 2 0 0 8 年上海大学硕士学位论文 7 2 工件的加工时间是与位置有关的超前 有奖延误受罚的排序问题 在本章中，我们考虑与正常加工时间成正比的递减率，即玩= k a t ( k 0 ) 的 模型我们有聊= n ，( 1 一舰) ，其中( 1 一船) 是一个递减函数不失一般性，我们假 设递减函数为( a 一沈) 我们得到乃= 哟( o 一沈) ，其中a 0 ，0 b 0 ，( a m 戕= m a x a j l j = 1 ，2 ，礼) ) ，b ( e j 忽1a 1 一b a m i n ) 0 ，有o c ! ； 而o j ，( j ，k 1 ，2 ，礼) ) ，且在工件序s 中，工件k 排在工件 j 的紧前工件，t 是工件k 在工件序s 中的开工时间( 参见图2 1 ) 由此工件k 和工 件歹对目标函数的贡献为 s ( k ，j ) = q 七t + o e k a k ( a 一沈) + a j t + a j a k ( a b t ) + a j a j ( a 一沈) 一b a j a j ( a 一沈) 交换序s 中工件k 和工件歹的顺序得到新序s 7 ，由此有 s 7 u ，k ) = a j t + a j a j ( a 一托) + a k t + a k a j ( a b t ) + q k a k ( a 一沈) 一b a k a k ( a 一沈) 我们可以得到 s ( k ，j ) 一s 7 0 ，k ) = ( a j a k ( 1 6 ) 一a k a j ( 1 6 0 七) ) ( n 一沈) 由于硒a k 丽 丽a j j 可，所以我们有s ( k ，j f ) ( 歹，七) i 一 二互二工卫 3 l 五 t 图2 1 性质2 1 若d m i n a j l j = 1 ，2 ，n ) ，将工件按照 可导葡) 的非降序排列将得到 排序问题1 i 乃= 吩( 口一沈) ，d m i n a j l j = 1 ，2 ，死) l 套1 ( q j 乃一岛马) 的一个最优 序也就是该问题在o ( n l o g n ) 时间内可解 2 0 0 8 年上海大学硕士学位论文 9 证明若d m i n a i l j = 1 ，2 ，死) ，则所有的工件都误工由此可得 e j l l ( q j t j 一岛易) = 1 ( ( q d ) ) = e l l q j g 一1a i d 由于后面一项是常数，由引理2 3 可知将所有的工件按照一、o j l ， 的非降序排 列将得到排序问题l l p j = ( 口一沈) ，d m i n a j l j = 1 ，2 ，n ) i 饕1 ( a j 乃一岛易) 的 一个最有序 性质2 2 若d g ( 1 一兀警1 ( 1 6 ) ) ，则将所有工件按照 楠) 的非降序排列将 得到排序问题1 b = ( 口一沈) ，d g ( 1 一兀冬1 ( 1 一) ) l 1 ( 乃一岛局) 的一个 最优序也就是该问题在0 ( n l o g n ) 时间内可解 证明若d g ( 1 一n 努1 ( 1 6 唧) ) ，则所有工件都不误工，由此可得 各1 ( 乃一岛局) = e 整- ( 一岛( d g ) ) = 墨岛g 一务，岛d 由于后面一项是常数，由引理2 3 可知将所有工件按照 桶) 的非降序排列 将得到排序问题1 i 功= q ( 口一沈) ，d g ( 1 一兀等1 ( 1 6 ) ) i 努。( 哟乃一岛易) 的一 个最优序 性质2 3 若哟兰岛0 1 ，2 ，n ) ) ，将所有工件按 砑孝而) 的非降序排列将得到 排序问题1 i 功= a j ( a 一配) ，哟三岛0 1 ，2 ，n ) ) i 距。( 乃一岛易) 的一个最优 解，也就是该问题在o ( n l o g n ) 时间内可解 证明由易一乃= d q ，我们可得 e j l i ( a i z p j e n = 等- ( ( 哟一岛) 乃+ 岛( 乃一易) ) = 凳( ( 一岛) 乃+ 岛( g d ) ) = e l l8 c i 一| 3 d 由于后一项是常数，由引理2 3 可知将所有工件按 碌f a j 丽) 的非降序排列将得 到排序问题1 i 功= ( o 一沈) ，哟三岛0 1 ，2 ，佗) ) i 各1 ( 哟乃一岛易) 的一个最 优序 性质2 4 若哟兰q ，岛三z ( j 1 ，2 ，佗) ) ，则将所有的工件按| ) 的非降排列 2 0 0 8 年上海大学硕士学位论文 1 0 ( s p t 序) 将得到排序问题l l p j = a i ( a 一沈) ，三q ，岛三z ( j 1 ，2 ，他】) l 饕1 ( 乃一 岛易) 的一个最优序，即该排序问题在o ( n l o g n ) 时间内可解 证明假设工件序盯为排序问题l l p j = a j ( a 一况) ，三q ，岛兰z ( j 1 ，2 ，礼) ) ie j l l ( - i t j 一 岛易) 的一个最优序，且它不是按s p t 规则排列得到的，由此必然存在一对工件j 和工件k 满足a 七 a f ，而工件j 为工件k 的紧后工件交换工件序仃中工件k 和工 件j 的位置得到新工件序盯7 ，下面我们分七种情况来证明性质4 在每种情况中，假 设t 为工件序盯中工件k 的开工时间首先，我们考虑工件k 和工件j 中无一工件 为跨越工件的情况 c a s e l 工件k 和工件j 皆为超前工件( 参见图2 2 ( a ) ) ，则工件k 和工件j 在工件序 仃中对目标函数的贡献为 o ( k ，j ) = 一p ( d t a k ( a 一沈) ) 一z ( d t a k ( a 一觇) 一a j ( a 一6 ( 亡+ a s ( a 一班) ) ) ) 同理对于工件序一，我们有 s 7 u ，k ) = 一p ( d t q ( n 一配) ) 一p ( d t 一吩( n b t ) 一a s ( a b ( t + 哟( n 一配) ) ) ) 因此我们有 s ( k ，j ) 一s 7 0 ，k ) = 卢( 口七一) ( n 一沈) 由于a s a j ，a b t 0 ，所以s ( k ，j ) ( 歹，七) 。 c a s e 2 工件k 和工件j 都是延误工件( 参见图2 2 ( b ) ) ，工件k 和工件j 在工件序口 中对目标函数的贡献为 s ( k ，j ) = 口( t + a k ( a 一研) 一d ) + q + a s ( a 一抚) + 哟( o b ( t + a s ( a 一院) ) ) 一d ) 工件k 和工件歹在工件序矿中对目标函数的贡献为 o ，k ) = q + a j ( a 一沈) 一d ) + q ( 亡+ a s ( a 一沈) + a j ( a 一6 + a s ( a 一耽) ) ) ) 由此我们有 s ( k ，歹) 一s 7 ( j ，k ) = a ( a s q ) ( 口一配) 由于a s 一 0 及a 一觇 0 ，所以s ( k ，歹) s 7 ( j ，七) 接着我们考虑在工件k 和工件j 中存在跨越工件的情况 c a s e 3 在工件序盯中，工件k 是一个跨越工件在工件序矿中，工件歹是一个跨越 工件( 参见图2 2 ( c ) ) ，证明同c a s e 2 c a s e 4 在工件序口中工件k 是一个跨越工件，在工件序o j 中d 为工件歹的完工时 间( 参见图2 2 ( d ) ) 在工件序一中，工件k 和工件j 对目标函数的贡献为 2 0 0 8 年上海大学硕士学位论文 1 1 s 7 0 ，k ) = q ( 亡+ ( 口一沈) + a k ( a 一6 ( + a j ( a 一配) ) ) 一d ) ) 由此我们有 s ( k ，j ) 一s 7 u ，k ) = q ( 亡+ a k ( a 一配) 一d ) 由t + a k ( a 一阮) 一d 0 ，可以得到s ( k ，歹) 0 ，尼) c a s e 5 在工件序口中，工件k 是一个跨越工件，在工件序一中，工件k 也是一个 跨越工件( 参见图2 2 ( e ) ) 在工件序盯中，工件k 和工件j 对目标函数的贡献为 s 7 0 ，k ) = q ( 亡+ ( 凸一b t ) + a k ( a 一6 ( 亡+ a j ( a 一抚) ) ) 一d ) 一f l ( d t a j ( a 一现) ) 因此，我们可以得到 s ( k ，j ) 一0 ，k ) = q ( 亡+ a k ( a 一沈) 一d ) + f l ( d t 一( o 一沈) ) ) 由于t + a k ( a 一配) 一d 0 和d t 一哟( o 一觇o ) ，所以得到s ( k ，j ) s 7 0 ，k ) c a s e 6 在工件序仃中d 为工件k 的完工时间，在工件序一中，工件k 为一个跨越 工件( 参见图2 2 ( f ) ) 在工件序盯中工件k 和工件j 对目标函数的贡献为 s ( k ，j ) = q + a + k ( a 一沈) + a j ( a 一6 ( 亡+ a k ( a 一沈) ) ) 一d ) 由此我们可以得到 s ( k ，j ) 一s 7 0 ，k ) = f l ( d t a i ( a 一沈) ) 由于d t a j ( ab t ) 0 ，所以得到s ( k ，j ) ( 歹，七) c a s e 7 在工件序口中，工件j 是一个跨越工件，在工件序矿中，工件k 是一个跨越 工件( 参见图2 2 ( g ) ) 在工件序口中，工件k 和工件歹对目标函数的贡献为 s ( k ，歹) = q ( t + a k ( a b t ) + ( o b ( t + a k ( a 一阮) ) ) 一d ) 一f l ( d t 一口七( 口一配) ) 在工件序矿中工件k 和工件j 对目标函数的贡献为 s 7 0 ，七) = q ( 亡+ ( 口一沈) + a k ( a b ( t + a j ( a b t r ) ) ) 一d ) 一z ( d t a a a 一配) ) 因此我们可以得到 s ( k ，j ) 一- 少0 ，k ) = z ( a u ) ( a k 一) 由于a k 一吩 0 及a b t 0 ，所以得到s ( k ，j ) s 7 ( 歹，七) 一卜号一2 ( a 图2 ) “ 仃卜卫丑一 图2 2 ( 5 ) 2 0 0 8 年上海大学硕士学位论文 1 2 仃卜守卫一 盯卜- 哥珥一 图2 2 ( c ) 盯卜一习尹- 盯卜j 习尹一 图2 2 ( e ) 仃卜习丑一 图2 2 ( d ) 盯卜- 习尹 图2 2 ( f ) 盯卜卫尹一 卜卫l 一 图2 2 ( g ) 图2 2 性质4 的七种情况 2 2排序问题( 只) 的一个动态规划算法 不失一般性，我们假设m i n a j 1 j n ) d 2 ( 1 一兀套1 ( 1 6 吩) ) ，因为前 面对d m i - n a j l j = 1 ，2 ，n ) 和d 2 ( 1 一n 翟1 ( 1 一呐) ) 的情况，性质2 1 、性质 2 2 已指出是多项式时间可解的由于排序问题( p 1 ) 中的目标函数为正则函数，因此 我们可以构建一个动态规划算法 令乃( c j ) = t j 一岛易，对于工件集 1 ，2 ，n ) 的一个子集j ，我们定义 ，= n j ，q j 为工件集，中最后一个工件的完工时间由引理2 2 可知，在 工件序，中，q ，的值与工件集，中工件的排法无关 假设我们已经构建了一个工件序，在其中工件集，中的所有工件都排在工件集 2 0 0 8 年上海大学硕士学位论文 1 3 j 中的任一个工件的前面我们知道，若工件序为最优序，则位于工件集j 7 中的工 件序也应为最优序在工件集j 中的工件排在时间q ，后的前提下，其中的工件序也 应为最优序 令f ( j ) 表示排在时间q - ，后的工件集j 中的所有工件对目标函数的贡献由此， 我们可以得到 边界条件：j = d ，f ( o ) = 0 对l j i = k ( k = 1 ，2 ，n ) 的递推关系为 f ( j ) = 嚼y f j ( q j + a i ( a 一6 q j ) ) + f ( j 一【歹) ) ) 当i j l = n 时，相应的f ( j ) 为排序问题( p 1 ) 的最优值，相应的工件序为排序问题( r ) 的 最优序下面我们通过一个例子来说明上述算法 例2 1 由3 个工件组成的工件集的参数由下表给出 表2 1 工件j 123 正常加工时间 5 67 延误罚因子哟 5 21 5 超前奖因子岛 52 42 其中a = 1 5 ，b = 0 1 ，d = 1 0 由动态规划算法的递推关系式，我们得到 当i j i = l j = 1 ) ， q ，= - 1 5 ( 1 一o 6 ) ( 1 一o 7 ) + 1 5 = 1 3 2 ， f ( j ) 2 型p ( q j + p 1 ) + f ( o ) ) = 5 ( 1 4 4 1 1 0 ) + = 2 0 5 ； j = 2 】， q ，= - 1 5 ( 1 一o 5 ) ( 1 一o 7 ) + 1 5 = 1 2 7 5 ， f ( j ) 2 粤争 ( q ，+ 仇) + f ( d ) 2 0 0 8 年上海大学硕士学位论文 1 4 j = 3 当l j l = 2 j = 1 ，2 ) ， j = l ，3 ) ， j = 2 ，3 ) ， 当i j i = 3 j = 1 ，2 ，3 ) ，l ， j ， = 2 ( 1 4 4 1 一l o ) + = 8 2 ： q ，= - 1 5 ( 1 一o 5 ) ( 1 0 6 ) + 1 5 = 1 2 ， f ( j ) 2 掣 ，3 ( q ，+ 船) + f ( 仍) ) = 1 5 ( 1 4 4 1 1 0 ) + = 6 1 5 ： q ，= 一1 5 ( 1 0 7 ) + 1 5 即，= 赌篇篇= 鼍j - - - - x ，, 即嘲f l ( q j + p 1 ) + f ( 3 ) = 1 6 1 5 ： 即旧 f 2 ( q j + p 2 ) + f ( 3 ) = 1 0 1 5 , ： 2 0 0 8 年上海大学硕士学位论文 1 5 q j = 0 ， f ( j ) = m j i ，n ( 口1 ) + f ( 3 ，2 ) ) = - 1 4 8 5 ，j = 1 ， 厶( 口2 ) + f ( 1 ，3 ) ) = 6 5 5 ，j - - 2 ， ( a 3 ) + f ( 1 ，2 ) ) = 1 5 9 5 ， j _ 3 ， = 一1 4 8 5 所以最优值为一1 4 8 5 ，相应的最优序为( 1 ，2 ，3 ) 在上述算法中，当i j i = k 时， 共有磷种工件集的选择方法，计算量为( 2 竹一1 ) d ( n ) 接下来我们给出该问题的一 个分枝定界算法 2 3排序问题( r ) 的分枝定界算法 推论2 1 排序问题( p 1 ) 存在一个最优序，在该序中工件集e 中的工件按 丽导丽】 的非降序排列，工件集t 中的工件按 而导丽) 的非降序排列， 证明由性质2 1 和性质2 2 显然可得 该分枝定界算法是从前向后分枝的对r t 个工件的排序问题，一个完全的搜索树 共有n 层结点，第0 层为根节点，从根节点分枝产生第一层有n 个节点，每个节点 对应一个序中的第一个位置已经排定工件的部分序所以对于第一层的每一个节点， 从层1 到层2 有( n 一1 ) 个节点因此，在第二层有( 佗一1 ) 率( n 一2 ) 个节点在第二 层中的每一个节点，工件序中的前两个位置的工件已排定，在第k 层中，工件序中的 前k 个工件已确定一般的，从第k l 层的一个结点分枝可以产生第七层n k + 1 个结点，每个结点对应前后个位置已排定的部分序事实上不需要考虑剩下的所有 备选分枝，在下面我们给出排序问题( 只) 的一个上界及对于每个节点的剪枝规则 1 、估计上界 首先，我们将所有的工件按照 粕) 及 而a j 可) 的非降序排列，得到的相 应工件序分别记为盯1 和0 2 接着，在工件序盯1 中，我们定义工件集e 及工件集 一e 中部分序分别为0 1 t 和o 1 2 我们将o l l 中的工件按 p i ( 1 一- b a i ) 的非降序排列 得到新的部分序记为一。，构建一个新工件序以= ( 口i 。f f l 2 ) ，相应的最优值为f ( 一) 2 0 0 8 年上海大学硕士学位论文 1 6 然后在工件序a 2 中我们记工件集一t 和t 中的工件序分别为0 2 1 及0 2 2 ，将位 于0 2 2 中的工件按 币a 习i 币) 的非降序排列，得到新的部分序记为吐2 ，构造一个新 序吒= ( 0 2 1 必2 ) ，相应的目标函数值记为f ( 以) 最后，得到排序问题( 只) 的下界为 f m i n = m i n f ( a i ) ，f ( 吐) ) ，相应的工件序为当前最优序 2 、剪枝规则 对于任一节点，假如我们得到一个部分序0 - 1 ，相应的序为( 盯1 ，) 1 、若工件序口1 中的最后一个工件的开工时间不在d 之前，由推论2 1 可知，该节点相 应的最优序为盯= ( 0 1 0 5 ) ，其中部分序o 2 是将工件集n 一0 1 中的工件按照 南) 的非降序排列得到的此时，不需要从该节点分枝相应的最优值为序盯= ( 盯1 0 5 ) 对 应的函数值若该目标函数值比当前最优序对应的目标函数值还小，则仃为当前的 最优序 2 、若工件序盯1 中的最后一个工件的完工时间没有超过d ，用推论2 1 检查盯1 中工件 的顺序即，若工件集e 中的工件不满足按 葡导丽】- 的非降序排列得到，则不需要 从该节点进行分枝 3 、若工件序仃1 中的最后一个工件是一个跨越工件，然后可以按照剪枝规则2 中类 似的方法来处理 下面我们通过一个例子来说明上述算法 例2 25 个工件的参数由表2 2 给出 表2 2 工件j 12345 正常加工时间 1 3586 延误罚因子哟 l 1 5 2 34 超前奖因子岛 0 111 553 其中a = 1 5 ，b = 0 1 ，d = 1 0 由分支定界算法第一步可得到工件序0 1 = ( 1 ，2 ，5 ，3 ，4 ) ，工件序0 2 = ( 2 ，5 ，3 ，4 ，1 ) ， 工件序一= ( 2 ，1 ，5 ，3 ，4 ) ，工件序畦= ( 2 ，5 ，1 ，3 ，4 ) 我们可以得到初始上界r i n = 嘶n 只“) ，致以) ) = 只以) = 1 9 ，初始序为( 2 ，5 ，1 ，3 ，4 ) 由分支定界算法的第二步( 具体步骤略) ，我们最后得到最优序为初始序为( 2 , 5 ，l ，3 ，4 ) ， 2 0 0 8 年上海大学硕士学位论文 1 7 最优值为1 9 2 0 0 8 年上海大学硕士学位论文 1 8 3 简单线性函数的加工时间的超前有奖延误受罚问题 在本章中，我们考虑简单线性函数的加工时间所有工件在时刻t o 到达，每个工 件的加工时间是其开工时间的线性函数，也就是，岛= 幻t ，其中为恶化率，t ( t t o ) 为工件j 的开工时间这个模型首先在m o s h e i o v 1 9 9 4 6 】中提出在简单线性恶化加 工时间下，本章的排序问题可以表示为 1 l 乃= b i t l 2 1 ( 乃一岛易) ( p 2 ) 由于排序问题i i i t j 由y u a n 1 9 9 2 1 4 】证明是p h a r d 的问题，由此我们 猜测1 切= 幻亡i 各1 ( q j t j 一岛e j ) 也是p h a r d 的对于这种模型，在3 1 中列 举了一些最优性引理，同时给出了一些多项式时间可解的特例在3 2 中给出了求 解排序问题( 马) 的一个动态规划算法及相应的算例在3 3 中，在快速估计下界方法 的前提下给出了一个分枝定界算法 3 1一些性质与多项式时间可解的特例 引理3 1 对于排序问题1 i