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

华中科技大学硕士学位论文 摘要 成批生产车间作业调度问题( j s s p ) 已被研究了几十年并被证实为n p 完全性问 题。对此类问题的求解是计算机科学技术中的瓶颈任务，由于存在众多约束条件， 使得该问题不存在有效的多项式时间解法，而且一般的算法所花费的时间往往随着 问题规模的增大呈指数增长，因此寻找问题的最优解往往并不现实，许多专家学者 提出了各种近似算法。近似算法能在较短的时间内求出问题的近优解，虽然这个解 不一定是问题的精确解，但已经能够较好的满足我们的需要。 为了得到一个关于车间作业调度问题的好的求解算法，在拟物、拟人思想的指 导下结合现有的算法设计了三个启发式算法，并将抽象的车间作业调度问题转化为 具体的物理模型。借鉴了劳动人民的社会经验和一些启发式规则提出了算法， 算法简单、快速。在算法的基础上，加入分枝定界的思想，提出了求解车间作业 调度问题的改进算法a - ，a l 算法提高了求解的精度，同时也降低了求解的速度。在 综合考虑了前两个算法的优缺点的基础上，提出了禁总搜索算法a 2 ，该算法以a 0 算法的解作为初始解，并提出了较好的邻域结构和搜索策略，a 2 算法兼顾了求解的 速度与精度。 针对以上三个启发式算法，测试了国际上一些瑶名的实例。测试结果素明这i 个算法都其自良好的求解性能。 、。l、 0 关键词；启发式算法；前沿沉底法；当d 茸格局；拟物、拟人法；分枝定界；禁忌搜索 ， 华中科技大学硕士学位论文 a b s t r a c t t h ej o b s h o ps c h e d u l i n g p r o b l e mo s s p ) h a sb e e ns t u d i e df o rd e c a d e sa n dk n o w n a sn pc o m p l e t ep r o b l e mt h a ti sab o t t l e n e c kt a s ki nt h ec o m p u t e rs c i e n c e b e i n gt h e r e s t r i c t i o no fm a n y c o n d i t i o n s ，t h ej s s pd o e s n o te x i s ta l l a l g o r i t h m o fe f f e c t i v e p o l y n o m i a lt i m e t h ec o m p u t i n gt i m eo ft h ea l g o r i t h mf o rs u c hp r o b l e mw i l li n c r e a s e e x p o n e n t i a l l ya l o n gw i t hi n c r e a s i n go fp r o b l e m ss c a l e s oi t i sn oi m p o s s i b l et of i n da p r e c i s i o na l g o r i t h m t ot h ed a y t h e nm a n ye x p e r t sa n ds c h o l a r sh a dr e s e a r c h e dt h i s p r o b l e ma n dh a dp u tf o r w a r ds o m ea p p r o x i m a t ea l g o r i t h m st h a tc a na p p r o x i m a t e l ys o l v e s u c hp r o b l e mi nt h es h o r t p e r i o d o ft i m e t h i ss o l v i n gc a n s a t i s f yo u rd e m a n d s t of i n dag o o da l g o r i t h mf o rt h e j o bs h o ps c h e d u l i n gp r o b l e m ，t h r e eh e u r i s t i c sa r e d e s i g n e dt o g e t h e rw i t he x i d e s t e n ta l g o r i t h mg u i db yt h ei d e a so fp h y s i c a l i f i c a t i o na n d p e r s o n i f i c a t i o n ，a n d a b s t r a c t j o bs h o ps c h e d u l ep r o b l e m i st r a n s f o r m e dt om a t e r i a l p h y s i c a lm o d e l b yu s i n gl a b o rp e o p l e se x p e r i e n c ea n ds o m eh e u r i s t i cr u l e sf o rr e f e r e n c e ， s oa oa l g o r i t h mi s s u g g e s t e d ，w h i c h l m n s s i m p l ya n ds p e e d i l y o n t h eb a s eo fa o a l g o r i t h m ，i d e ao fb r a n c ha n dh o u n di sa d d e di n t oi ts ot h a ti m p r o v i n ga l g o r i t h mn a m e d a 1i s p u tf o r w a r d ，w h i c ha d v a n c et h ep r e c i s i o na n df a l l st h es p e e d t a b o os e a r c h a l g o r i t h ma 3 i ss u g g e s t e d b yi n t e g r a t i n ga 0 a n da i t h i sa l g o r i t h m b e g i n sw i t ht h er e s u l t o fa 1a n dh a v eg o o d n e i g h b o rs t r u c t u r ea n ds e a r c ht a c t i c a l g o r i t h ma 1g i v e sa t t e n t i o nt o b o t ht h es p e e do fr e s o l v i n gp r o b l e ma n dt h ep r e c i s i o no fr e s u l t f o rt e s t i n gt h o s et h r e e h e u r i s t i ca l g o r i t h m s ，af e wf a m o u si n t e r n a t i o n a l e x a m p l e s a r ei n t r o d u c e d t h er e s u l t s i n d i c a t et h a tt h o s et h r e e a l g o r i t h ma l lh a v eg o o dr e s o l v i n gc a p a b i l i t y k e y w o r d ：h e u r i s t i c a l g o r i t h m ；f r o n tl i n ed e p o s i t i n g ；p r e s e n tc o n f i g u r a t i o n ； p h y s i c a l i f i c a t i o na n dp e r s o n i f i c a t i o n ；b r a n c ha n db o u n d ；t a b o o s e a r c h 华中科技大学硕士学位论文 1 1 研究背景及意义 1绪言 人们能够有效的解决许多问题，部分原因在于使用了有效的算法。对于某些知 道算法的问题，很有可能编写出一个低效的算法来“解决”这个问题，对于这些问 题。我们有更好的算法更快的找到答案。但是，实际生活中有许多问题，即使使用 最可能的算法也要花费很长的时间，比如汉诺塔问题。除了解决这些必须花费很长 时间运行的问题以外，还有许多问题，我们根本不知道它们是否存在有效的算法。 如团问题、货郎担问题、电路板布局问题、图着色问题以及背包问题等等。 在近几十年里，人们对这类不知道是否存在有效的算法的问题进行了深入而细 致的研究，并取得到了一个重要的理论成果，即复杂性理论。复杂性理论按照计算 难度把问题分为两类：p 问题和n p 问题。如果问题在常规计算机上使用多项式时 间可以解决，则这类问题称为p 问题。如果问题的算法在一个非确定性机器上以多 项式时间运行，则这样的问题称为n p 问题。 n p 完备性理论研究的就是这类n p 问题。有关n p 完全性问题最奇怪、也最有 吸引力的地方是：如果有人对其中的一个问题找剑了在常规计算机上以多项式时间 运行的算法，那么经过一系列归约，n p 中的所有其它问题也都可以在常规算机 上经过多项式时间得到解决。也就是说如果对其中一个n p 完全性问题找到了多项 式时问算法，就可以对n p 中所有其它问题找到多项式时间算法。因此对任意一个 n p 完全性问题寻找多项式时间解法的努力可以扩展到所有其它的n p 完全性问题 中。 由于在工程技术、军事领域、生产管理、组合优化、交通运输中许多问题都是 n p 完全性问题，它们都具有广泛的应用背景，因此对n p 完全性问题的研究具有极 其重要的理论意义 对于p = n p 是否成立人们花了很长时间来研究。如果p = n p ，就意味着n p 问题 有多项时时间解法。但实际上，目前还没有人能够设计出一个具有多项式时间复杂 性的精确算法来解决这类n p 完全性问题。因此大多数人认为p 并不等于n p 。 华中科技大学硕士学位论文 虽然对任何一个n p 完全性问题，到目前为止还没有找到一个精确的以多项式 时问运行的算法。但这并不意味着，面对这类问题我们完全束手无策，事实上为了 解决n p 完全性问题，有三种方法可以尝试：第一种方法是直接用具有指数时间的 算法来解决问题。n p 完全性问题中的一些问题尽管需要指数运行时间，但增长的 却不是非常快，如背包问题。第二种方法是解决这个问题的一个不太难的特定实例。 例如，图论中的许多问题是n p 完全性问题，但同样的问题应用到具有特定限制的 图中却不是太困难。对于一般图的顶点覆盖问题，其对偶图就有一个多项式时间算 法。第三种方法是寻找求解n p 完全性问题的近似算法，找到问题的一个近似解。 虽然近似算法并不一定能得到最好的解，但多数情况下已经可以满足我们的需要。 本文所要讨论的车间作业调度问题0 s s p ) 就是一个n p 完全性问题i “，该问题是 实现制造系统运筹技术，交通运输及邮电通讯技术，管理技术与组合优化技术发展 的核心。有效的调度方法与优化技术的研究和应用，已成为先进制造技术实践的基 础和关键。而且，随着现代工业的发展，企业的生产正朝着多类型、小批量、有着 不同完工时间和产品要求的方向发展，从而使得企业的生产作业计划安排工作难度 大。为了提高劳动效率，同时也提高经济效益，必须使所有的任务都尽早完成，由 于要考虑到充分利用生产设备，有效缩短生产周期等问题，实际操作过程中难免会 顾此失彼，因此，提出一个好的算法迫在眉睫。 实际上，对此类问题的求解已成为计算机科学技术中的瓶颈任务，由于存在众 多约束条件，使得该问题不存在有效的多项式时间解法，而且一般的算法所花费的 时蚓往往随问题规模的增大呈指数形式增长，即使在问题规模较小时，比如1 0 个工 件、1 0 个机器的调度问题就很难用精确算法得出最优解。从问题产生之日起。广大 的专家学者就一直从事着这一问题的研究，由于寻找问题的最优解往往并不现实， 而实际应用往往并非要求给出问题的最优解，一个好的近似解也能较好的解决问题， 因此对此问题的研究就转化为寻求问题的次优解。 1 2 国内外研究现状 经过近5 0 年的发展。车间作业调度问题的研究方法经历了从简单到复杂，从单 一到多一的过程。近似算法近年来得到了很大的进展，现有调度问题的解决方法大 2 华中科技大学硕士学位论文 体j 二可以分为以下几种类别：基于运筹学( o r ) 的方法，基于启发式规则的方法， 控制理论方法，基于人工智能的方法，基于d e d s 的解极模型方法，基于仿真的方 法，神经网络优化法，基于模糊数学理论的方法，拉氏松弛法，具有计算智能的局 部搜索法，组合调度方法。其中具有计算智能的局部搜索法又可分为：遗传算法 ( g a ) ，演化规划( e p ) ，禁忌搜索( t s ) ，模拟退火( s a ) 四种方法。 事实l 对于车间作业调度问题，所采用的近似算法主要是启发式算法。启发算 法的特点直观、简单、易于实现。虽然只是局部寻优方法，但对生产线优化调度问 题，寻求满足实际需要的近优解或满意解而非精确最优解，是大规模生产线优化调 度问题有应用前景的解决方法，此类算法处于学术前沿的一个非常重要的研究方向。 目前较为流行的是优先权规则调度算法，瓶颈机算法、思维进化算法、具有计算智 能的局部搜索法等等。 g i f f e r 和t h o m p s o n 的算法1 2 j 是优先权规则调度算法的典型代表。早期的近似算 法中，大多数是基于优先权规则的调度，此规则按照某种方法对每一个将有可能被 选取的操作作出相应的评价，将一个数值作为满意度赋予该操作，这样每一个可能 被选取的操作都有一个满意度值，再根据问题的需要选择满意度适宜的操作，这类 算法可以找到较好的近似解。 a d a m s 等人的瓶颈转移启发式算法1 3 j 是目前最有效的启发式算法之一，该算法 社! 多机凋度问题转换为单机调度问题，先找出机器的瓶颈度，优先为瓶颈度最大的 机器进行排序，每当一台新的机器排完序之后，都对那些已经排好序的机器再进行 优化，当所有的机器上的工序加工顺序都确定后，整个调度问题就解决了。由于此 算法对作业调度问题的解决具有很好的参考价值，因而曾被很多人进行了改进【4 i 。 实际上，有关单机调度问题的算法是由c a r l i e r 在1 9 8 2 年首先提出的i “，而瓶颈度 的思想在历史上也早有人提出过1 7 j ，a d a m s 等人提出的这个算法的主要贡献是对原 问题进行了松弛。 基于髓机局部搜索技术的算法其共同的特点是采用某种领域结构，在当前解所 在的领域内寻找新的改善解。此类算法为迭代算法，兼顾了求解的速度与精度，在 合理的时间内寻找尽可能好的满意解和尽可能大的规模。近年来，一些高级局域搜 索法由于具有普遍适用性和较低的经验复杂性等优点，得到了广泛的重视和应用。 华中科技大学硕士学位论文 它们是对传统搜索方法的一种改进，下面简单介绍常用的几种方法。 模拟退火算法( s a ) 【8 】是一种通用、高效、健壮、可行的拟物型随机近似算法， 它采j jm c t r o p o l i s 接受准则，以一组冷却进度表参数控制算法过程。其基本思想是 从给定仞始解开始，使用一产生器和接受准则，不断地把目前结构的解转变为邻 近结构的解。接受准则允许目标函数在有限范围内变坏，它由一控制参数t 决定， 其作用类似于物理过程中的温度t ，对于控制参数t 的每一取值，算法进行的迭代 过程，对应着固体在某一恒定温度下趋于热平衡的过程。并且控制参数的值必须缓 慢衰减，爿胄皂确保模拟退火算法最终趋于组合优化问题的整体最优解。如果要得到 一个高质量的近似解，还需要花很长时间进行退火1 们。s a 能较好地避免局部最优， 但算法的收敛速度很慢，搜索空间过于庞大下降温度难以掌握。这成为进一步应用 的阻力。s a 在随机分析、m a p k o b 理论、渐近收敛性、统计分析方法和并行算法等 学科中都有广泛的应用。 演化规划( e p ) 是本世纪6 0 年代提出的。主要用于数据诊断、模式识别、分类以 及控制系统的设计之中，并取得了良好的效果。后来，d b f o r g e l 借助于演化策略 f e s ) 方法对e p 进行了发展，并用到数值优化和神经网络训练等问题之中i ”j 。 埘遗传算法( g a ) 的研究也非常广泛，g a 是基于“优胜劣汰、适者生存”的 。种高度并行、随机和自适应优化算法。1 9 8 5 年，d a v i s i ”j 首次将遗传算法用于解 决调度问题。近年来，g a 得到了较为广泛和深入的研究【1 3 4 9 1 。它将问题的求解表 小成染色体的适者生存过程，通过染色体群的一代代不断进化，包括复制、交叉和 变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。 g a 原理和操作简单，通用性强，不受限制性条件的约束，且具有隐含并行性和全 局解空i l j j 搜索能力，由于在理论上和经验上被证实能提供在复杂空间中的鲁棒搜索， 在机器学习、模式识别、控制工程、v l s i 设计等领域，在生产调度中的应用也已很 多，g a 的早熟和搜索效率低问题是它的主要缺陷。 禁忌搜索算法1 2 0 1 ( t s ) 也称塔布搜索，是继模拟退火算法和遗传算法之后出现的 义一卜分有效的局部搜索算法。 i s 是为跳出局部最优而设计的一种确定性算法，在 陷入局部最优时做上升移动，它能找到调度问题中一些实例的最优解。但禁忌搜索 算法只有很好的解决了算法的参数后才能表现出良好的搜索效率，这也是大多数能 4 华中科技大学硕士学位论文 够跳离局部最优的算法所普遍存在的一个问题。 我的导师黄文奇教授最早提出了拟物、拟人思想【2 12 2 i 。其工作路径是到大自然 中去寻找智慧，即到物理世界中去寻找出与原始数学问题等价的自然现象，然后观 察其中物质运动的演化规律，从中受到启发以得出形式化的求解算法。可以称这个 工作路径为拟物方法。为此类问题找到合适的物理世界后，然后向人类学习，因为 人类在最近几千年的共同生活中形成了丰富的社会经验，利用这些经验往往可以得 ；好的启发式算法，我们可以将这种把人类的社会经验形式化为算法用以求解某些 特殊困难的数学问题的方式称为拟人途径。用拟物、拟人方法可以找到高效率的实 用算法。黄文奇教授利用这一方法在求解圆形p a c k i n g 问题、正交数组问题、s a t 问题、方格问题、三角形问题等1 2 3 埘】方面做了深入的研究，并取得了很好的成果。 由于各种调度算法都不同程度的存在着这样或那样的优缺点，近年来人们开始 把各种近似算法的组合应用【划研究作为热点，以弥补各自的缺点，发挥各自的优势， 达到高度次优化的目标。虽然对车间调度领域的研究已有几十年的历史，但至今尚 未形成一套系统的方法与理论，并且多数研究的问题规模较小，忽略了很多重要的 因素，建模时对真实环境进行了大量的简化，离应用尚有不少的差距。 1 3 课题的主要研究工作 本课题来源于华中科技大学计算机科学理论研究所的国家9 7 3 重点基础研究开 发规划项目。我们的目标是为车间作业调度问题研制出高效率的、实用的优化求解 算法。 具体的作法是在深入分析车间作业调度问题特性的基础上，讨论利用启发式算 法来求解这类问题。首先本文在拟物、拟人方法的指导下利用前沿沉底法设计了一 个优先权规则调度算法，然后将算法与分枝定界算法结合起来，最后讨论禁 忌搜索算法。即本课题拟进行如下工作： ( 1 ) 对调度问题进行转化，到自然世界中找出与此问题等价的物理模型，提出该 问题所涉及到的定义和定理，并对其进行简要说明。 ( 2 ) 通过总结人类的社会经验找出解决这一问题的拟人方法，从而得出启发式算 法，用该算法测试一些实例，将所得结果与最优解相比较。 华中科技大学硕士学位论文 ( 3 ) 对启发式算法作改进，将分枝定界算法用到该问题中得到改进算法a l ， 用a l 测试一些实例与舢的解作比较。 ( 4 ) 用禁忌搜索算法求解，测试具体的实例并将所获得的结果与前两个算法的结 果相比较。 1 4 本章小结 本章首先讨论了n p 完全性问题以及解决这类问题所要采取的方法，并初步探 寸了一下车间作业调度问题，该问题是一个典型的n p 完全性问题，具有重大的实 际意义。然后介绍了目前国内外探索该问题的一些策略和方法，对一些较为流行的 算法作了比较详细的说明，其中有些结合j s s p 进行了阐述。由于j s s p 是一种很复 杂的n p 完全性问题，人们曾用多种方法对其进行了求解，在这些方法中，有从全 局优化方面着手的，也有近似求解的。随着j s s p 规模的增大，用传统的遍历搜索 寻找最优解是几乎不可能的。由于目前还没有找到能在多项式时间内求解的精确算 法，因此只能采用近似算法来求解问题的近优解。最后对本论文的主要研究工作进 行了介绍。 6 华中科技大学硕士学位论文 2 成批生产车间作业调度问题概述 车间作业调度问题是一个最优化问题，每个最优化问题都包含一组限制条件 ( c o n s t r a i n t ) 和一个优化函数( o p t i m i z a t i o n f u n c t i o n ) ，符合限制条件的问题求解方 案称为可行解( f e a s i b l es o l u t i o n ) ，使优化函数取得最佳值的可行解称为最优解 ( o p t i m a ls o l u t i o n ) ，优化组合问题的目标就是从优化组合问题的可行解集中找到最 优解，此类问题都可用一类数学模型来进行优化。本文所要讨论的j s s p 就具有一 系列的约束条件，是典型的优化组合问题。本章首先介绍j s s p ，然后对此问题进行 分析，并将该问题进行转化，给出具体的物理模型，并对该问题的定义和结论进行 介绍，最后对该问题的可计算性与计算复杂度进行分析。 2 1问题的描述 j s s p 问题的描述如下：设有n 个工件在m 台机器上加工，且加工过程中满足 下面的两个约束条件：1 ) 每一工件的每道工序在m 台机器上的加工顺序及时间已 定，且每一工序在加工过程中不能被打断。2 ) 每一机器每次只能加工一道工序。则 浚问题的目标是如何在上面的条件下使总的加工时间最短。 也即满足以下六项假设条件： ( 1 ) 道工序不能同时在不同的机器上加工，即不能将其分成几部分同时在几台 不同的机器上加工；每道工序只在一台机器上进行。 ( 2 ) 不允许中断，当一道工序一旦开始加工，必须一直进行到完工，不允许中途 停下来，插入其它工序： ( 3 ) 对整个工件来说，在加工过程中采取平行移动方式，即当上一道工序完工后， 立即送下道工序加工： ( 4 ) 工件数、机器数、加工时间己知，且加工时间与加工顺序无关； ( 5 ) 允许工件在工序之间等待，允许机器在工序未到达时闲置； ( 6 ) 每台机器同时只能加工一道工序。 对于j o b s h o p - s c h e d u l i n g 问题我们建立如下数学模型： m i n t n 华中科技大学硕士学位论文 t j - q i d j j ( i j ) f q - “d i ivt i - | j d j i ( i , j ) e e m ，m e m ( 1 ) t i 0 上式中，以n = 0 ，1 ，2 ，n ) 来表示工序的集合( o 和n 表示开始和结束的虚工序) ， m 是所有机器的集合；f 是所有同一个工件的两道相邻工序的集合；e 。是所有可 能在机器m 上加工的两道相邻工序对的集合。t j 是工序i 的开工时刻；d “是工序i 的加工时间；v 的意义为“或”；t 。是最后的完工时间。 2 2 问题的转化 为了形象化此问题，在这里把每一道工序看作宽度相同的木块，木块的长度为 其所对应的工序的加工时间，对每一个工件中的工序按加工的先后顺序把工序所对 应的木块依次从下到上摆好，则每个工件就对应一摞木块，并且木块之间天然的不 会重叠。把每一台机器看成一个有底无顶的篓子，每个篓子的底部都位于同一条数 轴x 轴上，且篓的宽度与木块的宽度相同。 例如3 个工件在3 台机器上加工，总共1 0 道工序，其物理模型如图2 1 所示： 0 图2 1 物理模型示意图 其中每个木块上面的数字表示所要放入的篓号，如j 1 表示先在m 2 ，次在m 1 ， 后在m 3 上加工，图中的数轴表示机器轴。 没木块共有n 个用o i 表示第i 个木块，设木块i 加工时间为d j ，调度之后即 放入篓中后其底高设为t i 。 b臣群un甘n 华中科技大学硕士学位论文 对木块进行编号，如上图所示；每个木块右边的数字就是其编号，得木块的编 号为1 ，2 ，3 ，i i 。在调度中木块应满足如下约束； ( 1 ) 每一摞木块中，若木块i 位于木块j 的下方，则放入相应的篓中后，木块 i 仍位于木块i 的下方，且t i + d i t j 。如工件j l 的第一个木块o l 位于第二个木块 0 2 的下方，则把0 1 放到m 2 中，把0 2 放到m 1 中时，0 2 位于o l 的上方，即o l 的 丌始时间t l 早于0 2 的开始时间t 2 ，且t l + d l t 2 。 ( 2 ) 每个木块在放入相应的篓中时，篓中的木块不能相互重叠。在如上所述的 物理模型中由于木块和篓的宽度相等，所以这一个约束是天然成立的。 此问题即为在满足上述的两个约束条件下把所有的木块都放到相应的篓中，使 得所有的篓中顶最高的那个木块的项高能尽可能小。 2 3 定义和定理 本节对调度问题所涉及到的定义和结论加以说明。 定义2 3 1 工件约束指每一摞木块的加工顺序为从下到上。且木块之间不重叠。 即：对同一摞木块中，若o j 在o i 之上，则t i + d i t j 。 定义2 3 2 机器约束指同一个篓中的木块不重叠。即：对同一个篓中，任给 o 。和o j ，有t i + d i t j vt j + d j t i ，换句话说，除非o i 和0 j 使用不同的篓子，否则 o j 干l jo 。小能同时进行。 定义2 3 3 两个调度不同指的是至少有一个木块在这两个调度中开始加工的 时刻不同。 定义2 3 4 当前格局指在调度的任一时刻，有一部分木块已放入篓中的布局情 况。若没有一个木块放入篓中，则称为初始格局；若所有木块均已放入篓中，则称 为终止格局。 定义2 3 5 前沿集指在某一格局k 下，每一摞木块中位于最下方的一个木块的 集合，记为f k 。 定义2 3 6 沉底法指木块在放入相应的篓中时满足工件约束和机器约束，并把 术块放到它所能放的最低位置上。 定义2 3 7 前沿沉底法指在某一格局下，从前沿集中取一个木块，该木块用沉 9 华中科技大学硕士学位论文 底法放入相应的篓中。 定义2 3 8 木块i 的满意度s l - ( q i * n i 归i ，其中o i 、n i 、d i 分别表示该木块所 属工件的剩余木块( 指还没有调度的木块并包括本木块) 的总长、块数、以及本木 块的长度。 由以上定义及分析可得如下结论： 定理2 3 1 任取一个合法的调度m j ，都存在一个调度m i o 不比m i 差。 证明：任取一个合法的调度m i ，对已放入篓中的每一个木块按底高、篓号 来确定优先级。 其规则为；( 1 ) 底高小的木块优先级最高；( 2 ) 若底高小的不止一个，则篓号小的 木块优先级最高。 由此规则得到每个木块的优先级别。以下对调度m i 进行调整，即对放在篓中的 每个木块做这样的动作：选取优先级别最高的那个木块用沉底法“沉入”篓中，即 术块在满足工件约束和机器约束的条件下把它放到它所能放的最低位置上。重复这 样的动作直到调整完所有的木块。由于在此过程中每个木块只可能往下沉，不可能 往上升，并且都合法，因此得到一个新的调度m j 0 ，则m i o 不比m i 差。得证。 山对调度m i 的调整过程中可知调度m i o 实际上是由前沿沉底法得到的。 定理2 3 2 用前沿沉底法调度一定能得到最优解。 证明：设木块的总个数为n 。在合法的调度中，每一个木块的选取都应满足工 件约束，故木块应从前沿集r 中选取，则一个合法的调度按其木块选取的先后顺序 就对应所有木块的一个合法的全排列。合法的全排列指的是在每一摞木块中，若i 号木块位于j 号木块的上方，则在全排列中i 号木块仍位于j 号木块的右方。且合法 的全排列的个数不会超过n ! 个。现任取一个合法的全排列p i ，下证此全排列p i 所对 应的所有可行解中一定有个最好的解： 任取p j 所对应的一个合法的调度m j ，由定理2 3 1 可知，存在一个调度m 柏不比 m j 差，且m i o 是全排列p i 所对应的最好的调度。 由于合法的全排列个数有限，故在所有的这些调度中一定有一个调度所获得的 解最小，此调度就是所要寻求的最优调度。得证。 由定理2 3 2 可知，在寻求问题的可行解时，可利用前沿沉底法来调度，再辅以 1 0 华中科技大学硕士学位论文 定的启发式规则就可得到一个有效的算法。 2 4 调度问题的可计算性与计算复杂度 车1 1 日j 作业调度问题虽然是n p 完全性问题，但它是可计算的。 现如下证明之： 以图2 1 为例，木块已经编好了号。现进行如下调度：将木块按其编号由从小 到大的顺序依次摆放到相应的篓中，摆放过程中满足工件约束和机器约束，直到所 有的木块都摆放完为止。这个调度是一个合法的调度，即对应一个可行解，因此该 问题是可计算的。 在现实生活中有一些问题需要问题规模的指数时间来解决，比如汉诺塔问题不 可能用少于o ( 2 “) 时间来解决。这与花费o ( n 2 ) 或0 ( 1 n n ) 时间的算法截然不同，因为 这些方程中所有项的指数都是常数，即这些算法的运行时间都是多项式运行时间。 而时间复杂性是判断一个算法效率的主要指标。若将算法按时间复杂度来划分，则 町以分为两类：多项式时间算法和指数时间算法。我们当然希望在多项式时间内解 答问题，指数时间将是无法接受，也无法忍受的，一个多项式时间算法要比一个指 数时阃算法有效的多。而对具有指数复杂性的问题就要努力去寻找一个多项式时间 算法。 对于该车间作业调度问题，其精确算法就具有指数复杂性。下面对其进行说明。 设共有n 个木块，每个木块的长度为整数，设总长度为整数l 。对于第i 个木 块在放入相应篓中时，其底高t j 在区间【o ，l 】上共有l 种可能的取值，即木块i 最多 可有l 种放法。因此，若这n 个木块都放入各自对应的篓中，则这1 1 个木块在篓中 的位置所有可能的组合共有l n ，在这所有可能的组合数中。一定有一个组合对应n 个木块的底高分别为t l ，i 2 ，t n 就是问题的最优解，精确算法就是从这些所有可 能的组合中找到一个这样的组合。因此该算法的时问复杂度为o ( l n ) 。 既然精确性算法存在指数复杂性，因此我们必须寻求多项式时间算法给出问题 的次优解，一个好的次优解也能满足我们的需求，达到解决问题的目的，在此使用 启发式规则。启发式算法具有简单、直观、易于实现、计算复杂度低等优点。虽然 它1 门般不具有全局优化的特点，但在实际中得到了比较广泛的应用。 1 1 华中科技大学硕士学位论文 2 5 本章小结 奉章系统的描述了车间作业调度问题，并进行了较为详细的分析。为了直观的 思考问题，提出了一个等价的物理模型。针对这一具体的物理模型，为了以后工作 的方便，提出了一些基本的概念和定理，并对其进行了说明。最后对车间作业调度 问题的可计算性以及计算复杂度进行了分析，指出了该类问题的精确算法具有指数 复杂性，其时间复杂度为0 ( l n ) ，因此只能努力寻求多项式时间算法，即利用启发 式算法来给出问题的近优解。 华中科技大学硕士学位论文 3 车间作业调度问题的启发式算法 启发式算法是种凭直观和经验来构造的算法。对于一个具体的启发式算法来 说，其设计方法不仅要依赖于问题的具体特征，而且还要依赖于设计者的丰富经验 的积累以及直观的判断。该类算法不仅不能保证所得解的最优性，而且也无法说明 所得解同最优解的近似程度。但启发式算法比较简单，容易构造。一方面对任何一 个n p 问题，我们都可以设计出一个启发式算法。而且很多理论上能够产生最优解 的精确算法在实际计算中所得解可能比启发式算法有更大的误差，并且精确算法的 时间复杂度总是让人望而却步。另一方面启发式算法速度快，能在较短的时间内得 到较好的近似解。对于车间作业调度问题，通常所用的启发式规则有最短加工时间 优先规则( s p t ) 、最大剩余工作量优先规贝i j ( m w k r ) 、剩余操作个数最多优先规则 ( g o p n r ) 、剩余加工时间最长优先规则( u t m p t ) 、以及先来先服务规则( f c f s ) 等。 但单利用此规则来设计算法，效果往往不是很好。本章将介绍由拟物拟人方法所 得的启发式算法，把这些规则结合起来使用。 3 1 初始算法a 0 在拟物拟人思想的指导下向人类学习。劳动人民在实际工作中积累了丰富的经 验，这些经验都是宝贵的社会财富，可谓取之不尽。用之不竭。观察劳动人民在调 度时所常使用的策略，把这些策略总结起来，将一些经验和方法借鉴到我们的问题 当中，就能形成一个好的启发式算法。现将劳动人民在调度过程中常使用的一些方 法总结如下： 首先，在调度问题中，一般会采用一个非常简单的调度策略，即先来先服务。 对那些能够尽早开工的工序，就尽量安排其优先加工。因此，这说明在调度过程中 的任意一个格局k 下，所调度的工序应从前沿集f k 中选取，并且对于开工时间早 的木块赋予的优先权高。如果一个工序能够加工的时间到了还没有安排其加工，就 势必影响其后续工序的开工，使得总的加工时间延长，导致了资源的浪费，机器的 卒闲时间变长。 其次，如果有两个或两个以上的工序，其开始加工时间相等，既面临有多个工 华中科技大学硕士学位论文 序的选择时，在此采用最短处理时间优先的策略。加工时间短的工序由于其占用机 器的时i 训也相应较短，且能较好的填补机器的空闲时间，并且对其它工序的开工影 响不大。如果安排其优先加工，还能促使同在一个工件的其后续工序的开工时间提 前就有可能使得整个调度能尽早完成。在调度时，人们经常还会考察该工序的后 续工序的一些情况，也就是说我们不能只顾眼前，还应具有高瞻远瞩的眼光，对全 局进行把握。显然，如果我们所考虑的工序其后续工序加工时间长，也应赋予较高 的优先权。若该工序能被妥善安排一个开工时间，其后续工序也就能够按期开工， 就不会因该工序的误工而向后推延。同时，如果该工序的后续工序包括本工序的总 的个数比较多，这也说明了该工序的恰当处理是十分关键的，该工序的开工应予以 高度重视。这就是所谓的最大剩余工作量优先规则。按照这些策略，给工序i 赋予 一个优先权值，即为木块i 的满意度s j ，s j 最大的就优先加工。 再次，若满意度值s i 相等的不止一个工序，那采用的策略就更简单，就从这些 n j 选l ：序中任意选择一个工序，安排其加工，比如说按工序所在的工件号小的优先 进行处理。 最后，在调度问题中，一般会避免连续两次调度同一个工件的两道工序，这样 做能够使得每个工件的加工比较均衡。 由以上调度策略就得到本文的启发式算法：在调度的任一时刻，即格局k 下， 每个木块都从前沿集f k 中选取，且连续两次调度的木块不属于同一个工件。设t i 表示第i 个木块用沉底法放入相应篓中时得到的底高，s i 表示第i 个木块的满意度， j “表示第i 个木块所在的工件号。 对于某个格局k 下的每个前沿木块，可以用如下三元组来确定优先级： t i ，s 。，圯 这样一个三元有序数组所确定的优先级为： ( 1 ) t j 为第一优先级，其值小的优先级最高； ( 2 ) 若t i 最小的不止一个，则考虑s i 的值，其值大的优先级最高； ( 3 ) 若s i 最大的也不止一个，则考虑j h 的值，其值小的优先级最高。 由以上分析可知：a 0 算法的流程是从初始格局开始，优先调度每一个格局之下 的前沿集中的优先级别最高的那一个木块，直到调度完所有的木块，到达终止格局， 1 4 华中科技大学硕士学位论文 得到总的调度时l 刚，从而得到一个可行解。 3 2 算法a o 的实验结果 算法经过了编程实验测试。由于b e n c h m a r k 问题的研究有助于有效和公平 地比较算法的优化性能，因此我们所选取的算例均来自这些b e n c h m a r k 问题。其 中算例f 1 0 6 ，f t l 0 ，f 1 2 0 是由f i s h e r 和t h o m p s o n 于1 9 6 3 年提供的3 个著名的难题l ”j ， 算例l a 0 1 1 a 3 0 是由l a w r e n c e 于1 9 8 4 年提供的一批不同规模和难度的典型问题1 3 “ 算例o r b 0 1 o r b 0 5 是由a p p l e g a t e 和c o o l 于1 9 9 1 年提供1 3 3 j 。测试平台为：c p u 赛 扬5 3 3 m ，内存9 6 m ，操作系统w i n 2 0 0 0 。程序由c + + 语言编制实现。其实验结果 如表3 1 所示。 其中打星号的解表示达到了最优解。表3 1 将a 0 算法所到的结果与最优解作了 比较，从表中可以看出，当问题的规模较小时，计算结果接近于最优方案，并且有 8 个结果就是最优方案，而且算法所需的时间相当短，可以忽略不计，这一结果对 f个单纯的优先权规则算法来说是很好的。在这些算例中1 0 1 0 的难度比较大， 各种启发式算法都在求解这类规模的问题时遇到了困难，但算法所测试的结果比 起其他优先权规则算法来说还是比较理想的。当然a 0 算法的缺点是显而易见的， 随着问题规模的增大，算法的结果与最优方案相差也就越来越大，性能指标也变得 越来越差，但是这一缺点正是普遍存在于众多启发式算法中的，如何改进启发式算 法，使得算法的各项指标都能得到优化，有待于进一步的探讨。基于这一缺点，对 该算法应进行改进，以期求的更好的解。 3 3 本章小结 本章介绍了在拟物拟人思想指导下所提出的启发式算法a 0 。该算法吸收了几 千年求人类所积累下来的社会经验，同时还借鉴了启发式算法中通常会利用的一些 规则。通过这些经验和规则得出了一个比较有效的启发式算法，用算法计算了国 际上= 公开的一些算例。测试的结果显示了该算法的速度非常快，并且有八个算例得 到了最优解。但a 0 算法的不稳定性导致随着算例规模的增大所获得的解不是很理 想，因此有待于进一步的探讨。 华中科技大学硕士学位论文 4 车间作业调度问题的改进算法 a o 算法具有运行时间短的优点，同时又有对较大规模的实例所得到的方案有不 尽人意的地方。本章将引进分枝定界法对该算法进一步加以改进。分枝定界法是建 立在对搜索空间连续划分的思想上的，首先必须要知道任意特定解的代价的上界( 或 者下界) 。如果已经有一个解，其代价是c 个单位，并且知道下一个将要尝试的解的 代价有一个下界比c 大，而且求得是极小值，那么只需要忽略它，而不必去计算这 个将要尝试的解有多糟糕，然后去尝试另一个可能解。分枝定界法在货箱装船问题、 背包问题、货郎擐问题、旅行商问题、电路板排列问题等中有广泛的应用。 4 1分枝定界法概述 寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个， 在检查完所有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际 应用中，很少使用这种方式，因为候选解的数量通常都非常大，即使采用最快的计 算机也只能解决规模很小的问题。本文所讨论的j s s p 就是这种类型的问题。对候 选解进行系统检查的方法有多种，其中回溯和分枝定界是比较常用的两种方法。按 照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少。事实上， 这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结 束时可以找到所需的解。因此，这些方法通常用来求解规模很大的问题。 分枝定界法和回溯都是一种系统的搜索问题解空间的方法，两者的主要区别在 j 搜索解空间的方法和对e 节点的扩充方式不同。回溯法是使用深度优先方法搜索 解空l 训，在搜索时，开始节点既是一个活节点又是一个e 节点( e x p a n s i o nn o d e ) 。从 e 节点可移动到一个新节点。如果能从当前的e 节点移到一个新节点，那么这个新 节点将变成一个活节点和新的e - 节点，旧的e 节点仍是一个活节点。如果不能移到 一个新节点，当前的e 节点就“死了”，不再是一个活节点，那么便只能返回到最 近被考察的活节点( 回溯) ，这个活节点便成了新的e 节点。 分枝定界法一般使用宽度优先或最小耗费方法来搜索。每个活节点有且仅有一 次机会变成e 节点。当一个节点变为e 节点时，则生成从该节点移动一步即可到达 1 7 华中科技大学硕士学位论文 的所有新节点。在生成的节点中，抛弃那些不可能导出( 最优) 可行解的节点，其 余节点加入活节点表，然后从表中选择一个活节点作为下一个e - 节点。从活节点表 中耿出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。 分枝定界法中有两种常用的方法可用来选择下一个e 一节点： ( 1 ) 先进先出( f i f o ) ，即从活节点表中取出节点的顺序与加入节点的顺序相同， 凶此活节点表的性质与队列相同。 ( 2 ) 最小耗费或最大收益法，在这种模式中，每个节点都有一个对应的耗费或 收益。如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个e - 节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，则可用最 大堆来构造活节点表，下一个e 节点是具有最大收益的活节点。 4 2 改进算法a 1 由以上所述，分枝定界算法可以通过扩充e 节点即分枝来增加搜索范围，同时 也可以通过删除活节点即剪枝来提高搜索的效率。因此，在分枝定界算法中我们必 须明确的是e 节点的扩充方