（运筹学与控制论专业论文）工件加工时间非恒定且工件可拒绝的排序问题.pdf

摘要 排序问题是一类重要的组合优化问题本文提出一类新型的排序问题工 件加工工时间非恒定且工件可拒绝的排序问题，并对这类问题做了初步研究，具体 分为以下几方面； 1 介绍了有关排序问题，计算复杂性及近似算法等的一些基本概念，并对加工 时间菲恒定排序问题及工件可拒绝的排序问题的相关结果做了简要的介绍同时， 阐述了研究加工时间非恒定且工件可拒绝的排序问题理论意义与应用价值 2 工件加工时间是其开始加工时间的线性函数且工件可拒绝的排序问题 对于最小化最大完工时间与拒绝惩罚和的问题，最小化加权总完工时间与拒绝 惩罚和的问题以及最小化最大延迟延误与拒绝惩罚和的问题，我们分别证明了它 们是n p 一困难的，并设计了伪多项式时问的最优算法及充分多项式时间近似算法 3 工件加工时间是其基本加工时间和开始加工时间的线性函数且工件可拒绝 的排序问题 对于最小化最大完工时间与拒绝惩罚和的问题，我们证明了它是n p - 困难的， 并设计了伪多项式时间的最优算法及充分多项式时间近似算法 对于最小化加权总完工时间与拒绝惩罚和的问题，我们证明了它是n p - 困难 的，并对它的一个特例设计了多项式时间的最优算法 4 工件加工时间是其正常加工时问和开始加工时问的线性函数且工件可拒绝 的带优势关系流水作业问题 对于最小化最大完工时间与拒绝惩罚和的问题，最小化总完工时间与拒绝惩罚 和的问题，我们分别设计了多项式时间的最优算法 5 工件加工时间与工件所排位置有关且工件可拒绝的排序问题 对于最小化最大完工时间与拒绝惩罚和的问题，我们分别设计了多项式时间的 最优算法 此外。本文还研究了以下加工时间恒定的问题 。1 证明了加工时间恒定的最小化误工工件个数与拒绝惩罚和的排序问题是n p o 困难的 2 约束条件下加工时间恒定的工件可拒绝的排序问题 对于在拒绝惩罚和的约束条件下最小化最大完工时间的问题，在拒绝惩罚和的 约束条件下最小化最大延迟延误的问题，我们分别证明了它们是n p - 困难的，并 设计了伪多项式时间的最优算法及充分多项式时间近似算法 关键词t 排序；单机；流水作业；恶化工件；工件可拒绝；动态规划；最优算法； 近似算法；充分近似多项式时间算法； i i a b s t r a c t i i i s c h e d u l i n gp r o b l e mi sac l a s so fi 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 m i n t h i sp a p e r ，w ec o n s i d e ran e wc l a s so fs c h e d u l i n gp r o b l e m s - - - - s c h e d u l i n gp o b l e m sw i t h j o b s p r o c e s s i n gt i m e sb e i n gn o n c o n s t a n ta n dr e j e c t i o n t h em a i nr e s u l t si nt h ep a p e ra r e l i s t e da sf o l l o w s ： 1 w ei n t r o d u c es o m eb a s i cc o n c e p t so fs c h e d u l i n gp r o b l e m s ，t h e o r yo fc o m p u t a t i o n a l c o m p l e x i t ya n da p p r o x i m a t ea l g o r i t h m a l s o ，t h em a i nr e s u l t sr e l a t e dt os c h e d u l i n gp r o b - l e m sw i t hj o b s p r o c e s s i n gt i m e sb e i n gn o n c o n s t a n ta n ds c h e d u l i n gp r o b l e m sw i t hr e j e c t i o n a r el i s t e d i na d d t i o n ，w ee x p l a i nw h yi t i sb o t ht h e o r e t i c a l l ya n dp r a c t i c a l l ym e a n i n g - f u lt oc o n s i d e rt h ec o m b i n a t i o no ft h e s et w om o d e l s ，i e s c h e d u l i n gp r o b l e m sw i t hj o b s p r o c e s s i n gt i m e sb e i n gn o n c o n s t a n ta n dr e j e c t i o n 2 s c h e d u l i n gp r o b l e m sw i t hr e j e c t i o n ，a n dw i t hj o b s p r o c e s s i n gt i m e sb e i n gl i n e a r f u n c t i o no ft h e i rs t a r t i n gt i m e s f o rt h eo b j e c t i v e st om i n i m i z et h em a k e s p a n ，t h et o t a lw e i g h t e dc o m p l e t i o nt i m e sa n d t h em a x i m u ml a t e n e s s t a r d i n e s so ft h es c h e d u l e dj o b sp l u st h et o t a lr e j e c t i o np e n a l t i e s ， w es h o wt h a tt h e ya r en p - h a r d ，d e s i g np s e u d o - p o l y n o m i a lt i m eo p t i m a la l g o r i t h m sa n d f u l l yp o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e st os o l v et h e m ，r e s p e c t i v e l y 3 s c h e d u l i n gp r o b l e m sw i t hr e j e c t i o n ，a n dw i t hj o b s p r o c e s s i n gt i m e sb e i n gl i n e a r f u n c t i o no ft h e i rn o r m a lp r o c e s s i n gt i m e sa n ds t a r t i n gt i m e s f o rt h eo b j e c t i v et om i n i m i z et h em a k e s p a no ft h es c h e d u l e dj o b sp l u st h et o t a l r e j e c t i o np e n a l t i e s ，w es h o wt h a ti ti sn p - h a r d ，d e s i g nap s e u d o - p o l y n o m i a lt i m eo p t i m a l a l g o r i t h ma n daf u l l yp o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m et os o l v ei t f o rt h eo b j e c t i v et om i n i m i z et h et o t a lw e i g h t e dc o m p l e t i o nt i m e so ft h es c h e d u l e d j o b sp l u st h et o t a lr e j e c t i o np e n a l t i e s ，w es h o wt h a ti ti sn p h a r d ，a n dd e s i g nap o l y n o m i a l t i m eo p t i m a la l g o r i t h mt os o l v eas p e c i a lc 雠 4 f l o ws h o ps c h e d u l i n gp r o b l e m so nd o m i n a n tm a c h i n e sw i t hr e j e c t i o n ，a n dw i t h j o b s p r o c e s s i n gt i m e sb e i n gl i n e a rf u n c t i o no ft h e i rn o r m a lp r o c e s s i n gt i m e sa n ds t a r t i n g t i m e s f o rt h eo b j e c t i v e st om i n i m i z et h em a k e s p a na n dt h et o t a lc o m p l e t i o nt i m eo ft h e s c h e d u l e dj o b sp l u st h et o t a lr e j e c t i o np e n a l t i e s ，w ed e s i g np o l y n o m i a lt i m eo p t i m a la l g o - r i t h m st os o l v et h e m ，r e s p e c t i v e l y 5 s c h e d u l i n gp r o b l e m sw i t hr e j e c t i o n ，a n dw i t hj o b s p r o c e s s i n gt i m e sr e i a t e dt 0 i v t h e i rp r o c e s s i n gp o s i t i o n s f o rt h eo b j e c t i v et om i n i m i z et h em a k e s p a no ft h es c h e d u l e dj o b sp l u st h et o t a l r e j e c t i o np e n a l t i e s ，w ed e s i g np o l y n o m i a lt i m eo p t i m a la l g o r i t h m st os o l v ei t i na d d t i o n ，w es t u d yt h ef o l l o w i n gs c h e d u n n gp r o b l e m sw i t hj o b s p r o c e s s i n gt i m e s b e i n gc o n s t a n t 1 s c h e d u l i n gp r o b l e m sw i t hr e j e c t i o n ，a n dw i t hj o b s p r o c e s s i n gt i m e sb e i n gc o n - s t a n t f o rt h eo b j e c t i v et om i n i m i z et h en u m b e ro fl a t ej o b so ft h es c h e d u l e dj o b sp i n st h e t o t a lr e j e c t i o np e n a l t i e s ，w es h o wt h a ti t i sn p - h a r d 2 s c h e d u l i n gp r o b l e m sw i t hr e j e c t i o nu n d e rt h ec o n s t r a i n to ft h et o t a lp e n a l t i e so f t h er e j e c t e dj o b s f o rt h eo b j e c t i v e st om i n i m i z et h em a k e s p a n t h et o t a lw e i g h t e dc o m p l e t i o nt i m e s a n dt h em a x i m u m l a t e n e s s t a r d i n e s so ft h es c h e d u l e dj o b su n d e rt h ec o n s t r a i n to ft h et o t a l p e n a l t i e so ft h er e j e c t e dj o b s ，w es h o wt h a tt h e ya r en p h a r d ，d e s i g np s e u d o - p o l y n o m i a l t i m eo p t i m a la l g o r i t h m sa n df u l l yp o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e st os o l v et h e m ， r e s p e c t i v e l y k e y w o r d s ： s c h e d u l i n g ；s i n g l em a c h i n e ；f l o ws h o p ；d e t e r i o r a t i o nj o b ；r e j e c t i o n ； d y n a m i cp r o g r a m m i n g ；o p t i m a la l g o r i t h m ；a p p r o x i m a t i o na l g o r i t h m ；f u n yp o l y n o m i a l t i m ea p p r o x i m a t i o ns c h e m e s ； 原创性声明 本人声明t 所呈交的论文是本人在导师指导下进行的研究工作除了 文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写 过的研究成果参与同一工作的其他同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意 群纷嗍咖以畎“ 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有 权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布 论文的全部或部分内容 ( 保密的论文在解密后应遵守此规定) 签名锄目导师躲 日期潲州彤 第一章引言 1 1 排序问题( s c h e d u l i n gp r o b l e m s ) 简介 排序问题( s c h e d u l i n gp r o b l e m ) ( 参见b a k e r ( 1 9 7 4 ) ，p i n e d o ( 2 0 0 2 ) ，g r a h a me ta 1 ( 1 9 7 9 ) ) 是运筹学( o p e r a t i o n sr e s e a r c h ) 的个分支，是一类重要的组合优化问题( c 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 m ) 在理论上它与算法设计和计算复杂性( t h e o r yo fc o m p u t a t i o n a lc o m p l e x i t y ) 密切 相关，同时，它又广泛应用于管理科学、计算机科学、工农业生产，交通运输等领 域因而，排序问题一直受到国际上学术界的重视从深层次和长远来看，排序问 题的研究对提高效率、资源的开发和配置、工程进展的安排以及经济运行等方面都 能起到辅助科学决策的作用 一般地说，排序问题由机器( m a c h i n e ) 的数量，种类，环境以及作业性质和目 标函数构成通常我们称被加工的对象为工件( j o b ) 由竹个工件组成的集合记为 n = 以，厶 ，其中乃表示的第歹个工件 加工工件由机器来处理我们将m 台机器组成的集合记为m = 舰， ， 用坞表示第歹台机器只有一台机器的排序问题称为单机排序问题( s i n g l em a c h i n e s c h e d u l i n gp r o b l e m s ) ，否则称为多机排序问题( m u l t i p l em a c h i n e ss c h e d u l i n gp r o b l e m s ) 下面介绍一些排序问题的基本概念。 工件j 的加工时间向量鳓= 伽u ，姗 ，其中，肋表示工件歹在机器尬上 所需的加工时间 工件j 的到达时间( a r r i v a lt i m e ) 或准备时间( r e a d yt i m e ) 吩，它表示工件j 的 可以开始加工的时间 工件j 的交货期d j 工件歹的权重吻，表示工件j 的重要程度 用。表示工件j 的完工时间 工件的最大完工时间tg m = 僦z 0 ，j = 1 n ) 工件的最大延迟t k 眦= 僦z 岛一d j ，j = 1 礼 工件的最大延误t 晶m = 僦z q 一吗，o ) ，j = 1 n ) 误工工件；当= 1 时，称工件j 为误工工件，其中， 1 2 0 0 8 年上海大学硕士学位论文2 阮： 1 ，印呜 。 10 ，q 嘞 对于排序问题，国际上通常用g r a h a me ta t ( 1 9 7 9 ) 的三参数法来表示，即用q 俐7 来表示其中，口，卢，1 的意义如下 ( 1 ) a 指机器环境 机器可以是单台，也可以是多台对于多台机来说，按照功能可分为两大类： 即平行机( p a r a l l e lm a c h i n e s ) 和专用机( d e d i c a t e dm a c h i n e s ) 前者又可分为三类。 1 不同机器的加工速度完全致，且其速度不依赖于工件，称为同型机( i d e n t i c a l m a c h i n e s ) ，记为p 2 不同机器的加工速度不同，且其速度不依赖于工件，称为同类机( u n i f o r m m a c h i n e s ) ，记为q 3 机器的加工速度依赖于工件，称为异型机( u n r e l a t e dm a c h i n e s ) ，记为r 对于专用机来说也可分为三类； 1 流水作业( f l o ws h o p ) ，记为f 2 自由作业( o p e ns h o p ) ，记为d 3 异序作业o o bs h o p ) ，记为， ( 2 ) p 指特定的加工限制和约束 常出现的加工限制和约束有。工件j 需准备时间，有交货期，工件闯存在偏序 关系( 即优先加工约束，p r e c ) ，对工件的加工允许中断继续( p 彻p ) 等 ( 3 ) 7 指目标函数 目标函数一般根据实际需要来确定，在排序问题中常用的最小化目标函数有。 ，工一，正，琳，q ，乃，哟0 ，嘶乃，哟巧等 1 2 计算复杂性理论( t h e o r yo fc o m p u t a t i o n a lc o m p l e x i t y ) 对于排序问题这样类最优化问题( o p t i m i z a t i o np r o b l e m ) ，我们总是力图设计出 一些算法来求出问题的最优解，并用计算复杂性理论( 参见g a r e ya n dj o h n s o n ( 1 9 7 9 ) ) 来分析算法下面给出一些计算复杂性理论的概念 算法算法( a l g o r i t h m ) 是一步步求解问题的的通用程序 最优算法对于最优化问题万，若算法a 可以应用于7 r 的任意实例j ，并且能保 证得到j 的一个最优解，则称算法a 是问题，r 的一个最优算法( o p t i m a la l g o r i t h m ) 算法的计算复杂性对于最优化问题丌及其算法a ，算法a 的计算复杂性是指 对于问题霄任意实例，的可能输入长度执行该算法所需要的最长时间 2 0 0 8 年上海大学硕士学位论文3 设问题，r 的某个实例j r 用算法a 求解时，其输入长度为l ( 输入字符数) 若存 在一个一元多项式函数p ( z ) 使得算法a 的复杂性为d ( l ) ) ，则称算法a 是多项 式时间的( p o l y n o m i a lt i m e ) 否则称算法a 是指数时间的 判定问题复杂性的概念一般是针对判定问题( d e c i s i o np r o b l e m ) 来定义的某 问题若能用。是”或。否。来回答其解的结果称为判定问题任何最优化问题都存 在其相应的判定问题 p 类问题若某一判定问题存在某一算法，能在多项式时间内给出正确答案， 则称该问题属于尸类( p o l y n o m i a l ) n p 类问题若某一判定问题存在某一算法，对于答案为。是”的实例，首先给 出个猜想，而后验证这个猜想也仅需多项式时间，则称该问题属于n p 类( n o n - d e t e r m i n i s t i cp o l y n o m i a l ) 至于是否pcn p ，至今没有结论，一般猜想p p 多项式归约设有两个问题n 和1 2 ，若存在一个多项式函数，能将7 1 中的 任何一个实例，变换到7 1 中的个实例，( ，) ，并且满足t ，的答案为。是”当且 仅当f ( i ) 的答案为。是”，则我们称1 1 可以多项式归约( p o l y n o m i a l - t i m er e d u c i b l e ) 到您，记为7 1o ( 砣 p 困难对于某个问题r ，若n p 类中的所有问题都可以多项式归约到它， 则称丁为n p - 困难的( n p h n r d ) 尸完全性对于n p 类中的某个问题f ，若n p 类中的所有问题都可以多项 式归约到它，则称f 为n p - 完全的( n p c o m p l e t e ) 对于p 类问题，它们的难易程度也有差别 伪多项式时间可解p 类问题中一类相对容易一些的是伪多项式时间可解 p s e u d o - p o l y n o m i a lt i m es o l v a b l e ) 的问题对于某问题，若存在某算法，其计算复杂 性函数是关于问题实例j 的输入长度l e n g t h ( i ) 以及出现的最大数m 凹( ，) 二者的 多项式函数，则称该算法是伪多项式时间算法( p s e u d o - p o l y n o m i a lt i m ea l g o r i t h m ) ， 该问题是伪多项式时间可解的 一般意义下n p - 困难及强n p 困难对于存在伪多项式时间算法的n p 问题， 称之为一般意义下n p - 困难的问题( n p h a r dp r o b l e m si no r d i n a r ys e w ) 否则，则 称之为强n p 困难的问题( n p h a r dp r o b l e m si ns t r o n gs e n s e ) 1 3 近似算法( a p p r o x i m a t ea l g o r i t h m ) 许多最优化问题被证明为n p 一困难的，即它们不存在多项式时间的最优算法 对于这些问题，人们常常采用以下途径。 1 寻找多项式时间的近似算法 2 0 0 8 年上海大学硕士学位论文4 2 寻找在哪些特殊情况下该问题具有多项式时间的最优算法 p 近似算法对于一个最小化问题，如果某算法a 得到的解至多是最优解的 ( 1 + p ) 倍，p 0 ，则称算法a 是该问题的个p 近似算法( p a p p r o x i m a t i o ns c h e m e ) 充分多项式时间近似算法对于个最小化问题和一组算法 a t ，e o ) ，若对 于任意e 0 ，算法a 是该问题的( 1 + e ) 一近似算法，并且其计算时间是输入规模和 ；的多项式倍，则 a ? ，e o ) 为该问题的充分多项式时间近似算法( f u l l yp o l y n o m i a l t i m ea p p r o x i m a t i o ns c h e m e ) ，简称f p t a s 1 4加工时间非恒定的排序问题( s c h e d u l i n gp r o b l e m sw i t hj o b s p r o c e s s i n gt i m e sb e i n gn o n c o n s t a n t ) 在经典问题中，通常假设工件的加工时间是不变的 ( 参见b a k e r ( 1 9 7 4 ) ，g r a - h a m ( 1 9 7 9 ) 及p i n e d o ( 2 0 0 2 ) ) 然而，在许多实际问题中，工件的加工时间由于加工机 器设备，工件本身以及加工顺序等的因素的影响而不可能始终是恒定的这样的例 子很多比如实际问题中，机器的加工效率降低会导致工件加工时间的增长又如 在钢铁企业中，某些工件的加工有温度的要求如果工件在加工前有等待时间，将 引起工件温度的下降这样一来，无论是重新加温使其满足温度要求还是在不满足 温度要求的低温下加工，都将导致加工时间的增加与此同时，在许多情况下，工 件加工时间会减少比如，工人在实际操作中不断学习，积累经验，也可导致工件 加工时间的减少由此，产生了一类重要的新型排序问题工件加工时间非恒 定的排序问题( s c h e d u l i n gp r o b l e m sw i t hj o b s p r o c e s s i n gt i m e sb e i n gn o n c o n s t a n t ) 一 般地说，此类排序比经典的排序问题更为复杂，绝大多数均为n p 困难的问题 g u p t aa n dg u p t a ( 1 9 8 8 ) 与b r o w n ea n dy e c h i a l i ( 1 9 9 0 ) 提出了恶化工件( d e t e r i o r a t - i n gj o b ) 的概念，e p m 件的加工时间是其开始加工时间的递增函数他们假设工件的 实际加工时间为叼+ 如( 0 ) ，其中口，6 j ，t 分别为工件歹的基本加工时间，恶化 率及开始加工时间，并证明了 a j l b j 的非降序为最小化最大完工时间的最优排序 m o s h e i o v ( 1 9 9 1 ) 考虑a + b ，t 下的最小化运行时问和问题，并证明了6 f 的y 型序为最 优排序b a c h m a na n dj a n i a k ( 2 0 0 0 ) 与b a c t m a a ue ta 1 ( 2 0 0 2 ) 分别证明了最小化最大延 迟与最小化加权总完工时间这两个问题是n p - 困难的m o s h e i o v ( 1 9 9 4 ) 提出了简单 线性恶化工件( s i m p l ed e t e r i o r a t i n gj o b ) 的概念，即所有工件的基本加工时间都为0 他给出了最小化最大完工时间，运行时间和，加权运行时问和，最大延迟，最大延误及 误工个数这些问题的多项式时间的最优算法m o s h e i o v ( 1 9 9 5 ) 又研究了简单线性恶 化工件的平行机排序问题，并证明了最小化最大完工时间问题是n p 困难的同时， 2 0 0 8 年上海大学硕士学位论文5 c h e n ( 1 9 9 6 ) 证明了最小化总完工时间问题是n p 困难的c h e n ga n dd i n g ( 2 0 0 1 ) 研 究逐步恶化( s t e p - d e t e r i o r a t i n g ) 的模型并为时间表问题设计了一个伪多项式时间的 最优算法k o n o n o va n dg a w i e j n o w i c z ( 2 0 0 1 ) 研究了多台加工机器上的恶化工件的排 序问题其他考虑加工时间恶化工件的排序模型可以参见m o s h e i o v ( 1 9 9 5 ) ，i - i s i e ha n d b r i c k e r ( 1 9 9 7 ) ，c a je ta 1 ( 1 9 9 8 ) ，n ge ta 1 ( 2 0 0 2 ) ，w ua n dl e e ( 2 0 0 3 ) ，z h a oa n dt a n g ( 2 0 0 5 ) ， m o s h e i o v ( 2 0 0 5 ) ，j e n ga n dl i n ( 2 0 0 5 ) ，g a w i e j n o w i c ze ta 1 ( 2 0 0 6 ) ，b o s i oa n dr i g h i n i ( 2 0 0 6 ) ， w ua n dl e e ( 2 0 0 6 ) ，j ie ta 1 ( 2 0 0 6 ) ，w a n ga n dx i a ( 2 0 0 6 ) ，w a n ga n dc h e n g ( 2 0 0 7 ) ，w a n ge t a 1 ( 2 0 0 6 ) ，b a r k e t a ue ta 1 ( 2 0 0 t ) ，g a w i e j n o w i c z ( 2 0 0 7 ) ，w a n g ( 2 0 0 7 ) ，k a n ga n dn g ( 2 0 0 7 ) ， l e ee ta 1 ( 2 0 0 7 ) ，c h e n ge ta 1 ( 2 0 0 7 ) ，l e ea n dw ( 2 0 0 s ) ，l e ee ta 1 ( 2 0 0 8 ) ，o r o n ( 2 0 0 8 ) ，w u e ta 1 ( 2 0 0 a ) ，l e u n ge ta 1 ( 2 0 0 8 ) ，j ia n dc h e n g ( 2 0 0 8 ) ，w a n ge ta 1 ( 2 0 0 8 ) 等等 b i s k u p ( 1 9 9 9 ) 提出具有学习效应( 1 e a r n i n ge f f e c t ) 的排序问题此类问题假设工 件的加工效率会越来越高，即工件越往后加工，所需时间越少针对这类问题的 研究可以参见m o s h i e o v ( 2 0 0 1 ) ，m o s h i e o v ( 2 0 0 3 ) ，b i s k u pa n ds i m o n s ( 2 0 0 4 ) ，k u oa n d y a n g ( 2 0 0 6 ) ，k u oa n dy a n g ( 2 0 0 6 ) ，c h e n g e ta 1 ( 2 0 0 7 ) ，w ue ta 1 ( 2 0 0 7 ) ，w ua n dl e e ( 2 0 0 7 ) ， k u oa n dv a n g ( 2 0 0 7 ) ，k o u l a m a sa n dk y p a r i s i s ( 2 0 0 7 ) ，k u oa n dy a n g ( 2 0 0 7 ) ，w a n g ( 2 0 0 7 ) ， e r e n ( 2 0 0 8 ) ，w a n ge ta 1 ( 2 0 0 s ) ，w a n g ( 2 0 0 8 ) ，c h e n ge ta 1 ( 2 0 0 8 ) ，y a n ga n dc h a n d ( 2 0 0 8 ) ， b i s k u p ( 2 0 0 8 ) 等等 另外，关于加工时间非恒定排序问题的综述可以参见a l i d a e ea n dw o m e r ( 1 9 9 9 ) ， c h e n ge ta 1 ( 2 0 0 4 ) 1 5 工件可拒绝的排序问题( s c h e d u l i n gp r o b l e m sw i t hr e j e c t i o n ) 与此同时，经典排序问题假设所有工件必须加工，而在实际问题中有时某些工 件的加工是可以不进行的例如有的工件加工时间非常长，或费用很大，于是不加 工这一工件，而是通过支付一定的费用后送到外面去“外加工。或购买更合算这 样，选择哪些工件加工，哪些工件不加工( 即拒绝加工) 也是需要决策的这时我们 所考虑的排序问题，既要使常规的目标函数为最优，又要使拒绝加工工件所支付的 费用( 称为拒绝惩罚，r e j e c t i o np e n a l t y ) 最小我们把这类问题称为工件可拒绝的排 序问题( s c h e d u l i n gp r o b l m e sw i t hr e j e c t i o n ) ，用三参数表示法工件可拒绝排序可表示 为1 | r 巧i ，其中r 巧表示工件可拒绝目前，工件可拒绝的排序问题工的研究成果 还不多 2 0 0 8 年上海大学硕士学位论文 6 b a r t a le ta 1 ( 1 9 9 6 ) 引入了工件可拒绝( r e j e c t i o n ) 的概念他们考虑工件可拒绝 的同型机排序问题每个工件有个加工时间及以拒绝费用对于最小化最大完工 时间与总拒绝费用和的在线问题，他们给出了个( 1 + 雪) 算法，其中西是黄金分 割率对于同样的目标函数，s e i d e n ( 2 0 0 1 ) 考虑了可中断情况下的在线问题并给出 了个2 3 8 算法对于两台同类机及三台同类机的一个特殊情况，h ee t8 1 ( 2 0 0 0 ) 对于某个速率s 给出了最佳在线算法h o o g e v e ne ta 1 ( 2 0 0 0 ) 为可中断情况下的异 型机问题设计了一个1 5 8 - 算法对于加权总完工时间问题，e n g e l se ta 1 ( 1 9 9 8 ) 证 明了离线情况是一般意义下n p 困难的，并给出了一些算法e p s t e i ne ts 1 ( 2 0 0 2 ) 研究了在线情况下单位权并且单位加工时间的特殊情况s e n g u p t a ( 2 0 0 3 ) 研究了最 小化最大延迟及延误问题其他考虑工件可拒绝的文献有c a oe ta 1 ( 2 0 0 6 ) 与l ue t a 1 ( 2 0 0 8 ) 1 6 本文的主要研究内容t 加工时间非恒定且工件可拒绝的排序问题 ( s c h e d u l i n gp r o b l e m sw i t hj o b s p r o c e s s i n gt i m e sb e i n g n o n c o n s t a n ta n dr e j e c t i o n ) 从现有研究情况来看，加工时间非恒定的排序问题被国内外广泛地研究，工件 可拒绝的排序问题也有了一定的成果 然而，同时考虑加工时间非恒定与工件可拒绝的排序问题还没研究过因为这 两个概念都是现实生活的模拟，所以考虑这两种模型的结合是有意义的决策者可 以选择部分工件在加工时间非恒定的环境中加工，拒绝其他工件并支付拒绝费用 该模型的一个例子可以在工件加工中找到t 一些工件需要在一台机器上加工机器 在加工工件的过程中会磨损而减低加工效率，因而当一个工件较晚加工时，它需要 较多的加工时间这样，加工所有的工件也许不是最佳决策，决策者可以将部分 工件外包加工该模型的另个例子可以在陶瓷加工中找到陶瓷加工的主要步骤 是根据设计对原材料进行塑形原材料主要由粘土组成由于原材料会随放置时间 的增加而变硬，工人将花更多的时间来塑形那些较晚加工的原材料这样，某个陶瓷 工厂的决策者会考虑请其他工厂的工人对一些原材料进行塑形，并支付他们费用 本文研究了这样一类既考虑加工时间非恒定又考虑工件可拒绝的新问题( s c h e d u l - i n gp r o b l e m sw i t hj o b s p r o c e s s i n gt i m e sb e i n gn o n c o n s t a n ta n dr e j e c t i o n ) ，具体考虑以 下这些加工时间的可变方式- 1 工件加工时间是其正常加工时间和开始加工时问的线性函数 即，乃= 叼+ b i t ( 吩 o ，b j o ) 2 0 0 8 年上海大学硕士学位论文 7 2 工件加工时间是其开始加工时间的线性函数 即，功= b t ( b o ) 3 工件加工时间与工件所排位置有关 即，功= 产( 口 0 ) ， 乃= 勺严( 口o ) ， 乃= 口r - 1 ( d 1 ) ， 聊= 吩矿_ 1 ( 0 o ) ，其中叼，b ，t 分别为工件j 的基本加工时间，恶化率 及开始加工时间之后，带恶化工件的排序问题被广泛研究，可参见m o s h e i o v ( 1 9 9 1 ) ， m o s h e i o v ( 1 9 9 5 ) ，h s i e ha n db r i c k e r ( 1 9 9 7 ) ，c a ie ta 1 ( 1 9 9 8 ) ，a l i d a e ea n dw o m e r ( 1 9 9 9 ) ， b a c h m a na n dj a n i a k ( 2 0 0 0 ) ，c h e n ga n dd i n g ( 2 0 0 1 ) ，c h e n ge ta l 。( 2 0 0 i ) ，k o n o n o va n d g a w i e j n o w i c z ( 2 0 0 1 ) ，n ge ta 1 ( 2 0 0 2 ) ，b a c h m a ne ta 1 ( 2 0 0 2 ) ，w ua n dl e e ( 2 0 0 3 ) ，c h e n ge t a 1 ( 2 0 0 4 ) ，z h a oa n dt a n g ( 2 0 0 5 ) ，m o s h e i o v ( 2 0 0 5 ) ，j e n ga n dl i n ( 2 0 0 5 ) ，g a w i e j n o w i c ze t a 1 ( 2 0 0 6 ) ，b o s i oa n dr i g h i n i ( 2 0 0 6 ) ，w ua n dl e e ( 2 0 0 6 ) ，j ie ta 1 ( 2 0 0 6 ) ，w a n ge ta 1 ( 2 0 0 s ) ， w a n ga n dx i a ( 2 0 0 6 ) ，w a n ga n dc h e g ( 2 0 0 7 ) ，b a r k e t a ue ta 1 ( 2 0 0 7 ) ，g a w i e j n o w i c z ( 2 0 0 7 ) ， w a n g ( 2 0 0 t ) ，k a n ga n dn g ( 2 0 0 7 ) ，l e e e ta 1 ( 2 0 0 z ) ，c h e n ge ta 1 ( 2 0 0 t ) ，l e ea n dw u ( 2 0 0 8 ) ， l e ee ta 1 ( 2 0 0 8 ) ，o r o n ( 2 0 0 8 ) ，w ue ta 1 ( 2 0 0 s ) ，l e u n ge ta 1 ( 2 0 0 8 ) ，j ia n dc h e n g ( 2 0 0 8 ) ， w a n ge ta 1 ( 2 0 0 8 ) 等等 m o s h e i o v ( 1 9 9 4 ) 提出了简单线性恶化工件( s i m p l ed e t e r i o r a t i n gj o b s ) 的概念，即 所有工件的基本加工时间都为0 他给出了最小化最大完工时间，运行时间和，加权 运行时间和，最大延迟，最大延误及误工个数这些问题的多项式时间的最优算法 m o s h e i o v ( 1 9 9 5 ) 还研究了简单线性恶化工件的平行机排序问题，并证明了最小化最 大完工时问问题是n p 困难的同时，c h e n ( 1 9 9 6 ) 证明了最小化总完工时间问题 是n p - 困难的 工件加工时间是其开始加工时间的线性函数且工件可拒绝的排序同题，即考虑 简单线性恶化工件且工件可拒绝的问题还没有被研究在本章中，我们考虑单机情 况下的此类问题 考虑这样的加工时间非恒定的模型：乃= b i t