（运筹学与控制论专业论文）几种最优资源分配与排序问题研究.pdf

兰州大学2 0 0 7 届硕士学位论文 中文摘要 排序是一类重要的组合最优化问题本文主要讨论了离散型、连续型、离散 与连续混合型三种最优资源分配与排序问题，对每种问题都给出了相应的多项式 算法及算例分析。 第二章讨论了形如己i ，嚣s h ，乃= l lc o 离散型多资源排序问题，这一问题 等价于一类整数规划问题，得到了一个求解基本向量的分枝定界算法。 第三章研究了形如1i 乃= 乃鸭) ，“j 材，c h a i n sl 岣勺的连续型问 题的算法及其算法复杂性，同时证明了由此所求出的资源分配“确系最优资源 分配。 第四章研究了形如： 1 i 硝，。= 哆一乃甜2 ，叶：，砒船j 勺+ 吩) 的离散与连续混合型排序问题，给出了最优排序和最优资源分配的定义，讨论并 证明了寻求其最优资源分配的多项式算法。 关键词：排序、最优资源分配、资源约束、算法复杂性、多项式时间算法、 数学模型。 兰舟f 大学2 7 届顽士学位论文 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 蛐i m p o r t a n tc o m b i n a t i o n a lo p t i m i z a t i o n p r o b l e mi n t h i st h e s i s ，w es t u d yp r o b l e m so ft h r e ek i n d so fo p t i m a l r e s o u r c ea 1 1 0 c a t i o na n ds o r t i n ga b o u td i s c r e t e l y - d i v i s i b l e ，c o n t i n o u s - d i v i s i b l ea n dm i x e do ft h e mw 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 m , p o l y n o m i a l 。t i m ea l g o r i t h mo fr 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 gp r o b l e m s a r eg i y e ni ne v e r yp a r t s i nt h es e c o n dc h a p t e r ，ai 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 d f o rt h e d i s c r e t e l y - d i v i s i b l e s c h e d u l i n g p r o b l e m w i t h 只i 脚 妇，乃= 1 ic 衄ab r a n c ha n db o u n da l g o r i t h mi sg i v e n i nt h et h i r dc h a p t e r ，ac o n t i n o u s - d i v i s i b l ea l g o r i t h ma n ds p e c i a l e x a m p l ea b o u tli 乃= ( “，) ，壹叶s 品，c h a i n si 一。i sg i v e n w es t u d x j 爿 t h ec o m p l e x i t ya n dp r o v et h a t i st h eo p t i m a lr e s o u r c ea l l o c a t i o n i nt h ef o u r t hc h a p t e r , w ed i s c u s sak i n do fp r o b l e ma b o u t 1 i 蟛，。= 岛一乃“o ，吩：，鸱勺+ ) t h ed e f i n i t i o no ft h eo p t i m a ls c h e d u l i n ga n dt h eo p t i m a lr e s o u r c e a l l o c a t i o na b o u tt h em i x e do f d i s c r e t e l y - d i v i s i b l e a n dc o n t i n o u s d i v i s i b l ea r eg i v e n i 丑t h em e a nt i m e w ed i s c u s sa n dp r o v eap o l y n o m i a l t i m ea l g o r i t h mo ff i n d i n gt h eo p t i m a lr 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 p 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 , o p t i m a l r e s o u r c e a 1 1 0 c a t i o n ，r e s o u r c e c o n s t r a i n ，c o m p l e x i t y ，p o l y n o m i a l t i m ea l g o r i t h m , m a t h e m a t i c a lm o d e l 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的 成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内 容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对 本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式 标明。 本声明的法律责任由本人承担。 论文作者签名：堪日期：率。 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名： 导师签名：擞日期；立型：! 兰州大学2 0 0 7 届硕士学位论文 第一章引言 排序问题是一类组合最优化问题，求解排序问题的基本思路是：应用或借鉴 求解其它组合最优化闯题的方法，充分利用排序问题本身的特殊性质，以确定满 足约束条件的最优排序。有些排序问题可直接转化成其它的组合最优化问题求 解。对具有多项式算法的排序问题，要尽可能地找出空间复杂性和时间复杂性好 的算法，所谓空间复杂性是算法所占存储的多少，时间复杂性指的是计算时间的 长短，它们都是输入规模的函数，本文主要考虑时间复杂。性对于还不知道是否 有多项式算法的排序问题，首先要用复杂性理论进行分析，看它是否是n p 难 的，求解这类问题有两种基本方法：一是用分枝定界法、动态规划等巧妙的穷举 法求出它的精确最优排序，这类算法计算量大，只有对规模较小的问题才是可行 的；另一种方法是求出它的近似最优排序，各种局部搜索法和启发式算法都是很 有效的，这类算法计算量小，并能满足一定的实际需要，为了知道所德到的近似 最优排序与最优排序的近似程度，分析误差界是使用这类方法不可缺少的工作， 也是比较困难的工作。 本文所讨论的是一类比较复杂的排序问题，在这类问题中，当处理任务或作 业时，除需要处理机以外，还需要另外的附加资源，我们把这一类排序问题称为 资源约束( r e s o u r c ec o n s t r a i n e d ) 排序问题。资源可分为可再生( r e n e w a b l e ) 的 和不可再生( n o n r e n e w a b l e ) 的两种，可再生资源指的是它在任意时刻的临时可用 性受到约束，也就是说这类资源被使用它的任务释放后还可以再次被使用，不可 再生资源指的是它的一次可用性，这种资源被某个任务使用以后，在任何时刻都 不能分配给其它任务，如果资源的临时可用性和一次可用性都受到限制，称它为 双重约束( d o u b l yc o n s t r a i n e d ) 资源。从可分性的角度来看，资源又分为离散 ( d i s c r e t e l y - d i v i s i b l e ) 资源和连续( c o n t i n u o u s d i v i s i b l e ) 资源，离散资源能 从有限个可能的分配量中选择一种量分配给任务，而连续资源以任意小于或等于 某个给定值的量分配给任务。 排序( s c h e d u l i n g ) 问题是利用一些处理机( 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 ) 的方案或调 兰捕大学2 0 0 7 届硕士学位论文 度，在执行这些任务或作业时需要满足某些条件，如任务的到达时间、完工的限 定时问、任务的加工顺序、资源对加工时阀的影响等，最优的完成是指使目标函 数达到最小，目标函数通常是指加工时间的长短，如最大完工时间、处理机的利 用率、时间表长、最大延误、加权误工任务数等。 排序问题产生的实际背景主要是机器制造，后来被广泛应用于计算机系统、 运输调度、生产管理等领域。小到普通的生产部门的计划安排、人员调度、学校 课程表的制定，大到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算 法。近年来，排序总是受到广泛的关注，国内外广大学者将其研究成果不断地应 用于各种生产与服务行业当中，并产生了巨大的经济效益。 处理机、任务和目标函数三要素组成了排序问题。处理机的数量、类型和环 境有近十种情况，任务或作业和资源的约束条件更是错综复杂，再加上度量不同 指标的目标函数，形成了种类繁多的排序类型。一般用g r a h a m 等人在 9 中首先 使用的三元组来描述排序问题的类型，这样大大简化了排序问题的表示 三元组记号由三域组成：a 俐7 其中n 域表示处理机的数量、类型和环境。 卢域表示任务或作业的性质、加工要求和限制，资源种类、数量和对加工的影响 等约束条件。1 域表示要优化的目标函数。对于资源约束型排序问题，我们假设 有s 种附加资源 r = 足，足，匙 它们的数量为 h = 仉，如，) 其中i 5 是第f 种资源玛的数量，每个任务在处理机上执行时需要一定数量的各种 资源 五( 乃) = ( 墨( 弓) ，恐( 乃) ，e ( 弓) ) ，2 1 ，2 ，力 其中矗够) ( o 碍何) 岛，z = l ，2 ，$ 表示任务乃需要第f 种资源局的单位数量。 在这一类资源约束排序问题中， 口域中用来描述资源约束的项为r 黜a a p ，其中 r e s 表示资源受限，a ，6 , p 分别表示资源的种类、数量和任务对资源的需求。 2 兰州大学2 0 0 7 届硕士学位论文 本文所研究的问题除形如p 2 r e s ，乃= l i c 二的不可中断单位加工时间 的资源约束排序问题以外，其它这种类型的资源约束排序问题都是n p 一难的。 首先，不同的准备时间使问题变成n p 一难，甚至只有一种资源的问题 p 2 r e s 1l r j ，乃= l i c 二就是强n p 难的。其次，增加一个处理机也使问题变 成强n 卜难的，例如问题粥i 删，乃= l i c 二就是强n p 难的。最后，最简单 的优先约束也会引起强n p - 难，如问题p 2 r e s l 11 ，c h a i n s ，弓= 4 c o 是强n 卜 难的。 本文主要在资源约束的条件下，研究了离散型、连续型、离散与连续的混合 型最优资源分配与排序问题。其基本形式分别是： 己i 馏砌，乃= 1 ic o 1i 乃= 乃鸭) ，“，- u ，c h a i n si u 勺 j l 1 l d 矿，o = q 一巳“2 j ，吩：, c h a i n s l ( q 勺+ 吩) 给出了最优排序和最优资源分配的定义，讨论并证明了寻求其最优资源分配的多 项式算法。 类似于这种资源分配与排序混在一起的最优化问题很多，本文的工作在有 效地研究与解决这类问题方面进行了有益的探讨。 兰捕大学2 0 0 7 届硕士学位论文 第二章一类离散性多资源排序算法 构造排序算法是重要的非数值计算问题。简单地说，所谓对n 个元素的排 序( s o r t i n g ) ，就是使用“比较”操作来判断两个元素的大小( 或先后顺序) ， 最终为这n 个元素确定一个全序：从小到大( 或从大到小) 排列起来。可以证明， 排序问题的计算时间复杂性下界不低于o ( 1 0 9 n ) ，已有的一些算法：如堆分类法、 合并法、最少插入法等均在复杂性阶的量级上达到最优，但确定主项系数或具体 复杂性公式仍是一个较困难的问题 2 1 模型描述 在作业排序问题中，由于工序开始时间的各种组合数量非常之大，所以在 数学上将它称之为大型组合问题。目前，对该问题进行解决的方法主要有以下三 种：一是整数规划，二是分支定界法，三是启发式算法。“分支定界法”避免了 完全穷举，但其分支搜索过程仍具有穷举的性质，对于肌 非流水作业系统的 作业排序，其搜索过程相当复杂，且当作业数目n 和机器数目m 稍增，计算量会 迅速增加丽失去实际意义。因此整数规划及分支定界法在作业数目和机器数目较 少时，可用来解决该类问题，在实际应用中，则大量使用启发式方法，以求得满 意解。 本章主要讨论的问题是：具有m 台平行机( m 为固定的常数) ，资源具有单 位时间约束的，目标函数为极小化最大完工时间的排序问题，用三参数法表示为： p mf ，嚣s h ，只= lc 0 ，其中艺表示埘台平行机，a h 中的j 表示有j 种资源， j j i 表示单位时间内资源的供给量最多是个h 单位，c o 表示目标函数是极小化最 大完工时间。 2 2 算法及复杂性 定义2 1如果工件对资源需求相同，则把这些工件称为一类，称 4 兰州大学2 0 0 7 届硕士学位论文 = ( ，n 2 ， ) 为问题的类工件向量，其中啊表示第f 类的工件数，这一个同 类工件有相同的资源需求，且满足：。一= n 其中_ i 为工件的类数，h 表示所有 工件的数目。 定义2 2 如果工件集 以，以，以) 的资源需求r “) ，胄( 以) ，且“) 满足 f m ，l 胄) ，则称它为排序问题的一个基本例子，基本例子对应的 类工件向量称为基本向量。 引理2 1 2 8 】设基本例子( 基本向量) 为，个，用岛，6 2 ，岛表示对应的基本向 量，则根据以上定义，对于问题p 胁i ，帮s h ，弓= 1c 二我们有以下两个结论： 1 基本例子的最优时间表长为1 2 任何解工件集都是一些基本例子的工件集的并集。 证明1 由基本例子的定义可知，构成基本例子的工件集满足资源约束，且个 数不大于m 个，即可以在单位时间内在m 台平行机上同时加工，所以最优时间 表长为1 。 2 因为任何一个单位时间内m 台平行机所加工的工件集都有构成一个基本例子， 所以任以一个可行解集的单位时间内所加工的工件集都是基本例子，从而任何解 工件集都是基本功例子的工件集的并集。 根据以上结论，求解问题砌ir e ms h ，鼻- - 1ic 0 等价于把工件集分解为最 少的基本例子，即把向量n 分解成一些基本向量6 1 ，屯，岛的线性组合，使 岛( 1 f ，) 的系数和最小，这一问题等价于整数规划问题： m i n z = 弓 l = l f “e a = n 自d e l 矿或0 ，i - - - - 1 , 2 ， 这样，求解最优排序的问题归结求基本向量6 j ，i = l ，2 ，z 。 兰州大学2 0 0 7 届硕士学位论文 下边给出一个求解基本向量的分枝定界算法，该算法是对文献【2 6 】中的算法 在资源约束下的改进，在每一层分支中检验满足资源约束条件的工件，对不满足 条件的分支“删掉”不予考虑，形成新的一层分支，并求出其对应的基本向量， 直至最后，这样使计算量减少了很多，便于实现。 算法2 1 1 l ； ，以，以) ，等“，他，) ，其中吩指第类工件数，鸭定义为第f 类 工件的集合，g = 1 ，；( o ，o ，o ) ，h 为资源约束，川= a o 2 ) 2 取m 若m 不是一个元素，转3 ；否则，着r ( ) | i l ，找出的位置f ，置乞中 第f 位加1 。输出所有的屯 3 1 - l 一 ) ，叫= m ，七；l ，矗1 ( ) ；r ( ) 。 4 判断：若r ( ) ，找出m 的f ，置中第f 位加1 ，置g # q + l 再 判断：r ( ) 叶，存 在两批马，且，不妨设岛，正马及以岛，下面分( 1 ) ( 2 ) ( 3 ) 三种情况 讨论： ( 1 ) 若批目先于忍加工，则可将以与作一交换，即将以与山同放在批易中， 将以放在批岛中，其它工件不动； ( 2 ) 若批骂先于目加工，则可将与作一交换，即将以与以同放在批易中， 将歹，放在批层中，其它工件不动； 由于其它工件的完工时间都不变，则调整后优于调整前，将所有具有这种 性质的工件都作一调整，则得到最优值所以每批中的工件编号是连续的。 ( 3 ) 若批易，丑同时完工，则可将工件以和交换或和交换，其它工件不 动，则总目标函数值不变。将所有具有这种性质的工件都作一调整，则总 目标函数值变优，所以每批中的工件编号是连续的。 下证除工件以所在的批可能不是满批外，其它批均是满的。 首先，在上面这个经过调整所提的最优排序中包含z 的批为满的。 否则，设其只含以，五，石，i b ，分( j ) 、( u o - = 种情况： ( f ) 若工件石+ ”正。，厶所在的批在以，以，以所在的批之后，则将后面批中 的以，以。，以一一调进，得到一个满批，其余不动，又因p j - - p ，目标 函数值变化。 ) 若工件以+ p 以：，厶所在的批在包含，五，以的一批之前，不妨假设工 件屯，厶：，以u + 1 i ) 所在的批在包含，以，以的一批之前，目标 兰州大学2 0 0 7 届硕士学位论文 函数值变优，然后再按( o i t 程调整。 ( i ：f _ f ) 若工件以+ ，+ 2 ，以u + 1 七 ) 所在的批与，五，4 所在的批具有相 同的完工时间，下面再分两种情况： 若七口，则将工件，厶，凡：，厶一一调进以，以p o * o 以所在批，使以所 在的批为一满批，其它工件不动，则目标函数值不变。 若j & + 。，那么文一 - e t , 。c j - - ( o 口j c j ) = 6 l q + 6 2 q + + “一“l a l e o j t 一“：d ： n d s - 2a“l-2 一q 一“州a k + l q 一u n a n o j a b 喜q + 如骞q + + 拈。一地q 喜q 一如吒骞q 一t 娄q 一- 吼毫q 一一峨li - ii 一2 自l k ： # m i # 月 = u k a 。+ 。q + + 。q 扣j = k + l 一n t 喜叫a k + i 。o j t 2 a k + i - a k 地莓+ 瓴一吒“m 三q，= t忙i + i扭 i o # 十- = 瓴+ l 一吼) i。nq 一+ 。q | = 瓴+ l 一吼) l “一+ 一) q + 蚝ql m#t+1 i = k + l 由条件，= ，= 1 ，2 ，j l 可知，上式等于( 吒+ 。一吼) 魄，因为吒 + l ， 所以上式的值小于o ，即将任务按非增顺序排列得到的就是任务的最小捧列 ) 为了记号上的方便，不失一般性，设按吃n 非减顺序排列的任务下标排列为： z = k ，毛，磊+ i ，毛】2 阻2 ，孟，k + l ，万】， 而另外一组任务的下标排列为z 7 = 【1 2 ，k + l ，七， 】， ” 兰闸大学2 0 0 7 届硕士学位论文 其中吃 也。，那么。 噬，所以 e 一“i 以e w l - - u “。a k 。q 一一吒“一 l = k= l + l 1 月 l b q 十6 2 q + + 屯一地q - - u 2 a 2 q 一吼+ q 一“i + 。吼q 一一d v l l j - 1 “z h lh2，“ m 十li = 龟q + 虮q 也+ ，q 吨q f = tl “+ 1 k t l = k + l d = ( k 一瓯+ 。) q + ( 6 i “一以) 0 2 i - t扭t “ = 训睁l = k 一毫叫 忙i + 】 ， 由条件q = u 可知，上式等于= 一魂+ 1 ) 峨，又因为 魄+ l ，所以，上式小 于0 ，即将任务按，非减顺序排列得到的就是任务的最优排列 定义3 3矿z ，“是相应于z ，的最优资源分配，记 力= 纽警，例，2 ，n 州d 如果8 硝i ) 1 2 ) ，则称z 为问题( 3 1 ) 的稳定点。 定理3 6 稳定点是最优解的必要条件。 证明设z 是最优解，掣是相应于z 的最优资源分配，则一定有 吼i ，2 ) 帕，否贝，设存在f t ，使 _ ) ，交换z + ( f ) 和z + 的位置，得到另一个下标排列；“，则“是相应于z ”的一个资源分配，但不 一定是最优资源分配所对应的目标函数值记为 啊n c d 则有 硝f 卜州t ) 力e ，i ) 嗡力) 一 ，【j 】h ，【) 上式与是2 最优解矛盾，定理证毕。 算法3 3 q m 巳也 一 屿 q 距 一 q屯 + q 。m + q 岛 = 兰州大学2 0 0 7 届硕士学位论文 ( 1 ) 取初始点：o z ，置j i ；0 ( 2 ) 调用算法3 2 ，求相应于矿的最优资源分配矿 ( 3 ) 计算 q ：b = , - a eu * e , ，- ，：1 ，2 ，行 j u 1 ( 4 ) 按的递增的顺序重新排列得到_ ( 若2 ，毛和弓的相对位 置不变) ，如果譬：_ 。吒0 ，算法终止否则置量# | i + l ，转2 定理3 7算法3 3 是一个下降算法，算法终止于稳定点。 证明 用 表z k + 。按分配资源的目标函数值，则 善气 c - 。，置，冀 u h = q ，f l ，转4 ，执行4 后再转6 回， 。，且晤旁q 叶；吩+ 土a j ，2 屯一吩“0 ，_ ， q 每m a x q ) + 。u = 1 ，2 ，一问；【，# u 一( 若旁， t # _ i + 1 ，u 7 ；吩，矿# _ ，q 一q ，( j = l ，2 ，帕； c 声0 tk # l ，缸一- a r u t # uc 0 ；c i t 高i 5 ) u o ，转3 ；u = o ，进行下一步 6 )置 u 1 一- u j ( j = l 2 ，砂矿= ( + ，坞+ ，+ ) 7 )令 叶净，r j * 净矿，q + 车q 。，u = l ，2 , - - - , 厅) c # 0 ，c 一= c 一，a r + 等吃 严# 丘，扩净以 8 )停机 注h 为了后面定理证明的方便，现将算法4 1 第3 ) 步( 2 ) 中的i ) 、哟改为 f ) ，= 0 ，转4 ，执行4 后转6 ； f f ) r 0 ，置“。剐，+ 考， o 并记所得的算法为：算法4 2 兰州大学2 0 0 7 届硕士学位论文 注2 ：算法4 1 和算法4 2 中2 ) 、4 ) 、7 ) 三步是为下面定理的证明而添加的。 经算法分析易知本算法是一个多项式算法，且复杂性为o ( n 2 ) ；下面的定理4 i 肯 定用这一算法所求出“的是闯题( 4 1 ) 的一个最优资源分配。 引理4 i对于算法4 1 和算法4 2 ，有： 1 ) 一。c ，( 1 _ i 扩) ( 当循环次数后增加时，i 中元素不减) 2 ) 吩“ u j ，( 1 _ n ) ，( 1 七驴) ( 当循环次数七增加时，资源量叶不减) 3 ) 叶+ - - 0 ，- j + ( 对