（计算机软件与理论专业论文）滚动规划和调度算法分析及复杂流水线调度问题的研究.pdf

滚动规划和调度算法分析及复杂流水线调 度问题的研究 摘要 预测控制是于七十年代后期在工业过程实践中发展起来的一类新型计算机 控制算法。它已经得到了广泛的研究和应用。预测控制通过预测模型、滚动优化、 反馈校正把优化和反馈机制合理地结合起来，使得预测控制具有非常显著的优 点。 本文将预测控制思想运用到各种广义控制问题上，作了初步的研究工作： 1 将预测控制的思想应用到机器人路径规划和车间调度问题中。针对机器人路 径规划问题的特点，提出了能够与全局行为相联系的局部性能指标和滚动算 法，证明了在障碍物满足给定条件的情况下，随着滚动的进行，该局部性能 指标逐渐减小。并给出按照该滚动算法机器人走的路径长度的上界。 2 将预测控制的思想应用到车间调度问题中，针对车间调度问题中的两个典型 问题，提出了滚动算法，并作了性能分析。得到一些了滚动算法的一般结果。 针对单机问题进行了实验分析。由于滚动算法的理论分析的困难，作为经典 n p h a r d 问题的车间调度问题在滚动算法上的成果一直非常有限，本文的 成果也许可以成为这方面研究工作的一个思路。 本文还对一类复杂流水线的调度问题进行了研究，建立了两层整数规划模 型。并对上层模型提出了一种近似算法，大大减小了计算量。 关键词：滚动算法、竞争比、机器人路径规划、车间调度、单机调度、复杂流水 线 - - - _ 1 。”一 。 a bc tg 卧 a b s t r a c t m o d e l p r e d i c t i v ec o n 订o lt h e o r yw a sd e v e l o p e d i ni n d u s t r i a lp r o c e s sc o n t r o li nt h e e n do f7 0 s i th a sb e e nw i d e l ys t u d i e da n du s e da san e wk i n do fc o m p u t e rc o n t r o l a l g o r i t h m m o d e lp r e d i c t i v ec o n t r o lt h e o f yc a nb es u m m a r i z e di n t ot h r e ee l e m e n t s ， w h i c ha r ep r e d i c t i v em o d e l ，r o l l i n go p t i m i z a t i o na n df e e d b a c k s i n c ei tc o m b i n e st h e a d v a n t a g e so fo p t i m i z a t i o na n df e e d b a c k ，m o d e lp r e d i c t i v ec o n t r o lt h e o r yh a sg r e a t a d v a n t a g e i np r a c t i c e i nt h i sr e p o r t ，t h ep r i n c i p l e so f m o d e l p r e d i c t i v ec o n t r o l a r ea p p l i e dt ot w oa s p e c t s o f g e n e r a lc o n t r o lp r o b l e m s 1 t h ep r i n c i p l eo fm o d e lp r e d i c t i v ec o n t r o li sa p p l i e dt ot h er o b o t sp a t hp l a n n i n g p r o b l e m al o c a lp e r f o r m a n c ei n d e x i s p r e s e n t e d ，a n d ar o l l i n ga l g o r i t h mi s d e s i g n e d i ti sp r o v e n t h a ta st h er o b o tg o i n ga c c o r d i n gt ot h ea l g o r i t h m ，t h el o c a l p e r f o r m a n c ei n d e xb e c o m e sl e s s a n dl e s s ，p r o v i d e do b s t a c l e ss a r i s f ya g i v e n c o n d i t i o n t h ea l g o r i t h mg i v e sau p p e rb o u n do f t h ep a t hl e n g t h 2 。r o l l i n gs t r a t e 彩i sa l s o u s e di n s c h e d u l i n gp r o b l e m s r o l l i n ga l g o r i t h m s a l e p r e s e n t e d f o rt w oc l a s s i cj o b 幽o ps c h e d u l i n gp r o b l e m s c o m p e t i t i v ea n a l y s e sa r e c a r r i e do u t ag e n e r a lr e s u l tf o rr o l l i n ga l g o r i t h m sf o ras i n g l e m a c h i n es c h e d u l i n g p r o b l e mi sp r e s e n t e d ，e x p e r i m e n t sf o rs i n g l em a c h i n es c h e d u l i n ga l g o r i t h m sa l e g i v e n a c o m p l e xp r o d u c t - f l o ws c h e d u l i n gp r o b l e m i ss t u d i e di nt h i sr e p o r t at w ol e v e l m i x e di n t e g e rp r o g r a m m i n gm o d e ii sg i v e nf o rt h i sp r o b l e m a na p p r o x i m a t i o n a l g o r i t h mi sp r e s e n t e d f o rt h eu p p e rl e v e la n d c o m p u t a t i o n a le x p e n s e i sr e d u c e d k e y w o r d s r o l l i n ga l g o r i t h m s ，c o m p e t i t i v er a t i o ，r o b o tp a t hp l a n n i n gp r o b l e m , j o bs h o ps c h e d u l i n gp r o m e m s ，s i n g l em a c h i n e ，c o m p l e xp r o d u c t f l o w 第一章绪论 预测控制的思想在工业过程实践中产生并发展的。随着控制领域的不断扩 大，预测控制的思想被运用到越来越广泛的控制领域。它在机器人路径规划、车 间调度等领域也得到了运用。 本章先简要介绍预测控制的思想、机器人路径规划、车间调度问题以及复杂 流水线的调度问题，在此基础上给出本文的主要研究内容。 1 1 预测控制思想 预测控制是一种在工业过程实践中发展起来的控制方法。它通过预测模型、 滚动优化、反馈校正把优化和反馈机制合理地结合起来，在一定程度上克服了不 确定性的影响，实现了在线的优化控制。预测控制的研究和应用非常广泛。并且 随着控制理论的发展，控制对象的不断增多，新的系统的加入使得一些传统的控 制方法逐渐无法使用。但是预测控制的思想却始终能够历久如新。不少文献己对 预测控制理论研究及工业应用现状作了较详细的综述，如 1 3 】。这些研究预测控 制算法的论文，并没有在真正意义上统一刻画预测控制的通用特征。为了让预测 控制能够运用到更加广泛的系统中，对预测控制本身的描述必须重新定义，使之 能够满足一般系统的需要。 预测控制是由预测模型、滚动优化、反馈校正三项基本原理组成的【4 】。在文 5 中，又把这三项原理进一步延伸为场景预测、滚动窗口优化、反馈初始化， 使它不仅适用于控制问题，而且适用于动态未知环境下的规划、调度、决策等广 义控制问题。文 6 从预测控制的基本原理出发，基于系统行为的描述，定义了 预测控制中一些重要的基本概念，并在此基础上提出了预测控制的系统行为描 述。探讨了预测控制局部性能指标选取应满足的性质，并将结果应用于若干实际 系统中。 需要指出的是，传统的预测控制在系统分析中存在着严重的困难，这种困难 的本质在于每次滚动优化时所采用的局部性能指标只是简单地从全局性能指标 中截取一段，在全过程中这一指标不断发生变化，但始终不能与全局性能指标定 量地联系起来，而要在每次滚动优化时采用全局的性能指标，却又因为预测模型 对系统行为描述的不完全性以及在此基础上全局性能指标计算的无意义而无法 实现。因此，在对预测控制进行广义化描述时，必须对预测控制的原理从信息的 角度进行更深入的分析，并立足与全局信息对模型和优化进行刻画。 1 1 1 场景预测 在预测控制中，必须建立一个描述动态系统场景演变的预测模型，这一模型 包含了所要求解问题的所有已知信息，特别要反映出动态系统演变的原因、演变 的规律、约束的条件和优化的目标。任意给定一种控制律( 求解策略) ，就可以 根据这一模型预测出系统的动态演变过程，并进而求出相应的性能指标。因此， 场景预测的核心是以所要求解的控制律为输入，所要优化的性能为输出的广义的 预测模型。 由于不确定性的存在，对系统未来变化的预测不可能是准确无误的。从系统 行为的角度来看，预测模型主要反映了在系统运行过程中控制器对系统的了解程 度。一般说来，对系统近期行为的预测比较准确，可以用确定的模型加以描述， 而对其远期的行为则可能存在不同的模型描述。传统的预测控制为了解决预测的 确定性，一般都采用单个预测模型。但这只是处理不确定性的简化手段，而不是 全局预测的必然模型。从一般的角度而言，系统行为的多样性是对系统现有信息 的有限性的一般描述。然而，这种多样性的引入也改变了利用这些模型进行优化 的方式。如果根据传统的预测控制，从系统环境信息集合中选取一个环境信息作 为滚动优化的基础，在这个环境信息所对应的预测模型上进行滚动优化，这种滚 动优化的机制有其致命的弱点。对于某个特定的模型，虽然当给定了某个合法输 入时，都可以计算出在这种控制律下。由于不确定性存在，描述系统将来可能行 为的模型有很多个。根据某个模型得到的控制律并不一定是有意义的。这样就不 得不选择适当的局部性能指标，作为每一步滚动优化的凭据。以下进一步讨论滚 动优化的一般描述。 1 1 。2 滚动窗口优化 全局问题的求解被在线滚动进行的一系列局部问题的求解所取代，在滚动的 绪论 每一步，确定某种以当前状态为基点的滚动窗1 3 ，仅对这一滚动窗口内的局部问 题通过场景预测和优化求解最优策略，并实施当前策略。随着动态过程的延续， 推进窗口的移动，从而形成滚动优化。控制是在对系统信息不完全了解的情况下 进行的，需要在线反复增加和补充新的信息，重新优化。 采用局部性能指标首先是因为系统的不确定性使得系统目前对将来的预计 总是不够准确的，其次是为了降低计算量。由于预测模型集定义了滚动优化的范 围，如果能够在预测模型集的一些模型中找到一组子模型，在这些子模型上进行 优化就可以减小计算量。在这个子预测模型集上，对系统进行滚动优化。在选定 了子预测模型集之外，预测控制算法一般会选取一组局部性能指标。在每一步， 预测控制算法都在这个子预测模型集上根据某个定义在公共区域的局部性能指 标优化控制量，并实施这个控制量的一部分。从系统的实施睛况得到新的信息， 进而进行下一步的局部优化。如此滚动进行。在每一步滚动优化的过程中，子预 测模型集以及局部性能指标共同定义了这个局部优化问题。子预测模型集的不同 选取得到不同的优化论域，而局部性能指标的选取则牵涉到全局性能指标与局部 性能指标的一致性问题以及滚动优化是否有意义。 1 1 3 反馈初始化 在滚动的每一步，首先要根据最新的实时信息对滚动窗口中的场景重新初始 化。这意味着下一步优化时，不但考虑了预测模型所提供的确定性因果信息，而 且也把不确定信息引起的系统变化包含在内。这样就可使每一步的优化都建立在 反馈得到的最新实时信息基础上。反馈初始化是衔接相邻两次滚动优化所必不可 少的一环。它从受控系统的运行中得知系统现在的状态；随着系统的运行。对系 统的了解也随之增加，从而对系统将来的行为的估计进行更新；同时对局部性能 指标也不断更新。在此基础上才能对系统进行新一轮的优化控制。 本文将预测控制的一般原理应用于机器人路径规划问题和车间调度问题。这 些都是广义控制问题，为预测控制原理的一般化研究打下基础。 1 2 机器人路径规划问题 移动机器人路径规划问题是指在有障碍物的工作环境中寻找一条恰当的从给 - 3 - 定起点到终点的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的 障碍物。当环境信息已知时，离线的全局规划可以解决这一问题，并且能对某些 性能指标作优化。在这方面已有大量深入的研究【7 。”， 然而，在许多情况下，机器人的环境信息是不完全的，甚至是未知的，机器 人只能探测到局部信息。针对这种情况，人们已提出了不少解决未知环境下路径 规划问题的方法和策略。这方面的工作主要可以分为两大类。 一方面的工作是在地图建立的基础上的。移动机器人首先建立地图【1 3 - 1 4 然后进行路径规划。通过探索环境，机器人可以逐渐建立全局地图，这样基于全 局地图，机器人的路径规划就比较容易。这种方法对于在同一个环境下要执行多 种任务的机器人非常实用。得到全局地图以后，路径规划的效率会大大提高，甚 至可以求得最优解。在某些情况下，机器人需要进行几次预规划以便获得更精确 的地图信息【1 3 】。这就要求机器人拥有很大的内存容量来存储这些信息。对于只要 执行单个任务的机器人，建立全局地图意味着要得到很多冗余信息，否则正因为 路径规划是在全局地图上进行的，机器人本身的定位就成为一个非常现实的问 题。对于不确定环境中的路径规划问题f 1 6 49 】，因为已有的环境信息是不完全的， 只能通过求得局部的路径轨迹或者子目标，并且实时地更新地图信息滚动地进行 得到整个规划轨迹。 另一方面的工作是利用实时信息进行实时避障。机器人不断地探测信息并且 不断地规划出一条趋向目标点的可行路径。这种方法的优点是每次决策需要相对 较少的环境信息，因此速度快。但很难保证全局可达性。 2 0 利用v i r t u a lf o r c e f i e l d 方法解决了在未知环境下机器人的避碰问题，这种方法却不能保证机器人 一定会到达终点，在某些情况下这种方法甚至会导致不稳定【2 1 】。 2 2 将动态窗口 方法应用到路径规划问题中，并且考虑了机器人的运动学约束。机器人在避障的 同时，可以快速地向目标点移动。尽管这个方法得到广泛的应用，机器人仍然很 容易陷入局部最小点。 利用实时信息进行的局部规划很难保证全局可达性。一些方法将必要的全局 信息引入规划中以保证可达性。 2 3 研究了在不确定环境中启发式路径规划方 法。机器人记忆了环境中某些特殊的点，利用一个全局性能指标来进行规划。不 过在很多情况下，路径因为缺乏优化而变得不是很理想。2 4 通过存储更多的环 境信息对算法进行了改善。 2 5 提出了全局动态窗口的方法，拓展了【2 2 1 q h 结果。 探测信息被融合到全局地图中，以获得空间的连通性。将反应式避障的动态窗口 方法和利用从目标点开始计算的传播算法得到的无局部最小点的全局导航函数 结合起来。f 2 6 将两个基本元素结合起来：地图建立和导航算法。首先，机器人 收集周围的环境信息并将这些信息融入全局地图。其次，利用a 算法生成一条 从当前位置到达目标点的局部最优路径。机器人沿着该路径直到已知区域的边 缘，当遇到未知障碍物时，停下来重新计算。虽然这些方法充分利用了探测到的 环境信息，并能够保证可达性，但是计算的区域往往会很大，特别是当已经探索 了大片区域的时候。信息的存储将占用大量的空间，计算量也越来越大。这些方 法也不适用于复杂的动态环境。 事实上，在未知环境中的移动机器人路径规划问题牵涉到如何利用探测到的 信息，使得规划的路径不仅可达，而且尽可能优。优化和反馈这两方面必须同时 考虑在内。【2 7 将预测控制中的滚动优化思想运用到机器人路径规划问题中，提 出了带滚动窗口的有效算法。算法充分利用实时探n - n 的局部信息，在线滚动地 进行规划。这样算法计算复杂度始终保持在一个低水平上，从而有高的反应速度， 而且能够保证可达性。但是由于缺乏对算法的分析，不能定量地给出该算法好坏 的程度。也不能知道机器人实际所走的路径长度和最优解之间到底有多少差距。 本文在文 2 7 】的基础上，进一步提出了一种和全局性能指标有关的局部性能 指标，根据这种局部性能指标得到的滚动路径规划算法，在针对一类特殊障碍物 的分布情况下，这种局部性能指标实际上就是机器人到达终点全局性能指标的上 界。并证明了这个局部性能指标随着滚动的进行是单调下降的。 1 3 车间调度问题 车间调度是一个经典的n p h r a d 问题，半个世纪以来，已经有大量的文献 针对这一大类问题进行了深入的研究。由于问题本身的难度，使得研究的进展一 直相当缓慢。针对不同的问题虽有不同算法提出，但在整体上却没有一套非常系 统的方法对各种问题进行研究。这些研究可以从问题和算法两个角度进行分类。 1 3 1 车间调度问题的分类 对于n p h a r d 问题，要在多项式时间范围内求出最优解几乎是不可能的。 所以这方面的研究集中在对近似算法的研究。一个近似算法a 是一个多项式算 法，即算法可以在多项式时间的范围内绘出计算结果。算法a 的输入是某个具体 问题的一个实例厶算法根据这个实例计算出解。而这个问题本身可以对这个解 进行性能评价a ( d 。对于这个实例，问题本身存在最优解以及最优解所对应的性 能指标o p z 奶。评价算法4 给出的解的好坏可以有很多种方法。本文中所采用 的是它们的比值，即a ( 1 ) o p t ( 1 1 。在所有的实例中存在一个最大值( 针对r a i n 的性能指标) ，m 弘a ( 1 ) o p t ( i ) ，这是判断算法好坏程度的一个性能指标。称 为算法彳的近似比，记为p 。 从算法种类的角度来划分车间调度问题，可以分成离线( o f f - l i n e ) 算法、在 线( o n l i n e ) 算法、近在线( n e a r l y0 1 t l i n e ) 算法以及带前瞻的在线算法( o n l i n e a l g o r i t h mw i t hl o o k a h e a d ) 。离线算法主要针对工件和机床的信息全部已知的情 况，给出原问题的解。在线算法则针对只知道已经到达的工件信息或者目前的机 床情况，没有将来的信息情况，对当前情况进行调度。近在线算法和带前瞻的在 线算法都是在知道部分将来信息的情况下，对目前的工件进行调度的算法。近在 线算法这个名称主要用在预知机床的损坏或者修复情况，从而对工件进行合理的 调度。而带前瞻的在线算法则是在预知将要到达的工件信息的情况下对当前的工 件进行调度。本文的研究范围是带前瞻的在线算法。 由于在线算法和带前瞻的在线算法不知道将来( 全部) 的工件信息，对它们 而言，将来的情况可能会改变。在进行算法的性能分析时，它们的近似比被称为 竞争比。 1 9 7 9 年，g r a h a m 在文 2 8 中系统地对车间调度问题进行了划分c 提出了表 征每一类车间调度问题的记号，即a l 卢i ，。这个记号由三个代码组成：表示 机床的环境信息。比如a = 1 表示单机的工作环境、口= p 表示并行机的工作环境， 即有多台机床，每台机床都是一样的，机床的数量没有预先给定。用下表对a 的 一些常用取值进行解释。 a 的取值说明 单机 p 并行机( p a r a l l e lm a c h i n e ) ，即多机，所有的机床都是一样的 u n i f o r m l y r e l a t e d p a r a l l e l m a c h i n e ，多机，每台机床有不同的加 q 工速度。 u n r e l a t e dp a r a l l e lm a c h i n e ，多机，每台机床针对不同的工件有 r 不同的加工时间。 f l o ws h o p ，每个工件都要按照一个相同的次序经过所有机床才 f 能完成加工。 o p e ns h o p ，每个工件可以按照任何次序在所有的机床上都加工 d 完才算完工了。 j o bs h o p ，每个工件都有事先规定好的可能的加工次序，工件必 ， 须按照这些次序完成所有的加工。这是最复杂的情况。 p m 并行机，不过事先已经确定共有m 台机床。 u n i f o r m l y r e l a t e dp a r a l l e lm a c h i n e ，事先已经确定一共有m 台机 q m 床。 r mu n r e l a t e dp a r a l l e lm a c h i n e ，事先已经确定一共有m 台机床。 f mf l o w s h o p ，事先已经确定一共有m 台机床。 o m o p e ns h o p ，事先已经确定一共有m 台机床。 咖j o b s h o p ，事先已经确定共有，l 台机床。 表1 1 ：车间调度分类a 的取值 卢表示问题中工件方面的信息。比如卢= 5 表示工件是动态到达的，每个工 件有一个到达时间( r e l e a s ed a t e ) r ，工件只有在这个时间以后才可以开始加工。 卢= s ，表示每个工件在加工前需要一段准备时间j ，。这个阶段的准备工作可以与 其它工件的加工同时进行。有些选项是可以和其它选项一起使用的，比如 卢= ，p m t n 表示工件是动态到达，并且是可以抢占的，即任何工件的加工都可 以被打断，在以后的任何时刻继续加工。卢一些常用的取值用下表进行概括。 口的取值说明 0 工件动态到达。 每个工件都有一个交货时间( d u ed a t e ) 。如果工件的完工时间 d 大于这个交货时间，该工件没有准时完工。 0工件的有准备时间s j 。 工件的加工满足给定的先后关系。即某些工件只有在它们的前 p r e c 序工件加工完以后才能加工。 在线算法，即只知道已经到达的工件信息，不知道末到达工件 o n 1 i n e 的信息。 t ，m t n 可以抢占。 工件加工的任何时刻都可以被打断，在将来的任何时刻，被打 r e s t a r t 断加工的工件必须重新加工。 d e d i c a t e某些工件只能在某些机床上加工。 工件的准备时问随机床上一次加工的工件而定。因而准备时间 5 4 是一个n x n 的矩阵，其中n 表示工件个数。 表1 2 ：车间调度分类一1 3 的取值 ，表示问题的性能指标。常用的性能指标见表1 3 所示。例如，p 【0 c ，表 示在并行机上加工动态到达的工件，性能指标要求所有工件完工时间之和最小。 从上述的讨论中可以看出车间调度问题是非常多的。在这些问题中，除了少数几 个问题可以用多项式算法求得最优解以外，其它都是n p h a r d 问题。求取这些车 间调度问题的解有很多方法，以下分别简单介绍一下。 绪论 7 的取值说明 ( 二。最后完工的工件的加工时间。 厶。延期时间最长的工件的延时。 i c i所有工件完工时间之加权和。 l lj 所有工件延期时间之加权和。 u j = 1 表示该工件延期，否则为0 ，所以该性能指标表示延期的 u ， 工件数。 这项性能指标反映了j i t 的要求，工件尽可能在指定的时间完 q l c j - d j l 工。 1 3 2 优先规则 表1 3 ：车问调度分类y 的取值 在车间调度问题中，有一些问题可以利用简单的规则求出最优解。这些规则 中，很多是根据一个指标对工件进行排序，所以计算的复杂度是o ( n l o g n l 。以 下分别进行介绍。 s p t ( s h o r t e s tp r o c e s s i n gt i m e ) 规贝, 0 t 2 9 规定在任何时刻，总是先加工加工时间 最短的工件。这个规则之所以著名是因为针对1j i c ，问题，它可以给出最优解。 可以利用简单的交换来证明其正确性。在此基础上，1 9 5 6 年提出的s m i t h 规则 将工件按照竹哆从小到大排序，按照这个次序加工工件得到了1 l | z ，c ，的最优 解。e d d ( e a r l i e s td u ed a t e ) 规则要求把工件按照交货期( d u ed a t e ) 从小到大排 序，按照这个次序加工工件。e d d 规则所给出的结果是l | | l 。问题的最优解。 如果在上述问题的基础上加上工件动态到达的限制，就变成世界上最难的问 题：l - - t 。然而，再加上可以抢占，问题又交得简单了。针对1 1 p m t n 】c j 问 题，s r p t ( s h o r t e s tr e m a i n i n gp r o c e s s i n gt i m e ) 规则【3 l 】动态地优先加工剩余加工时 间最短的工件。即当有新的工件到达时，如果新到达的工件的加工时间比在加工 工件的剩余加工时间短，则将在加工工件抢占，加工新到达的工件，反之则继续 加工原工件。这个规则给出了该问题的最优解。同样地，e d d 规则是 1 lr j , p m 加l 厶。的最优算法。工件可以抢占的特性好像可以抵消工件动态到达所 带来的困难，但是1 1 0 l c ，和1 1 0 l k 。都是n p c o m p l e t e 问题。要找到算法求出 这些问题的最优解几乎是不可能的。 上述问题都是单机调度问题。对于那些更加复杂的问题，简单的规则仍然可 以起到很大的作用。1 9 5 4 年，【3 2 】提出的j o h n s o n 规则是f 2i | c 二的最优算法。 1 9 5 9 年，m c n a u g h t o n 提出了m c n a u g h t o n sw r a p a r o u n d 规则，是pip m t n c 二。问 题的最优算法。 上述的讨论中，规则都是作为最优算法提出的。然而规则的另一个重要的方 面是作为近似算法。这方面的研究工作成为调度问题研究的突破。因为很多问题 本身是n p h a r d 问题，比如尸i c m 。，不太可能为这些问题找到最优算法。然 而一些规则却可以在性能上给出保证。 1 9 6 6 年，g r a h a m 提出了l s ( l i s ts c h e d u l i n g ) 算法，这是p | | c 呲问题的2 近似算法，也是第一个调度问题的近似算法。它给出解在性能上肯定比两倍的最 优性能小。1 9 6 9 年，他提出著名的l p t ( l o n g e s tp r o c e s s i n gt i m e ) 规则【3 4 】，先加 工加工时间长的工件。l p t 规则改进了l s 规则的结果，将近似比推进到4 3 。 此外，针对p l p r e c ic m 。和0 i 问题，l s 都是2 近似算法。 由于规则从本质上是一种简单的排序算法，对于一些比较复杂的问题，如包 含工件动态到达要求的问题，规则不会有意地给出一段等待时间来改进解的性 能。对于一些问题，规则甚至不能给出一个有限的近似比。因此，规则有很大的 局限性。下一节将介绍更为复杂的贪心算法。 1 3 3 贪心算法p 5 1 贪心算法是将原问题分解为一系列予问题，通过求解这些子问题递增地构造 解的一种算法。对于每一个子问题，算法总是求最优解，故名贪心算法。很多贪 心算法利用了最优解的特性，利用动态规划的方法进行求解。以下介绍几个用贪 很多调度问题都可以归纳为1 l i ，m 。问题。其中非减函数乃( q ) 是工件完工时 间的惩罚函数。如果令一( t ) = f d j ，那么原问题就成了i i i l m 。 令，为工件集合。找出使得乃( p ( j ) ) 最小的作为最后要加工的工件，然 后令j = ，一，不断地重复上述操作就得到了一个调度。可以证明这个调度正 是1 i 问题的最优解。 类似地，对于l l p r e c l _ ，o 问题，也可以找出在，中没有后序工件，并且使得 ( p ( ，) ) 最小的，作为最后要加工的工件，然后令了= y - 。重复上述操作直 到了= a 。这样得到的调度也是该问题的最优解。 容易看出上述算法的计算复杂度为o ( n 2 1 。由于每次计算都确定了解的一部 分，以后的求解都建立在以前计算的基础上。正是利用了问题的这种特性，大大 降低了计算复杂度。接下来介绍几个比较复杂的贪心算法。 在所有的n p h a r d 问题中，有一些是相对比较容易的，因为针对这一类问 题，存在一种伪多项式算法。这些算法的计算复杂度虽然不是多项式的，但是可 以写成和问题参数或者幂有关的多项式形式。这种问题称为弱n p c o m p l e t e 问 题。如1 | l ，u j 问题。 对于l j i 吐。问题，由于要使延期完工的工件的权值之和最小，原问题可以 转化为找出一个调度使得按时完工的工件权重之和最大。可以构造如下动态规划 算法。先将所有的工件按照e d d 规则排序，令，为l ，中权重之和大于， 加工时间之和最小的工件集合所对应的加工时间之和。= 0 ，l 。= * 。利用 以下的递推公式来计算所有的，。 ”1 i n v m ( r o , s , r o - , j 把+ l 咒兹掌1 于是，c o 最大的 a o 所对应的工件集合就是原问题的最优解。可以看出，上 述算法的计算复杂度为o ( 一哆) 。当q 有界时，算法的复杂度就成为d ( h 2 ) 了。 p i i 问题是另一个有伪多项式算法的问题。利用动态规划的方法，可以 得到计算复杂度为d ( n 。5 ) 的算法，其中一共有j 种加工时间不同的工件，n 为 工件数。 上述的讨论中，可以看出利用问题本身的特性设计动态规划方法，利用中间 结果避免重复计算是解决车间调度问题的一个重要手段。 1 3 4 两分图最小匹配方法 图论中现有的结论和方法被应用到求解车间调度问题中，得到了很多成果。 因为两分图的最小匹配问题存在多项式算法，如果可以把一个车间调度问题归结 成为此问题，就可以利用现成的算法对车间调度问题进行求解。 一个将调度问题转化为两分图最小匹配问题的典型例子是r i l c ，问题【3 6 0 ”。 因为 mlml ，| ，m 。 q = 吒= e e 只。= n ，。 f 爿i = i产l 扣l i = ti = lk = l 其中，为在机床i 上加工的工件个数，h 为机床i 上加工的倒数第k 个工件。 将原问题转化为两分图匹配问题，如下图所示。左边的节点v ，代表工件，共有 n 个节点。右边的节点代表机床i 的倒数第k 个位置，蜊g n x m 个节点。连 接叶和魄的边的权值为女岛a 这样， 图的任意一个匹配就对应原问题的一个 解。而最小匹配就对应了原问题的最优 解。由于两分图晟小匹配问题存在多项 式算法，rl c ，就存在多项式算法。 类似地，文 3 8 利用最小匹配法解决 了0 i p m t n i 问题。匹配方法成为解 决车间调度问题的一个常用手段。 图1 1 ：r l l c 。转化成两分图匹配问 誉一 1 3 5线性规划方法 和匹配方法一样，线性规划问题也存在多项式算法。如果能够把一个车间调 度问题转化为线性规划问题，这个问题同样可以得到解决。 比如r i p m t n l c m 。问题【3 9 】，如果定义为工件在机床i 上加工的百分比， 原问题可以表示成为如下形式。 m i n d = l j = l 月 p , j x j 蔓d p 口吻d 0 i = 1 ，m j = 1 ，n i = 1 ，m ，j = 1 ，n 其中，d 为最大的完工时间。由此就解决了r i p m t n f 问题。 利用线性规划方法不仅可以对某些调度问题建模，得到该问题的最优解。对 于那些不能表达成线性规划的问题，由于不少可以表达为整数规划模型，把整数 规划问题松弛成为一个线性规划问题可以求出该问题的下界。虽然经过松弛以后 得到的解可能不是原问题的可行解，把这个不可行解经过处理以后得到可行解的 性能指标与线性规划的最优解在性能上存在一定的关系，从而得到一个有性能保 证的近似算法。近年来，这种方法在很多车间调度问题上都得到了应用。线性规 划方法可能是车间调度问题研究中被应用得最多最广的方法。 上述讨论的r i p m t n i l 问题实际上是尺| | 问题的一种松弛，rj | 问 题可以建成如下形式的整数规划模型 4 们。 m i n d = 1 j = l ，卅 i = 1 岛而s d i = 1 ，m j 削 而 o ，1 ) f = 1 ，所，= 1 ，n 这是一个n p c o m p l e t e 问题。如果把最后一个约束用0 来代替，并且加上约 柬 矗= 0 ，p u d 由于上述约束隐含在原来的整数规划模型中，放松约束以后得到的线性规划问题 是原问题的一个松弛问题。解这个线性规划问题得到一组解磊。这个解不一定 是原问题的可行解，但是利用如下的处理方法，根据工“得到一组可行解。如果 ；g = l ，那么就把工件j 放在机床i 上加工。如果o 西 1 ，那么以工件和机床 为节点，以0 埘 i 为边( f ，j ) 的权值构成的两分图存在一个匹配，可以把剩下 的工件匹配到机床上。这样就得到个可行解。这个可行解的性能指标不会大于 2 d ，所以也就小于等于两倍原问题的最优性能指标。从而通过松弛为线性规划 问题以及重构可行解的方法，得到了2 近似算法。 这种方法被广泛地用到很多其它问题上。s r p t 规则可以给出问题 l 0 ，p m t n i q 的最优解。而1 1 0 i q 问题是强n p h a r d 问题。作为这个问题的 一种近似，s r p t 规则给出的工件完工时间c f 不一定是可行解。但是根据这个松 弛解，根据c f c f sc ：将工件进行排序。然后按照这个次序进行加工就构 成了原问题的一个可行解c ? 。可以证明 掣2 g 越j = l 于是，这个多项式算法是l f 0i q 问题的2 近似算法a 同样的方法也被用于1 1 0 ，p r e c i z c ，问题，甚至更为复杂的问题。由于整数 规划问题中可行域通常不是连通的，而最优解一般在可行域的顶点上，可行域凸 包的研究对松弛解与原问题解之间的联系有着非常重要的意义。这方面的工作可 以参考文 4 1 , 4 2 。 整数规划或者线性规划建模可以有多种方法，优化变量也各不相同。除了上 述所说的利用工件的完工时间和工件完成的百分比作为优化变量以外， 4 3 】利用 判断工件，在f 时刻是否被加工的o - 1 变量作为优化变量。这种建模方法优化 变量多，但可以描述各种不同的约束条件。 4 2 利用工件加工的平均时间作为优 化变量。这些不同的建模方式被应用于各种不同的调度问题上，研究了它们之间 的关系，得到了非常深入的结论。 作为另一种将把线性规划的最优解转化成可行解的方法，“点被非常深入 地研究。“一点方法是将工件j 按照在加工到a p ，那个时刻的先后次序进行排序， 然后按照这个次序进行加工的方法。文献 4 3 】利用a 一点提出了离线和在线算法 的一个框架，【4 2 针对单机问题做了详细的研究。 4 4 提出了确定性离线算法更 好的近似比以及相应的具有相同近似比的随机在线算法。a 点概括了以前讨论 的取整方法，并且随机选取a 大小得到的随机算法将单机问题的近似比推进到 e ( e 一1 1 = 1 5 8 。 1 3 6p t a s 算法 近年来，对于一些特定的问题提出了p t a s ( p o l y n o m i a lt i m ea p p r o x i m a t i o n s c h e m e ) 。这些算法可以以任意精度接近最优解，而算法的复杂度也随着精度要 求非线性增加。这些p t a s 在理论上有非常重要的价值。 正如前面提到的，i i i z o w , 问题存在伪多项式算法，计算复杂度为 。( 肷手哆 只要哆有界，那么算法就成了多项式算法了。如果预先知道最 优性能指标矿，通过对原来的权重乘以系数( ) 以后向上取接，得到新的 权僮。再对这个转化后得到的问题进行求解，可以在o ( ”3 ) 的时间范围内计算 出性能指标小于等于( 1 + ) 矿的解。这样，如果能够找出w 的下界矿，使得 利用w 对原问题进行转化以后计算出来的结果小于等于f l + e ) w ，因为 ( 1 + e ) w ( i + e ) w 。，计算出的性能指标也就小于等于( 1 + ) 形。利用两分法， 可以用时间复杂度为o ( 1 0 9 n ) 内找到这样的w 。这样，l l i q 哆问题存在时 i 删o ( n 3 l o g n e ) p t a s ，即可以找到性能指标不大于( 1 + s ) 矿的解， 其中可以任意小。 对于其它一些调度问题，也找到了p t a s 。比如p i lc m 。、1 10i l 。4 6 4 7 1 等。利用比例系数和取整对原问题进行转化是设计p t a s 的重要方法。近年来， 在一类性能指标为q 和q q 的调度问题上找到了p t a s 是调度近似算法理论 中的一个重要突破。 1 3 7 在线算法 上述的研究工作主要集中在知道所有工件信息以后的离线算法。对于有些情 况，工件是随机到达的，算法知道已到达工件的信息，但不知道那些还没有到达 工件的信息，在这种情况下要保证算法的调度结果要满足一定的性能要求，就导 致了在线算法的研究。在线算法的综述请参考文 4 8 1 。 作为一种近似算法，在线算法求出的解通常不是最优解。因为工件是动态到 达的，算法在进行当前决策时并不知道以后的信息，而算法在整个过程结束以后 所得到的调度策略要与最优解进行比较，这就决定了在线算法的设计和分析比离 线算法更加困难。 在线算法的分析手段是建立在离线算法的设计和分析的基础上的。线性规划 方法的研究对在线算法研究有很大的帮助。对于单机调度问题 l ir j ，o n 一h e l ，c ，文 4 9 】提出了d e l a y e d s w p t 算法。利用线性规划方法，可 以得到上述算法的竞争比为2 。 类似地，对于其它的一些调度问题，也存在在线算法。在线算法的研究是车 间调度问题近似算法研究的一个重要领域。 1 3 8具有前瞻的在线算法( 滚动算法) 对将来要到达工件信息的了解程度，很大程度上决定了调度的质量。离线算 法知道所有工件的信息，文 5 0 给出了p t a s 算法，可以以任意的精度逼近最优 解。而在线算法仅仅依靠已经到达的工件信息，不考虑任何将要到达的工件信息。 根据目前的研究结果，确定型在线算法的竞争比最好是2 ，而随机在线算法最好 只能达到：j e l 5 8 。在实际生产过程中，调度算法往往不仅知道已经到达的工 件信息，而且可以利用部分将要到达的工件信息。对于这部分信息的利用应该可 以改善算法调度的质量。 对于不完全信息情况下的控制问题，工! 蚴立程中发展起来的预测控制已给出 了很好的解决方案，它的核心是采用滚动优化控制代替全局最优控制，实践己证 明了这是一种十分有效的控制方法，滚动优化的思想同样也可以应用于信息不完 全情况下的调度问题。文 5 1 】提出了具有前瞻( l o o k a h e a d ) 的在线算法的概念， 它利用将要到达的k 个工件信息设计了算法l k a 进行调度， 5 1 特别分析了一步 前瞻在线算法l 1 a 的竞争比，由于l l a 算法采用只根据下一个要到达的工件信 息对当前的调度进行最优决策，没有考虑到以后可能到达的工件会影响整个调度 结果，所以这个算法的竞争比为0 + 1 ) 3 。这远比 4 9 提出的在线算法差。总的 说来，在调度领域中滚动调度的研究特别是对其性能的分析还刚开始。 本文将预狈4 控制原理应用到车间调度问题中，提出车间调度滚动算法一般描 述。详细研究了单机问题l l c ，和并行机问题p i i c o ，针对这些问题分别提 出了滚动算法。并在算法的性能分析方面给出一些理论结果。 1 4 复杂流水线调度问题 除了将预测控制应用于上述问题意外。本文还研究了复杂流水线调度问题。 复杂流水线调度问题是一个经典的生产调度难题。这些流水线往往具有批处理 机、可重入等特性，大大增加了调度的难度。由于描述整个生产线长期的生产模 型很复杂，对流水线的优化是一个n p h a r d 问题，通过建立一个模型进行求解 几乎是不可能的。一般采用分层的建模方法。对于企业而言，利润是首要的考虑 因素。企业根据订单要求以及