（控制科学与工程专业论文）基于复杂网络理论的复杂调度问题求解方法研究.pdf

浙江大学博士学位论文 摘要 摘要 调度作为资源分配的一种手段在各个领域都得到了广泛的重视。现实 中的调度对象通常具有动态性，随机性，以及不确定性等特点，本文中把 该类调度对象称为复杂调度对象，而相应的调度问题则称为复杂调度问题。 调度规则由于其简单灵活的特点，被广泛采用于求解复杂调度问题。当前 的调度规则大多源于生产实际，缺少一种系统化的方法。复杂网络作为研 究复杂系统结构的一种新兴的理论为调度提供了新的契机。本文通过给复 杂调度对象建立复杂网络模型，从而将复杂调度问题转换成复杂网络上的 节点遍历问题，并且在复杂网络的框架下提出了系统化设计调度规则的方 法。最后将这些调度规则用于求解多资源独立任务复杂调度问题取得了不 错的效果。本文的研究内容以及创新点主要包括以下几个方面： 根据现实的复杂系统特点从三种不同的视角提出了三个多特征复杂网 络模型，包括区域固定局部世界模型，能力固定局部世界模型，以及基于 博弈的动态演变模型。 首次给出了复杂调度对象的网络化描述，将复杂调度问题转换成复杂 调度网络上的节点遍历问题，这为解决实际复杂调度问题提供了新的视角 和方法。 通过某种映射关系可以把调度目标转换成复杂调度网络的某个全局特 征，从而将复杂调度网络的局部特征作为设计调度规则的启发式信息。比 如网络平均度值以及平均功效和复杂调度问题之间就存在某种关联，而节 点度值，节点聚类系数，以及本文提出的节点冗余度均可作为设计调度规 则的启发式信息。 给出了复杂调度网络建模的具体步骤，并且通过这些步骤在基于一些 假设的基础上给四类复杂调度对象，多资源独立任务每个事件所需资源数 服从均匀分布调度对象，多资源独立任务每个事件所需资源数服从幂律分 布调度对象，多资源非独立任务每个事件所需资源数服从均匀分布调度对 象，以及多资源非独立任务每个事件所需资源数服从幂律分布调度对象， 构建了各自的复杂调度网络模型，并对这些复杂调度网络进行了结构特征 分析。 浙江大学博士学位论文 摘要 提取了三种基于复杂调度调度网络结构的调度规则，主要包括基于节 点度值，聚类系数，以及冗余度的调度规则，并将它们用于求解多资源独 立任务复杂调度问题，相比几种经典的调度规则而言，取得了不错的效果。 关键词调度；多资源；独立任务；复杂网络；节点遍历；系统化设计； 调度规则；启发式；节点度值；聚类系数；冗余度；博弈 l v 浙江大学博士学位论文a b s t r a c t a bs t r a c t s c h e d u l i n g ，a sar e s o u r c ed i s t r i b u t e dp l a n ，i sr e c o g n i z e da n dw e l ls t u d i e d i nv a r i o u sa r e a sa n dd e p a r t m e n t s r e a l - w o r l ds c h e d u l i n go b je c t sa r ea l w a y s d y n a m i c ，s t o c h a s t i c ，a n di n d e t e r m i n a t e s u c hs c h e d u l i n go b j e c t sa r en a m e da s c o m p l e xs c h e d u l i n go b j e c t si n t h i st h e s i sa n dt h ec o r r e s p o n d i n gs c h e d u l i n g p r o b l e m sa r en a m e da sc o m p l e xs 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 gr u l e sa r et h e m a i nm e t h o d st os o l v et h i st y p eo fs c h e d u l i n gp r o b l e m sf o rt h e i rs i m p l e n e s s a n df l e x i b i l i t y h o w e v e r ，m o s to fe x i s t e ds c h e d u l i n gr u l e sa r es u m m a r i z e d f r o mo p e r a t o r s e x p e r i e n c e sa n dt h e r el a c k sas y s t e m a t i c a ld e s i g n i n gm e t h o d c o m p l e xn e t w o r k ，a sat o o l t h e o r yt od e s c r i b ea n da n a l y z et h es t r u c t u r eo f c o m p l e xs y s t e m s ，m a yp r o v i d eat o t a l l yf r e s hv i e wf o rs c h e d u l i n gp r o b l e m s t h r o u g hb u i l d i n gc o m p l e xn e t w o r km o d e l sf o rt h o s ec o m p l e xs c h e d u l i n g o b j e c t s ，t h ec o m p l e xs c h e d u l i n gp r o b l e m sc a nb et r a n s f e r r e dt on o d et r a v e r s e p r o b l e m so nc o m p l e xn e t w o r k s t h e nal o to fs c h e d u l i n gr u l e sc a nb ep r o p o s e d u n d e rt h eb a c k g r o u n do fc o m p l e xn e t w o r kt h e o r y i nt h i st h e s i s ，t h r e en e w s c h e d u l i n gr u l e sa r es y s t e m a t i c a l l yp r o p o s e da n da p p l i e dt om u l t i - r e s o u r c e s i n d e p e n d e n tt a s kc o m p l e xs c h e d u l i n gp r o b l e m s ，a n dg e tv e r yw e l lr e s u l t s t h e m a i nc o n t e n t so ft h i st h e s i si n c l u d ef o l l o w i n gf i v ep a r t s ： p r o p o s et h r e em u l t i p r o p e r t i e sc o m p l e xn e t w o r km o d e l sb a s e do nt h e m e a s u r e m e n t so fm a n yr e a l - w o r l dc o m p l e xs y s t e m s t h et h r e em o d e l sa r e r e g i o n - f i x e dl o c a l - w o r l dm o d e l ，a b i l i t y - f i x e dl o c a l w o r l dm o d e l ，a n dg a m e t h e o r yb a s e dd y n a m i c a le v o l v i n gm o d e l d e s c r i b i n gc o m p l e xs c h e d u l i n gp r o b l e m sw i t hc o m p l e xn e t w o r k sf o rt h e f i r s tt i m e ，t h es c h e d u l i n gp r o b l e m st h e nc a nb ec o n s i d e r e da sn o d et r a v e r s e p r o b l e m so nc o m p l e xn e t w o r k s ，w h i c hp r o v i d e sn e w v i s u a la n g l e sa n dm e t h o d s t os o l v ec o m p l e xs c h e d u l i n gp r o b l e m s t h el o c a lp r o p e r t i e so fn o d e si n c o m p l e xs c h e d u l i n gn e t w o r k s a r e c o n s i d e r e da sh e u r i s t i ci n f o r m a t i o nf o rc o m p l e xs c h e d u l i n gp r o b l e m sa n du s e d t od e s i g ns c h e d u l i n gr u l e s ，t h r o u g hm a p p i n gt h es c h e d u l i n gp r o b l e m st og l o b a l p r o p e r t i e s ，e g ，a v e r a g ed e g r e eo ra v e r a g ee f f i c i e n c y ，o ft h en e t w o r k s a n d s e v e r a ll o c a lp r o p e r t i e so fn o d e s ，e g ，d e g r e e ，c l u s t e r i n gc o e f f i c i e n t ，a n d r e d u n d a n c yp r o p o s e db yt h i st h e s i sa r ea l lc a nb eu s e dt od e s i g ns c h e d u l i n g r u l e s v 浙江大学博士学位论文a b s t r a e t p r o v i d ed e t a i l e ds t e p sf o rm o d e l i n gc o m p l e xs c h e d u l i n gn e t w o r k sa n d f o l l o w i n gt h e s es t e p s ，b u i l dc o m p l e xs c h e d u l i n gn e t w o r km o d e l sf o rf o u rt y p e s o fc o m p l e x s c h e d u l i n go b j e c t s ，i e ，m u l t i - r e s o u r c e si n d e p e n d e n t t a s k s c h e d u l i n go b j e c t sw i t ht h en u m b e ro fr e s o u r c e so n ee v e n tn e e d e df o l l o w i n g u n i f o r md i s t r i b u t i o n ，m u l t i r e s o u r c e si n d e p e n d e n tt a s ks c h e d u l i n go b j e c t sw i t h t h en u m b e ro fr e s o u r c e so n ee v e n tn e e d e df o l l o w i n gp o w e r l a wd i s t r i b u t i o n ， m u l t i r e s o u r c e s d e p e n d e n t t a s k s c h e d u l i n go b j e c t s w i t ht h en u m b e ro f r e s o u r c e so n ee v e n tn e e d e df o l l o w i n gu n i f o r md i s t r i b u t i o n ，a n dm u l t i - r e s o u r c e s d e p e n d e n tt a s ks c h e d u l i n go b je c t sw i t ht h en u m b e ro fr e s o u r c e so n ee v e n t n e e d e df o l l o w i n gp o w e r l a wd i s t r i b u t i o n t h e ng i v es t r u c t u r a l a n a l y s i sf o r t h e s ec o m p l e xs c h e d u l i n gn e t w o r k s p r o p o s et h r e ed i f f e r e n ts c h e d u l i n gr u l e sb a s e do nt h es t r u c t u r eo fc o m p l e x s c h e d u l i n gn e t w o r k s ：d e g r e eb a s e dr u l e ，c l u s t e r i n gc o e f f i c i e n tb a s e dr u l e ，a n d r e d u n d a n c y b a s e dr u l e t h e n a p p l y t h e s e s c h e d u l i n g r u l e st o s o l v i n g m u l t i r e s o u r c e si n d e p e n d e n tt a s kc o m p l e xs c h e d u l i n gp r o b l e m s ，a n dg e tb e t t e r r e s u l t sc o m p a r e dw i t hs e v e r a lo t h e rc l a s s i c a ls c h e d u l i n gr u l e s k e y w o r d ss c h e d u l e ；m u l t i r e s o u r c e s ；i n d e p e n d e n tt a s k ；c o m p l e xn e t w o r k ； n o d et r a v e r s e ；s y s t e m a t i c a l l yd e s i g n ；s c h e d u l i n g r u l e ；h e u r i s t i c ；d e g r e e ； c l u s t e r i n gc o e f f i c i e n t ；r e d u n d a n c y ；g a m et h e o r y 浙江大学博士学位论文 插图目录 插图目录 图1 1 由两台机床和三个任务组成的开放车间问题( 左) 以及它对应的p e t r i 网，其中s 1 ，s 3 ，和s s 为未成品，s ，和s 。为s ，的半成品，而s 6 ，s 和 s 。为s 。，毛，和s 。对应的成品，s ，和s 。表示机床，t ，一t 。为组装环节， 圈中的黑点表示该产品或机床的数量。7 图2 1 复杂调度对象的网络化描述示意图。3 0 图2 2 本文研究思路的系统框图( 实线部分) ，以及后续可以深入研究的内 容( 虚线部分) 。图中的“事件触发”是指当新任务到达( 即产生新的 待处理事件) 或者某个事件被处理完时触发调度决策。3 0 图2 3 一个简单动态o p e ns h o p 调度对象的网络化描述。3 2 图2 4 一个简单动态o p e ns h o p 调度网络的某个调度过程。绿色节点表示当 前时刻正在遍历的节点，不着色的节点表示当前时刻未遍历到的节点， 遍历完的节点连同和它相连的边一起退出调度网络。调度约束反映在图 中绿色节点之问都没有直接连接，调度目标反映在在最短的时间内让整 个调度网络消失。3 4 图2 5 杭州萧山机场飞机航班到达机场信息表。3 6 图2 6 杭州萧山机场飞机航班离丌机场信息表。3 6 图2 。7 杭州萧山机场2 0 次航班对应的复杂调度网络( 其中三个时刻的网络 场景) 。3 7 图2 8 四个不同任务的子任务d a g 。3 9 图2 9 三个p c 机组成的网格资源。3 9 图2 1 0 网格计算调度网络的某个场景。3 9 图2 1 l 两个钢锭初轧任务分解网络。4 2 图2 1 2 两个钢锭初轧任务因资源冲突形成的子网络。4 2 图2 1 3 钢锭初轧过程调度网络的某个场景。4 3 图2 1 4 运动会赛程安排调度网络的某个场景。4 4 图3 1 网络节点的特征通常可以通过该节点的某些局部信息( 用虚线圈表示) 来定义，比如图中红色节点有四个直接相连的节点，而绿色节点有三个 直接相连节点，这就体现了这两个节点之问的差异，该特征定义为节点 的度值，在后文中还将进一步阐述。4 9 图3 2 三个不同类型的网络，需通过定义网络的全局特征来区分它们，比较 简单的有节点总数，边总数，平均节点度值，节点度分布等。5 0 图3 3 网络结构向特征空问的映射。从一个网络结构中可以提取很多个特征， 把它们排列成一个向量的形式则可看成是某个特征空间的一个点，如果 反过来这些特征能够唯一确定某类或某个网络，则可以认为该特征向量 完全表示该类或该个网络，形成一一映射。5 0 图3 4 图中a l 号节点的度值分别为：5 ，2 ，3 ，2 ，3 ，4 ，2 ，1 ，l ，1 ，l ， v 浙江大学博士学位论文 插图目录 1 。：，：! 图3 5e r 随机网络：( a ) 一个简单的例子；( b ) 1 0 个节点数为1 0 ，0 0 0 连接概 率为p = 0 2 的随机网络的平均度分布图【1 3 】。5 3 图3 - 6 几个不同类别复杂网络的度分布【1 0 】。( a ) 演员合作网络，其中节点个 数为n = 2 1 5 , 2 5 0 ，平均度值为( k ) = 2 7 7 8 。( b ) 万维网，其中节点个数 为n = 3 2 5 ，7 2 9 ，平均度值为( k ) = 5 4 6 。( c ) 电力网，其中节点个数为 n = 4 9 4 1 ，平均度值为( k ) - 2 6 7 。它们幂分布的指数分别为：( a ) 7 一，= 2 3 ，( b ) 7 = 2 1 ，以及( c ) 7 。，= 4 。一5 3 图3 7 节点聚类系数的计算图示，节点f 的聚类系数可以理解为节点f 周围节 点( 与节点f 直接相连) 形成的一个局部网络所含的边数与这些节点形 成的全连接网络所含的边数的比值，图中节点a l 的聚类系数分别为： 1 1 0 ，0 ，0 ，0 ，1 3 ，1 6 ，0 ，0 ，0 ，0 ，0 ，0 。5 5 图3 8 ( a ) 网络的模块化结构；( b ) 网络的层次模块化结构【1 1 1 。5 6 图3 - 9 几种不同细胞代谢网络的聚类函数【1 1 】。5 7 图3 1 0 某节点出现故障时( 打红叉的节点) ，它周围的边将一起失去效用( 打 红叉的边) 。6 0 图3 1 1 一个简单的关于节点重要性的例子。6 l 图3 1 2 一个简单的关于节点f 的两阶局部网络图，在图中节点f 共有5 个邻 节点，分别是a ，b ，c ，d ，和e 。这5 个邻节点之间只有两条直接连接 的边，分别为a b 和c d ，用棕色的边表示；而它们之中还有几对节点通 过另外的节点间接相连的，用蓝色的点和边表示，如节点b 和节点c 通 过节点g 间接相连。6 2 图3 1 3e r 随机网络的平均遍历时间与网络平均度值( k ) 之间的关系图。( a ) 连接概率p 取0 ，0 1 ，1 。( b ) 为了反映细节，连接概率p 取 o 0 1 ，0 0 2 ，o 0 9 。6 5 图3 1 4e r 随机网络的平均遍历时间与网络节点总数之间的关系图，其中 所有不同规模网络的平均度值都等于8 。6 6 图3 1 5 网络平均最短路径( d 随着节点发生故障( 方) 或被攻击( 圆) 所占 总体节点数比例厂的增加而变化的情况 2 0 4 】。( a ) 因特网，包含6 , 2 0 9 个节点以及1 2 ，2 0 0 条边( ( k ) _ 3 4 ) 。( b ) 万维网，包含3 2 5 ，7 2 9 个节点 以及1 ，4 9 8 ，3 5 3 条边( k = 4 5 9 ) 。6 8 图4 1 表4 1 所示任务一资源分配表对应的2 0 个任务到达时刻复杂调度网络 场景结构示意图。7 6 图4 2 资源数为2 0 0 的对应复杂调度网络的网络平均度值( k ) ( 左) 和网络 平均功效( e ) ( 右) 随时间变化规律图，其它参数设置为s 。= 1 ，s ，= 5 ( 多 资源独立任务复杂调度对象每个任务所需资源数服从均匀分布) 。从左 图双对数图中可以看出该复杂调度网络的平均度值随着时间的推移呈 v 1 1 1 浙江大学博士学位论文插图目录 幂函数增长，而从右图单对数图中可以得出网络平均功效随着时间推移 呈对数增长。7 7 图4 3 资源数为2 0 0 在动态到达5 0 0 个任务时刻对应复杂调度网络场景的度 分布图( 左) 和聚类函数图( 右) ，其它参数设置为s 。= 1 ，s ，= 5 ( 多资 源独立任务复杂调度对象每个任务所需资源数服从均匀分布) 。7 8 图4 - 4 表4 2 所示任务一资源分配表对应的2 0 个任务到达时刻的复杂调度网 络场景结构示意图。7 9 图4 5 资源数为2 0 0 的对应复杂调度网络的网络平均度值( k ) ( 左) 和网络 平均功效( e ) ( 右) 随时间变化规律图，幂函数指数参数设为旯= 3 ( 多 资源独立任务复杂调度对象每个任务所需资源数服从幂律分布) 。从左 图双对数图中可以看出该复杂调度网络的平均度值随着时间的推移呈 幂函数增长，同样从右图单对数图中可以得出网络平均功效随着时间推 移也呈幂函数增长。8 0 图4 6 资源数为2 0 0 在动态到达5 0 0 个任务时刻对应复杂调度网络场景的度 分布图( 左) 和聚类函数图( 右) ，幂函数指数参数设为五= 3 ( 多资源 独立任务复杂调度对象每个任务所需资源数服从幂律分布) 。8 0 图4 7 表4 3 所示事件一任务一资源分配表对应的5 个任务到达时刻的复杂 调度网络场景结构示意图。8 3 图4 8 资源数为2 0 0 的对应复杂调度网络的网络平均度值( k ) ( 左) 和网络 平均功效( e ) ( 右) 随时间变化规律图，其它参数设置为s j = 1 ，s ，= 5 ， e b = l ，e ，= 5 ( 多资源非独立任务复杂调度对象每个任务所需资源数 服从均匀分布) 。从左图双对数图中可以看出该复杂调度网络的平均度 值随着时问的推移呈幂函数增长，而从右图单对数图中可以得出网络平 均功效随着时间推移呈对数增长。8 3 图4 9 资源数为2 0 0 在动态到达2 0 0 个任务时刻对应复杂调度网络场景的度 分布图( 左) 和聚类函数图( 右) ，其它参数设置为s 。= 1 ，s ，= 5 ，e 。= 1 ， e ，= 5 ( 多资源非独立任务复杂调度对象每个任务所需资源数服从均匀 分布) 。8 4 图4 1 0 表4 4 所示事件一任务一资源分配表对应的5 个任务到达时刻复杂调 度网络场景结构示意图。8 6 图4 1 1 资源数为2 0 0 的对应复杂调度网络的网络平均度值( k ) ( 左) 和网络 平均功效( e ) ( 右) 随时间变化规律图，其它参数设置为五= 3 ，e b = 1 ， e = 5 ( 多资源非独立任务复杂调度对象每个任务所需资源数服从幂律 分布) 。从左图双对数图中可以看出该复杂调度网络的平均度值随着时 间的推移呈幂函数增长，而从右图单对数图中可以得出网络平均功效随 着时问推移呈对数增长。8 7 图4 1 2 资源数为2 0 0 在动态到达2 0 0 个任务时刻对应复杂调度网络场景的 i x 浙江大学博士学位论文插图目录 度分布图( 左) 和聚类函数图( 右) ，其它参数设置为2 - - 3 ，e b = 1 ，e 。= 5 ( 多资源非独立任务复杂调度对象每个任务所需资源数服从幂律分 布) 。8 7 图6 1 采用三种经典调度规则( r a n d o m ，l p t ，l q r ) 和本文提出的三种 调度规则( d ，c ，r ) 得到的结果相比采用完全随机调度规则得到的结 果的增量百分比示意图( 任务所需资源数服从均匀分布的多资源独立任 务复杂调度问题) 。1 0 9 图6 2 采用三种经典调度规则( r a n d o m ，l p t ，l q r ) 和本文提出的三种 调度规则( d ，c ，r ) 得到的结果相比采用完全随机调度规则得到的结 果的增量百分比示意图( 任务所需资源数服从幂律分布的多资源独立任 务复杂调度问题) 。1 10 x 浙江大学博士学位论文附表目录 附表目录 表1 1 几类调度算法比较列表。1 4 表2 12 0 次航班在机场的停留时间区间表。3 6 表2 2 钢锭初轧过程不同阶段所需的资源列表。4 1 表4 1 多资源独立任务资源数服从均匀分布的任务一资源分配表。7 5 表4 2 多资源独立任务资源数服从幂律分布的任务一资源分配表。7 9 表4 3 多资源非独立任务资源数服从均匀分布的事件一任务一资源分配表。 8 ：! 表4 4 多资源非独立任务资源数服从幂律分布的事件一任务一资源分配表。 8 1 ； 表6 一l2 0 个例子e x l e x 2 0 的参数设置表。一1 0 3 表6 22 0 个例子中初始复杂调度网络场景的度值方差，聚类系数方差，和冗 余度方差的比较一览表。10 4 表6 3 三种经典调度规则( r a n d o m ，l p t ，l q r ) 和本文提出的三种调度 规则( d ；c ，r ) 用于求解2 0 个多资源独立任务复杂调度问题得到的 结果列表。1 0 8 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得逝姿盘堂或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位做作者龇留喷签字吼埘年莎月i 1 日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权逝江盘堂可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字日期：瑚年舌月 7 日签字日期：) 矿舴舌月l1 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 浙江大学博士学位论文致谢 致谢 随着本博士论文的完工，二十一载的求学生涯终将告一段落。在此首 先我要感谢我的导师吴铁军教授和李艳君副教授。跟随吴老师走过这五年 应该说是我人生中的一大幸事。一方面，吴老师渊博的知识，睿智的思维， 以及严谨的学术作风时时刻刻指引着我在学术上的开拓进取，每次和他交 流都能让我收获新的知识以及克服难题的信心；另一方面，吴老师一丝不 苟以及锐意进取的人生态度同样也必将影响我终生。李老师则更像是一位 细心的大姐，无论是科研或是生活都能给我以指导和启迪，非常怀念大家 在一起做项目的那段时光，虽辛苦但开心。衷心感谢陈关荣教授将我引入 复杂网络这个充满挑战的领域。同时也由衷地感谢系里其他老师在学习和 科研上给予我的关怀和帮助。 感谢武晓莉师姐，孙丽丽师姐，王梅师姐，刘庆平师兄，和徐伟强师 兄在我刚进实验室时给予我的指导和帮助：感谢张雪雯，陈迎迎，俞峰， 和徐德刚在我刚进课题组时给予我的鼓励，每次和你们的讨论都能让我获 益匪浅；感谢杜方在程序设计方面的指导；感谢蔡晓慧，李宗涛，江文德 在一起完成项目时给予的帮助，和你们的合作非常愉快；感谢d r l u nl i 提供的博士论文；感谢常爱英师姐，郑俊华，陈俊风，周春芳，周微，崔 成刚，周黔，王磊，于海生，衷路生，马俊等同门师兄弟师姐妹们给予的 鼓励和帮助。所有这些经历都是我人生中的宝贵财富。 感谢一起携手走过这段岁月的兄弟们，童长飞，李小波，黄少锋，唐 亮，程路，张浩，郑松，候鑫，王旭，徐玉，方舟，你们的陪伴和鼓励在 这五年中给予了我极大的动力，怀念一起讨论学术，打篮球，ks c ，以及 聚餐的同子，。相信大家都会有美好的未来，加油! 最最感谢我的父母，你们的殷切期望是我努力奋斗的原动力，你们的 谆谆教导我将永远铭记在心中，家永远是我最宁静的避风港。 最后向所有帮助过我和将要帮助我的老师，同学，和朋友们表示最诚 挚的感谢，谢谢你们为我做的一切! 宣琦 2 0 0 8 年4 月 于求是园 浙江大学博士学位论文第1 章绪论 第1 章绪论 摘要资源调度作为资源分配的一种手段在各个领域都得到了广泛的重视， 在各个领域，当前已提出很多调度对象建模方法，并根据这些模型提出了 很多调度算法，但总体而言，各种模型优缺点并存，而提出的调度算法也 有其不同的适用对象。复杂网络作为研究复杂系统结构的一种统计物理学 领域的新兴理论则为求解资源调度问题提供了新的契机。本章首先介绍调 度领域当前存在的调度对象建模方法和调度算法，并简略分析它们各自的 优缺点；紧接着简略介绍复杂网络理论当前的一些研究现状；随后提出本 文的研究动机和方法；在此基础上给出本文研究内容及其结构组织；最后 给出本文创新点。 关键词调度；调度规则；复杂系统；复杂网络 1 1 引言 通常系统被定义为是相互联系，相互作用的诸元素的综合体，精确地 讲一个系统中必须包含至少两个不同对象，这些对象称为系统的组分，按 一定的方式联系在一起。一般而言，系统的组分可以划分为更小的组分， 构成系统的最小组分或基本单元，即不可再细分或无需再细分的组成部分 称为系统的元素。此处所谓元素的不可再分性是相对于他所隶属的系统而 言的，离开这种系统，元素本身又可看作由更小组分组成的系统 1 ，2 。对 于一个经典的生产调度系统而言 3 ，某个任务在某台机器上加工称作一个 事件可看作是该系统的元素，而某两个事件之间有资源竞争，比如都需要 使用某台机器或者涉及到同一个任务，则可以看成是对应的两个元素之间 有关联。 作为一个系统，最关键的地方在于它的涌现性，即若干元素相互作用 能产生这些元素不曾拥有的新性质，此处元素之间的相互联系起了至关重 要的作用 1 ，2 。单独的机场只能用来停飞机，但在机场之间开辟了航线就 形成了一个复杂的航空系统；同样工厂过程系统中的元素，比如反应装置， 加热、冷却装置，或者存储装置，只有当把它们按照一定的方式组装在一 起时才能体现出应有的价值；更不用说生命系统中无生命的原子和分子组 织成细胞，蛋白质然后产生生命这种神奇的性质了。而调度问题之所以成 为一个问题也正在于元素之间的相互联系，即资源竞争，如果没有了这些 资源竞争 3 ，比如对于任何一个经典的生产调度系统而言，任何一种机器 浙江大学博士学位论文第1 章绪论 无限多，则所有任务并行运行即可，完全不必要提出所谓的调度算法。通 过这些实例，可以清楚地看到系统中元素相互关联形成的系统结构应当是 系统之所以成为系统的灵魂所在。而所谓的系统结构则可以用一个网络图 来描述 4 ，5 。图中每个节点表示一个系统组分，每条边表示相应的两个组 分之间的某种关联，这样任何一个复杂系统都可以用一个网络结构，各个 节点的动力学函数，以及各条边的关联函数来完美地表示。去掉节点的动 力学函数以及边的关联函数剩下的网络拓扑结构就可以完美地描述一个系 统的结构。 系统结构的重要性人所共知，而现实复杂系统的结构中含有随机性这 一点也被大家普遍承认，一直在2 0 世纪术以前，在研究许多未知的复杂大 系统时，人们一直在随机图( e r 随机网络 6 ，7 ，即给定一批节点，任何两 个节点之间的连接概率都相等，等于某个介于o n l 之间的实数) 的框架下 来描述这种复杂系统结构的随机性 8 ( 对于较小规模的系统而言，如果能 用网络描述它的基本结构，则结构随机性可以用该网络图中节点随机消失 和增加以及边的随机消失和增加来描述) 。这有其相关的历史背景，因为 在这个阶段计算机科学刚刚起步，数据搜集以及处理能力非常落后，无力 具体了解这些复杂系统的结构，因此把复杂系统的结构用随机图来描述的 这种想法就好比通常人们认为提取的现实数据中含有白噪声那么自然，无 可厚非。当前，随着各个学科，特别是计算机学科的发展，使得我们能够 获取各种系统的大量数据，并且能够快速地对它们进行分析，通过提取这 些实际系统的网络拓扑结构，科学家们提出了很多新的结构统计特征( 特 征提取) 9 一l3 ，比较发现其中的一些统计特征与e r 随机网络相差甚远， 这样的事实要求我们构造符合这些实际特征的网络，这就是复杂网络建模 问题( 注：复杂网络建模与传统建模有些许区别，复杂网络的模型只是为 了解释为何实际的复杂系统会有某些特征，该领域的人潜在地认为网络的 结构具有大量的随机性，但这些特征是其中的不变量，因此研究这些特征 更有意义) ，所有这些研究导致了最近复杂网络理论的诞生与发展，这一 理论涉及自然，社会科学各个领域。通过将不同领域的复杂系统抽象地描 述成复杂网络以后，复杂网络理论要做的事就是从结构的观点上来给这些 不同领域的网络进行分类，分别建模，同时探讨某些网络特征对系统整体 动力学特性的影响，因此至少从目前来讲，复杂网络理论是研究系统结构 的一门新兴学科。 2 浙江大学博士学位论文第1 章绪论 当前己提出的系统建模方法有很多，主要包括智能方法 1 4 1 6 ，代数 方法 17 1 9 ，以及图论方法 2 0 - 2 5 3 等。其中图论方法由于能够很直观地 体现系统的结构而得到极为普遍的研究，对于调度问题而言，这种建模方 法使用也非常频繁，最常见的就是p e t r i 网 2 3 2 5 。 本章的后续结构安排如下：在第二节简要介绍本文的研究对象( 或称 为应用背景) ，即调度系统，包括调度的定义，分类，建模，以及求解方 法；接下去在第三节简要介绍复杂网络的主要研究思路及其发展历程；在 第四节阐明本文的研究动机。第五节给出本博士论文的研究内容和组织结 构；最后在第六节介绍本文的创新点。 1 2 调度系统 一个系统通常会包含很多的任务和资源，它们包括很多形式，比如车 间里的机器，机场登机门，运动会上的运动场馆和运动员，计算环境中处 理单元等都可以看作资源；而任务则可能是生产过程中的操作，机场飞机 的起飞和着陆，体育项目的实施，计算机程序的执行等等。通常所谓的生 产系统包含车间里的机器( m a c h i n e ) 以及生产任务( j o b ) ，本节主要通 过介绍由这些要素形成的经典生产调度问题 3 ，2 6 ，2 7 来了解资源调度的 本质，因为其它的调度问题通常只需在此基础上把任务和资源替换一下即 可。 1 2 1 调度的定义与分类 资源调度是一个决策过程，在大多数的制造和生产系统中扮演着重要 的角色，通常意义上的生产调度有如下定义： 定义1 1 生产调度：如何将有限的机器资源分配给在一定时间内的不 同生产任务从而来达到某种优化。 这样的定义也适用于其它对象的调度，只需把相应的任务和资源改换 一下即可( 这一点在后文将不再提及，默认使用生产调度的述语，其它调 度的例子在第二章中将会有详细介绍) ，比如对于机场登机门分配调度问 题而言，资源为登机门，任务为飞机起飞前与飞机着陆后每架飞机必须有 一个登机门，而调度的优化目标则是使用尽可能少的登机门来满足这种需 求 2 1 。根据调度对象是否含有动态性或随机性，调度可分为静态调度 2 8 ，2 9 和动态调度 3 0 3 6 3 ： 浙江大学博士学位论文 第l 章绪论 静态调度：被调度的任务集合确定；调度之前所有任务已经到达；任 务在每台机器上的处理时间确定；同时每台加工任务的机器连续可用， 即不会出现机器故障。 动态调度：与静态调度相反，如果在上面所有环节中有一个体现出了 动态性，比如被调度的任务集合不确定；需调度的任务陆续到达；任 务在每台机器上的处理时间不确定；或者机器偶然需要维修或者会发 生故障，则称在这类系统上的调度为动态调度，本处将随机性调度归 入了动态调度。 从问题求解的复杂性来说，静态调度问题由于所有参数都已确定且与 时间的变化无关，因此在资源调度问题求解的历史中首先得到了充分的研 究，并且除了在求解过程中如何解决“组合爆炸”问题外，在求解算法方 面也已有完善的发展。相对而言，动态调度问题的求解则要复杂得多，虽 然该类问题在现实生活中大量存在且具有极为重要的实际意义，但问题的 求解不但没有完善的解决方案，甚至连基本求解策略方面的研究也仍处于 初级阶段。 本文的主要研究课题是动态调度问题的求解，在第二章中我们将给出 本文的具体研究对象，不仅具有简单的任务动态到达，任务在每台机器上 处理时间的随机性，而且还具有不确定性等因素，在后文我们称这类调度 对象为复杂调度对象。 从调度对象的具体生产过程来看，无论是静态调度还是动态调度都可 以分为以下三类： 流水车间( f l o ws h o p ) 3 7 4 1 ：每项任务具有相同的流程，即每项 任务在所有机器上按一定的相同的顺序执行，每个任务的加工路线都 相同。 加工车间( j o bs h o p ) 4 2 - 4 6 ：每项任务有不同的流程，即每个任务 具有自己确定的加工路线。 开放车间( o p e ns h o p ) 4 7 5 1 ：每项任务的工作路线可以由调度者 决定，即工作路线是不确定的，开放的。 三者的主要区别在于，流水车间与加工车间加工路线都具有方向性， 而且流水车间每项任务都具有完全相同的流程，这种方向性表现在网络图 上就是所谓的有向图。开放车间相对前两者则具有更大的自由度。 4 浙江火学博士学位论文第1 章绪论 如果允许调度者在任何时间中断一项任务的加工，而把另一项任务放 到该机器上，这类调度称为可中断调度 5 2 - 5 4 ，否则则称为无中断调度 5 5 ，5 6 。这里，一项中断的任务已经进行的加工不会丢失，当一项中断的 任务重新返回到机器上时，它只需要加工完剩下的工作即可。无中断调度 一般来讲比可中断调度复杂，而且无中断调度通常作为一个n p 问题1 当任务 和机器数量比较多时会呈现组合爆炸，此时用经典的优化方法来求解这类 调度问题将会比较困难。 另外，根据完成任务所需资源种类的多少，调度问题还可分为单资源 调度问题和多资源调度问题，前面所讲的经典生产调度问题基本都属于单 资源调度问题，现实中的绝大部分较复杂的调度问题都属于多资源调度问 题 2 4 ，