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

华中科技大学硕士擎位论文 揍鬟 车问侔泣调度闻题燕一种缀难静缀合优识翊题，它属于n p 宠全阕题彳崮予它 固有的计算复杂性，几乎无法用经典的方法找到其墩优解。以往，许多专家学者曾 对该问题进行过研究，并提出了多种优化和j 黩似算法。但当问题的规模较大时，优 证算法熬挫缝表现褥劳不理想，嚣近似舞法镰往求鼹速度抉，显绣褥到豹续暴瞧蒡 不太坏，在许多情况下使用它们是较为合理的，一般能够满足用户的需骚，故人们 大多采用近似算法对其求解。偿随着计算速度的急蒯增加锨及调度效率的提高，得 到一擎| i 更好的调度冀法傻交愿卡分重要0 为了得到令好的求鳄舞法，人们缝往将 生物遗传、模拟退火、禁忌搜索、拟物拟人苓算法相互结龠在一起，构成混合算法 对其求解，取褥了较驽翡缩栗。 錾于混含算法的思想，采用拟物拟人算法的策略，将抽象的审问作业调度问题 形象化，提出了前沿沉底法，并在前沿沉底法的基础上，提出了种求解车闯作业 调度阏题弱初始算法积基予拐娥葵法的改进算法。将翅始冀法与局部搜索能力极强 的禁惫搜索算法相结合，得到了一种混合算法。用初始算法、改进算法以及混合算 法分荆对车闷作监调度阕惩进程了求辩，逶避对计髯维系静魄较襁分耩说鞠，复合 算法是赢效实用的，在求解性能与运辣效率方面比单纯的初始算法要好得多。 关键淫：n p 难藏躲；搀犍调度；鳃会鼗纯；禁忌搜索；瘫发式规戴；蔫澄淀嶷法； 拟物拟人方法；模拟退火 华中科技大学硕士学位论文 a b s t r a c t t h e j o bs h o ps c h e d u l i n gp r o b l e m i so n eo f v e r yh 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 n p r o b l e m s ，w h i c hb e l o n g s t on o n d e t e r m i n i s t i cp o l y n o m i a lc o m p l e t e p r o b l e m s i ti su s u a l l y h a r dt oa c h i e v et h eo p t i m a ls o l u t i o nw i t hc l a s s i c a lm e t h o d sd u et oi t sh i g hc o m p u t a t i o n a l c o m p l e x i t y i nt h ep a s t ，m a n ye x p e r t sa n d s c h o l a r sh a dr e s e a r c h e dt h i sp r o b l e ma n dh a d p u t f o r w a r ds o m eo p t i m u mo r a p p r o x i m a t ea l g o r i t h m s b u t ，w h e n t h es c a l eo ft h i s p r o b l e mb e c o m e sl a r g e ra n dl a r g e r , o p t i m u ma l g o r i t h m sa r en o tv e r ye f f i c i e n t t h e ns o m e p e o p l ep r e f e rt os i e v e t h i sp r o b l e mw i t l la p p r o x i m a t e a l g o r i t h m s w h i c ha r eu s u a l l yv e r y f a s ta n dt h e c o m p u t i n gr e s u l t s a r en o tv e r yp o o r u n d e rm u c hc i r c u m s t a n c e s ，i ti s r e a s o n a b l ea n dc a nm a k eu s e r sn e e d s w i t ht h er a p i di n c r e a s eo fc o m p u t i n gs p e e da n d e f f i c i e n c y , i ti sv e r yi m p o r t a n t t og e tab e t t e rs c h e d u l i n gm e t h o d t of i n dag o o d a l g o r i t h m f o rt h ej o bs h o ps c h e d u l i n gp r o b l e m ，g e n e t i ca l g o r i t h mo rs i m u l a t e da n n e a l i n go rt a b o o s e a r c ho r p h y s i c a l m c a t i o n a n d p e r s o n i f i c a t i o na l g o r i t h m i s i n t e g r a t e d w i t he a c h o t h e r t h e s ec o m p l e xa l g o r i t h m sa r ev e r ye f f i c i e n ti n s o l v i n gt h ej o bs h o ps c h e d u l i n g p r o b l e m a n d g o o d r e s u l t sa r eo f t e na c h i e v e d a d o p tt h et h o u g h to fc o m p l e xa l g o r i t h m s ，t h ej o bs h o ps c h e d u l i n gp r o b l e mi s p h y s i c a l i f i e db yt h ep 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 ns t r a t e g ya n daf r o n t i e r l o w e s t m e t h o di sp r o p o s e d u n d e rt h eg u i d a n c eo ft h ef r o n t i e r - l o w e s tr u l e ，ab a s ea l g o r i t h ma n d ar e p a i r e da l g o r i t h ma r ep r e s e n t e d b yi n t e g r a t i n gt h eb a s ea l g o r i t h mw i t ht a b o os e a r c h a l g o r i t h m ，ac o m p l e xa l g o r i t h mi sg o h e n t h ej o bs h o ps c h e d u l i n gp r o b l e mi ss o l v e db y t h e s ea l g o r i t h m s t h et e s tr e s u l t si n d i c a t et h a tt h ec o m p l e xa l g o r i t h mi sb e t t e rt h a nt h e b a s ea l g o r i t h m ，f o ri ti sa p p l i c a b l ea n de f f e c t i v ea n dh a sg o o d c o m p u t i n gp e r f o r m a n c ea n d h i g hs e a r c h i n ge f f i c i e n c y k e yw o r d s ：n p - h a r dp r o b l e m ；j o bs h o ps c h e d u l i n g ；c o m b i n a t o r i a lo p t i m i z a t i o n ；t a b o o s e a r c h ；h e u r i s t i c s ；f r o n t i e r - l o w e s t ；p h y s i e a l i f i c a t i o n a n d p e r s o n i f i c a t i o n ； s i m u l a t e da n n e a l i n g n 华中科技大学硕士学位论文 1 1 研究背景及意义 1 绪论 n p 难问题足当代数理逻辑和理论计算机科学的第一问题，许多专家学者曾对它 进行过认真深入的研究，但始终没有解决它1 1 ，“。在国内，象中国的航空航天大学、 山东大学、国家智能计算机开发中心、中国科技大学、清华大学等部门都从事过这 方面有价值的研究，各有特色。在国外，以美国a t & t 公司的贝尔实验室，俄勒冈 大学以及加拿大的c a l g a r y 大学等单位的研究最为先进。实际上，在求解n p 难问题 的实用快速算法的研究方面，我国处于国际领先水平。 n p 问题是所有可在多项式时间内用不确定算法求解的判定问题的集合，即如果 实现某问题的算法能在一个不确定性机器上以多项式时间运行，则这样的问题就称 为n p 问题。p 问题则是所有可以在多项式时间内用确定算法求解的判定问题的集合， 即如果某一问题在常规计算机上使用多项式时问可以解决，则这类问题就称为p 问 题。刈j 二某些n p 问题，若知道其存在有效的非确定性算法，但不知道它是否存在有 效的确定性算法，且不能证明这些问题中的任何一个问题不存在有效的确定性算法， 则这类问题称为n p 完全性问题。对于n p 完全性问题，如果有人对其中的一个问题 找到了能在常规计算机上以多项式时间运行的算法，那么经过一系列的归约，n p 中 的所有其它问题也都可以在常规计算机上经过多项式时间得到解决，即如果对于任 何个n p 完全性问题找到了一个能在多项式时问内求解的算法，则可以对所有这些 问题找到能在多项式时问内求解的算法。但至今为止，还没有谁能找到这样一个算 法，敞寻求在多项式时间内求解n p 完全问题的近似算法足目前解决此类问题的主要 再 嵌。 我所在的计算机科学理论研究所对n p 难问题拟物方法的研究已持续了2 1 年， 川这种途径求解n p 难问题，在国际上最早由我所提出，现在美国、英国已有人追随。 这说明本文研究n p 难问题已有了充分的经验背景。对有关纯粹数学问题“p = ? n p ” 华中科技大学硕士学位论文 的研究，我所有多年的经验，且在名称为“p = ? n p 问题初步研究”的项目方面取得 了很好的成果。这说明本文研究n p 难问题已有了充分的理论基础。 实践证明在工程技术、军事、工商管理、交通运输及自然科学研究中的六千余 个问题都足n p 难问题。寻找求解n p 难问题的快速算法，不仅在理论研究上，而且 在多方面的应用领域中都有极其重要的意义。 过去，由于n p 难问题解得太慢，工程技术部门遇到n p 难问题就降低要求绕着 弯子避开了，甚至使该项技术都被放弃了。有了n p 难问题的快速求解算法后，相应 的求解软件就会被有关部门作为关键部件加以引用。如：军事部门，用以支撑军事 推理数据库；计算机研制部门。用以支撑生产设计计算机的辅助设计；通讯设备研 制部门，j t j 以支撑电话交换系统的自动化；计算机软件公司，用以支撑软件自动开 发；某些纯粹理论研究部门，用以作为辅助逻辑推理等等。 本文所要讨沦的车问作业调度问题是一个典型的n p 完全问题。由于该问题固有 的计算复杂性，求其最优解的计算量往往随问题的规模呈现指数型增长，就算使用 再高速的计算机都要耗费大量的时问，甚至根本无法实现，故对其寻找高效可行的 近似算法有着重要的实际意义和理论价值。 1 2 国内外研究概况 n p 难问题是计算机科学理论领域里的一大难题，当今国际上解决n p 难问题较 为流行的方法有生物遗传法、模拟退火法、禁忌搜索法和神经网络法等算法。 遗传算法( g e n e t i ca l g o r i t h m s ，6 a ) 是近几年来兴起的一种随机优化技术，它属 于全局优化算法。g a 算法通过模拟生物界的自然进化过程，在大批潜在解中搜索解 空间，每次迭代都充分利用原有优良解中已积累起来的知识，计算收敛迅速稳定， 现已在众多理论和应用学科中得到了广泛应用。 模拟退火算法( s i m u l a t e d a n n e a l i n g a l g o r i t h m s ，s a ) 是1 9 8 2 年k i r k p a t r i c k 等人 将金属热m l l u | j 的退火工艺的思想应用于组合优化问题领域而提出的一种新的搜索 技术。s a 算法采川m e t r o p o l i s 接受准则，以组冷却进度表参数控制算法过程，可 以在多项式时问内找到近似最优解。s a 算法是针对局部搜索算法( l o c a l s e a r c h 华中科技大学硕士学位论文 a l g o r i t h m ) 改进而提出的，它是一种通用、高效、健壮、可行的拟物型随机近似算法。 s a 算法可以较容易地并行实现，适合于求解时i 刊随问题规模呈指数级增长的组合优 化类问题，因此具有很大的实用价值。 禁忌搜索算；法( t a b o os e a r c ha l g o r i t h m s ，t s l 是一种有效的求得全局最优解的启 发式搜索算法，最早由g l o v e r 于1 9 8 6 年提出，它是克服局部最优的一种策略，在国 际i ：已成功地应用于资源规划、通讯、超大规模集成电路设计、运输以及图论、神 经删络等领域。t s 算法是继模拟退火算法和遗传算法之后出现的又一十分有效的局 部搜索算法。模拟退火算法、生物遗传算法、禁忌搜索算法和人工神经网络并称为 四大现代启发式算法。t s 算法与模拟退火一样也是一种“爬山”算法，前者模拟固 体退火，而后者模拟一种智力过程。t s 算法已在许多组合优化领域中显示出强大的 寻优能力，并以其较高的求解质量和效率得到人们越来越多的青睐。t s 算法是一种 在全局逐步寻优的优化算法，它通过一个灵活的记忆近期操作的存贮结构和藐视准 则达到搜索解空阳j 的目的。对于一些较为复杂困难的问题，这一方法显示出极强的 寻优能力，出此法得到的解甚至超过了以往得到的最好解。已经有人将t s 算法运用 剑车问作业调度及其相关的问题之中，取得了较为满意的结果。 在求解n p 难问题方面，本文提出了拟物拟人方法( p 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 na l g o r i t h m ) 。拟物拟人方法基本不同于以上所提及的这些算法，但效 率比以上算法都要高，这是由于拟物拟人方法有针对性地为具体问题找到了非常贴 切的物理世界，而不是象在模拟退火、遗传、神经网络等算法中那样依赖于一个始 终不变的因而往往是不太贴切的物理关系阳】。 车问作业调度问题( j o bs h o ps c h e d u l i n g ，j s s ) t 5 】是一种特殊困难的组合优化问 题，它足n p 完全问题1 6 1 ，即使在规模较少时，也很难求出其最优解。从问题产生之 | i l 起，广大的专家学者就直从事着这一问题的研究，并提出了各种优化算法( 精 确算法) 和逼近算法( 近似算法) 1 7 1 。优化算法主要基于分枝定界方法；逼近算法主 要为迭代算法。尽管优化算法有不少改进，但其费时的缺点仍无法克服，对于j s s 问题的规模一般局限在1 0 0 个操作上下，并且算法的实现还需要相当的技巧。近二 f 以米，近似算法得到很大的发展。此类算法兼顾求解j s s 问题的速度和精度， 在合理的i l q 问内寻找尽可能好的满意解和处理尽可能大的规模。近似算法的求解策 华中科技大学硕士学位论文 略通常有：优先权调度、瓶颈资源平移、几何策略、工件插入、局部邻域搜索、模 拟退火、禁忌搜索、生物遗传、拟物拟人策略等。在这些策略中，有些是构造性的， 生成一个j s s 的调度表；有些是迭代性的，用于改进调度表的性能。当然，如果单 地使用这些算法，往往难以得出较好的结果。通常的作法是，将其中的一种方法 与另外一利，或多种方法相结合来求解j s s 问题，这样可以相互弥补彼此的缺点，发 挥各自的长处。 长期以来，j s s 问题研究的方法始终以启发式算法为主导，相关的一些研究工作 也都是围绕着启发式算法进行，尽管这样的研究取得了一定的效果，但是却存在着 难以克服的弱点，如计算规模不可能扩大、寻优结果不具备全局特性等等。后来有 学者提出了基于遗传或模拟退火等算法的车间作业调度算法，其运算效果比单纯的 常规启发式算法好多了。如：遗传算法不依赖于问题的具体形式，具有很高的稳健 性，对求解诸如j s s 这类问题具有较为显著的优势。但遗传算法较高的稳健性却导 致了其较低的运算效率。当j s s 问题规模较大时，便会存在计算速度慢与结构参数 难以确定的弱点。降低了其搜索效率，而在很多情况下，运算效率对于一个算法来 说又往往是很重要的1 8 】0 故可以将遗传算法与启发式方法相结合，利用遗传算法改进 启发式算法求解的性能，同时利用启发式规则引导遗传算法的搜索过程，以提高其 求解效率h 。 1 3 课题主要研究工作 本课题要解决的问题是“车间作业调度问题”，即若干个工件要在若干台机器上 以尽可能短的时间加工完，但要受两个条件的限制，即：每个工件不能同时被两台 机器加工；每台机器每次只能加工一个工件。 本文制订的目标是，为车间作业调度问题研制出当今国际领先水平的、效率极 高的、实用的近似求解算法，并且为所得算法作出执行软件。 具体的作法是，先对当今国际上流行的一些关于j s s 问题的算法进行研究、测 试和分析，并总结其实现规律和技巧，找出其可取之处。进而基于拟物拟人方法提 出一些自己的启发式算法，并对这些算法进行测试和分析，以便找到一个好的基本 4 华中科技大学硕士学位论文 算法。有了一个好的基本算法之后，便在此算法的基础上进行迭代、回溯或将此算 法与其它诸如模拟退火、禁忌搜索等算法相结合，最终得到一个较优的关于j s s 问 题的求解算法。具体说来，我进行的研究工作主要有以下几个方面： 1 ) 利用实物模型，将抽象复杂的问题形象化和具体化，加深对问题的理解与分 析。 2 ) 在实物模型的基础上，抽象出j s s 问题的数学模型，进而基于数学模型和拟 物拟人思想提出求解此问题的一些基本算法，并对其进行测试，找到一个较好的基 本算法a o 。 3 ) 在基本算法a 0 的基础上，利用禁忌搜索算法对j s s 问题进行求解，并将结 果与同类算法进行比较和分析。 华中科技大学硕士学位论文 2 车间作业调度问题综述 本章首先给出了需要解决的车间作业调度问题，并对其进行了数学及网络图形式 的描述，接着针对此问题作了几点假设，并给出了它的数学模型，最后阐述了此问 题的可计算性和计算复杂性等相关性质。 2 1 问题描述 车问作业调度h i 题( j o bs h o ps c h e d u l i n gp r o b l e m ，j s s ) ，即是如何使n 个工件在m 台机器上以尽可能短的时间加工完的问题，其中要受到以下两个条件的制约： 1 ) 每个工件必须在它所指定的机器上加工，且不能同时被多台机器加工； 2 ) 每台机器每次只能加工一个工件。 在一台机器上加工某一个工件称为一个操作( o p e r a t i o n ) ( 或一道工序) ，每个操 作的时问是一定的且不能被中断。加工完所有的工件所花的时间最小是解决此问题 婴达到的目标。 令n = 1 ，2 ，n ) 为操作集，m 为机器集，a 为成对的操作集，这些成对的操作受 以上第一个条件的限制；e k 为在机器k 上完成的操作，受第二个条件限制，故不能 在时问上交叠；又令d i 为固定的加工时问，且t i 为操作i 的开始时间。这样上述问题 的数学表述形式为【5 1 ： m i n t n q t i d i ，( i j ) a t i 0 i n t r t i d i v t i t j d i ( i j ) e k ，k m ( p ) 问题( p ) 的任何一个可行解都称作一种调度。 为了后面几章算法实现的需要，下面介绍一下j s s 问题的网络图实现形式1 5 , 1 0 】。 令g = ( n ，a ，e ) 。其中n = 0 ，1 2 ，n ) 为结点集合，对应操作集合；a 为实线弧， 6 华中科技大学硕士学位论文 对应工序的优先关系；e 为虚线弧，对应同一台机器上进行的工序对。弧上的数字表 示对应的工序所花的时间。虚线弧被分成了几个集团e k ，e = u ( e k ，k m ) ，每个集团 对应一台机器。将g 中的所有虚线弧去掉可以得到图d ，即d = ( n ，a ) 。集团e k 中的 一个选择s x 就是在e k 的成对弧中只取定一条。如果一个选择没有图内的循环，那么 陔选择就是非循环的。每一个非循环的选择s k 对应机器k 上的一个排序，反之亦然。 因此对机器k 上的工件进行排序，就是在e k 中选择出一个非循环的选择。一个完全 选择s 由所有的选择s k 组成。用一个完全选择代替原来的集合e ，可得到图d 。= ( n ，a u s ) 。每一非循环的完全选择定义了一个排序，而对应于这一排序的总的加工周期 等于d 。中最长路径的长度。故若用图的语言来描述的话，j s s 调度问题就是寻找一 个非循环的完全选择s e ，使在图d 。中的最长路径尽可能小。其中这条最长的路径 称为关键路径。 ( 工件1 ) ( 工件2 ) ( 机器1 ) ( 机器2 ) ( 机器3 ) 图2 1j s s 问题示例图 在图2 1 中共有三个工件，三台机器，每个工件有三道工序。每个矩形块代表工 件的一道工序，每个矩形块的左边数字表示工序的编号，中间带圆圈的数字表示机 器号，右边数字表示完成此道工序所要花费的最短时问。 其中：i ：件1 的第一道工序要在机器2 上完成，耗时2 个单位；第二道工序要在机 器3 ，j ：完成，耗时1 个单位；第三道工序要在机器1 上完成，耗时3 个单位。 工件2 的第一道工序在机器1 上完成，耗时3 个单位；第二道工序在机器2 上完 成，耗时2 个单位；第三道工序在机器3 上完成，耗时2 个单位。 华中科技大学硕士学位论文 工件3 的第一道工序在机器2 上完成，耗时1 个单位；第二道工序在机器1 上完 成，耗时2 个单位；第三道工序在机器3 上完成，耗时1 个单位。 将图2 1 表示成网络图的形式，如图2 2 所示： 缓 图2 2j s s 问题网络图 在图2 2 中，结点0 与结点1 0 分别表示开工与结束时间点。结点表示工 件1 的三道加工工序；结点表示工件2 的三道加工工序；结点表示工 件3 的三道加工工序；同一工件上的几道工序用实线弧相连。结点之间用双 向虚线弧相连，表示这三道工序将要在同一台机器即机器2 上完成；同理，结点 之问用双向虚线弧相连，表示这三道工序将要在同一台机器即机器1 上完成； 结点之间用双向虚线弧相连，表示这三道工序将要在同一机器即机器3 上完 成。结点指向其它结点的所有有向线段( 实线或虚线) 上所标注的数字均为2 ，表 示工序1 的加工时间为2 ，也就是说，要完成工序1 ，至少要耗时2 个时间单位。其 - | 结点指向结点的单向实线弧表示只有在完成工序1 之后才能完成工序2 ，结点 与结点之问有双向的虚线段，表示可以先花2 个时间单位完成工序1 之后再完 成工序5 ，也可以先花2 个时间单位完成工序5 之后，再完成工序1 。其它实线段与 虚线段表示的意思相类似。在图2 2 中，由结点o 一一一一结点1 0 的单向弧 构成了一条关键路径，其长度为8 。 2 2 关于车间作业调度问题的几个假设 1 ) 每种工件包含若干个操作，这些操作的数目是以正整数为单位的，且每个操 作所耗费的时间数也是以正整数为单位的，操作是工件在机器上加工的最小 华中科技大学硕士学位论文 工作单位。 2 1 每台机器可以加：i = 多种类型的工件，但同时只能加工一个工件，且机器在加 工过程中不能被其它工件优先占用。 3 ) 每个工件的任意一个操作只能在它所对应的机器上完成，且同一工件的任意 两个操作不能在同一台机器上连续进行。 4 1 工件在加工过程中主要考虑工件在机器上的加工时间以及工作受所给条件约 束时的等待时问，忽略其它因素的影响( 如：机器丌机、关机，取放工件等 时问以及机器出现故障等因素) 。 5 1 允许机器存在空闲时间，工件存在等待时间，但对于某一道工序在加工过程 中不能存在中断，一旦开始就加工至完成为止。 2 3 车间作业调度问题的数学模型 1 ) 设j 代表n 个工件的集合，则有j = 仙，j 2 ，j i ，j 。) ( 1 i n ) 。其中工件j i 的操作 2 ) 设m 代表m 台机器的集合，则有m = m 1 ，m 2 ，m j ，m 。 ( 1 j m ) 。其中机器 m j 上的工序数为l j ( 1 j m ) 。它0 3 , z 0 1 , 2 剖0 3 , k 其中o i j 为工件i 的第j 道工序( 1 i n ，1 j m ) ，k = m a x ( k l ，k 2 ，k 。) 。 4 1 设m o 表示所有机器的工序排列，则m o 可以表示为： 瑚= 【芝0 z , 1 薯0 m , 2 引0 x , 1 其小0 j 表示机器i 的第j 道工序( 1 i m ，1 j 1 ) ，l = m a x ( 1 l 1 2 ，l d 。 华中科技大学硕士学位论文 j s s 问题的数学模型定义： 设j 为工件集合，m 为机器集合，m o 为机器加工工序排列阵。如果对于一个 给定的机器工序排列j m o ，满足f ( j m o ) = m i n f ( j m ) ，即j m o 使目标函数f ( j 9 取值最 小，且满足工件、机器的约束关系，则称j m o 为j s s 问题的最优解，而称求解j m o 的过程为车间作业调度【8 1 。 工件、机器、操作的c 语言结构可描述如下； s t r u c to p e r a t i o n i n tm n o ；+ 操作所在的机器号 i n tj n o ；- 操作所在的工件号 i n tt a l l ；4 操作的耗时+ i n tn o ；+ 操作在对应的工件中的编号+ ) s t r u c tm a c h i n e ，机器结构 i n tn o ；+ 机器编号+ i n tt a l l ；+ 预定的机器的最后完工时间+ i n tn u m ；机器上的已加工的操作总数 m _ o p e r a t i o no p o p ；尸o p 结构数组的最大值为机器的r u m + s t r u c tm _ o p e r a t i o n i n ts t a r t ；+ 每台机器上加工过的操作的开始时间， i n te n d ；+ 每台机器上加工过的操作的结束时间+ i n tn o ；+ 工件上的操作的统一编号+ ) 1 0 华中科技大学硕士学位论文 s t r u c tj o b i n tn o ；+ 工件编号+ i n tp n u m ；p 记录工件上的操作总数+ i n tn u m ；+ 汜录工件上剩余的操作数+ i n tp n o j j o p ；+ 工件上操作的编号( 不是总的统一的编号) + ) 2 4 车间作业调度问题的可计算性和计算复杂性 按时问复杂度一般可将算法分为多项式时间算法和指数时间算法两类，其中多 项式时间算法是指存在某个以输入长度n 为变量的多项式函数f ( n ) ，使其时间复杂性 函数为0 ( “n ) ) 的算法：指数时间算法是指对任何时间复杂性函数都不可能用多项式 函数取界定的算法。一个多项式时间算法显然要比一个指数时间算法有效，对具有 指数复杂性的问题，人们一般是尽量去寻找一个多项式时间算法来求其次优解。车 间作业调度问题的精确算法就具有指数复杂性，下面对其详细阐述： 对于m 台机器，n 个工件的j s s 问题，若每台机器上要完成的工序为n ，则此问 题的解实际上是每台机器上各工件加工顺序的排列1 1 l l ，可表示如下： m l ：o n ，0 1 2 ，0 1 3 ，o l n m 2 ：0 2 1 ，0 2 2 ，0 2 3 ，0 2 n m m ：0 m 1 ，0 m 2 ，0 m 3 ，0 m n 其中o i j 为机器m i 上的第j 道工序，o i j e ； j l j 2 ，j 。 ；m i 表示机器i ；j j 表示工 件j 。由于每台机器完成n 个工序的分配方案有n ! 种，m 台机器的总的分配方案就有 ( n ! ) “种，这样，上述问题的解空间规模就为( n ! ) ，即所有的可行解和不可行解共有 ( n ! ) “个。在这( n ! ) 。个解中，一定存在最优解。事实上，在这( n ! ) “个解( 即分配方案) 中，那种分配方案使所有的工件加工完后最终所花的时间最短，那种分配方案就是 最优解。当然这种最优解可能有一个或多个( 有多个时均相等) 。对于指数级数列 华中科技大学硕士学位论文 ( n ! ) ，即使当m 与n 取不大的值( 如取1 0 ) ，要遍历整个解空间去搜索最优解也是 不可能的。例如：当m = 1 0 ，n = 1 0 时，解空间规模就有( 1 0t ) 1 0 = 3 9 6 x 1 0 6 5 ，若 用每秒运算一亿次的计算机，也得1 2 6 x1 0 5 0 年。显然，如此求其最优解是不可行的。 尽管当j s s 问题的规模较大时，人们几乎无法找到其最优解，但对于任何规模 的j s s 问题，一定能找到它的可行解，即满足工件、机器约束关系的一种所有操作 在机器上的排序。 不妨设j s s 问题的总工序数( 即总操作数) 为n ，工件有n 个，机器有m 台， 其中第i 个工件的总工序数为n i ( 1 i n ) ，从而n - - e n i ( 1 i n ) 。将所有的工序依次 编号为1 ，2 ，n 。编号按 的顺序进行，具体的编号方法是： 先对工件1 的所有工序编号，按工件1 上所有工序完成的先后顺序依次编号为1 ， 2 ，n l 。再对工件2 的所有工序编号，按工件2 上所有工序完成的先后顺序依次 编号为n l + 1 ，n 1 + 2 ，n l + n 2 。如此类推，直到将所有工序编号完毕，如图2 3 所示。有了所有工序的编号后，便可以按照下面方法加工工件。 先在工序1 对应的机器上( 图2 3 中为2 号机器) 完成工序1 ；工序1 完成后， 再在工序2 对应的机器( 1 号机器) 上完成工序2 ；工序2 完成后，再在工序3 对应 的机器( 1 号机器) 上完成工序3 ；如此类推，直到所有的工序完成为止。显然，得 到的调度是一种合法调度，即找到了j s s 问题的一个可行解。具体的编号和调度情 况如图2 _ 3 所示。 其中每个工件左边的数字表示工序的编号，中间带圆圈的数字表示此工序所对 应的机器。 2 溷 ( 工件1 ) ：嗍 图2 3 操作编号示意图 1 2 2圄骈 j q 3 ( 华中科技大学硕士学位论文 2 5 小结 尽管人们已经针对j s s 问题提出了不少解决方案，但由于其固有的复杂性，仍然 没有那一种方案对一般j s s 问题的求解普遍有效。本章对j s s 问题的复杂性进行了 分析，并给出了j s s 问题的几种表述形式，为后面章节中关于此问题算法的实现作 准备。 1 3 华中科技大学硕士学位论文 3 车间作业调度问题相关算法浅谈 在本章里，将对常用的一些求解j s s 问题的算法进行了介绍，其中重点介绍了 生物遗传算法和模拟退火算法。由于拟物拟人算法和禁忌搜索算法是本文讨论的重 点，故分别在第四章和第五章中对其加以详细阐述。 3 1 启发式算法介绍 组合最优化( c o m b i n a t o r i a lo p t i m i z a t i o i n ) 是通过对数学方法的研究去寻找离散 事件的最优编排、分组、次序、或筛选等，它是运筹学( o p e r a t i o n sr e s e a r c h ) 中的一 个经典且重要的分支。组合优化问题的目标是从组合问题的可行解集中求出最优解， 它有三个基本要素：变量、约束和目标函数。在求解的过程中选定的基本参数称为 变量，对变量取值的种种限制成为约束，表示可行方案衡量标准的函数称为目标函 数。故此问题可用数学模型描述为： m i n f i x ) s t g ( x ) 0 x d 其中，f ( x ) 为目标函数，g ( x ) 为约束函数，x 为决策变量，d 表示有限个点组成的集 合i ”1 。 一个组合优化问题可以用三个参数( d ，f ，f ) 表示，其中d 表示决策变量的定义 域，f 表示可行解区域，f = x ix e d ，g ( x ) o ，f 中的任何一个元素称为该问题的 可行解，f 表示目标函数。满足e ( x ) = m i n f ( x ) l x f ) 的可行解x 称为该问题的最优解。 组合最优化问题的特点是可行解的集合为有限点集。由直观可知，只要将d 中有限 个点逐一判断是否满足g ( x ) 的约束和比较目标值的大小，该问题的最优解一定存在 和可以得到。因为现实生活中的大量优化问题是从有限个状态中选取最好的，所以 大量的实际优化问题是组合最优化问题。 但由于一些组合最优化问题还没有找到求最优解的多项式时间算法，人们不得 华中科技大学硕士学位论文 不尝试用启发式算法来求解组合最优化问题。启发式算法( h e u r i s t i ca l g o r i t h m ) 是相对 最优算法提出的，它在可以接受的计算费用内去寻求最好的解，但不能保证所得到 解的可行性和最优性【”l 。在实际问题中，有些难的组合优化问题可能还没有找到最 优算法，即使存在，但由算法复杂性理论，得知它们的计算时间是无法接受或者这 种方法是不切实际的。而启发式算法编程简单、运行速度快、容易修改、且得出的 解往往不是太坏。另外，若将启发式算法运用到最优算法之中，则可较大地提高最 优算法的性能。当然，启发式算法的性能较大的依赖于实际问题以及设计者的经验 与技术，当求解某问题时，它表现出极大的不稳定性，有时对于同一个问题的不同 实例的计算，都会得出不同的结果，这些应该是它的不足之处。 对于很难的j s s 问题，即使是1 0 个工件、1 0 台机器的规模都几乎无法找到其 最优解，故人们很自然地会寻找一些求解j s s 问题的近似算法。象基于优先派遣规 则的实现方法有：最短加工时间优先( s p t ) 、最大工作剩余优先( m w k r ) 、先到 先加工( f c f s ) 等，这些通过基于看起来似乎局部最优的决策来构造的解决方案， 是一种单向的、贪心类型的方法【1 4 】，它们往往运行速度快，且通常得到了并不太坏 的解。在许多情况下，能够达到问题的要求。 3 2 生物遗传算法介绍 遗传算法( g e n e t i c a l g o r i t h m ，g a ) 是近几年发展起来的一种崭新的全局优化算法， 它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，来实现各个 个体适应性的提高。g a 算法基于自然选择和遗传学机理的搜索寻优法，它通过遗传 基因代码，利用繁殖、交叉、变异三个基本算子，在点群中进行全局寻优，保证了 快捷准确的搜索特性，正在被许多领域广泛应用。 g a 算法是一类模拟自然过程、特别是模拟生物界自然进化和遗传过程的随机启 发式搜索算法，具有在复杂空间求问题近似最优解的能力。它是基于一个候选解群 的迭代过程，使用遗传算子在问题空间中进行搜索，采用适应值来评价候选解的优 劣，为求解复杂优化问题提供了一个有效方法。 用g a 算法解决问题时，首先要对待解决问题的模型结构和参数进行编码，一 华中科技大学硕士学位论文 般用字符串表示，这个过程就将问题符号化、离散化了。 g a 算法的运行过程为一个典型的迭代过程，其必需完成的工作内容和基本步骤 如下l ”1 ： 1 ) 选择编码策略，把参数集合x 和域转换为位串结构空间s ； 2 ) 定义适应值函数“x ) ； 3 ) 确定遗传策略，包括选择群体大小n ，选择交叉、变异方法，以及确定交叉概 率p c 、变异概率p m 等遗传参数； 4 ) 随机初始化生成群体p ； 5 ) 计算群体中个体位串解码后的适应值f ( x ) ： 6 ) 按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体； 7 ) n 断群体性能是否满足某一指标。或者已完成预定的迭代次数，若不满足则返 回步骤6 ) 。 遗传算法是多学科结合与渗透的产物，已经发展成一种自组织、自适应的综合 技术，广泛应用在计算机科学、工程技术和社会科学等领域。其研究工作主要集中 在以一f j l 个方面： 1 ) 基础理论方面：包括进一步发展遗传算法的数学基础，从理论和试验研究它 们的计算复杂性。在遗传算法中，群体规模和遗传算子的控制参数的选取非常困难， 但它们又是必不可少的试验参数。在这方面，已有一些具有指导性的试验结果。遗 传算法还有一个过早收敛的问题，怎样阻止过早收敛也是人们正在研究的问题之一。 2 ) 分布并行遗传算法方面：遗传算法在操作上具有高度的并行性。许多研究人 员都在探索在并行机和分布式系统上高效执行遗传算法的策略。对分布并行遗传算 法的研究表明，只要通过保持多个群体和恰当控制群体问的相互作用来模拟并行执 行过程，即使不使用并行计算机，也能提高算法的执行效率。 3 ) 分类系统方面：分类系统属于基于遗传算法的机器学习中的一类，包括一个 简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。分类系 统被人们越来越多地应用在科学、工程和经济领域中是目前遗传算法研究中一个 十分活跃的领域。 4 、遗传神经网络方面：包括连接权、网络结构和学习规则的进化。遗传算法与 华中科技大学项士学位论文 享枣缝嘲终棚绥台，正成功地爝予从时闻序列分褥来送行财政预算。在这燕系统巾， 淫练僖弩怒模翻黥，数爨是有臻黟熬，一般缀难燕确绘爨每个执行的定量撂徐。翅 祭慕髑遗传嚣法求学习，戴毖克黢这些姻难，显罄撮裹系统蛙艟。m u h l e n b e i n 分拆 了多按感麴极鼷络的鼹黢性，菸猿恕下伐睾枣经网络憋熄遽锩毒串经嘲络。 s 遴健箨法方帮；模叛蠢然避亿过稔爵淑产漤餐棒瓣诗舞梳雾法避豫冀法。 遽传算法憝其中三转蒜型的雾法之一，冀余嚣释算法是避截：攥粼( e v o l u t i o n a r y p r o g r a m m i n g ，e p ) 帮j 莛纯策耀f e v o l u t i on a r ys t r a t e g i e s ，e s ) 。遮三静舞法怒旋戴独立 施发展起来的。 尽管g a 算法在熬个逊亿过程中韵遗传操作燕随视性的，餐它所呈现崮的特萑 并不蹩完全蘧撬羧索，它戆有效羹鏊萃| l 臻历史僖惑交接测下一我裁望性能密爨提蹇魏 寻优点集。这样代一 弋不叛进他，最质收敛至一个最适应环境的个体上，求褥问 题的最优解。g a 算法所设计的五大蒙辩：参数编码、初始群体的设定、避应度函数 的设计、遗传操作的设计和控制参数的设定。 g a 冀法其脊缀强豹搜索毙力，黠求释蒙j s s 溺援之类熬典裂豹n p 攫翘题共有 较为显薯的伐势。g a 算法她一个夔要特征是算法不依赖于阍题的具体形戏，具翁很 巍的獠越性。当然，遗传葵法也存奁过譬收敛和运算效攀较底等阏题。 甚蠢磷突袭暌，将蘧传黪法与颞求绥闻戆鲍疑体特赢稳缝食，对于攥嵩髯法戆 搜索效率越重要终蔫l 甜。文献f l i 】中褥襄发式冀法与健统熟逡转葵法熊缕合涞求 解j s s 瓣繇。其莛体镁法是，将作渡l 净孛熬“最缀期工爵瓣馋宠娥刘( s p t ) ”与 “最大剩余羔作灌优巍撬刘( m w k r ) ”弓l 入遗传簿法，并拳i 蹋邻城接索法( n s t ) 在遗传算法瀚基础上徽硒部辅翡接索，寨提高求瓣质蚕。由予一般豹速佟算法在撬 聿亍避程中，常露产垒大嚣静不霉盼解，往往鬻要兹赞大整熬辩溜去憝瑾窀裁。走琴 | 用痘发式调度援则将阅题的鳃空阉绒至某个包含禽性能解的予空间上，辩邋行遗传 搜索，然厝应用邻域搜索法来寻找可能落在予空间外的疆好奇勺解，能大大提高算法 的运行效率。文献f 9 1 中也怒通过将扇发式规蒯与遗传算法褶结合的方法| 涞求解j s s 藤瑟豹，它糕蠲g a 蒸溶改滋痘袋式骞法豹袭解挂能，溺嚣裂耀瘤发式麓期零l 暴g a 蓦法的援索过程，太大摁裹了j s s 阕题的求解效率。文献 1 8 r 蝴l j 指出，熔予遗传算 法把握总 拳搜索的能力较强。但腿部寻优能力较夔，丽基于知识的启发戏算法及模 1 7 华中科技大学硕士学位论文 拟退火算法等有很强的局部搜索能力，若在遗传算法的搜索过程中融合这些优化算 法的思想，构成一种混合遗传算法，则是提高遗传算法运行效率和求解质量的有效 手段。有计算表明，混合遗传算法能够有效地适用于大规模加工过程中调度问题的 优化计算，在运行时间、适应性和最优率等方面都具有很高的搜索优势。 混合遗传算法与基本遗传算法的总体运行过程相似，只是在混合遗传法中，染 色体的选择依据是个体完成局部搜索后的适应度，而不再是出生时的适应度。混合 遗传算法可以描述如下f 1 8 】： 1 ) 进化代数计数器