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

华中科技大学硕士学位论文 摘要 牟阳j f l ；业调度问题就是用组机器加t 一组一l 件，每个工件有若干个工序，把 这些j l ：序按j 一定次序加工，在加i ：的过程- p 要满足刈题特定的约束条件，并使加 i 。充所有的i ：序后形成的最终凋度的时州跨度尽可能短。 该问题是个典型的n p 完全问题。n p 完全问题的精确求解算法的计算h 寸i h j 会 随着问题规模的增大而呈现指数增力l l ，因此，用精确算法求解车问作业调度问题是 小实际的。而近似算法则能在较短的时间求出问题的满意解，虽然这个解并不一定 足问题的最优解。由于车间作业调度问题是一个很重要的实际问题，凶此，寻求陔 叫题的近似算法有重要的理论价值和实际意义。 求解车m 作业调度问题实际卜就是给待加工的工序确定一个调度顺序并达到优 化| = = = | 的。为r 诵定工序的调度顺序，可以用优先指派规则。算法m p 是一个基j 二优 先指派枷则的启发式算法，该算法会给被考察的工序子集中的每个工序都赋予一个 优，l j 级，优先调度优先级最高的工序。算法m p 通过贪心法次确定了工序的开工 时叫，凶向速度很快，但搜索范围有限。向结合了算法m p 和枚举策略的枚举算法 m i ，e 则l j _ 以通过枚举来增加算法的搜索范围。 求解车间作业调度问题的局部搜索算法l s 是按照局部搜索的一般步骤，结合了 姓体问题构造出来的。由于算法l s 中提出的初始解方案、邻域构造方案以及搜索策 略的方案都是引对本问题的，因而，算法l s 能够比较好的求出问题实例的近似解。 实际测试结果表明，这三个启发式算法对于求解车间作业调度是可行而且有效 的。 关键词。启发式算法；格局；贪心法；局部搜索；模拟退火 华中科技大学硕士学位论文 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 m ( j s s p ) c a nb ed e s c r i b e da sf o l l o w s ：w ea r eg i v e nas e t o f j o b sa n d as e to fm a c h i n e s e a c hj o bc o n s i s t so fac h a i no f o p e r a t i o n s t h ea i mo f m e p r o b l e m i st of i n dt h em i n i m u mm a k e s p a n o f t h es c h e d u l e t h ep r o b l e mi san pc o m p l e t ep r o b l e m t h ec o m p u t i n gt i m eo ft h ep r e c i s i o n a l g o r i t h mf l o r t h ei n s t a n c eo ft h ep r o b l e mw i l li n c r e a s ee x p o n e n t i a l l yw h e nt h ei n s t a n c e i n c r e a s e s s o ，i t su n w i e l d yt os o l v et h ep r o b l e mw i t hap r e c i s i o na l g o r i t h mt ot h ed a y h o w e v e r ，h e u r i s t i cm e t h o dc a l lw o r ko u tt h ei n s t a n c eo ft h ep r o b l e m ，t h o u g ht h er e s u l t m a yb en o te x a c ts o l u t i o n f o rt h ej s s pi sa ni m p o r t a n tp r o b l e mo fo u rd a i l yl i f e i t i s i m p o r t a n tt of i n dh e u r i s t i ca l g o r i t h m t os o l v et h ej s s pi st of i n da l lo r d e rf o rt h e o p e r a t i o n s t h em e t h o d b a s e do n p r i o r i t y r u l e sc a nd e c i d ew h i c h o p e r a t i o nt ob ep r o c e e d e dn e x t t h eb a s i ca l g o r i t h mm p i sb a s e d o np r i o r i t yr u l e t h eo p e r a t i o n si nt h ec o n s i d e r e ds u b s e ti sa s s i g n e da p r i o r i t ya n d t h eo n e w h i c hh o l dt h eh i g h e s tp r i o r i t yw i l lb ep r o c e e d e dn e x t b e c a u s et h em pc a l ld e c i d et h e n e x to p e r a t i o na to n e t i m e ，t h es p e e di sq u i c k b u tt h es o l u t i o nm a d eb ym p i sn o ts og o o d t t o w e v e r ，t h ea l g o r i t h mm p e ，w h i c hc o m b i n e dm pw i t he n u m e r a t e ，c a l le n l a r g et h e s e a r c hs p a c e ，c a l lf i n db e t t e rs o l u t i o n t h el o c a ls e a r c ha l g o r i t h ml si sd e s i g n e dt os o l v ej s s pi so b s e r v et h ec o m m o n s t e p s a n dc o m b i n e dw i t hs p e c i a lp r o b l e m f o rt h em e t h o df o ri n i t i a ls o l u t i o n 、n e i g h b o r h o o d s t r u c t u r e 、s e a r c hs t r a t e g ya r ep r o v i d e da i ma tt h ej s s p , t h ea l g o r i t h ml sc a nm a k eo u t g o o da p p r o x i m a t es o l u t i o n t h ea b o v et h r e eh e u r i s t i ca l g o r i t h m sa r ea l lf e a s i b l ea n de f f e c t i v em e t h o d st ot h ej o b s h o ps c h e d u l i n g p r o b l e m k e yw o r d s ：h e u r i s t i c ；c o n f i g u r a t i o ng r e e d y ；l o c a ls e a r c h ；s i m u l a t e da n n e a l i n g i i 华中科技大学硕士学位论文 1绪论 1 1 研究背景及意义 在计算机出现之前，人们要用手工来完成很多复杂的计算，有些问题由于规模 太大，让人无从下手。当计算机出现之后，这一切都得到了改观。例如，排序是一 个容易的问题，譬如说需要按升序排列一张数表，即使一台小型机都能相当快地处 理i 0 0 万个数。 但和人一样，计算机也碰到了一些困难的问题。如要制定一所大学的课程表， 课程表必须满足某些合理的限制，如不能有两个班在同一时间使用同一教室。时间 表问题看来比排序问题要困难得多。如果有1 0 0 0 个班，即使是使用一台超级计算机， 制定一份最好的课程表也可能需要若干世纪。这个课表问题只是实际生活中的一个 例子，而这样的例子是数不胜数的，如货郎担问题、电路板布局问题、图着色问题 等等。 这就说明有的问题用计算机容易解决，而有的问题则难解决。对于那些计算机 难以解决的问题的研究不仅在数学、计算机科学领域中有重要的理论意义，而且对 j 二认识、分析众多复杂的新问题也有很大的实用价值。 在过去的几十年里，人们对这类计算机也难以解决的问题进行了深入和细致的 研究，得到了一个重要的成果，那就是复杂性理论。复杂性理论产生了一个按照计 算难度给问题分类的方法。简单地说，其中的p 是成员资格可以在多项式时间内判 定的语言类，n p 则是成员资格可以在多项式时间内验证的语言类。而n p 完备理论 研究的正是被称为n p 类的一些问题。它们具有性质：若有一类问题找到多项式算法， 则它们全体都得到解决；同样，若证明了它们中任何个肯定不存在多项式算法， 对它们的全体也可以放弃这方面的努力。s c o o k 在1 9 7 1 年发表的( t h ec o m p l e x i t yo f 7 f h e o r e mp r o v i n g p r o c e d u r e s 和r 勋叩在1 9 7 2 年发表的( r e d u c i b i l i t ya m o n g c o m b i n a t o r i a lp r o b l e m ) ) 论文奠定了n p 完全理论基础。随之而来，p = n p 是否成立则 华中科技大学硕士学位论文 成了理论计算机和当代数学中悬而未决的问题。大多数研究人员相信这两个类是不 相等的，因为人们投入了大量的精力为n p 中的某些问题寻找多项式时间的算法，但 都以失败告终。这不禁让人猜测，不管p = n p 是否成立，n p 难度问题的完整精确解 法，其复杂度都会是让人难以接受的。 不解决p ：n p 这个问题，就一定得不出关于n p 完备问题困难程度的结论来。 尽管这个问题具有重大的理论意义，并且许多科学家也为此做出艰苦的努力，但仍 未得到精确的证明，并且希望还很渺茫。这个问题的解决也许尚待时日。也许需要 新的数学方法的出现才能做出圆满的回答。 n p 问题广泛存在于众多的科学领域，如管理科学、计算机科学、生物学、代码 设计、电子工程等等领域，在这些领域的科学研究和工业生产中涌现出了像货郎担 问题、图着色问题、设备布局问题等等。尽管人们对这些问题进行了很长时间的研 究，但到目前为止，还没有发现有效的多项式时间的算法。 由于很多具有实际意义的问题都是n p 完全问题，它们非常重要，所以不能因为 得不到这类问题的多项式时间内的精确求解算法就放弃对它们的研究。如果一个问 题是n p 完全问题，那么到目前为止就不可能找到一个给出其精确解的多项式算法， 这并不是说，就没有一线希望了。解决n p 完备问题有两种方法：第一，如果问题实 例的规模很小，则用具有指数时间的算法来解决问题就很理想了；第二，如果问题 实例的规模很大，但仍有可能在多项式时间内( 最坏情况或平均情况) 找到近似解。 本文要讨论的车间作业调度问题是一个典型的n p 完全问题( 2 】，而且是属于最难 的那一类【3 】。车间作业调度问题是优化组合问题中最难解的问题之一。我们可以解决 随机产生的有3 0 0 - - 4 0 0 个城市( 超过1 0 0 0 0 0 个变量) 的货郎担问题，可以解决有 数百个约束和数千个变量的覆盖问题，但我们却很难解决1 0 个机器，l o 个工件，1 0 0 个工序的凋度问题。因为车问作业调度问题是我们日常生活中一个很重要的实际问 题，所以去寻求在适当时间内能够产生可以接受的调度的快速算法是很自然的。 由于车间作业调度问题本身的计算复杂性，我们不可能去寻求该问题的精确解 法。而启发式方法，“既天才洋溢又疏忽大意，不受拘束，巧妙而富有人性”能 把问题大为简化，可在浩瀚的搜索空间中迅速找到解答。为了设计出求解本问题的 华中科技大学硕士学位论文 启发式方法，我们必须借鉴人们在调度工作中的经验知识，借助这些经验，我们可 以得到问题的满意解答，但不一定是精确解。 我的导师黄文奇是最先提出求解n p 难问题的拟人、拟物思想的学者之一【4 , 5 , 6 , 7 , 8 】。 庄方格、圆形、三角形等的p a c k i n g 问题研究中做了大量的研究工作f 9 , 1 0 , 1 1 】。其中 文献【7 】在拟物算法的基础上提出了两个拟人策略，为具有n p 难度问题的圆形 p a c k i n g 问题找到了一个高效率的实用求解算法。 1 2 国内外研究情况 1 1 前国内外的很多学者对车间作业调度问题都作了深入的理论研究，产生了两 类 ：要研究方法。一类是为了得到问题的精确解而进行的定性研究，而另一类则体 恍了当今求解n p 难问题的主流，即利用近似算法来寻求问题的近似解。 住4 二州作业调度的算法研究中，早期的近似算法大都基于优先指派规则的。优 先指派规则就是按照一定的规则从指定的子集中找出下一个将要被调度的操作。这 些规则包括s p t ( 最短加工时间优先) 、m w k r ( 剩余工作最多优先) 、f c f s ( 先来 先服务) 等等。这些规则按照贪心法一次性决定工序的开工时间，因此，这些近似 算法都很快，而且它们所找到的问题的近似解都还比较好。在有些情况下，这就足 够了。然而，随着计算机的处理速度的加快和调度工作对高效率调度的需求，寻找 更好的调度算法变得越来越重要了。在这种情况下，比较好的启发式算法就应运而 q - 了，如瓶颈机算法、禁忌搜索算法等等。 a d a m s 、b a l a s 和z a w a c k 在1 9 8 8 年首先提出了瓶颈机算法1 1 2 1 ( s h i f t i n g b o t t l e n e c k m a c h i n ep r o c e d u r e ) 。他们提出一个给机器确定瓶颈度并优先给瓶颈度最高的机器排 序( 这早的给机器排序就是给在同一台机器上加工的工序确定一个先后次序) 的方 “、。、用这种方法给所有的机器都排完序后，整个调度问题就解决了。为了给机器 排序，对f 每一台还没有排序的机器都在松弛原问题之后来求解这个机器的单机调 度问题，即每次只考虑一台机器的调度问题。用这些单机调度的所得到的时间跨度 的人小来给这些还没有排序的机器确定优先级，优先级最高的机器的瓶颈度最高。 优先给瓶颈度最高的机器排序。每当一台新的机器排序完成之后对那些已经排好 序的机器进行再优化，这样有可能通过再求解一次单机调度问题使最终求解的结果 华中科技大学硕士学位论文 吏优。当所有的机器的顺序都确定后，就可以很容易的求出调度的时间跨度了。 a d a m s 等人提出的这个算法的主要贡献在于他们给出了一个松弛原问题来确定 给机器排序的方法。而瓶颈机器的概念在历史上早有人提出过【u 1 ，求解单机调度问 题的算法是c a r l i e r i “1 在1 9 8 2 年提出的。在a d a m s 等人的文献中提出了算法s b i 和 枚举了瓶颈机器的算法s b i i ，这两个算法的结果在当时是很好的。而且算法s b i i 求 出了一个很难的算例( f t l o ) 的最优解，因而瓶颈机算法在历史上影响较大，并被很 多人改进过“ ”j 。 禁忌搜索( t a b us e a r c h ) 是一个为优化组合问题寻求近似最优解的启发式算法。 它山g l o v e r 提出并形式化 1 7 , 1 8 , 1 9 , 2 0 l ，是求解优化组合问题的一种得到广泛应用的方 法1 2 1 ，2 3 0 4 1 。禁忌搜索是在2 0 世纪7 0 年代后期被最先运用在非线性覆盖的优化组合 问题中，从那个时候开始，禁忌搜索被用于各种不同的问题中，如计算机调频问题、 空i 训布局等问题。最新的研究包括货郎担问题、图着色问题、电路板布局问题，这 些问题用禁忌搜索可以得到问题较好的解。 在用禁忌搜索来求解车间作业调度问题的时候，必须要给算法提供一个初始调 度。然后通过交换初始调度中工序的位置来产生这个调度的邻域，邻域中的每个元 素都足一个合法的调度。计算出邻域中每个调度的时间跨度，选取时间跨度最小的 那个凋度作为下一次迭代的初始解，并从当前解跳到这个时间跨度最小的解。这种 从。个解跳到另一个解称为一个“动作”。为了避免在搜索的过程中形成环路，这个 “动作”被规定为“禁忌动作”，并且在后面规定的次数内不能重复这个动作。在进 行了算法所规定的迭代次数后，禁忌搜索结束。 禁忌搜索是一个效率较好的启发式算法，它能找到调度问题不少算例的最优解。 但禁忌搜索要面对很多的问题，如初始螭问题、邻域结构问题、搜索策略问题等等。 只有很好地解决了这些问题，禁忌搜索算法才能表现得更好。 13 课题主要研究工作 为了求解车间调度问题，我们提出了基于优先指派的快速拟人算法，并在这个算 法的基础上引进枚举策略，设计了相应的枚举算法。同时我们也试着把拟人算法和 局部搜索算法结合起来求解车间作业调度问题，最后对于改进算法做了一些探讨。 华中科技大学硕士学位论文 本课题拟进行的工作主要如下： ( 1 ) 对车问作业调度问题提出相应的几何模型。对算法所涉的基本概念进行说 明，以利于研究工作的进行。 ( 2 ) 利用拟人思想，借鉴人们在实际调度工作中所采取的策略提出基于优先指 派的拟人算法。并用这个算法进行问题实例的测试。 ( 3 ) 在拟人算法的基础上引进枚举策略，设计出枚举算法。并用枚举算法进行 问题实例的测试。 ( 4 ) 用局部搜索算法求解车间作业调度问题，并测试具体的实例。 ( 5 ) 探讨改进算法的策略。 1 4 本章小结 本章主要讨论了车间作业调度问题的背景及意义。车间作业调度问题是一个典 型的n p 难问题，对于该问题的求解目前还没有找到多项式时间内精确求解的算法， 所以，我们只能寻求用启发式算法来求解问题的近似解。在本章中，我们论述目前 求解陔问题的启发式算法，包括瓶颈机算法、禁忌搜索算法。最后对本论文的研究 工作进行了说明。 华中科技大学项士学位论文 2 车间作业调度问题综述 车间作业调度问题就是对待加工工件的工序进行合法的排序，使机器按照这个 工序顺序来加工，在加工的过程中要满足问题一定的约束条件，使加工完成后最终 形成的调度的时间跨度尽可能的小。这是个典型的优化组合问题。优化组合 ( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是通过数学方法的研究去寻找离散事件的最优编排、分 组、次序或筛选，是运筹学( o p e r a t i o n sr e s e a r c h ) 中的一个经典且重要的分支，所 研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等领域。优 化组合问题的目标是从组合问题的可行解集中找到最优解。它有三个基本要素：变 量、约束和目标函数，表示可行方案衡量标准的函数称为目标函数。因此，该问题 可用数学模型描述为如下形式： m i nf ( x ) s t g ( x ) i 0 x d 其中，f ( x ) 为目标函数，g ( x ) 为约束函数，x 为决策变量，d 表示为有限点集。 一个优化组合问题可用三参数( o ，f ，f ) 表示，其中d 表示决策变量的定义域， r 表示可行解区域f = x ix d ，g ( x ) 0 ，f 中的任何一个元素称为该问题的可行解， i 1 表示目标函数。满足f ( x ) = m i n f ( x ) lx f ) 的可行解x 称为该问题的最优解。 优化组合问题的特点是可行解的集合为有限点集。由直观可知，只要将d 中有限个 点逐“一判别是否满足g ( x ) 的约束和比较目标值的大小，就一定能找到该问题的最优 解。 在计算机科学、v l s i 设计、设备布局和生产调度这些领域出现了大量的优化组 问题，其中的一些问题已经被证明为n p 难问题“”，因而它们到目前为止没有多项式 时间内求解的精确算法。 本章将对车间作业调度问题进行描述，并对该问题计算复杂性、肩发式算法以 及算法中所涉及的基本概念进行说明。 华中科技大学项士学位论文 21 问题描述 车间作业调度问题的描述如下：有一组工件要用一组机器来加工，在加工过程 i j 满足两个约束条件( 1 ) 加工每个工件的机器的顺序是确定的；( 2 ) 每个机器一次 j 能加：【：一个工件。每个工件有若干个工序，每个工序的加工时间是确定的而且在 加工的过程中不可以被中断，使加工完所有的工序后形成的最终调度的时间跨度尽 f 】r 能的短。 这里，我们用n = o ，l ，2 ，n ) 来表示工序的集合( 0 和n 表示开始和结束的“哑” 工序，并非实际存在) ，m 代表机器集合，a 代表受条件( 1 ) 所约束的工序对的集 合，e k 代表受条件( 2 ) 所约束的在机器k 上加工的工序对的集合，d i 和t i 分别表示 工序i 的加工持续时间和开始加工时间。这样，问题就可以表示为如下形式f 2 6 1 ： m i n t n t i - t d j ， t i 0 ， ( i j ) a ， i n ，( p ) t r t i d i v t i - t j 一d j ，( i j ) e e k ，k e m 任何一组满足( p ) 的t i ( i - l ，2 ，3 ，n ) 都称为一个调度。我们的目标就是要找一个 调度，使t 。尽可能的小。为了更直观的理解问题，我们把它上面的代数表述转化为 如图2 1 的几何形式： 、 圈2 1 一个初始调度格局 图2 1 表示一个简单的调度问题。图中每个矩形块表示一个工序，每一列矩形块 表示一个工件所有的工序，为了方便起见，我们为每个矩形块都做了统一的编号， 华中科技大学硕士学位论文 每个矩形块右侧的号码即为这个矩形块的统一编号。矩形块中间的那个数字表示加 j i j 这个二 序的机器号码，如工件i ( 即j 1 ) 先后要在机器m l ，m 2 ，m i ，m 3 上加工。矩形 块的高度表示加工这个工序机器所用的时间( 高度为整数) 。图中的坐标系中的横轴 表示时间，纵轴表示机器。这样，图2 1 就表示了个4 个工件，3 个机器，1 2 个工 序的简单调度问题。 现在我们就是要把代表工序的矩形块调度到代表机器的横线上面去，并把矩形 块“躺”着放在对应的横线上面。在调度的过程中要满足如下约束： ( a ) 矩形块在工件中的先后顺序在机器中也要得到满足，并且它们在t 轴上的 垂直投影不能重叠。如工件l 要在m i 上加工完第1 道工序之后才能在m 2 上加工第2 道工序。这里，我们用矩形块r i 代表由m l 加工的工序，用矩形块r 2 代表由m 2 加 工的工序。那么，我们要先把r i 摆放到m i 上去，再把r 2 摆放到i n 2 上去，并使r i 在t 轴上的垂直投影的开始时间小于r 2 在t 轴上的垂直投影的开始时间，并且这两 个投影不能重叠。 ( b ) 任何两个处在同一条横线上的矩形块( 即在同一个机器上加工的工序) 在 t 轴的垂直投影不能重叠。 我们就是要在满足条件( a ) 和( b ) 的前提下把矩形块调度到横线上去，并使调度 完成之后所有的矩形块在t 轴上的垂直投影区域尽可能的小。 2 2 问题的计算复杂性分析以及启发式方法介绍 算法是为了实现某个任务而构造的简单指令集。对于算法，d e k n u t h 给出了一 个非形式化的定义： 一个算法，就是一个有穷规则( 指令) 的集合。它为某个特定类型问题提供了 解决问题的运算程序。 从这个定义我们可以看出，所谓算法是一组定义严谨的运算顺序规则，并且每 一规则都是有效的，而且是明确的。这组规则在有限的时间内终止。 算法可以指导计算机按照人的意图去完成各种各样繁重的劳动：数据管理、数 学运算、图象处理、辅助设计等等。这一切都使得人们认为所有的事情都要屈服于 功能强大的计算机面前。但事实上算法不可解的问题是存在的。正如计算机出现之 华中科技大学硕士学位论文 自h 人们所遇到的情况一样，有些问题我们可以求解，有些则不可能( 在适当时间内) 求角牟：。这可以分为两种情况：一是对于那些不确定的非数学型任务，根本不可能用 计算机解决。因为计算机仅能执行算法，即计算机只能准确地和一般地理解一系列 指令，此指令序列是用于求解严格确定的可计算性问题。二是对于有些问题，虽然 原则上存在一一种算法可以求解其任一实例，但因该算法需要过长的时间或者太大的 存储空间而使得它变得完全无用。另一方面，对于绝大多数问题，我们常常会遇到 这样的情形：求解某一问题的不同算法在时间、空间要求上相差很大，即使同一算 法，当用来求解问题的不同实例时，其性能表现差异也较大。这些问题就是计算复 杂性所讨论的问题。 算法对时间和空间的需要量称为算法的时间复杂性和空间复杂性，问题的时间 复杂性是指求解该问题的所有算法中时间复杂性最小的算法的时间复杂性。在算法 分析和设计中，沿用实用型的复杂性概念，即把求解问题的关键操作，如加法、乘 法等运算指定为基本操作，然后把算法执行的基本操作的次数定义为算法的时间复 杂性。 对于某一一问题a 和任一可能的输入长度n ，称用所给算法求解a 的所有大小为 n 的例子所需的时间的最大值为该算法在输入长度为n 时的复杂性。对于不同的算法， 就有着不同的时间复杂性函数。复杂性幽数的不同变化方式反应了算法的好坏程度。 例如，时间复杂性函数关于输入长度的增长速度就是判别一个算法实际效率的主要 指标。那么，什么样的时间复杂性函数所对应的算法是好的、可以接受的呢? 现今， 在计算机科学中存在这样一个一般的约定：仅当算法的时间复杂性函数随着问题例 子的输入长度的增加而多项式增长时，才认为这个算法是实用的、有效的。按照这 个观点，可以将算法分为两大类。 多项式时间算法( p o l y n o m i a lt i m ea l g o r i t h m ) ：是指存在某个以输入长度n 为变 量的多项式函数p ( n ) ，使其时间复杂性函数为o ( p ( n ) ) 的算法。因此，复杂性为0 ( n ) 、 o ( 10 6 n 3 ) 、o ( 5 n 8 ) 等的算法为多项式时间算法。 指数时间算法( e x p o n e n t i a lt i m ea l g o d t h m ) ：是指任何时间复杂性函数不可能如 上用多项式函数取界定的算法。这类算法的时间复杂性函数典型的例子有2 “、n ! 、 n “等。 华中科技大学硕士学位论文 由于指数复杂性函数的增长速度比多项式函数的增长速度要快的多，因此，随 着问题例子规模的不断增大，任意一个多项式时间算法终归比任一个指数时间算法 更有效。所以，多项式时间算法要比指数时间算法好得多，是人们常常更加希望得 到的。也正是由于这些原因，人们往往将多项式时间算法称为有效算法，并将“好” 的算法与其等同起来。现在普遍认为，在找到求解它的某个多项式时间算法之前， 。个问题并未被很好的求解。因此，常称一个问题具有难解性( i n t r a c t a b i l i t y ) 或为难解 的，如果它是如此困难，以至于没有多项式时间算法可以去求解它。 那么车间作业调度问题的精确求解算法是多项式时间算法还是指数时间算法 呢? 下面我们将给出该问题的算法复杂性。 对于任一调度问题我们假设该问题中所有待加工的工序的个数是n ，这n 个工 序所需要的总的加工时间是t 。下面我们给出一个如图2 2 所示的一般模型的算法复 杂性。 l 圈2 2 一般调度问曩的几何模型 上图中每个矩形块都表示一个工序，我们按照如图所示的方法给每个矩形块一 个统一的编号。对于矩形块i ，当我们把它放到它所对应的横线上的时候，它在区间 o ，t 】中总共有n i 种可能的摆放位置。 n i - - - - t k i其中k i 表示某一常数 那么我们把这n 个矩形块逐一放到各自对应的横线上的时候，所有可能的组合 数为 1 0 2 n 卸 门日日 心 一 舢 舢 u!口n 和 2 u几u几 妒 n u 山 华中科技大学硕士学位论文 c 2 n l + n 2 + + n o = ( t k 1 ) + ( t - k 2 ) “”+ ( t k 。) 这里，c 表示这些矩形块所有可能的组合，在这些组合中一定有一种组合对应 着调度问题的最优解。那么我们的任务就是找一个算法，使这个算法能从这个组合 空矧中找到那个对应调度问题最优解的组合，这样，这个能找到问题最优解的算法 的复杂性就为o ( t “) 。 从算法的时制复杂性可以看出，车间作业调度问题的精确求解算法是一个指数 时间算法。到目前为止，我们只能用精确算法求出该问题较小规模算例【”1 ，对于大 的算例，通过启发式算法我们也得到了一些重要的结果【2 8 l 。我们知道，指数时间算 法的计算时间使人无法忍受或因问题的难度使其计算时间随着问题规模的增加而以 指数速度增加，而且计算所需的存储空间也会远远超过目前计算机的存储容量。但 出于车间作业调度问题又有它非常强的实际应用背景，有鉴于此，人们不得不尝试 用+ 些并不一定可以找到问题最优解的启发式算法来求解它。 启发式算法可以如下定义： 一种基于直观和经验构造的算法，在可以接受的花费( 指计算时间和占用空间等) 下给出组合优化问题每个实例的一个可行解，该可行解与最优解的偏离程度不一定 事先可以预计。 启发式算法不一一定能保证所得解的可行性和最优性，甚至在多数情况下无法阐 述所得解同最优解的近似程度。 在进行启发式算法设计的时候，我们总是希望在牺牲尽可能少的最优性的同时， 来获得尽可能多的有效性。一般来说，对任何n p 困难问题，总可以按照某种策略来 改计出求解它的启发式算法。依赖于对解的质量或者精度的要求，由启发式算法所 找到的个近似解可以是对一个问题的最终答案，也可以作为某个算法的一个输入。 例如，将由近似解所提供的上、下界信息作为输入。对于减少分枝限界算法的运行 时间有非常大的帮助。 由于不同的启发式算法通常都是针对所需求解的某类问题而设计的，且设计方法 不仅依赖于问题的具体特征，而且利用了某些直观的或经验性的准则，因此，要给出 启发式算法的一个准确划分或某些完全一般的近似算法是比较困难的。到目前为止， 华中科技大学硕士学位论文 补仪已有大量的启发式算法可用于求解各种n p 完全或n p 难的问题，而且，对于同一 i u 题，常常也有数个不同的启发式算法。那么如何对这些启发式算法来进行归类和划 分l 蛇? 一种方法是按照设计启发式算法的不同思路来分。如贪婪算法、局部搜索算法、 原始一对偶算法等等。另一种更自然更合理的分类方法是按照不同启发式算法的近似 比或性能比来分类。如定常近似比算法、最好可能近似比算法等等。 近年来，由于对组合优化问题的深入研究和实际工业生产需要的推动，涌现出 了大量的启发式算法。这些算法对于特定问题的某些算例能够很好的逼近甚至找到 最优解。和精确算法相比，启发式算法有它自己的优缺点： 优点：理论上能够产生最优解的精确算法在实际计算中所得解可能比启发式算 法有更大的误差。这是因为在对问题的求解过程中，该问题的数学模型其实就是实 际问题的简化，或多或少忽略了一些因素；计算中要用到的数据在采集中存在偏差， 本身就具有不精确性；对参数估计也不准确性。 有些组合优化问题可能还没有找到最优算法，即使存在，由算法复杂性理论可 以矢i | 道它们的计算时间是让人难以接受的。而启发式算法能在较短的时间内得到让 人满意的解。启发式算法还具有速度快，算法的编程简单，易于实现容易修改。启 发式算法简单易行，比较直观，容易被使用者接受。 缺点：启发式算法不能保证得到问题的最优解，而且启发式算法具有极大的不 稳定性，甚至对同一问题的不同实例的计算中都会得到不同的效果。在实际应用中， 这种不稳定性造成计算结果不可信。 2 3 算法所涉及的基本概念 在本节中我们将对算法所涉及的一些基本的概念进行说明，以利于后面工作的 进行。 定义2 3 i 格局是指调度的某一时刻已放到横线上的矩形块的布局情况。图2 1 表示一个格局，在这个格局中横线上没有摆放任何矩形块，我们称这样的格局为初 始格局。经过几次调度之后，图2 1 演化为图2 3 。在图2 3 中，已有一部分矩形块 被调度到横线上，我们称这样的格局为一个中间格局。如果所有的矩形块都被调度 到横线上，我们称这样的格局为终止格局。 华中科技大学硕士学位论文 i 8 1 6 1 1 图2 3由圈2 1 演化成的新的格局 定义2 3 2 前沿矩形块指在某一格局下工件中未被调度的矩形块中位置最低的矩 形块。对于图2 3 表示的格局中，编号为2 ，6 ，9 ，1 0 的矩形块为当前格局的前沿矩 形块，临且它们分别为工件j l ，j 2 ，j 3 ，j 4 的前沿矩形块。 定义2 3 3 贪婪沉底法指把矩形块合法地( 即满足条件( a ) ，( b ) ) 放到它所对应的横 线l 并使它在t 轴上的投影的起始值尽可能的小。 定义2 3 4 终止格局的时间跨度在把所有的矩形块都调度到横线上质，就成为一 个终止格局。我们把终止格局中所有的矩形块都向t 轴做垂直投影，投影在t 轴上的 起始位置和投影在t 轴上的终止位置之间的距离我们称之为终止格局的时间跨度。 2 4 本章小结 本章主要对车间作业调度问题进行了描述，并为了便于直观的思考问题，我们 把这个问题转化为一个几何模型。通过利用这个几何模型，我们找出问题的算法复 杂度为o ( t n ) ，说明车间作业调度问题是一个n p 问题。对于这类问题的求解我们目 前只能用启发式算法来寻求问题的近似解。文章同样对启发式算法的进行了阐述， 并对它的优缺点进行了说明。最后，对于论文中的一些基本概念进行了说明。 华中科技大学硕士学位论文 3 车间作业调度问题的拟人算法 3 1拟人策略的核心思想 通过儿十年的实践表明，对于调度这类n p 难问题，根本就不存在经典高效的求 解算法。因此，我们在求解这类问题的时候只能以理论为基础，并借鉴一些人们在 实际调度工作中的一些经验和方法，模拟人们的行为而得到一些启发性方法。并以 这些启发性方法为基础，提出一种简单而有效的确定性车间作业调度问题的启发式 算法。作为启发式算法，它的最大的优点是大大的减少了计算时间，同时算法比较 直观，而且尽管它不能保证所得到的解是最优解，但在大多数情况下，它的解都是 能让人接受的。 i i i _ i 面我们将从如下几点总结一些调度工人在调度工作中的一些经验知识。 第一，调度工作的目标就是使终止格局的时间跨度尽可能的小，因此，对于一 般的_ ：人，他们将会遵从一种规则：先来先服务( f c f s ) 。很显然，这个规则能使工 序的开工时间尽可能的早。如果有个工序已经可以开工了，但却没有人理它，让它 闲置在那里，这样，势必会造成“窝工”。一个工序“窝工”就会影响后面若干个工 序的按时开工，这样就可能会使整个调度工作所需时间变长。 第一：，如果有多个工序可以开工，那么先来先服务规则就不能解决这个问题了。 这时候，有经验的工人就会从如下几点对这些工序作一些比较，然后选择某个工序 优先加工。( 1 ) 加工时间短的工序优先是其中的一个规则。因为加工时间短的a zj - y 所 需的加工时间比较少，对整个格局的影响不大。不会使整个调度工作所需的时间有 人大的改变；( 2 ) 这几个工序中后续工序的加工时间总和最大的工序优先加工是另一 个规则。有经验的工人都会意识到只有尽快把加工时间最长的工件的工序优先调度 j 会使最后关机时间尽可能的早，这样就意味着调度工作所需的时间尽可能的短；( 3 ) 这几个工序中后续工序的个数最多的工序优先加工是第三个规则。未加工的工序个 数越多就意味着组合的可能越多。为了减少组合的次数，优先调度后续工序个数最 多的那个工序则是一个明智的选择。 4 华中科技大学硕士学位论文 第一，如巢多个工序在这多静优先麓刘下它翻酌优先级剐还是一样，这澈明在 这羊串饶先指溅趣粼f 这些工序豹谯先级别楚一样豹，困褥霹戮按照蠢己熬舔羹l l 选取 搂；卜个勰。 这些勰则都楚一令有经验熬调度工夫教调痰王作中黢采取的方法秘繁路，我 | 】 露以氆鉴这些方法鞠镶略来设计一个寝发式算法，即我 | 】艇谗的拟人舞法。 3 2 基子优先指澈规舞l j 的拟人算法辩p 优先指派规则是指在多个可以选择的工序中优先选择优先级最商的工序来调度 的胤则。通常优先指派算法都是速度很快的确定性算法，所求得的问题的近似解的 优度则对于不同的算例而有所不同。对于某些算例，优先指溅算法能够找到最优解， l 町刈r 囟腾算例，优先指派算法所计算得到的近似解和最优解相去甚远。 粗：车问作业问题的求解中，历史上讶经出现过不少的优先指派规则。i s k a n d e r 等 人曾经试验过超过1 0 0 种规则 2 9 l ，如最短加工时间优先( s p t ) 、最长加工时间优先 j 1 1 i ! 则( l p t ) 、剩余工作最少优先规则( l w k r ) 、剩余工作最多优先规则( m w l 勰) 、 剩余操作个数最少优先规则( f o p n r ) 、剩余操作个数最多优先规则( g o p n r ) 、剩 余加工时间最短优先规则( s r m it ) 、剩余加工时间煅长优先舰则( l r m p t ) 等等。 h j 这些优先规则来求解车间作业调度问题一个最大的好处是计算时间非常的短，但 是计算的结果却不好。我们仔细分析一下，不难看出这些优先规则都有一个共同的 特点，那就是它们都怒单一优先指派规则，即它们只用一个标准来给待选择的对象 指定优先级，这显然越不妥当的。我们知道，车间作业问题之所以难解，就在予n p 问题的组合爆炸。丽组合爆炸体现在调度过程中就是每一步调度我们都会遇到到底 逸择i 郴个【：序丌工的问题，要作出一个接近正确选择的抉择就藤考虑到很多的因素， 粜，i f 考虑一个因素擞然疑不够的。因此，我们就借鉴了人们在调度点作中的一些 鳗体的t 作经验来设计出一个用多个规则( m u l t i p l ep r i o r i t y ) 来给待选择的正序确定 优先级的拟人算法m p 。以下就是对算法m p 的描述。 我们用f j 表示某一格硒下j j 的前沿矩形块，d i 表示f i 的糯度，q i 袭示在该格局 1 - j 。中未调度的所有矩形块的高度乏和，t i 表示把f l 按贪婪沉底法放剿它所对应的 横线上时f j 在t 辅上所形成的雅直投影的起始位置，n i 蹙在该格尉下 尚未调度的 华中科技大学硕士学位论文 除了f i 之外的矩形块的个数。 对予某个格髑下豹每个翦浍矩形块，我们都霹戳周 这个三元组给它确定一个优先级。 这令兰元缝确定傀轰级豹方滚是：1 ) 善先魄较第一磺，第一矮最小黝那个藏澄 姚彤块的优先级最高；2 ) 如果第项最小的不噍一，那么比较第二项( 比较的对象 魏楚那鳖第一瑷达到最小豹蓠滏雉形块掰瓣应豹王俘) ，第二璜最大熬王侮豹奏萋瀣矩 彤块的优先级最高；3 ) 如果第二项最大的也不唯一，那么我们确定第一项达到最小、 絷一项达到最大的那些工件中工件号褥最小的工l 串的蓊沿矩形获的优先缀簸离。 拟人算法m p 描述：从初始格局开始，优先调度每个格局中所有前沿矩形块中 陇先级最简的那个矩形块，壹至格局到达终止格简。 扶土灏的表述可以焉如，在为每一个裁沿矩形块( 这些矩形块都是供选择的对 歙) 确定优先级别的时候。我们综合考虑了它们的开工时间、加工完每个工件所要 麴鲢蚓、每个工l 串剩余豹矩形块瓣个数以及该蔫沿矩形块熬热王瓣闼豹长发这些因 索。实际t ，这个给前沿矩形块确定优先级别的规则是结合了前面所列举的若干个 攀往兔攒派矮鲻靛。这样，在为每一令蔫澄矩形块确宠凭先级豹辩嫉，我翻藏考 虑了很多的因素，作出的选择也念比单一优先指派规则客观的多。 3 3 算法m p 的测试结果及算例评析 我翻爝m p 测试了一些算铡，这彗被灏试的算翻都怒国际上公舞懿铡子，暴律 结粜! l ! 表3 1 。 满螫流鳞静怒，本文中所有的计算都楚在一螽个入梳上完成的。梳器的基本配 谢勾：c p u 赛扬6 3 3 m h z ，内存1 2 8 m ，擞作系统是w i n d o w s 2 0 0 0 。算法怒周c + + 实 脱的。交中带+ 的项表示对予该冀例，算法能找到壤优解。 这些被测试的例子中的f 1 0 6 、i l l 0 、f 1 2 0 由f i s h e r 和t h o m p s o n 于1 9 6 3 年提供l 删， l a 0 6 - 1 a 1 5 、1 a 1 7 、l a 2 t 、1 a 2 3 由l a w r e n c e 于1 9 8 4 年提供剐。这些算错中i l l 0 的难 度最大( 从最先被提出到最终被解决用72 0 多年) 。对予i l l 0 算例，以前出现的一 黛优先指派算法如s p t 、m w k r 、t w o r k 等的计算绪采都在1 2 0 0 左右，郎使楚 a d a m s 等人中所提出的算法s b i 的计算缭果也是1 0 1 6 ，没有m p 趵计算结果好。瓤 1 6 华中科技大学硕士学位论文 e j m p 在极短的时间内找到了7 个算倒的最优解，这在优先指派算法中是很少见的。 衰3 1算法m p 的测试结果 m p 算例i ：件个数机器个数工序个数最优解 结果计算时间( 秒) f 1 0 6663 65 56 8 l n 1 01 01 01 0 09 3 01 0 0 7 l f 1 2 0 2 051 0 01 1