（概率论与数理统计专业论文）分批排序问题和资源约束排序问题.pdf

摘要 摘要 排序问题是一类重要的组合最优化问题。本文讨论了分批排序、流水成组排序 和资源约束排序问题。文章分三部分：带到达时间的分批排序的数学模型；带滞留 时问的流水作业成组排序问题的多项式算法：三个资源约束排序的最优算法。 第二章给出了问题l ib ，r ，f 吒。的o - l 整数规划模型；利用统计软件s a s 中的 l p 过程编程对这一模型进行数值求解实验，得到了按此数学模型计算机能求得最优 解的该问题的规模 第三章讨论了带滞留时间的两台同顺序成组流水作业排序问题f 2 ls 。 g tc t 眦，分析证明了此问题存在的多项式算法。 第四章讨论了两个单机排序的资源分配问题1 10 ，p ，= 屯一口j “，c 眦。 6 l e u 和1l0 ，p r e c ，p ，；q 一口，“，e i “，以及离散资源约束排序问 题p 2 r e s ，p 5 a ，2 a ，ic 。( 加工时间相等的任务不能在两台机器上同时加 工) 。分析证明了这些问题存在多项式算法。 关键词：排序，分批排序，成组技术，资源约束，数学模型。 作者：姜冠成 指导老师：闻振卫 a b 豇r a c 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 s a l li m p o r t a n tc o m b i n a t i o no p t i m i z a t i o np r o b l e m i nt h i s t h e s i s ，w es t u d yp r o b l e m so fb a t c h i n gs c h e d u l i n g ，f l o ws h o pw i t hg r o u pt e c h n o l o g y , r e s o u r c ec o n s t r a i n e ds c h e d u l i n g w ew i l ld i s c u s st h es c h e d u l i n gp r o b l e mi nt h r e ep a n s ： t h em o d e lo fb a t c hs c h e d u l i n gw i t ha r r i v a lt i m e ；t h ep o l y n o m i a la l g o r i t h mo ff l o ws h o p s c h e d u l i n gp r o b l e mw i t ht i m el a gb e t w e e np r o c e s sa n dw i t hg r o u pt e c h n o l o g y ；t h r e e o p t i m a la l g o r i t h m so f r e s o u r c ec o n s t r m n e ds c h e d u l i n gp r o b l e m s i nt h es e c o n dc h a p t e r , a0 - 1i n t e g e rp r o g r a m m i n gm o d e li sf o r m u l a t e df o rt h e s c h e d u l i n gp r o b l e mw i t hr e l e a s et i m eo ns i n g l eb a t c hp r o c e s s i n gm a c h i n em i n i m i z i n g c o m p l e t i o nt i m e lb ，nic 眦a c c o r d i n gt ot h i sm o d e ln u m e r i c a lt e s t sa r em a d ea n dt h e s i z e so f c o m p u t a b l ei n s t a n c e sa r eo b t a i n e dw i t hl pp r o c e s so f s t a t i s t i c ss o f t w a r es a s i nt h et h i r dc h a p t e r , w es t u d yf l o ws h 叩s c h e d u l i n gp r o b l e mw i t ht i m el a gb e t w e e n t w o p r o c e s s e s a n d w i t hg r o u p t e c h n o l o g y m i n i m i z i n gc o m p l e t i o n t i m e f 2 i j h ，g t i c 一 i ti sp r o v e dt h a tt h e r ee x i t sap o l y n o m i a la l g o r i t h mf o rt w o - m a c h i n ep r o b l e m s t h ef o u r t hc h a p t e rd i s c u s s e st w or e s o u r c ea l l o c a t i o np r o b l e m si ns i n g l em a c h i n e s c h e d u l i n g w i t ha r r i v a lt i m e s 1 io ，p ，= b 厂4 ，“，ei “a n d 1 i o ，p r e c ，p ，= 6 厂口“，e l “，a n dad i s c r e t e l y - d i v i s i b l er e s o u r c ec o n s t r a i n e d s c h e d u l i n gp r o b l e mp 2 ir e s ，只= 口，2 ac m u ( t h ej o bo f w h i c hp r o c e s s i n gt i m ei s s m * n e c a nn o tb ep r o c e s s e di nt h em a c h i n es i m u l t a n e o u s l y ) i ti sp r o v e dt h a tt h e r ee x i tt h r e e p o l y n o m i a la l g o r i t h m sf o rt h e s ep r o b l e m s k e y w o r d s ：s c h e d u l i n g ，b a t c h i n gs c h e d u l i n g ，g r o u pt e c h n o l o g y , r e s o u r c ec o n s t r m n ， m a t h e m a t i c a im o d e l w r i t t e nb y j i a n g - g u a n c h e n g s u p e r v i s e db yv i c e p r o w e n - z h e n w e i 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文足本人在导师的指导下，独赢进行研究丁作所 取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或集体已经发表或 撰写过的研究成果也不含为获得苏州大学或其它教育机构的学位证书而使用过的材 料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人承 担本声明的法律责任。 研究生签名：主毳j 鲨日期：兰! 堕竺! 吖】9 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文台作部、中国 社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子文档可以采 用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密i 宅 3 r j , b ，允许论文被查阅和借阅，可以公布c 包括刊登) 论 文的全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名 导师签名 邀日期：必 熟掣 分批排序问题年n 资源约束排序问题第一章序苦 第一章序言 l ，l 背景 排序( s c h e d u l i n g ) i h 题是一类重要的组合最优化问题，它产生的背景主要是机器 制造，后来被广泛用于计算机系统、运输调度、生产管理等领域事实上，排序问题 在编制作业计划，企业管理，航空航天，医疗卫生等各个领域都有着广泛的应用它 是利用一些处理机( p r o c e s s o r ) 机器( m a c h i n e ) 或资源( r e s o u r c e ) ，最优地完成一批给定 的任务( t a s k ) 或作业( j o b ) 在执行这些任务或作业时需要满足某些限制条件，如任务 的到达时阀、完工的限定时间、任务的加工顺序、资源对加工时问的影响等最优的 完成指的是使目标函数达到最小，而目标函数通常是对加工时间的长短、处理机的 利用率的描述 排序理论可归结为下面两类问题，一：给定了任务或工程，如何合理地安排各 项具体工作的顺序，使得花费尽量少的人力、物力、财力等资源，以完成这项任务 或工程；二：现有的人力、物力等资源已经确定，如何安排具体工作的顺序，使这 些资源能发挥尽量大的收获 1 2 符号 二 。 经过几十年的发展，排序的理论和算法，已成为组合最优化之中的一个重要分 支，对它的分类，目前一般采用国际上通用的表示方法，即三参数分类法， 口i i y 其中： a 表示处理机的数量、类型和环境，它可以为： l ：单处理机( s i n g l em a c h i n e ) ： p m ：m 个同速机( i d e n t i c a lm a c h i n e ) ； 乏锄：m 个恒速机( u n i f o r mm a c h i n e ) ： r m ：m 个变速机( u n r e l a t e dm a c h i n e ) ： f m ：m 个处理机，流水作业( f l o ws h o p ) ； d m ：m 个处理机，异顺序作业( j o bs h o p ) ： o m ：掰个处理机，开放作业( o p e ns h o p ) ： 口表示任务或作业的性质、加工要求和限制，资源的种类、数量和对加工的影 响等约束条件它同时可以包含多项，可能的主要有： ，：任务有不同的到达时间 p r e c ：工件间存在优先加工约束； p r m u ：这个约束只可以出现在流水作业环境中作业按通过第一个处理机的 l 分批排序问题和资源约束排序问题第一章序苦 顺序始终不变的通过所以的处理机 y 表示要优化的目标函数，它可以是： c ：时问表长； c ，w ，c ，：总完工时间，加权总完工时间： ：最大延误 一般情况下，排序问题是寻求使上述目标函数或某些目标函数同时达到最小值 的最优排序 1 3 论文的主要内容 第二章讨论用数学规划方法处理分批排序问题建立数学规划模型来研究解决 排序问题是一件有意义的工作本章给出问题1j 丑，r ，ic 。，的。一l 整数规划模型；利 用统计软件s a s 中的l p 过程编程对这一模型进行数值求解实验，得到了按此数学 模型计算机能求得最优解的该问题的规模 第三章讨论带滞留时间的两台同顺序成组流水作业排序问题f 2 is 。 g r | c m 。给出了求问题最优解的多项式算法 第四章先讨论一个离散资源约束排序问题尸2 r e s ，p i = a ，2 a ，ic k 。( 加 工时间相等的任务不能在两台机器上同时加工) 并给出多项式算法然后讨论两个 单机排序的资源分配问题1 r j ，p ，一6 ，一口，“，。e i ”，和10 ， p r e c ，p ，= 6 ，一口，“，c 。e l “，并给出求其最优资源分配的多项式算法 2 分批排序n d 题年资源约束 | = 序问题第二二帝带到达时间的分批排序问题的模型 第二章带到达时间的分批排序问题的模型 2 1 引言 分批排序问题最早是在半导体集成电路制造的最后测试阶段预烧作业过程中 提炼出来的它是一种新型的重要的排序问题单机分批带到达时间排序问题可描 述为，n 个工件在一台机器上加工，工件可以分批，每批一台机器最多可同时加工 口个零件，每个工件有着自己的加工时间( 工时) 与到达时间( 到时) ，每批的加 工时间为本批中工时的最长者，每批加工的开始时间至少为本批中到时的最迟者， 排序的目的是寻求使最大完工时间最小或总完工时间最小的工件排序 s k u t e l l a 9 把平行机排序中的尸难题pi q 和r1 c i 表述成二 次0 - 1 整数规划模型，求得了令人满意的近似解：罗守成 1 3 、张倩 1 8 分别给出 了1i w ，c ，( 单机加权完工时间和问题) 的二次规划表示张召生等 2 0 给出了 llb j w ，c ，( 单机分批加权完工时间和问题) 的数学规划形式，并利用该数学规划 给出了s p t 序是1 f 曰f c ，( 单机分批完工时闻和问题) 的最优解的另一个证明 张玉忠等 1 9 对于分批排序问题的复杂性进行了讨论l i uz h a o h u i 等 8 证明了 1 ib ，r f1 c 。，( 单机分批带到达时间的最大完工时间问题) 是且，尸困难的 本章给出问题l f 丑， c 嗽的。一l 整数规划模型：利用统计软件s a s 中的l p 过程编程对这模型进行数值求解实验，得到了按此数学模型计算机能求得最优解 的该问题的规模 2 2 排序问题l ib ，l c 一的数学模型 问题描述，我们假定： ( 1 ) 设有门个工件，= j ，：= 1 ，z ，再 要在一台机器上加工工件，的加工时 间( 工时) p ，和到达时间( 到对) r ，是事先知道的记p = ( p i 。p ：，p 。) 7 ，r = ( ，2 ，) 7 分别表示工件集，的加工时间向量和到达时间向量 ( 2 ) 一台机器可以把一些工件作为一批同时加工一批中晟多可加工b ( 批容量) 个 工件( 口n ) ( 3 ) 一批工件加工的时间等于此批工件中工时的最大者一批工件可以开始加工的 时间大于等于此批工件中到时的最大者批处理一旦开始，不允许中断，并且批 处理过程中不允许移走工件或增加工件 ( 4 ) 记日为机器上第i 批加工的工件集，i 依次是l ，2 ，n ( 有的批可以是空 集) 记c ，为第i 批工件且的完工时间 分批排序问题和资源约柬排序问题第二章带到达时问的分批排序问题的模型 ( 5 ) 目标是使最大完工时间c 虽小 分别用一阶方阵= ( j 。) 、l 。= ( 蜘) 、z 。= ( z 。) 表示决策变量，其意义是 fl ，表示工件，在b 中j j n i ； “。l0 ，表示工件j ，不在b ：中加工， 一f1 ，表示工件，在b 中为加工时间最大的工件( 有多个工件时任取一个) ； 删i0 ，表示b 中加工时间最大的工件不取， 一fl ，表示工件j ，在b ，中为到达时间最大的工件( 有多个工件时任取一个) ； ”】0 ，表示b ，中到达时间最大的工件不取， 对于问题1 ib ，0i c 。，有如下约束： e x 。= 1 ， j = 1 ，n i 1 b ， i = 1 ，n 卢i e y “1 ， i = i ，n y f x f ， i = l ，n j = l ，1 p j x 口p ，i = 1 ，n j = l ，n z # s 1 ， i = 1 ，群， z f 工f ， i = 1 ，n - ，= 1 ，一，竹 0 z n r ，i = l ，挖，= 1 ，n x u , y f ，z f o ，1 ，f = l ，栉，= 1 ，栉 ( 2 1 ) ( a ) 表示每一个工件只能属于一批，( b ) 表示每批最多可加工曰个工件( c d ) 表示每批中工时最大工件的约束( e ) 表示每批的加工时间等于其所含工件中工时 最大者( f g ) 表示每批中到时最迟工件的约束( h ) 表示每批的到达时间等 于其所含工件中到达时间最大者 单机分批带到达时间排序问题的可行方案即满足约束条件( 2 1 ) 的矩阵爿、 砭。、乙。就是：矩阵以。中每列恰有一个元素为1 其余均为0 ，每行至多有8 个 元素为l 其余均为o ；矩阵e 。由在z 的每行中将元素为l 中对应加工时间最大 的那个( 不唯一时任取一个) 元素i 保留下其余均改为0 所形成；矩阵z 。由在j 的每行为1 的元素中将一个对应到达时间最大的元素i 保留下其余均改为0 所形成 下面考虑问题l ib ，i c 眦的目标函数 4 m z z_ = z m yyy = m xx m ( 一 j | 置吐记“ 泐 够 坌垫! ! ：壁塑丝塑塞塑丝塞型壁塑璺苎三空壁些塑塑型生型塑型型旦垦盟堡兰! 一 ( 1 )第f 批工件的加工时间为r 尸= p ，y f ，s i ” ( 2 ) 第f 批中的工件的最迟到达时间为z 。r 2e r j y f j = l ( 3 )第i 批工件的完工时恻为c i = m a x c 。，z i r + i 尸，f l ，其中 c o 。0 于是我们得到如下的定理： 定理21 ：最后一批( 即第h 批) 工件的完工时间c 。满足： c 。= m a x z r + i 窆= 1 尸，z ：r + 窆i = 2 p ，z t r + 娄r p z 。r + 匕p ) 证明：以下证对每个f ：l ，2 ，n 有 z ，r + r p 当f = 1 时显然有：c l = z 1 r + 一p = m a x c o ，z 1 r + r p 假设当t = ，l 一1 时结论成立即： c h = m a x z 1 r 十 z ( - 1 ) r + l ) p z 2 r 则f = 九时，c = m a x c 圳z 。r ) + l p = m 8 , x c 。一。+ p ，z 。r + p ) = m a 。 m a x _ z 。尺+ 霎i 尸，z ，月+ 薹n - i r p ，z t r + 薹p ，- z _ ”r ；r 。) p + 一p ， z 。r 十p = m a x m a x z r 十艺1 p ；l p ，z ：r + 苫p + p i ， 一 n z h 尺+ - i r p + k p ，z t m r + 卜尸+ k p ，z r + e 尸 f = = m a x z 。r + e pz ：r + i p ， z 。r + i p ， p l ， r t z p ，m 十 r 扣 zp l ，h + rz ，i x am i | c p r 1 础 + r h zp r - m + p f 1 分批排序问题和资源约束排序问题第二章梦到达堕塑塑坌垫塑：壁坚塑塑堡型 z 。r + j p l 所以结论成立口 对于一个n 维列向量6 = ( 6 ，b ：，b 。) 7 ，简记m a x ( 6 ) 2 f l a x b ，b 2 轧) ，于是，定理1 中的c = m a x ( a 。匕。p + z r ) 其中 爿= 1ll 1 0 1l l o0 o o l1 o1 ( 2 2 ) 由于目标函数中的最大完工时间c 聃。为最后一批的完工时问g 所以我们得到问 题1 l 口，_ c k 。的数学规划模型为 m i n 厂= m a x ( 以。匕。p + z 。r ) = 1 ， = 1 ，n f = i 矗b ， i = 1 ，n j t l y o 1 ， i = 1 ，n y f ， i = 1 ，z - ，2 1 ，h ( 2 ，3 ) p ，为r p ，i = 1 一nj 2 1 ，n 1 ， i = 1 ，阼 乙， i = l ，n j = l ；。，n 0 z 1 r ， i = 1 ，n j = 1 ，群 x u , y # ，z f o ，1 ) ，f = l ，1 j = l ，1 其中，p = ( p ，p ：，p 。) t ，r = ( r i ，r ) 7 2 3 数学模型( 2 3 ) n 数值求解实验 我们用统计软件s a s 中的线性规划过程l p 对问题1 曰，r i c 。的0 - i 整数规划 模型( 2 3 ) 进行计算机编程求解实验每个规模的问题做5 - - 1 0 个实例假定到 达时间向量月和加工时间向量p 均取整数，其中p 按等概分布取自 l ，2 ，2 0 ， 由计算机随机产生，r 取自 o ，1 ，2 0 上的等概分布实验的结果由表2 1 给 出 观察表2 1 中数据我们看到，所用的平均c p u 时间r 与n ( 工件数) 以及口( 批 容量) 的关系是：当b 一定时，n g 大贝t ! t 越大，这显然符合常理：而当挖一定时， 分批排序问题和资潭约束 非序问题 第二_ 茕j 带到达时问的分批排j 芋问题的模型 b 越小则t 越大，这不是直觉所能感知的当n = l l 时，计算时间已经较长，随着月的 变大或者b 变小，计算时间会更长所以对仃超过1 0 的问题，用此模型求精确解不 理想 丁什数n批窖量日平均c p u 时| 自j ，( 秒 t 件鼗1 8 平均c 时问t ( 秒 4 分64 9 秒 28 8 24 9 26 7 7： ：j8 l9645 5 7 2 3 05 79 5 2 分3 04 8 秽 8 869 2 94 2 分：j 5 列秒 8 768 ：j 93 4 分3 l0 5 秒 r675 7 92 3 4 分3 09 8 秒 8 51 l3 5 1 11 14 分1 88 6 秒 8486 8 1 04 分秘2 4 秒 3 踅业 一 一l ! j _ _ 盐墅量址l 一 表2 1 2 4 数学模型( 2 3 ) n n 进及数值求解实验 从上述实验我们发现，有些批是空集，即存在某些i 使= 0 ，j = l ，2 ，n 这是由于我们对模型的假设中允许有的批次可以是空集，使得模型的批数总为以 这使变量( ，y o ，z 口) 的个数有着不必要的过多，从而也使计算时间较多为使 计算时间减少，对于问题lb ，r ， c 。的满足一定条件的实例，我们可以将批数n 减少到m ，从而减少变量的个数以减少计算时间为此我们有， 定理2 2 设_ ，p p p ，并设存在| ，1 k 一2 ，使p + p j ，+ + p a 一 p + p + + p a ， 记 珊：i 业i + 七 胛( b 2 ) 则存在1 b ，0 1 c 。的最优解使至多只需要m 批其 ib 。 中k 1 表示大于等于盘的最小整数 证明：由于_ p + p ：+ + p ，非空的每批至少加工一个工件， 所 以至多k 批加工后所有未加工的工件都已到达，未加工的工件至多还有，l k 个对 于这些都已到达而未加工的工件排序问题，相当于求解问题1 l b l c 咐。，由文献 7 ， 1 9 可知，最优解中至多另外再需要i 兰i 批因此定理2 2 得证口 7 分批刊序问题和资源约束排序问题 帮一章带到达时间的分批排序问题的模型 由定理2 2 ，模型改进后的批数是聊：l ! 兰i + 七以下简称由将模型( 2 3 ) 口 的批数仃用肌替换所得的模型为批数改进模型m 的大小与咒，b 及k 有关，当r 和 曰一定时，女越小则m 越小，或当n 和女一定时，口越大则越小；越小，批数 改进模型中变量的个数就越少，从而使得计算时间越少 下面对问题l b ，r ，fc 的模型( 2 3 ) 的批数改进模型进行求解实验( 程序 见附录) 每个规模的问题做5 次实例假定r 取自f 0 ，l ，5 0 ) 上的等概分布， 尸取自f 1 7 ，1 8 ，4 5 上的等概分布由于月产生的整数至多为5 0 ，p 产生的整 数至少为1 7 ，因1 7 + 1 7 + 1 7 = 5 1 5 0 ，所以七3 由上节的数值计算得出的规律：当工件数，z 固定时，批容量丑越小，计算时间 越大；当批容量占固定时，工件数九越大，计算时间越大我们在进行批数改进模型 求解实验时，对于工件数托固定时，当给出计算时间较长时的批容量丑后，丑更小 的不再给出( 计算时间会更长) ；工件数也未连续给出( 因为疗大时能较快算出的问 题，n 小的时候能更快地算出) 实验结果由表2 2 给出 由表2 2 中的结果可见，当n 5 0 且口较大( 超过n 的半) 时，问题能较快 解决当n 较大，曰相对较小时，解决问题需要较长时间 算例2 1 ：给定n = 1 2 ，b = 5 分批排序问题和资源约束排序问题第二二章带到达时问的分批排序问题的模型 r = ( o ，3 ，1 l ，1 9 ，2 0 ，3 1 ，4 4 ，4 5 ，4 6 ，4 6 ，4 9 ，4 9 ) ( 已按递增排序) ， p = ( 4 4 ，2 3 ，3 4 ，3 6 ，3 5 ，3 6 ，3 3 ，4 5 ，3 3 ，3 0 ，3 8 ，3 3 ) ， 求此分批带到达时间排序问题的最小的最大完工时间( m a k e s p a n ) 解： 用批数改进模型求解，得到k = 2 ，m = 4 ，问题的解见图2 1 第一批f ， ，2 ：到达时间r 。- = i n a x 0 ，3 ) = 3 ，开始加工时间s l = r 。= 3 ，加工时间只- - m a x 4 4 ， 2 3 = 4 4 ，完工时间c l = 蜀+ 露= 3 + 4 4 = 4 7 ：第二批 以，。，以，以，l ， ： 到达时 恻r ，- = t n a x 1 l ，1 9 ，2 0 ，3 8 ，4 4 = 4 4 c i = 4 7 ，丌始加工时间s 2 = c ，= 4 7 ，加工时间 只= m a x 3 4 ，3 6 ，3 5 ，3 6 ，3 3 = 3 6 ，完工时间c 2 = s 2 + 只= 4 7 + 3 6 = 8 3 第三批 以，厶， ， ，。2 ：到达时间r 3 = m a x 4 5 ，4 6 ，4 6 ，4 9 ，4 9 = 4 9 o ，b ， o ， 丝，牙，【0 ，6 ，口 ，0 ( j = 1 。2 ，z ) 是已知的，丝，是资源分配的下限，不失 一般性，可设丝，= o ，订j 是资源分配的上限，( 二。为排序的时问表长设c 为限定的 时间表长。问题的目标是使不可更新资源消耗总量“达到最小 当问题( 4 1 ) 中还包含任务间优先关系( p r e c ) 约束时，那么问题( 4 1 ) 变 成为问题( 4 2 ) 本文将给出求问题( 4 1 ) 和( 4 2 ) 最优资源分配的多项式算法 4 3 1 问题1 1 5 ，p = b ，一a j l l ，c 一t l z u 求此问题的最优解分两步首先，由文献 6 】知，对于任何给定的可行资源分配 向量甜，：，。) ，问题1 ，厅= 屯一口，群，i 的最优排列z 就是按到达时 间_ 不减排列不失一般性不妨设 r 2 ，即最优排列是z = 【1 , 2 ，川， 它与资源分配“= ( “，“：，“。) 无关；然后再求最优资源分配“( 算法( 4 3 1 ) ) 对于给定的c ，当不分配资源( 即z u 卸) 而得到的问题的时间表长c o = m a x n + 6 量，屯+ b k ，+ 饥，+ 钆) e 时，那么问题( 4 1 ) ( 或( 4 2 ) ) i = l t 2k - i。一 是平凡的当每个任务的资源分配都达到资源约束上限( 即材= 巧，- ，= 1 , 2 ，甩) 而 得到的问题( 4 1 ) ( 或( 4 2 ) ) 的时间表长。= m a x + p 。， t z l r 2 + p 一， 女= 2 + 窆p 。，。+ p 。) e 时，其中p j = b j - - a i 乃，那么问题( 4 1 ) ( 或( 4 2 ) ) 没 一f 有可行解因此我们总假定堡。c ，对f - ，+ l ，+ 2 ，i lo ) n 。s ，= s ，一i + p ，一1 ，f = f + 1 ，+ 2 ，n il 由递推关系s ，= s f _ 1 + p h ，i = l + 1 ，h + 2 ，h ，得到s i = s ，+ p 女 k 。， 1 s i = 5 ，十p t ，i = l + 1 ，l + 2 ，n t = ， n卜l“ + n j ，+ p i + p t = s ，+ p l ，i = l + l ，l + 2 ，n t = it = ll = fi = f h月n 由式( 4 5 ) e = m a x q + z p ，_ 。+ p ，+ p t ，r + p 。) = ，k = + lk = f = + p t 月 3 l s ，= r t ，e = + 仇，引理得证口 i = ， 定理4 3 1 算法4 3 1 得到的资源分配是问题( 4 1 ) 的最优资源分配，也 就是( z ，u ) 是问题( 4 1 ) 的最优解 证明：由引理4 3 2 知，当存在一个，使得，为满足= 成立的最大下标( 1 z n ) 时 c 。= c 。= + p 。= + ( 钆一a , u 女) i = ，t f 于是c 。的值只和下标大于或等于，的任务有关因此只有分配资源给下标大 ! 于等于，的任务，才可能使得c 。的值减少( 算法4 3 ，1 中的步骤( 3 ) ) n nn 又c 哪。= e ：+ 仇= + ( 6 。一吼“。) = l + 瓯一吼“。 i z ft f t = ft ；， 当c 。下降的相同值下，把资源分配给以( 七= ，i + i ，甩) 最大的任务时，资源 消耗最少，即目标函数“j 上升最小定理4 3 1 得证口 分批排序问题和资源约束排序问题 第叫章资源约束排序 4 3 2 问题li ，p r e c ，p ，= b ，一a j u jc 。、ci h ， 与问题( 4 1 ) 类似，求问题( 4 2 ) 的最优解也分两步首先求出在任何给定的资 源分配向量“= ( “l ，9 2 ，“。) 下的问题l ir j ，p r e c ，p ，2b j a u ，i c 。的最优排 列z ，注意到z 和加工时间没有关系【1 5 ，即与”= ( u ，撑：，u 。) 没有关系然后 求出最优资源分配u + ( 仍用算法4 31 ) 由文献 5 知，对于任何给定的资源分配向量u = ( u 。，u ：，u 。) ，即p ，= b j a ，u ， ( 已知) 问题1 ir ，p r e c l g 。是多项式可解的当为正的后继时，记为z 一 t 定义1 ：如果对于优先约束p r e c 中的任何满足- i 关系的两个任务i 、i ， 一定有关系，那么我们称问题的到达时间与优先约束 p r e c 是相适的，否则称 为不相适的 对于不相适的到达时间，从无前驱元开始，我们把每个任务的到达时间 修正 为弓： 巧：= m a x f 互- y = 1 ，2 。，栉 ( 4 6 ) 使修正后的到达时间与优先约束p r e c 成为相适的 下面假定到达时间与优先约束是相适的 算法4 3 2 1 5 ： ( 1 ) 置t ：= 互，正，e ，万- 0 ( 2 ) 设fct 是丁的无后继的任务全体所成子集， 选择五孝，使k = m a x ； r ，i 疋孝，) ，不唯一时任选一个 ( 3 ) 把正排在部分排列占的前边，形成新的排列，即6 ：= t ，巧】 ( 4 ) 如果丁o ，转( 2 ) ，否则停止计算 由 1 2 】知，算法4 3 2 得到的排列z + 是问题( 4 2 ) 的最优排列该算法的复杂性是o ( n 2 ) 值得注意的是算法4 - 3 2 得到的排列z 和加工时间没有关系 因此在得到最优排列z 下，再用算法4 3 1 可以求得问题4 2 ) 的最优解 分批排序问趔椰资源约束排岸问题 第五市总结 第五章总结 本文主要讨沦了分批、成组排序和资源约束排序中的有关i 司题 第二章对单机分批带到达时问的最大完工时间排序问题1 曰，ic n 。建立了 o 1 整数规划模型并进行了数值求解实验对任务数n 比较大的n p 一困难问题1 l b ， ，ic n 有较好效性能比的、有效的近似算法还有待进一步研究 第三章讨论了带滞留时问的两台同顺序成组流水作业排序问题f 2s 。 g tc ，给出了多项式算法 第四章讨论单机排序的资源分配问题l 0 ，p j = b j 一口，“，c e i “， 和1 r j ，p r e c ，p j = 6 一d ，“，c 。、e i “，以及离散资源约束排序问题 p 2 m ，p ，= 口，2 a ，j 免。( t 或r 的任务不能在两台机器上同时加工) ，并 给出了它们的多项式算法对于问题尸2l