（计算机软件与理论专业论文）求解车间作业调度问题的快速算法.pdf

华中科技大学硕士学位论文 摘要 i l 日j 作业调度问题就是在一定条件的约束下，对机器上一些待加工的工件进行 迪当的调度，使得完成所有给定加工工件的加工工期尽可能的短。车间作业调度问 题是个典型的n p 难度的组合优化问题，对于大规模的计算实例，在实际的计算 t h 没有一种最优算法能在适当的时间内计算得到其精确解，因此，构造能在适当 彭l t 叫内汁算得到大规模实例的一个可行解的启发式算法是有意义的。体论文采用 拟物方法和禁忌搜索方法分别对求解车间作业调度问题的启发式算法进行了探讨和 研究。 通过坩车i 剐作业调度问题的分析和借鉴人们在实际生活中解决问题的经验，建 j “方块一篓子”模型并以该模型作为分析车间作业调度问题的物理世界模型。眩模 型有助于j j u 深对车| 、日j 作业调度问题中物质运动的生动现象的理解，是拟物算法t 0 的基础。使用t o 算法计算了6 2 个精确解已知的典型实例，求得其中1 4 个实例的解 达到精确最优，而每个实例的计算时间在p i l 2 3 3 的个人计算机上不多于o 0 6 秒。此 外，还将t 。算法与其它多种基于优先规则的启发式算法的计算结果进行了分析和比 较。j 求解车间作业调度问题的苤星搜塞墓鎏是按照基本的禁忌搜索算法的一般步 骤，选择基于拟物方法的算法t o 来确定搜索的起点，选定一种定义较小邻域的邻域 结构，以简单的禁忌表实现短期记忆以避免局部搜索循环和过早陷入局部最优值。 采用该算法进行6 2 个典型实例的计算实验，求得其中2 4 个实例的解达到精确最优， 身将该算法与另外两种算法的计算结果进行了分析和比较。 汁算实验表明，以上两种启发式算法对于求解车间作业调度问题是可行的而且 是有效的。、 关键词：启发式算法；拟物方法；格局文禁忌搜弋 华中科技大学硕士学位论文 a b s t r a c t j o bs h o ps c h e d u l i n gp r o b l e mr j s s p ) c a l lb ec o n s i d e ra st op r o p e r l ys c h e d u l eas e t l ) 1 j o b so nas e to fm a c h i n e sw i t ht h eo b j e c t i v et o m i n i m i z et h em a k e s p a n ，i e ，t h e m a x i m u mo fc o m p l e t i o nt i m e sn e e d e df o rp r o c e s s i n ga l lj o b s ，s u b j e c tt os o m ec e r t a i n to n s t r a i n t s j s s pi sat y p i c a ln p - h a r dc 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 nt h e l 、i a c t i c a lc o m p u t i n g ，f o rt h ei n s t a n c e sw i t hl a r g es c a l e ，n oa l g o r i t h mc a ng e tt h ea c c u r a t e s o l u t i o n sw i t h i nt h ea c c e p t a b l et i m e t h e r e f o r e ，i ti si m p o r t a n tt oc o n s t r u c tt h eh e u r i s t i c a l g o r i t h m t o g e t t h ef e a s i b l es o l u t i o ni nt h e a c c e p t a b l e t i m e i nt h i s t h e s i s ， p h y s i c a l i f i c a t i o ns t r a t e g ya n d t a b us e a r c hm e t h o di si n t r o d u c e dt os o l v et h ej s s r t h r o u g h t h ea n a l y s i so ft h ej s s pa n dt h er e f e r e n c eo f p e o p l e se x p e r i e n c e s t os o l v e t h ep r o b l e m si nt h ea c t u a ll i f e ，“b l o c k s b a s k e t s m o d e li sb r o u g h tf o r w a r da n di s r e g a r d e da st h ep h y s i c a lw o r l do f t h ej s s p t h em o d e li sh e l p f u lt ou n d e r s t a n dt h el i v e l y p h e l t o m e n ao fs t a t ec h a n g e si n j s s pa n di st h eb a s et oc o n s t r u c tt h ef a s th e u r i s t i c a l g o r i t h m 1o w eh a v eu s e da l g o r i t h mt o t oc o m p u t e6 2t y p i c a li n s t a n c e sw i t hk n o w n e x a c ts o l u t i o n ，t h er e s u l ts h o w s ，s o l u t i o n so f1 4i n s t a n c e sw e r et h es a n l ea st h et h e i re x a c t s o l u t i o n s h o w e v e r , t h ec o m p u t i n gt i m ef o re a c hi n s t a n c ei sn om o r et h a n0 0 6 so n t h ep c w i t hp 1 1 2 3 3c p u i na d d i t i o n ，w eh a v ec o m p a r e da n da n a l y z e dt h ec o m p u t i n gr e s u l t so f 1ua n ds e v e r a lo t h e rh e u r i s t i ca l g o r i t h m sb a s e do np r i o r i t yd i s p a t c hr u l e l h et a b us e a r c ha l g o r i t h me m p l o y e di nt h i st h e s i st os o l v ej s s pi sc o n d u c t e db yt h e c o m m o ns t e p so fb a s i ct a b us e a r c hm e t h o d w eu s ea l g o r i t h mt ot o g e tt h e i n i t i a l s e a r c h i n gp o i n t ，c h o o s ean e i g h b o r h o o ds t r u c t u r ew i t hs m a l ln e i g h b o r h o o d ，u s es i m p l e t a b ul i s tt or e a l i z es h o r t t i m em e m o r yi no r d e rt oa v o i dl o c a ls e a r c hc y c l ea n dg e t t i n gi n l o c a lm i n i m u mp r e m a t u r e l y f i n a l l y , t h ea l g o r i t h mw a st e s t e do n6 2t y p i c a li n s t a n c e s w i t ht h er e s u l t so f2 4i n s t a n c e sg e t t i n gt ot h ee x a c ts o l u t i o n s ，m o r e o v e rt h ec o m p u t i n g r e s u l t sh a sb e e n a n a l y z e da n dc o m p a r e d w i t ho t h e rt w o a l g o r i t h m s c o m p u t i n g t e s t ss h o w st h ea b o v et w oa l g o r i t h m si sf e a s i b l ea n de f f e c t i v et os o l v e j s s p k e y w o r d ：h e u r i s t i ca l g o r i t h m ；p h y s i c a l i f i c a t i o nm e t h o d ；s t a t e ；t a b u s e a r c h 华中科技大学硕士学位论文 1 1 研究背景及意义 1绪论 计算机是2 0 世纪最为重大的发明之一，它深刻地影响了社会的生产活动和人们 fj ：j ，t - ：i 6 方式，可以说它的影响遍及所有的角落，它的应用范围之广让人惊奇。而让 人们更为惊奇的是它的发展速度，4 0 年来在发展速度上它一直遵循着每两年翻一翻 的“摩尔”定律。时至今日，家用的个人计算机的运算速度就能够达到每秒数亿次。 发展速度如此之快的计算机技术让人们对于计算机的计算能力很难产生怀疑，而在 f i 然界中，有关计算的问题亦是无穷无尽，有的简单，有的复杂，有的问题从理论 j l 二被论b e 计算机根本做不了，有的问题理论上可做，而即使采用现在世界上最快 的汁算机所要花费的汁算机时问将会多得出乎人们的想象。町以笼统的说，在 r 算 丰j 【科学，f ，这些理论上可解实际中难解的问题称为n p 完全问题。 n ：管理科学、计算机科学、分子物理学和生物学以及超大规模集成电路( v l s i ) 设汁、代码设计、图象处理和电子工程等科技领域中，存在着大量的这类n p 完全 u j 题。其中许多问题如贷郎担问题、图着色问题、没备布局问题等，至今没有找到 确效的多项式时问的快速算法。而这类问题由于其本身的挑战性和很高的应用价值 g f 起一大科学工作者们广泛的关注。 本文所要讨论的车阃作业调度问题就是一个典型的n p 完全问题。这一问题广 泛仔伍f 运筹管理、交通运输、通信网络、工业工程等领域，对于这一问题求解方 澎、的训究小仅在理论研究上而且在多方的应用领域中具有极重要的意义。 当住定约束条件之下，为完成某种确定的目标，涉及到如何将有限的资源分 削到确定的一些任务时，调度问题就会产生。在实际的生产活动中，有各种各样的 i 岗度问题，如计算机的中央处理器的作业调度问题、交通运输系统中的运载工具的 调度问题以及工厂的生产调度问题等。对这些实际调度问题的研究通常是从这些问 题l j 抽象出一个合适的数学模型，抽象得到的模型在某种程度上必须抓住实际问题 的核心矛盾并且以数学模型方式计算得到的解可以方便的转化为实际问题的解。此 外摸型不能过于简单以至于缺乏可靠性但也不能过于复杂而使得具体问题的计算所 华中科技大学硕士学位论文 ，籍的时1 日j 不切实际。针对不同的应用背景，在调度理论中有多种调度模型被使用和 例究，而其中车间作业调度( j o bs h o p ) 模型是最受关注的模型之一，因为它是实 助、，j ! 产中最普遍的调度问题的抽象并且也是经典n p 难解问题之一，该模型可能是 l 矧度理论中被研究得最多和使用最为广泛的模型之一。 鉴j 二牟j 日j 作业调度问题本身的复杂性所导致的寻求其精确解的高难度性。使得 jj 该问题的研究主要集中在寻求具有实际应用价值的近似算法的方向上，这种方 出是当前求解众多n p 完全问题的主要方向。 我的导师黄文奇教授多年以来一直从事s a t 、p a c k i n g 等具体的n p 完全问题 的研究工作。是国际上率先提出了求解n p 难度问题的拟物、拟人思想的学者之一 1 1 - 5 1 ，并应用这一思想提出了达到国际领先水平的求解s a t 、p a c k i n g 问题的高效 率的实用算法，积累了求解n p 完全问题丰富的经验。这些经验是我们研究车间作 业凋度问题的宝贵财富。 12 国内外研究概况 牟问作业调度问题是最难解的组合优化问题之一。不仅是因为它是n p 完全的， mll 在：实际计算中也是n p 完全问题中最难问题之一1 6 l ：对于随机产生的城市数目 为3 0 0 - 4 0 0 的旅行商问题或者是数百个约束条件和数予个变量的集合覆盖问题在 迅、与的时i 、日j 内可以对其进行精确的求解。但对于2 0 个： 件2 0 台机器4 0 0 个工序的 4 问作业调度i 、u j 题，采用精确求解的算法所需要的计算时间将是不切实际的。 车| 、日j 作业调度问题的精确求解主要是采用数学规划方法和枚举方法。早期有学 者采j 羁整数规划的方法尝试求解车间作业调度问题，但不久就有学者指出整数规划 方法4 i 能产生实用的求解算法，面f r e n c h 明确表示将车间作业调度问题用整数规划 公，表示来出在计算上是不可行的【7 j ，这表明求解车间作业调度问题采用整数规划 的数学方法是不恰当的。因此，对于精确求解车间作业调度问题就集中到枚举方法， 巾分枝定界又是主要的枚举策略之一，其基本思想是隐式的枚举一切可行解。这种 牧举彳i 是简单的完全枚举，而是以一种比较“聪明”的方式进行，尽可能的去掉一 些明显的非最优点，从而避免完全枚举。这种方法自诞生之日起，流行至今。目前， 埘这种方法研究的重点放在如何改进分枝定界策略，从而产生一个更强大的排除规 华中科技大学硕士学位论文 则，以便侄搜索的最初阶段排除更多的非最优点，从而大幅度减少运算时间。对于 求解小规模实例的最优解，分枝定界方法是一种有效的方法，但计算大规模实例所 需的计算时问仍是不切实际的，因而限制了这种方法的广泛使用。 d l 于车间作业调度问题在实际生产中，并不总是要求得到精确的最优解，因此 州f 究者很自然的考虑到使用近似算法在适当的时问内得到一个可接受的近似最优 解。而近似算法中的灵感主要是受自然现象和人类社会中的智慧的启发，因此又称 为启发式方法。 心管近似算法不能确保得到精确的最优解，甚至在多数情况下，无法预计所得 列的解同最优解的近似程度，但对于一个大规模的实例采用最优算法是不切实际的， f j i 使刖近似算法则可以在可接受的时间范围内得到近似最优解。而实际的计算表明， 女f 的近似算法通常能在可接受的时间内得到与精确最优解相差甚小的近似解，甚至 刈r 人；等| i 分的实例，近似算法能得到的近似解与精确最优解一致。这种曾经被称为 “快速与h 陋( q u i c ka n dd i r t y ) ”的方法，由二f 能够满足解决实际问题的需要，得 刨l ! 人的发展【8 l 。求解车间作业调度问题的启发式算法主要以如下四种类型：优先 规则、基于瓶颈策略的启发式算法、人工智能方法、局部邻域搜索方法【9 l 。 应厢于车间作业调度问题的启发式算法最早的发展就是基于优先指派规则的， d ij ：这种算法易于实现并且能够显著的降低计算花费( 主要指计算时间、空间花费) ， 仗得它成为实际应用中被普遍使用的方法。这种方法主要是确定一种优先级规则。 使j ji 幺规则从待调度的工序集合中选择一个优先级最高的工序，并用贪心的方法对 该i f ，f 进行凋度，如此进行，直到所有的工序都调度完毕。 b i 在1 9 5 5 年就有研究学者进行这种算法的研究r 作，二十世纪六七十年代，优 先措派规则算法得到巨大的发展，各种优先规则数以百计。1 9 7 7 年p a n w a l k e r 和 i s k a n d e r 在发表的论文中收集和整理了多达1 1 3 中优先规则1 10 j ，h a u p t 在1 9 8 9 年发 表的论文辞t 对优先规则算法进行了更为广泛的讨论和总结i 川。在许多有关优先指派 规 则算法的研究中存在一个共识：使用单一优先指派规则的算法在计算时间上占绝 对的优势，但在计算结果的优度( 与精确解的逼近程度) 上，到目前为止没有一种 单优先指派规则算法占有优势。鉴于单一优先指派规则算法在计算优度上的拙劣 表脱，按某种策略将多个单一优先指派规则结合起来，形成一种组合优先指派规则 算法是很自然的想法。这种组合单一优先规则的算法在过去的研究中，组合方式主 华中科技大学硕士学位论文 ；婴是埘多个单的优先指派规则采用概率组合方法，即在调度过程的某阶段，确定 待加f 1 序的优先级别将采用的规则是以一定的概率从多个给定的单一优先规则中 选 i 。l a w r e n c e 将单一优先规则算法与采用对十种单一优先规则使用随机选择的组 ；等算法的计算表现进行比较，结果表明：组合优先算法计算结果的优度有很大提高 1 h 消耗了较单优先规则算法更多的计算时问l l ”。而现代更为复杂的组合方法是采 h 遗传算法和模糊逻辑【1 3 j 。这种在组合方式的选择上引入人工智能技术的方法，复 杂性人幅度增加与计算优度不佳的表现并不相称。 简单的优先指派规则算法能满足许多实际调度问题应用的需要，而且解决这些 + 眶物、凋度问题采用这些算法也是合理的。但随着计算机技术的发展，计算机的计算 速度j j | j 快，实际的应用需要对调度问题的求解提出了更高的要求。花费更多的计算 代价换取更高优度的解成为新的启发式算法的目标。转换瓶颈机( s h i f t i n g b o t t l e n e c k ) 策略的算法就是实现这一目标的典型算法1 6 j l “j 。 转换瓶颈算法的主要思想是将多机问题放宽约束转化为多个单机问题，多次反 复使川c a r l i e r 算法f l5 1 对单机问题进行求鳃。每一阶段，使用c a r l i e r 算法计算每一 f f 术作调度机器的瓶颈度，并对这些机器按瓶颈度值从大到小进行排列，选择值最 人的机器作为该阶段的瓶颈机。在考虑已调度完成机器上的工序排列和忽略除瓶颈 帆以外的未调度机器条件下。采用c a r l i e r 算法对瓶颈机进行计算得到瓶颈机上所有 i 序的调度次序，每完成一台瓶颈机的调度，对已调度好的机器的工序次序重新进 行优化，如此进行，直到所有的机器的工序次序都确定好。a d a m s 在2 l 世纪8 0 年 代中期采用综合转换瓶颈的方法和枚举策略的算法s b i i 在几分钟内求解得到当时 被公认的最难实例f t l 0 的最优解。转换瓶颈方法自提出后得到不断的改进和发展， j 川，最为引人关注的趋势是与其它的启发式方法结合丽发展的新的算法，这些综合 算法通常都取得很好的计算结果，典型的代表有基于转换瓶颈策略的局部搜索算法 【l 叫和基于转换瓶颈策略的禁忌搜索算法7 1 。 人1 ：智能是将生物科学和计算智能结合而形成的计算机科学的一个分支，它最 塾奉的思想起源于对生物的理解，使用自然界中的法则以寻求问题的解决之道。在 球解车间作业调度问题方面，有多种人工智能技术被应用，如专家系统，知识工程 等，但主要被使用的神经网络和约束可满足性技术。计算的结果表明这些人工智能 力法在求解车间作业调度问题上的表现欠佳。但计算花费却很大 9 1 。相比而言，局 部领域搜索方法在求解车间作业调度问题上的表现却很成功，以至于这类算法成为 华中科技大学硕士学位论文 j 见阶段求解车间作业调度问题最有效的方法之。 局部邻域搜索算法可概括如下：以一可行解为搜索起点，搜索以该点为“中心” 以定的邻域结构所构成的邻域，在邻域中按某种策略选择新的邻域“中心点”，再 搜索新中心点的邻域，如此循环，直到满足搜索终止条件。从算法种可看出，算法 终1 1 时得到点( 即局部最优点) 的性质依赖于算法的初始解的选择、邻域的结构的 定义和邻域中选点的规则以及搜索停止条件的确定。初始解通常采用快速优先舰则 掉法，很容易得到，而好的邻域结构的定义却很困难。如果邻域结构确定的邻域比 较人，即邻域中点的数目较多，找到优度好的邻点的概率也就较大，但会花费更多 的时日j ，反之，如果邻域比较小，花费的时间较少，但找到优度好的邻点的概率就 坟小。凶此，选择的邻域结构确定的邻域规模应大小适宜。局部邻域搜索算法一个 k ， ：的缺陷是容易陷于局部最优的陷阱，有时局部最优解与全局最优解相差甚远。 n 尽量避免局部最优带来的影响而发展起来的各种跳出局部最优值的策略也发展成 b 了各种新的启发式算法，如禁忌搜索( t a b us e a r c h ) 1 1 9 - 2 0 1 模拟退火( s i m u l a t e d a n n e a l i n g ) | 2 t l ，遗传算法( g e n e t i ca l g o r i t h m s ) 1 2 2 1 等。这些新发展的启发式算法在 球解车间作业调度问题中取得了很好的结果，是当今求解车间作业调度问题研究最 酱遍的方法。 3 课题主要研究工作 本文将采用拟物方法和禁忌搜索方法分别对求解车俺j 作业调度问题的启发式算 法进 探讨和研究。拟开展的主要工作如下： ( 1 ) 任深刻理解车l 、日j 作业调度问题和拟物方法思想的基础上，寻找车间作业调 殳涮题等价的物理世界，并观察物理世界物理状态变化的规律，总结从中体会到的 片；发式思想，并将这些思想融入到求解车间作业调度问题的算法构造中。 ( 2 ) 对各种启发式思想进行分析并进行算法实验。确定有效的拟物算法。并对 该算法进行详细的描述和分析，并通过对标准实例的计算，测试算法的执行效率。 刑算法的优缺点进行论述。 ( 3 ) 采用基本禁忌搜索算法对车间作业调度问题进行求解，通过算法实验，了 解不同的搜索起点对基本禁忌搜索算法的影响，探讨算法改进的方向。 华中科技大学硕士学位论文 2 车间作业调度问题 4 三问作业调度问题是一个典型的组合优化问题，在实际的生产活动中，有许多 j 、用领域有这一问题的原形，并且车问作业调度问题是经典的n p 完全问题，对于 这一问题计算方法的研究有重要的理论意义和实际价值。研究问题的基础是对问题 的深刻理解。本章将给出车间作业调度问题的三种描述形式，并对其中的有关术语 进行说明。 2 1 问题、算法、可计算性和复杂性 f 1 ：计算机科学里，问题是需要回答的一般性提问，通常含有若干个参数或自由 变量，这些自由变量的值还没有给定。问题的描述是通过给定：( 1 ) 所有参数的一般 性描述，( 2 ) 陈述答案或解必须满足的性质。给问题的所有参数指定了具体的值，就 彳 j 剑问题的一个实例1 ”j 。 j l 形式化的况，算法是一步一步地求解问题的通用程序。以日常用语来说，算 、j 称为过程或处方。为了具体一些，可以把它们看成用某种精确的计算机语言写 成的计算机程序。如果一个算法可以应用于问题i 的任何实例f ，并且保证得到实例 “内解，那么就称该算法解问题l 。 算法在数学中已经有很长的历史，但在2 0 世纪之前，算法概念本身一直没有精 确地定义。1 9 0 0 年，数学家希尔伯特在巴黎举行的世界数学家大会上发表了著名的 演i 兑，提 i 了2 3 个数学问题，其中的第1 0 个问题就是关于算法的，这个问题就是 婪没一个算法来测试多项式是否有整数根。当然当时他没有使用算法这一术语， f 【j 用这样一+ 旬短语：“通过有限多次运算就可以决定的过程”。有意思的是，从希尔 佃特对问题的陈述中可以看出，他明确地要求设计一个这样的算法。由此可见，他 扫一明显的假设这样的算法是存在的，人们所要做的只是找到它。1 9 7 0 年，马提亚塞 维卉( y u r im a t i j a s e v i c ) 在戴维斯( m a t i nd a v i s ) 、普特纳姆( h i l a r yp u t n a m ) 和罗 宾赴( j u l i ar o b i n s o n ) 等人工作的基础上，证明了检查多项式是否有整数根的算法 是1 i 存在的。由此可知，希尔伯特提出的第l o 个问题是算法上不可解的。算法的明 确定义首次出现在丘奇( a l o n z oc h u r c h ) 和图灵( a l a nt u r i n g ) 于1 9 3 6 年写的文 华中科技大学硕士学位论文 荜- p 。j t 奇使用称为九演算的记号系统来定义算法。图灵则使用机器来做同样的事 情。这两个定义后来被证明是等价的。 由此可看出对于自然界中纷繁复杂的问题，有些问题算法上是能够求解的，而 些则不能。诅j 明算法上不可解的问题的存在，是汁算理论中最具哲学意义的定 _ h 之i 2 4 1 。计算机的计算能力看上去是如此强大，使得人们相信所有问题最终都将 m 服：j 二它们，甚至有人担心计算机在未来会统治整个人类。而算法上不可解的问题 的存在这一定理的证明，一方面在一定程度上可以消除一部分人对计算机技术发展 的忧虑，另一方面可以帮助人们在试图解决某些问题时把握正确的方向。 汁算机科学中的可计算性理论可以帮助我们清楚地、精确地区分有算法的问题 f 没有算法的问题。然而，在“原则上”的可解性和“实际上”的可解性之间存在 敝人的差别。可计算性理论研究“原则上”的可解性，而“实际上”的可解性是要 能够h j 可能利用的空间和时间来完成运算的算法问题。在习惯上，我们把不仅在原 l 驯l ：、而且在实际上也是可解的问题叫做易解的，把在原则上能够解决、但在实际 f ：0 i 能解决的问题叫做难解的1 2 ”。车间作业调度问题就是属于这类原则上可解但实 际j 二难解的问题。 。实际研究中，一般地，人们感兴趣的是寻找解问题最“有效”的算法。在最广 泛的意义f ，效率的概念包括执行算法所需要的全部计算资源，主要包括计算时问 f ij , t 算所需的空问资源。但是，对于难解的问题通常“最有效的”算法就是指最快 的算法。因为时间需求常常是决定一个具体算法是否有足够的效率用于实际的主要 | l 素，上要被考虑的就是这个资源1 2 3 i 。 算法的时间需求可以用一个变量表示，这个变量就是问题实例的“规模”。可以 之来描述该实例所需要输入的数据总量。这样做是方便的，因为很容易预料问题 1 实例的相对难度随着它们的规模变化。我们常常用一种非形式的方式度量问题实例 的规模。例如，对于车间作业调度问题常常用工件、机器和工序的数目表示实例的 蚬模。如果要以数学的方式精确地处理时间需求，在定义实例的规模时，对于车间 i 业调度问题当然还要考虑每个工件的每道工序的加工时间长度和加工机器编号等 聪素在内。 因此，可以把用来作为计算机输入所提供的问题实例的描述看作一个有穷的字 华中科技大学硕士学位论文 符串，这个字符串中的符号取自一个有穷的输入字母表。虽然有许多不同的方式都 能够描述给定问题的实例，但是假定事先已选定一种具体的方式。因而每一个问题 郜和种具体的方式，即一个固定的编码方案相联系，这个编码方案把问题的实例 映射到描述它们的字符串。问题i 的实例i 的输入长度定义为在由i 的编码方案确定 i 的描述中的符号数目。正是这个数目，即输入长度，用来作为实例规模的形式度 鞋。 鲜法的时问复杂性函数表示这个算法的时间需求，对每一个可能的输入长度， 给日 用该算法解这种规模的问题实例所需要的最长时间。当然，只有确定了用来决 ，t 输入长度的编码方案和用来决定执行时间的计算机或计算机模型之后，才能明确 地定义这个函数。而实际上，这些具体的选择对于问题的性质的区分几乎没有任何影 响。凶此对每一个问题确定一个具体的编码方案和一个具体的计算机或计算机模型， j 把时间复杂性看作是由相应的输入长度和执行时间所决定的。 不同的算法具有很不相同的时间复杂性函数。说它们当中哪些“效率足够高”哪 h 争效率太低”。总要看具体的情况。但是，计算机科学家们公认一种简单的区别， 这种区别对这些问题提供了重要的透彻的分析，这就是多项式时间算法和指数时间 辩法之间的区别。 j l 要存在一个常数c 使得对所有的n 0 都有i ，( n ) 晦c g ( ”) ，那么我们称函数 ( ，) 是( ) ( g ( n ) ) 的。多项式时间算法定义为时问复杂性函数是d ( p ( n ) ) 的算法，其中p 魁。个多项式函数，月用来表示输入长度。不能这样限制时间复杂性函数的算法称 1 ：指数时j 、日j 算法。假设问题和解决该问题的一个算法已经给定，若对该问题的任意 的个实例i ，实例的输入长度为疗，存在多项式函数g ( n i ) ，使得l ，阳p i j g ( n f ) 恒成 立，我们称该算法为解决该问题的多项式时间算法。特别对优化问题，当一个算法 为求解该优化问题最优解的多项式时间算法，则称为该优化问题的多项式时间最优 算法。 对于给定的一个优化问题，若存在一个求解该问题多项式时间最优算法，则称 给定的优化问题是多项式时间可解问题，或简称多项式问题，所有多项式问题集记 为p ( p o l y n o m i a l ) i n 题。 并不是所有的组合优化问题都能找到求解最优解的多项式时间算法。也就是说， 华中科技大学硕士学位论文 也4 i 能肯定一些组合优化问题是否属于p 。经过几代数学家的努力，他们研究、整 理了一类难以求解的组合最优化问题，迄今为止，这些问题还没有一个有能求得最 优斛的多项式时l 、日j 算法。这一类组合最优化问题归为所谓的n p h a r d l 2 “。2 0 世纪7 0 ： f 仞斯蒂芬库克和奥尼德列文发现n p 中的某些问题的复杂性与整个类的复杂 棚关联。这些问题中任何一个如果存在多项式时间算法，那么所有n p 问题都是 岳项式时问可解的这些问题称为n p 完全的【2 3 j 。如果n p 中某一个问题是难解的， 那么所有n p 完全问题也都是难解的。因此，n p 完全问题i 具有如下的性质；如果 ，& n p ，则，n p p 。更精确的说，j p 当且仅当p = n p 。 p = n p 是否成立的问题是理论计算机科学和当代数学中最大的悬而未决的问题 j ：。假设j p p ，现在可以给出更详细的n p 世界图形，如图2 1 所示。注意n p 小是简单地划分成“p 的领域”和 n p 完全的领域”。如果p 不等于n p ，那么在n p ，定存在既不能在多项式时间内解决，又不是n p 完全的问题。 山于受认识能力的限制和凭借自身的在人类社会中生存的经验，目前人们有一 个广泛的信念p 尸，故而只能假设这些难解问题不存在求解最优解的多项式时间 算法。在实际的研究中，在尸a l p 的假设下进行研究似乎比致力于证明p = n p 更合 适蝗。 图2 1 对n p 世界暂定的看法 j f 因为一些组合最优化问题还没有找到求最优解的多项式时间算法，而这些组 合最优化问题又有非常强的实际应用背景，人们才不得不尝试用一些并不一定可以 求解到最优解的算法，如启发式算法来求解组合优化问题，这也是本文研究车间作 业渊度问题所采用的主要技术路线。 9 华中科技大学硕士学位论文 2 2 车间作业调度问题描述 2 2 1车间作业调度问题描述及目标函数 车问作业调度( j o bs h o ps c h e d u l i n g ) l f i 题可作如下简单描述： 牟问- p 有一些待加工的工件o o b ) 和用于加工这些工件的一些不同的机器 ( m a c h i n e ) ，每。个 件需经过数目一定且先后关系确定的加工工序( o p e r a t i o n ) 来完 成，每道 序由工件在某一台预先指定的机器上不间断的加工预定的一段时问 ( d i n a t i o n ) 来完成，整个加工过程中，需要满足如下约束条件： ( j ) 机器约束：每一台机器在任何时刻最多只能对一个工件进行加工； ( 2 ) 一卜件约束；工件的每道工序必须在指定的机器上加工，且必须在其前道工 j ( 如粜仔侄) 加工完成后力能开始加工，且任何一个工件在任何时刻最多只能在一 订+ j 【器f ：j j hl 。 在满足以上条件的情况下，如何为每一道工序选择一个合适的开工时阃，使从 j | i i 到加 完所有的工件的时间跨度( 力w i i 期1 尽可能的短。 假定： l ，= l ，2 ，n ) 表示工件的集合； m ； i ，2 ，m ，表示机器的集合； d = p i ，向j e a ， 、 ( 1 ) t l t l p ivt t p j ( i ，j ) e e k k m c n 1 0 华中科技大学硕士学位论文 f ，2 0 ，i o( 3 ) 约束( 1 ) 表示同一工件的工序必须按预先确定的加工顺序进行加工，约束( 2 ) 表示 裨j 同一机器上加工的工序必须按照一定的先后顺序，同一机器在任意时刻不能同时 进行两道工序的加工。在满足上述条件的与每一道工序相应的一组t l ( 产n 。盯) 对应 问题的一个可行调度。而寻找使“+ f 尽可能小的可行调度是求解车间作业调度问题 的目标。 2 2 2 车间作业调度问题的图表示 为了更直观的理解车间作业调度问题，可将其表示成析取图( d i s j u n c t i v e g r a p l l ) g j = ( 旷爿，e ) 1 2 7 1 1 2 引，其中矿是节点集合，4 是实线弧集合，e 是虚线弧集合。 i 割( j 中的每。个节点对应一道工序，其中0 和月+ j 号节点分别表示虚拟的开工和 充一 序，分别称为图的起点和终点。起点与每个工件的初始加工工序用实线弧相 连，每个r 件的最后一道工序与终点用实线弧相连。实线弧集a 表示各工件上工序 的加l ：次序集合，即为工序约束，a 中任一弧( f ，_ ，) 的弧长为只；虚线弧集e = u 峨 奠l j 风表示在机器k 上加工的工序的约束关系，f 中任一弧( f ，j ) 是双向的，表示调 j 建之| ；1 ，机器上待加工的工序的次序尚未确定，因此弧长为p ，或p ，具体取何值要 依赖f 渊度后工序i 和工序，的加工先后次序。调度问题就对应于如何确定图中虚 线弧的方向即确定机器上工序的加工次序，形成一个无环路的单向图，使得图中的 豉长= 路径尽可能的小。每个无环路的单向图对应于一类可行调度，每一个可行调度 必定会有一个无环路单向图与之对应，而且这一调度顺序的最优解的加工周期就等 二相应无环路图的最长路径的长度”1 。 为说明上述概念，采用以下实例进行说明： 表2 1 一个3 3 实例 工件号工件加工工序序列( 机器号，工序加1 时间) j l( 1 ，8 ) ，( 2 ，6 ) ，( 3 ，l o ) j 2( 2 ，5 ) ，( 3 ，8 ) j s( i ，3 ) ，( 3 ，7 ) ，( 2 ，4 ) 华中科技大学硕士学位论文 表2 1 给出了一个车间作业调度问题的3 3 实例的描述，该实例表示有3 个工 件年f i3 台机器共8 道工序，每道工序表示为( m ，p ，) ，其中珊，表示加工该道工序的机 器号，p 。表示该道工序的加工时间。其中以工件1 为例，工件l 有3 道工序，第l 道l ：序是在1 号机器上加工8 个单位时间来完成，第2 道工序需要在2 号机器上加 l6 个单位时间，第3 道工序在3 号机器上加工1 0 个单位时间完成。 对j ：l 述实例采用析取图表示如图2 2 所示，图中节点内的数字表示该工序的 编号，实线弧上的数字表示该弧的长度，即起点节点所对应工序的加工时间，每一 j 件的所有工序按加工次序由实线弧连接，在同一机器上加工的工序由双向虚线弧 十互连接，虚线弧的长度取决于调度所确定的机器上加工工序的先后加工次序。 蚓2 23 3 实例析取图表示 图2 33 x 3 实例一可行解的有向图表示 图2 - 3 是图2 2 对应实例的一可行解所对应的单向图，该图中从0 节点到9 号节 r 伯9 最长路径为对应实例在这种调度安排下的加工周期。最长路径为( 0 ，l ，6 ，7 ，3 ，5 ，9 ) ， ( = 度为l = o 十8 + 3 十7 + 1 0 + 8 + 0 = 3 6 。 223 车间作业调度问题的物理模型 以上述3 3 实例为例，其对应的物理模型如下图2 4 所示： 华中科技大学硕士学位论文 酗2 43 3 实例物埋模型样式幽4 如图2 4 所示，每一道j ：序对应于。一个方块，方块中标识的数字表示j f j 于加工 该道i 序的机器编号，方块的长度表示完成该道：i ：序所需要的加工时间，方块左边 圳割- ，的数字表示该方块的统一编号，即与图表示方法中，【序的编号相对应。每一 j 刑。i l j 一摞具有相同图案、高低关系确定的方块表示，这些具有相同图案的方块按 j 其所代表工序的加工先后顺序自下向上摞起。不同工件具有刁i 同的图案。每一台 机器对应于一个上端开口，下端封闭的篓子，篓子的底高定为0 ，篓子具有理想长 度。图2 4 表示为表2 1 所描述的一个3 个 ：件3 台机器的实例所对应的物理世界样 式，以 件山为例进行说明，其芡有3 道工序，分别由m t ， 毛，m 3 机器加工。图 2 5 表示与图2 3 对应的该实例的一个可行解的样式。 i 璺i2 53 x 3 实例一可行解物理空间样式图 圈闷国山 【。) d f ：) 神 船 竹 ”5 o 图图 华中科技大学硕士学位论文 化物理模型q ，车间作业调度问题的就是如何将篓外的方块全部合法的放入篓 一l ，使得篓f 中处在最高位置方块的顶尽可能的低。如图2 5 所示，最高位置的 一块为5 号方块，在图示的放入方法下，其顶高为3 6 ，即这种调度结果的加工周期 勺3 6 。所i 肖合法是指放入要满足一定的约束条件，这些约束条件主要是指机器约束， j 件约束。在这两种约束下，放入方块对应的要求是：在同一篓子中的方块放入时 1 、能有重叠；每一方块只能放入所标识的篓子中，同一图案的方块在放入篓中前有 十当高低关系，放入后应保持这种相对关系。如在放入前，a 方块底比同摞b 方块 的顶高h 个单位，放入篓中后，a 方块的底比b 方块的顶高不小于h 个单位。如图 2 5 所示，在放入篓中前，3 号方块的底比1 号方块底顶商3 个单位，放入后，3 号 0 块底商为1 8 ，1 号方块顶高8 ，1 8 8 3 。 23 车间作业调度问题的可计算性和复杂性 从4 ：问作业调度的物理模型中，可以看出寻找车问作业调度问题的一个可行解 ，肌艟住满足所有约束条件的情况下，确定每个篓子中方块的排放顺序和其对应的位 澍，1 m 其t 1 关键是确定每个篓子中方块的堆放次序。因为，当每个篓子中的方块堆 放顺序确定后，就可以按“向下对齐”方法确定每个方块的最低摆放位置，因此就 ；j 以确定一个可行的调度的加工周期。但是，有时各篓子中的方块顺序堆放不恰当 会导致无法按“向下对齐”的方法确定所有方块的位置，这样的对应篓中方块堆放 顺序也就不能对应一个合法的可行解调度。对应到图的表示中，相当于单向图中出 j 皑了环路。“向下对齐”的方法如下： s t e p i ：将各篓中的方块按确定的堆放顺序堆放在篓中，所有方块均处于未定 化状态，循环次数汜为0 ； s t e p 2 ：依次扫描各篓子中堆在最下面没有定位的一个方块，仅在如下情况，对 l 敛一块作定位动作，即将方块放置于相应位置，且将其状态置为已定位。 ( 1 ) 如果该方块在未放入篓之前是同图案方块的最低位置的方块，即代表工件 鲫絷。道i ：序，同时也是篓子中堆放最下面的方块，将这样的方块的底就定位于篓 ：的底高；如果不是篓中堆放最下面的方块，则将该方块定位于篓中不与已定位方 块有重叠的尽可能低的位置上； 1 4 华中科技大学硕士学位论文 ( 2 ) 如果该方块不是在未放入篓之前同摞相同图案方块的最低位置的方块，且 具赢接i i i 继同图案的方块已经定好位置，则将该方块的底定位于篓中尽可能低的位 置i l 不低于其前继同图案方块的顶的高度。 s i 、e p 3 ：如果所有的方块定位完毕或者循环次数大于方块个数，停止，其中循环 次数大于方块个数表示这种排序不能产生一个可行解；否则，跳到s t e p 2 ，循环次 数加l 。 釉羽 图2 63 x3 一可行调度“向下对齐”方法执行状态变化过程示意图 蚓2 6 为图2 3 对应调度方案按照“向下对齐”方法确定各方块位置的状态转换 小意图，其中篓中灰色方块表示为未定位方块，黑色方块表示已定位方块。 山“向下对齐”方法得到的加工周期是这种调度下最小的，因为每一工序都没 有逛洪即每道工序都是在满足机器和工件约束的条件下最早可能开工的时间开工。 女图2 5 所示，在不改变每个篓子中方块的顺序的情况下，即不改变每台机器工序 的调度顺序，每个方块都已经是处在的满足约束条件的最低位置上；而图2 7 所示 i 是在同样的调度顺序下一种调度方案，这样得到的也是一个可行调度，但5 号方 块和8 号方块都没有放置在满足约束条件的最低位置上，可以看出这样得到的加工 倒期比图2 7 所示的调度的加工周期大。因此，对于一组各篓中工序的排序，只需 要考虑使用“向下对齐”方法确定该排序所对应的工期。 对于车| 、日j 作业调度问题任一实例f ，其规模为n m ，即n 个工件