（应用数学专业论文）加工时间线性恶化的排序问题.pdf

国防科学技术大学研究生院学位论文 摘要 排序问题是一类重要的组合最优化问题在经典排序问题中通常假设任务的加工 时间为常数，但在许多实际问题中，常出现任务加工时间随其开始加工时间推后而增 长的现象本文结合实际应用背景，突破经典排序中任务加工时间为常数的限制，研 究任务加工时间线性恶化的机器排序问题这类模型比相应的经典排序问题更复杂， 绝大多数是n p 难问题本文主要在如下几个方面作了一些工作： 1 最小化加权总完工时间的单机排序问题在任务加工时间简单线形恶化下，根 据平行链约束中关键任务优先规则，本文对任务间具有树约束的排序问题，提出了最 大家庭树优先规则，进而给出了复杂性为d ( 玎2 ) 的最优算法当任务间具有一般约束 时，给出了该问题的一些性质，并构造了近似算法 2 最小化完工时间的平行机排序问题通过子乘积问题，本文证明了问题p 2 】p = 口，s ，jc 。的n p 困难性在简单线形恶化下，本文把对同速机的研究推广到恒速机 的情况，对恒速机排序问题q ，圳p ，= 口，s ，ic 一，给出了复杂性分别为d ( ，z ) 和d ( h 2 ) 的两种启发式算法，并分析了这两种算法的绝对性能比 3 最小化完工时间的流水作业排序问题在作业加工时间简单线形恶化下，为了 构造满足约束条件的复合作业，本文提出了作业的非负开始和停止延迟恶化率，给出 作业间具有平行链约束和串并有向图约束的两台处理机流水作业排序问题的最优多 项式算法；对n p 难问题f 2 l 岛= 蜀+ 口d 岛i c 一，通过定义处理机间的优势关系， 得到处理机在满足优势关系下，线形恶化最小化完工时间的流水作业排序问题砌l 岛= + 磊i c 二的多项式算法 关键字：排序；单机；平行机；流水作业；加工时间恶化；约束条件；最优算法； 启发式算法 第1 页 国防科学技术大学研究生院学位论文 a b s t r a c t s c h e d u l i n gi sa i ii m p o r t a mc o m b h a t o r i a lo p t i m i z a “o np r o b l 舢n i nt h ec i 髂s i c a ls c h c - d 1 1 l i n gi ti su s u a l l ya s s 啪e dt h a tm ep r o c e s s i n gt i i n e so ft 1 1 e t a s k sa r ec o n s t a n tv a l u e s h o w e v e r ，t h ep h e n o m e n o nm a tt h ep r o c e s s i n gt i m eo ft h et a s ki si n c r e a s e d 谢t l li t ss t a m i 冯 t h ed e l a y e do f t e no c c l l r si i lm a n yp r a c t i c a ls i t 删o n s h lt h i sp a p c r ，t l l es c h e d u l i n go f l i i l e a rd e t e r i o r a t m gp r o c e s s m gt i m ei ss t u d i e db yb r e a c h 抽gt l l ec o n s t a r l tr e s t r i c t i o no ft h e p r o c e s s i n gt i m e sd f 也et a s k si nm ec l a s s i c a ls c h e d u l i n g 。t h em o d e l sa r em o r ec o m p l e x t h a nc l a s s i c a ls c h e d u l i n gp r o b l e m s ，m o s to f w h i c ha r en p t l 瓤p r o b k m s t h em a i nc o n t r i - b u t i o n si nm i sp 印e rc a nb es u m m a r i z e da sf o l l o w s ： 1 。m i n i n l i z et 1 1 et o “w e i 曲t e dc o m p 】e t i o nt i m es 咄l en l a c l l i n es c h e d u l i n gp r o b l e m s u n d e r 恤s i i n p l el i n e a rd e t e r i o r a t i n g ，a c c o r d i n gt ot l ：l ep d o d 移r u l eo fn l ek e yt a s k 砸t i l p a r a l l e lc h 硝咀sc o n s t r a i n t st 嬲k s ，t h ep r i o r i t yr u l eo fm em a x i m a lf h m i l yt r e e 耐t l ln e p r e c e d e n c ec o n s 仃a i n t si sp r c s 盯此d m o r e o v e r ，t h e 叩t i m a lp o l y n o m i a la l g 鲥s 、v i t ht h e t i m ec 伽叩l e x i 母o f0 ( h 2 ) a r eg h c n f o rt h es i m p l el i n e 甜d e t e r i o r a t b gm o d e lw i t hg e n e r a lp r e c e d e n c ec o n 删n t s ，s o m ep m p e n i e sa r eo b t a i n e d ，如r d l e h n o r e ，a na p p r o x i m a t ea l g o r i 也mi sc o n s 舡1 l c t e d 2 m i n i m i z et l l em a k e s p a np a m l l e lm a c h i i l es c h e d i l l i n gp r o b l e m s t h en p - h a r dp m b l e m p 2 忉，= 口，s ，| c 嘣i s p r o v e d b y s u b s e t p m d u c t i o n p r o b l e m i n m i s p a i 赋u n d e r 恤s i - m p l el 曲e a rd c 哇e r i o m t i n g ，t h ep m b l e mo f i d e n t i c a lp r o c e s s o ri se x t e n d e dt o 蛹f o 玎np f o c e s s o rc 船e ，f o r 也ep r o b l e m ( 抑1p ，= 口，s ，i c 黼，m e 卸oh e u r i s t i ca l g o d l h m s 诚m1 h et i m e c o i n p l e x 姆o f d ( 疗) a n dd ( 疗2 ) a r e 舀v e nr c s p c c t i v e l y 蚰dt l l ea b s o l u t ep e r f o 瑚如c er a t i oo f t h e “a l g o r i m m sa r ea n a l y d 3 m i n i 商z e 血em a k c s p a i ln o ws h o ps c h e d i l l i n gp r o b l e m s u n d e rt l l e s i m p l el i n e a r d e 州o r a t m g ，n o i m e g a t i v es t a r t 锄ds t 叩l a gd e t e r i 删n gr a t e sa r ei i l 订o d u c e ds oa st o c o l l s t n l c tc o m p o s i t ej o b ss a t i s f 甄n gp r e c e d e n e er e l a t i o n s b a s e do nm o s e ，t h eo p t i m a l p 0 1 y n o i n j a la l g o r l m m sa r eg i v e nf o rt h e 柳。一m a c h m en o ws h o ps d l e d l | 1 m gp r o b l c m 、v i t h t l l es i m p l el i n e a rd e t e r i o r a t i n gm o d e lw i t hc l l a i n s 趿ds e r i e s p 删l e ld i 铲印h sp r c c e d e n c e c o i l s 觚i n t s j o b sr e s p e c t i v e i yf o r t l l e n p - h a r d p r o b l 锄f 2 f 既= + 西f c o b y d e f i n i n gd o m i m t i n gr c l a t i o n s 锄o n gp r o c s s o r s ，伍ep 0 1 y n o m i a la l g o 打t l l i n sa r eg i v e nu n d e rm e d o m m a t i n gp r o c s s o r sr e s p e c t i v e l yf o rt 1 1 eg e n e f a ll i n e a rd e t e r i o r a t i n gt h en o ws h o ps c h e d u i i n g p f o b i 锄，m f p f = 彳f + a p s i c 眦 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 l l i n e ；p a r a l l e lm a c h 访e ；n o ws h o p ；d e t e r i o r a t i n g p r o c e s s i n gt i i n e ；c o n s t r a i n tc o n d i 廿o n ；o p t 劬a 1a l g 耐t l l i n s ；h e 嘶s t i ca l g o m 第页 国防科学技术大学研究生院学位论文 图1 1 - 1 图1 1 2 图1 1 3 表2 2 1 图2 2 1 图2 3 1 图3 2 1 图3 2 2 图4 2 1 图4 2 2 表4 2 1 图4 3 1 图4 3 2 图4 3 3 图4 4 1 图4 4 2 图4 4 3 图表目录 任务间优先约束图 链、入树和出树 例1 1 3 的g a n t t 图 任务的权值和恶化率 任务问优先约柬图 初始约束图( a ) 和变换后的约束图( b ) 加工方式( a ) 加工方式( b ) 作业序列盯 排序万，万。的加工次序 作业的恶化率向量 可迁的串并有向图 图4 3 1 对应的二叉树 链的形成过程 模型( 1 ) 的加工方式一 模型( 2 ) 的加工方式一 模型( 3 ) 的加工方式一 第i i 页 _ _ o h h m砣鸵”凹”砣匏”巧” 独创性声明 y 8 86 3 8 8 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：拉王盟间堡挂墨丝塑韭庄回塑 学位论文作者签名：聋! ! l 基 日期：知喀年1 1 月i s 日 学位论文版权使用授权书 本入完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 垄王盟回垡! 眭墨些盟盐压闷题 学位论文作者签名： 聋m l 塞 日期： 动。孓年月f 皇日 作者指导教师签名：i 9丝日期：纠年，月加日 国防科学技术大学研究生院学位论文 第一章绪论 一直以来排序问题都受到国际上学术界的重视题为美国国防部与数学科学研 究的报告认为，2 0 世纪9 0 年代以至2 l 世纪数学发展的重点，将从连续的对象转 向离散的对象，并且组合最优化将会有很大的发展，因为“在这个领域内存在着大量 急需解决而又极端困难的问题，其中包括如何对各个部件进行分隔、布线和布局的问 题”这“分隔、布线和布局”就与排序有关 排序( s c h e d u l i n 曲问题也称调度问题，是组合优化中一个重要的分支它是利用一 些处理机( p r o c e s s o e ) 、机器( m a c l l i n e ) 或资源( r e s o u r c e ) ，最优地完成一批给定的任务 ( t a s k ) 或工件( i o b ) 在执行这些任务时，需要满足某些限制条件，如任务的准备时间、 任务的加工次序等等最优的完成是指目标函数达到最小，而目标函数通常是对加工 时间长短，机器利用率高低的描述排序问题最早起源于机器制造业，现已逐渐发展 成为运筹学、系统科学、控制科学、管理科学和计算科学等多个学科领域的交叉学 科广泛应用于工程技术和经济管理的各个领域作为一门应用科学，它在作业安排、 制造工厂的最优设计、交通枢纽的排序及工程进度的控制等方面有着深刻的实际背景 和广泛的应用前景随着现代工业的发展，排序论中的“机器”和“工件”已不是单纯的 机器制造业中的“车床”和“车床加工的螺丝”，已经从“车床”和“螺丝”等具体事物中抽 象出来，是抽象的，一般的概念排序中的“机器”可以是数控机床、计算机中央处理 器、医生、机场跑道等等，“工件”可以是零件、计算机终端、病人、降落的飞机等等因 此排序问题中，工件是被加工的对象，是要完成的任务机器是提供加工的对象，是 完成任务所需要的资源排序是指在一定的约束条件下对任务和机器按时间进行分配 和安排次序，使某一个或某一些目标达到最优排序是安排时间表的简称这里机器 和任务可以代表及其广泛的实际对象 总之，从普通生产部门计划安排、人员调度、学校课程表制订，到宇宙飞船复杂 庞大的飞行计划，都要用到排序的理论和算法 1 1 排序中的一些基本知识 排序问题是一个相当广泛的研究领域，包含大量的不同模型，算法和结果适用 于某一模型的算法，只要将模型的条件稍加变化，该算法则不适用即使是一个小范 围领域内的排序问题也包含几页因此我们只介绍与本论文直接相关的概念其他概 第1 页 国防科学技术大学研究生院学位论文 念读者可参考文献【1 【2 】 3 1 1 1 排序问题的定义 给定n 个任务的任务集r = 正，疋，l ) ，m 台处理机的处理集p = e ，b ， 只 ，j 种资源的资源集r = 置，r ：，r ，) 排序问题是在一定条件下，为完成各项 任务，把p 中的处理机和月中的资源分配给r 中的任务，使目标函数达到最优在不 引起混淆的情况下，有时用任务的下标直接表示该任务 排序问题基本上是由处理机的数量、种类与环境，以及任务或作业的性质和目标 函数所组成 处理机 只有一台处理机的排序问题称为单( 处理) 机( s i i l 酉ep r o c e s s o r ) 排序问题，否则称为 多( 处理) 机排序问题 在多处理机排序问题中，如果所有处理机都具有相同的功能，则称它们为同类机 或平行机( p a r a l l e lp r o c e s s o r s ) 平行机按处理的速度分为三种类型：如果所有的处理 机具有相同的速度，则称之为同速机( i d e “c a lp r o c e s s o r s ) ：如果处理机的速度不同， 但每个处理机的速度都是常数，不依赖被加工的任务，则称它们为恒速机f o 】f i n p r o c e s s o r s ) ；如果处理机的速度依赖被加工的任务，则它们被称为变速机( u n r c l a t e d p r o c e s s o 哟 多处理机的另一种情况是多类型机( d e d i c a t e dp r o c e s s o r s ) 多类型机指的是m 个处 理机具有不同的功能在多处理机环境中，被加工的任务需要在不同的处理机上加 工在这种情况下，通常把任务( t a s k ) 称为作业0 0 b ) 设作业集“，j ：，以 ，每个 作业j ，有玎，道工序( o 删i o n ) ，以，以工序指的是作业在某处理机上被加工 的这部分任务如果每个作业需要在每个处理机上加工，即”，= m ，= 1 ，2 ，九而 且每个作业的工序也相同，即在处理机上加工的顺序相同，把这种处理机的环境称为 同顺序作业或流水作业( n o ws h o p ) 若每个作业需要在每台处理机上加工，每个作业 有自己的加工顺序，则称之为异顺序作业( j o bs h o p ) 若每个作业需要在每台处理机上 加工，每个作业可按任意顺序加工，则称之为自由顺序作业或开放作业( o p e ns h o p ) 任务或作业 排序问题中的约束条件，主要是指任务或作业的性质以及他们在加工过程中的要 求和限制下面给出描述任务的一些性质的相关数据 ( 1 ) 任务加工时间向量，= ( a ，仍- - ，) ，其中岛是任务t 在处理机c 上所 需要的加工时间对同速机既= p ，对恒速机岛= p ，s 。，p ，是标准的加工时间( 一 般是速度最慢的处理机的加工时间) ，s ，是处理机只的速度因子对多类型机既是工 序j 。在对应处理机上的加工时间j = 1 ，2 ，聊，_ ，= 1 ，2 ，珂 ( 2 ) 任务准备时间r 是任务丁已经准备好可以被加工的时间如果所有任务的准 第2 页 国防科学技术大学研究生院学位论文 备时间相同，则取，= o ，= 1 ，2 ，n ( 3 ) 任务工期d ，是对任务r 限定的完工时间若不按期完工，应受到一定的惩罚 ( 4 ) 任务优先因子w ，是一个权，它表示任务丁，相对于其他任务的重要程度 如果排序问题中，每一个任务在加工时的任一时刻都可暂停加工，加工该任务的 处理机可去加工任何其他的任务，以后可在任何时刻在任意处理机上重新继续加工， 这种排序问题称为可中断捧序( p r e e m 曲v es c h e d m e ) 任何任务都不允许中断的排序问 题称为不可中断排序( n o n p 咖p t i v es c h e d u l e ) 加工任务时另一个重要限制是任务之间的优先约束( p r e c e d e n c ec o n s 仃a i n t ) 任务 之间的优先约束是任务集r 上的一个偏序关系一f 斗瓦意味着必须加工完任务丁， 才能开始加工任务e 如果任务集r 中至少有两个任务受到优先约束的限制，那么丁 中的任务称为相关的，否则称为无关的一般用一个称为优先约束图的关系图来表 示关系图是一个无环有向图g = ( r ，且) ，点对应r 中的任务，r 中的弧对应偏序关 系如果节点丁，到节点瓦存在一条有向路，则称任务丁，和任务瓦之间存在优先关系t _ 瓦，称r ，为瓦的先驱，瓦为丁，的后继如果t 斗疋，而没有一个节点瓦满足t 寸 瓦，瓦瓦，则称r ，是瓦的直接先驱或疋是f ，的直接后继图1 1 1 是任务优先约束 图的一个例子显然在多类型机中，作业的工序集总是相关的，而作业集可以是相关 的，也可以是无关的t ，斗以表示在每台处理机上，作业l ，的工序加工完成后，作 业 的工序才能在该台处理机上开始加工 五 疋 图1 1 1 任务问优先约束图 在优先约束中有几种重要的情况 ( 1 ) 如果每个任务最多有一个先驱和一个后继，则优先约束图称为链( c h a i s ) ( 2 ) 如果每个任务最多有一个后继，则优先约束图称为入树( i n _ t r c e ) ( 3 ) 如果每个任务最多有一个先驱，则优先约束图称为出树( o u t 吨e ) 链、入树和出树约束的例子分别如图1 1 2 ( a ) 、( b ) 、( c ) 所示 曩 瓦 乃正 疋 图1 1 2 链、入树和出树 ( c ) 正 瓦 第3 页 l 瓦k 国防科学技术大学研究生院学位论文 目标函数 用c = ( c 】，c ：，c 。) 表示任务的完工时间向量，要极小化的目标函数总是完工 时间c 的函数本文以下面两种函数为目标函数 ( 1 ) 时间表长( m a k e s p a n ) c 。= m a ) ( c ，) 它等于最后一个被加工完的任务的完 工时间小的时间表长意味着处理机有高的利用率 ( 2 ) 平均加权流时间和加权总完工时间 平均加权流时间f = ：。w ，：。w ，其中e = c ，是任务l 的流时间，在 计算机系统中，作业或进程的流时间称为周转时间，所以平均加权流时间也称为平均 加权周转时间把平均加权流时间进行变形，即 f = ：。叶，：；。= ；：。w j c ，；。u 一：。w ，o _ 一 因为：。w ，和：w ，r ，；：。w ，均为常数，极小化f 相当于极小化加权总完工时间 w ，c ，因此都以加权总完工时间( t o t a lw e i g h t e dc o m p l e t i o n t i i n e ) 作为目标函数 1 1 2 排序问题的分类 在排序问题中，如果所有的数据在进行决策之前都是已知的，则称为确定性排序 ( d e t e l l n i n i s t i cs c h e d u l i n 曲问题若有的数据在做决策时是未知的，它们是一些随机变 量，但它们的分布是已知的，这类排序问题称作随机排序( s t o c h a s t i cs c h e d u l i n g ) 问题 一个排序问题由处理机、任务或作业和目标函数三要素组成处理机的数量、类 型和环境有近十种情况，任务或作业和资源的约束条件更是错综复杂，再加上度量不 同指标的目标函数，形成了种类繁多的排序问题为了简化排序问题的表示，我们用 g r a h 锄掣4 j 首先使用的三元组来描述排序问题的类型 三元组记号由三个域组成：z l l ，其中z 域表示处理机的数量、类型和环境如 1 ：单处理机；p m ：研个同速机；q 魄：m 个恒速机；f m ：m 个处理机的流水作业 域表示任务或作业的性质、加工要求和限制等约束条件如，表示任务有不同的到达 时间，如果域中不出现，则说明，= o ，= 1 ，2 ，疗；，印表示加工时可中断， 若域中不出现p 聊妒，则表示加工时不可中断；p 阳c ，c 矗d 泌，f 肋一p p ，d 洲r p p 表示任 务的相关性，分别为一般优先约束、链、入树和出树，若卢域中不出现这些项，则任 务集无关；p 一“，舢盯这两个约束只可以出现在流水作业环境中，分别表示作业按 照通过第一个处理机的顺序始终不变地通过所有处理机和每个作业各个相邻工序之 问是连续的，域表示要优化的目标函数如c 。为时间表长；w ，c ，为加权总完 工时间详情可参考文献 3 】 例1 1 1 劬c o 表示一个任务集无关、不可中断、极小化排序时间表长的恒速 机排序问题 例1 1 2 砌i 岛= p ，i w ，c ，表示一个由m 个处理机组成的流水作业排序问题， 每个作业的所有工序的加工时间都相等，目标函数是找一个加工作业的顺序，按这个 顺序加工作业使加权总完工时间最短 第4 页 国防科学技术大学研究生院学位论文 1 1 3 排序问题的求解 由于排序问题中的处理机、任务或作业都是有限的，绝大部分排序问题是从有限 个可行解中找出一个最优解，使目标函数达到极小在排序问题中，把可行解称为可 行排序( f e a s i b l es c h e d u l e ) ，最优解称为最优排序( o p t i m a ls c h e d u l e ) 一个可行排序是 一个顺序或排列，按照这个顺序，在给定的处理机上加工所有的任务或作业 例1 1 3 排序问题f 2 | | c 嘣，其中 = 5 ，p 。= ( 4 ，5 ) ，p ：= ( 4 ，1 ) ，岛= ( 1 0 ，4 ) ，p 4 = ( 6 ，1 0 ) ，见= ( 2 ，3 ) 对问题f 2l ic 二，作业集的任何一个排列都是一个可行排序，而 以，以，山，以， 1 是最优排序 为了直观和方便讨论，很多研究排序问题都用g a n t tc h a n s 表示可行排序，如例 1 1 _ 3 的最优排序的g a i l t t c h a n s 由图1 1 3 给出 bl 以l 以 l 以 图1 1 3 例1 1 3 的g a n n 图 对一个可行排序，若有准备好未被加工的任务，就不准许有空闲的处理机，称这 种可行排序为无耽搁排序( n o n d e l a ys c l l c d u l e ) ，反之就是耽搁排序( d e l a ys c h e d l l l e ) 无 耽搁排序相当于不允许强迫处理机空闲对于大多数排序问题，包括所有的可中断排 序，最优排序是无耽搁排序然而，也有一些不可中断排序问题的最优排序是耽搁排 序本文讨论不可中断无耽搁的排序问题 1 1 4 排序问题的算法与复杂性 根据排序问题的特点，绝大多数问题是n p 难题，其最优解往往很难找到，甚至 根本找不到而在实际应用中也没有必要去找最优解，只需找到满足一定要求的启发 式解或近似解因此研究排序问题主要有两个方向一是对p 问题寻找多项式时间算 法，或者对n p 难问题在特殊情况下寻找有效算法，也就是研究n p 难问题的可解情 况二是设计性能良好的启发式算法和近似算法当然无论是启发式算法还是近似算 法都应该是多项式时间的实际上，n p 难问题可解情况的多项式时间算法往往是可 以作为n p 难题本身的启发式算法和近似算法 设4 是一个使目标函数最小的优化问题，是问题4 的一个实例，p 是所有实例 的全体记0 p 丁( ，) 是实例j 的最优目标函数值，珂( ，) 是由算法舅得到例子，的目标 函数值如果对某个实数p o ，对问题4 的所有实例p 有 | 【贸( ，) 一o p r ( 明o p r ( di p 则称p 是算法舅的一个上界如果不能确定算法是否有界，或者能够确定算法的上 界是无穷大时，这个算法称为启发式算法( h e l l r i s t i ca l g o r i t h m ) 当b 是有限数( 不是无 第5 页 国防科学技术大学研究生院学位论文 穷大) 时，这个算法称为是近似算法( a p p r o x h a t ea l g o r i t h m ) 用启发式算法和近似算 法得到的解分别称为是启发式解或近似解 对于一个启发式算法，一个重要的工作是分析最坏情况下的误差界，从而来评价 该算法的好坏，显然p 越小近似算法的精度越高由于 【贸( ，) 一0 p r ( d 】d p 丁( ，) = 贸( ，) o p r ( ，) 一1 因此常用绝对性能比【5 1 ( a b s o l u t ep e r f o n n a n c er a t i o ) r 。= 舅( ，) o p 丁( ，) 来衡量算法 的好坏显然r 。的界接近1 的算法是好算法 对于具有多项式算法的排序问题，要尽可能的找出空间复杂性和时间复杂性好的 算法空间复杂性是指算法所占存储的多少时间复杂性指算法对于给定问题所需计 算时间的长短本文主要考虑排序问题的时间复杂性 1 2 排序问题的推广 近年来，计算机的出现和广泛应用，对排序问题产生重大影响，新的排序模式层 出不穷、不断涌现它们是在突破经典排序基本假设的基础上建立起来的非经典的新 型的现代排序【6 j 根据1 9 9 3 年e l l a w l e r ，j k l e 曲a ，a h g 黜曲o o vk a i l ，d b s h m o y s 等【lj 的观点，经典排序问题有以下四个基本假设 ( 1 ) 资源类型经典排序假设一台处理机在任何时刻最多只能加工一个任务；同 时还假设，一个任务在任何时刻至多在一台处理机上加工 ( 2 ) 确定性经典排序假设决定排序问题的一个实例的所有( 输入) 参数都是事先知 道的和完全确定的 ( 3 ) 可运算性经典排序是在可以运算、可以计算的程度上研究排序问题，而不 去顾及诸如如何购置机器和配置设备等技术上可能发生的问题 ( 4 ) 单目标和正则性经典排序假设排序的目的是使衡量排法好坏的一个一维目 标函数的函数值最小，而且这个目标函数是任务完工时间的非降函数 相应地，作为资源类型这个基本假设的突破，有成组分批排序、同时加工排序、 不同时开工排序和资源受限排序等；作为确定性这个基本假设的突破，有可控排序、 随机排序、模糊排序和在线排序等：作为可运算性这个基本假设的突破，有应用排序、 人员排序和智能排序等；作为单目标和正则性这个基本假设的突破有多目标排序、准 时排序和窗时排序等 当然上述经过推广的排序问题不可能包括不断涌现的新型排序问题 1 3 研究概况 排序领域内许多早期的工作是在制造业推动下发展起来的，普遍认为1 9 5 4 年 第6 页 国防科学技术大学研究生院学位论文 j o l u l s o n 的论文【7 】是经典排序问题的第一篇从这篇文章问世以来的半个多世纪中， 全世界已发表排序问题的文献2 千余篇早在2 0 世纪6 0 年代中国科学院越民义教授 就注意到排序问题的重要性和理论上的难度，7 0 年代初他和韩继业一起研究同顺序 流水作业排序问题，他们发表在中国科学上的论文1 8 】开创了中国研究排序论的先 河但对排序问题的研究到8 0 年代，感兴趣的人才越来越多且对问题的研究主要 集中在一些经典排序的模型上 近年来，出现许多新模型，主要表现在加工方式和目标函数上，从而也表现在用 来解决问题的方法上，吸引了不少研究学者特别是唐国春、张峰等编著的现代排 序论【6 】是我国迄今为止对现代排序研究最为完整的综述在各类新的排序模型中， 任务加工时间恶化的排序是一类重要的问题，这类问题突破经典排序问题中的确定性 假设在此问题中，任务实际加工时间通过基本加工时间，恶化率( 增长率) 和开工时 间函数来描述由开工时间函数的不同，问题通常分为线性恶化和非线性恶化两种情 况为方便叙述，先给出问题的一般描述 给定行个任务的任务集丁= 佤，疋，l ，如果任务r ，的开工时间为s 。，则其加 工时问p ，( s ，) = j ，+ 口，厂 ，) ，其中口，为大于零的常数，称为任务t 的恶化率x ， 称为丁的基本加工时间( 即没有恶化现象发生时，任务丁，的加工时问) ，厂( s ，) 是开工 时间的函数，= 1 ，2 ，刀 若厂 ，) = s ，则称该问题为线性恶化排序问题若，厂( s ) 是非线性函数，则称 该问题为非线性恶化排序问题 线性恶化单机排序问题由g u p t a 和g u p t a 【9 】b m w n e 和y e c h i a l i 【1o 】分别独立提出 来的对于基本加工时间是确定量的情况，目标函数为极小化最大完工时间的排序问 题1 l p ，= 工，+ 口，s ，ic m 。，g u p t a 和g u p t a 得出把任务按x ，口，不减顺序排列得最优 排序b r o w n e 和y e c h i a l i 考虑任务的基本加工时间是随机变量的情况目标函数为 极小化最大完工时间的数学期望进一步得到把任务按e ，) ，口，不减顺序排列得最 优排序如果任务有准备时间，则问题变得复杂c h e n g 和d i n g 在文献【1 1 中研究了 问题l lp f = ，+ 口，s ，r ，fc 一和1 | p ，= x ，+ 口，s ，r ， o ，r i ，证明了问题1 i p ， = z ，+ 口，s ，jc 。是n p 难的，而问题1 l p ，= z ，+ 口，s ，e o ，) ic 一至少是 n p 难的对于任务有工期限制的情况，c h e n g 和d i n g 在文献【1 2 】中作了详细研究， 证明了问题1 i p ，= x ，+ 口，s ，d ，ic 一是n p 难的 尽管极小化最大完工时间问题lp ，= z ，+ 口，s ，lc 。，存在多项式算法，但对其它 目标函数却相当复杂对极小化加权总完工时间问题1 i p ，= 石，+ 口，s ，| w ，c ，b a c l l l n a n 和j a n i a l 【等i l3 j 证明了问题是n p 难的大多数文献都研究其特殊情况m o s h e i o v 考虑基本加工时间相同的情况，对于问题l ip ，= x + 口，s ，i w ，c 证明了最优排序具 有关于恶化率的v 型性质对问题l lp ，= z ，+ 醯i w c 则更复杂，如果权与基本 加工时间成比例，文献 1 4 】证明了该问题的最优排序具有关于基本加工时间的n 型性 第7 页 国防科学技术大学研究生院学位论文 质在此基础上构造了复杂性为0 伽l o g h ) 的多项式算法 对于恶化率与基本加工时间无关的其它目标函数单机问题的研究，大多数考虑特 殊情况由于任务较多时，对实际加工时间而言，恶化率的影响远远大于基本加工时 间的影响同时考虑到一般问题的复杂性，m o s h e i o v 在文献【1 5 】中对基本加工时间为 零的情况作了研究，并称该问题为简单线性恶化排序问题文献【2 2 】讨论了恶化率与 任务无关的线性加工时间调度问题 相对于单机排序问题，平行机排序问题的研究结果较少c h e n 在文献【1 6 】中证明 了问题p 川p ，= 口，s ，l c ，是n p 难的，h s i e h 和b r i c k e r 在文献 1 7 研究了问题尸棚l p ， = z ，+ 口，s ，ic m 。，给出了启发式算法，并对算法的性能作了分析 与平行机问题类似，多类型机情况的研究结果也很少文献【1 8 】对简单线性恶化 的多类型机问题作了研究对问题f 2 i b ，= s i c 0 。给出了复杂性为0 0 l o g n ) 的多 项式算法，该算法与经典问题f 2 l ic m 。的j o h n s o n 规则类似对f 3 1 只，= & lc i 。， 证明了该问题是n p 难的对自由作业问题有类似的结果而异顺序作业问题，对任 务多于处理机数的一般情况，问题，2 i 岛= s ic 。是n p 难的对问题f 2 i 岛= + 口。& l c 二，文献【1 9 】作了分析，并证明了该问题是n p 难的 非线性恶化排序问题相当复杂，研究成果甚少文献【2 0 】讨论了非线性简单恶化 下最小化完工时间的单机排序问题的一些性质 第8 页 国防科学技术大学研究生院学位论文 第二章单机排序问题 在实际问题中，我们经常会遇到这样一种现象：任务的加工时间随其开始加工时 间推后而增长，如在钢铁企业中，某些任务的加工有温度的要求，在满足温度要求的 情况下，任务的加工时间为常数如果任务在加工前有等待时间，将引起任务温度的 下降，这样一来，无论是重新加温使其满足温度要求，还是在不满足温度要求的低温 下加工，都将导致任务加工时间的增加又如，处理机长期加工或其它原因导致速度 下降也能产生类似的问题在这类问题中，任务的加工时间与任务开工时间有关类 似的问题模型在维修工作、塑料工业及医疗等方面也有广泛的应用【9 】 1 5 】【1 9 】刚因此 研究任务加工时间是任务开工时间函数的排序问题更有实际意义相应地把这类排序 问题称为加工时间恶化( d e t e r i o 删j n 曲的排序问题 本章突破经典排序中任务加工时间是常数的限制，研究任务加工时间线性恶化的 排序问题2 1 节、2 2 节和2 3 节将分别讨论任务间具有链约束，树约束和一般约束， 任务加工时间是开工时间线性函数的单机排序问题 2 1 链约束下线性恶化单机排序 本节讨论任务问具有平行链约束，任务加工时间是开工时间简单线性函数的单机 排序问题目标函数为最小化加权总完工时间用三参数表示法，该问题记为 l c f 邶，p ，= 口，s ，i w ，c ， ( 2 1 1 ) 引理2 1 1 对于排序问题1 i p = 口，s ，| _ q ，任务按m ( 1 + 口，) 口，非增序排 列可得最优排序，且目标函数值；：。竹q = s 。：。兀：。( 1 + ) ，其中s 。为第一个 任务的开始加工时间 为方便叙述，设n 个任务形成坍条平行链，表示为厶：巧，斗正：斗j 互。；三： e l 斗正2 斗斗正。：；上。：乙1 一l 2 一斗乙，第f 条链中含有一个任务， ( f - 1 ，2 ，m ) ，且：1 = 玎 定义2 1 1 如果要求一旦加工某个链，就必须加工完该链的所有任务，然后再接 着加工另一条链中的任务，则称该链不可中断 定义2 1 2 如果加工某一条链时，可以不必全部加工完所有的任务，就可以加工 其他链中的任务，然后回来再加工前面链中剩余的任务( 要保持任务原来的优先顺 第9 页 国防科学技术大学研究生院学位论文 序) ，则称该链可中断 引理2 1 2 【2 1 】对于链不可中断的排序问题1ic 砌伽。，= 口，s ，l w ，c ，任务按 2 。w 。兀i 。( 1 + 口g ) 【兀羔。( 1 + 口f ) 一1 】非增排列可得最优排序 定义2 1 3 2 1 1 对链三。：毛斗正：呻呻k ，令，+ 满足 ：。w * 兀：。( 1 + 口f ) l ：；。w m n ：。【1 + 口f ) i 办2 1 砾鬲：万2 磷1 1 面鬲l r f 则称只f 为链厶：l 。斗正：斗斗l 的p 因子，任务i r 为该链的关键任务 引理2 1 3 】如果l f i 为链上，：正。斗巧：斗的关键任务，则存在一个最优 排序，在该排序中，任务死，l2 ，- 一，z ，连续加工而不被其他链中的任务打断 由引理2 1 3 可构造链可中断排序问题( 2 1 1 ) 的最优算法【2 ” 算法2 1 1 ( 关键任务优先规则) s t e p l 在当前未加工的链中，选择p 因子最大的链： s t e p 2 连续加工已选定的链，直到加工完该链的关键任务； s t e p 3 若已加工完全部的任务，停止否则，转s t e p l 该算法的复杂性为。伽2 ) 2 2 树约束下线性恶化单机排序 本节讨论任务间具有出树约束，任务加工时间是开工时间简单线性函数的单机排 序问题目标函数为最小化加权总完工时间用三参数表示法，该问题记为 1 i d “f 护e p ，p ，= 口，sji w ，c ， ( 2 2 1 ) 为书写方便，下面直接用任务的下标表示该任务 定义2 2 1 【2 3 】设为有根树的n 个节点( 任务) 构成的集合对任意节点v ， 以v 为根节点，v 的全部或部分后继节点导出的树叫做v 的家庭树 定义2 2 2 在节点v 的所有家庭树中使比值 p ，= ：。、兀：。( 1 + 口，) 兀：l ( 1 + 口，) 一l 】 最大的家庭树，叫做v 的最大家庭树，记为e e 对应的p 值称做节点v 的p 因子 定义2 2 3 设m 为一些节点组成的集合，且这些节