（计算机软件与理论专业论文）基于改进蚁群算法的总拖期问题研究.pdf

基于改进蚁群算法的总拖期问题研究 论文题目： 专业： 硕士生： 指导老师： 基于改进蚁群算法的总拖期问题研究 计算机软件与理论 曾傲 衣杨副教授 摘要 总拖期问题( t o t a lt a r d i n e s sp r o b l e m ，1 四) 是调度问题中的经典难题。单机总 拖期问题( s i n 酉em a c h i n et o t a lt a r d i n e s sp r o b l e m ，1 t ) 和并行多机总拖期问题 ( p a r a l l e li d e n t i c a lm a c h i n et 0 t a lt a r d i n e s sp f o b l e m ，p t ) 是许多学者研究的重点 问题。然而，p 胆更加符合实际生产，由于机器数量的增加必然使得加工的调度 更加复杂。因此，调度工作确保尽可能准时交货，或者将总拖期降到最低，成为 一大难题。蚁群算法( a m tc o l o n yo p t i m i z a t i o n ，a c o ) 提出至今，因为其优秀的搜 索寻优特性被广泛的应用于组合优化问题，也曾被不同学者应用于单机总拖期问 题。 本文在蚁群算法的基础上，针对并行多机总拖期问题的特性，提出了基于启 发式规则的改进蚁群算法，并对算法进行了性能优化。其内容包括： 首先，对1 曙，p 胆和a c o 的研究历史，现状进行了研究综述。总结了p 厂r 的最优解调度性质，以及介绍了目前求解厂r 的优秀算法。 其二，设计了将a c o 用于求解w 厂r 的复杂解构造模型和简单解构造模型。 简单解构造模型在复杂解构造模型的基础上，利用引仃的数学模型以及无差别 机器特性而提出。 其三，针对a c o 求解p 厂r ，提出了基于厂r 分解原则的侯选列表构造方法， 信息素更新策略以及改进局部搜索算法。 其四，设计了求解p 厂r 的a c o 算法实验，验证了算法的准确性，稳定性， 和有效性，并且和以往算法进行仿真对比实验。同时也对a c o 的参数设置优化 进行了初步的研究。 最后，实验显示本文提出的改进a c o 算法比以往的算法在不同程度上有所 提高。 关键字：调度；并行多机调度；进化计算；蚁群算法；总拖期问题 基于改进蚁群算法的总拖期问题研究 t i t i e ：ah y b r i da c o a l g o r i t h mf o r t h et o t a l t 硼i n e s sp r o b l e m m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：z e n ga o s u p e r v i s o r ：y iy a n g a b s t r a c t t l l l et o t a l t a r d i n e s sp f o b l e m ( 耵曙) i sac l a s s i cp r o b l e mo fs c h e d u l i n gp r o b l e m t h es i n 酉em a c h i n et o t a lt a r d i n e s sp r o b l e m ( 1 力田a i l dt h ep a r a l l e li d e n t i c a lm a c h i n e t o t a lt a r d i n e s sp m b l e m( 厂r )a r et o w i m p o n a n tp f o b l e m s w h i c hh a v e b e e n j n v e s t i g a t e dw i d e l y h o w e v e f ，p 厂ti sm o r ep r a c t i c a l i nt h ea c t u a l i n d u s t f yp r o d u c t i o n t h ec o m p l e x i t yo fs c h e d u l i n gj o b si si n c r e a s i n 酉yd i f f i c u l ts i n c em o r em a c h i n e sa f e i n v o l v e d a tt h i st i m e ，a ne f f e c t i v em e t h o d ，h o wt oa l l o c a t et h e s ej o b st om a c h i n e s a n dh o wt o d e c r e a s i n gt h ec o s to ft a r d yj o b s ，i sv e r yn e c e s s a r y am e t a - h e u r i s t i c a l g o f i t h md e f i v e d 舶mn a t u r e ，c a l l e da n tc o l o n yo p t i m i z a t i o n ( a c o ) a l g o r i t h m ，i s u s e df o rt h es i n 醇em a c h i n et a r d i n e s sp f o b l e mb e c a u s eo fi t se x c e l l e n tc a p a b i l i t yt o s o l v et h ec o m b i n a t i o n a lp r o b l e m s i nt h j sp 印e r ，ah y b r i da l g o r i t h mb a s e do na c o ，l l a c oi sp r o p o s e dt os o l v ep 厂r t h em a i nc o n t e n tc o n t a i n s ： f i r s t ，t h eh i s t o f ) ra n dd e v e l o p m e n to ft r p ，p 厂ra n da c oi ss u r v e y e d w e c o n c l u d et h ep r o p e f t i e so f 厂ro p t i m a ls o l u t i o n ，柚ds i m p l yi n t r o d u c et h ee x c e l l e n t a l g o r i t h mo fw 厂r s e c o n d ，ac o m p l e xc o n s t m c tf i g u r e 锄das i m p l ec o n s t m c tf i g u r e 盯ed e s i g n e d ， r c s p e c t i v e l y t h ef i g u r e sa r ep r e s e n t e db yt h ec h a r a c t e r i s t i c0 fp a r a l l e lm a c h i n e p r o b l e m s n i r d ，ac o n s t n l c t i n gc a n d i d a t el i s tm e t h o db a s e do nt h ed e c o m p o s i t i o nm l e so f t h ep a r a l l e lm a c h i n ep r o b l e mi sp r o p o s e d i i la d d i t i o n ，锄e f f e c t i v el o c a ls e a r c hi su s e d a f t e ri t e r a t i o ni nt h eh a c o ，w h i c hb r i n g ss o m eb e n e f i ti nf i n d i n gt h eb e t t e rs o l u t i o n f o u n h ，w ed e s i 印s o m ee x p e r i i n e n t so fp 厂rb yl 认c ot oa p p r 0 v et h a ti t se x a c t ， s t a b i l i t y 孤de f f e c t i v e m e a l l w l l i l e ，t h ec o m p 撕s o ne x p e r i m e n t sw i t h0 t h e ri n t e l l i g e n t 中山大学硕士学位论文 a l g 嘶t h m sa r ei n v o l v e d n ec o n f i g l l r a t i o n o fh a c o sp a r 锄e t e r si sd i s c i l s s e d s i m p l y a tl a s t ，t h er e s u l to fe x p e f i m e n t ss h o w st h a th a c op e r f 6 加sb e t t e ri nt h e p r o b l e ms c a l el i m i t a t i o n m e a n w h i l e ，i t so p t i m a lr a t ei sm u c hh i 曲e f 雒db e t t e rt h a n c u r r e n ta l g o r i t h m sr c s u l t k e yw o r d s ：s c h e d u l i n g ；p a r a l l e lm a c h i n es c h e d u l i n g ；e v o l u t i o n a r yc o m p u t i n g ；a c o ； t h et o t a l t a r d i n e s sp r o b l e m 论文原创性声明内容 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者虢暂钦 日期：z 旃户月7 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：j 极 同期乒矽睁p 月丫日 中山大学硕士学位论文 第1 章引言 1 1研究背景 1 1 1 并行多机总拖期问题的意义 ( 1 ) 并行多机总拖期问题具有较大的应用意义 盈利是企业生存与发展的最基本条件。为了追求高额的利润，企业必定接收大量的定 单，加大生产数量，缩短生产时间。但是有限的资源往往限制了生产，如何以最优的方式 调度工作，利用机器，人力，物流等资源是生产调度问题核心问题。但是再优化的调度， 如果生产量超过了生产能力，也必定会出现无法按时交货的情况。无法按时交货会造成企 业极大的损失，按照生产合同除了要赔偿顾客的损失外，对企业的声誉也会受到影响。企 业始终都要以生产定单为主，为了降低生产的风险，就应更多的考虑定单拖期的问题。 降低产品的总拖期数是企业降低其产品的生产成本和维持客户重要手段之一。随着科 技的进步和社会经济的发展，人们对产品的要求越来越高，对制造业而言，加剧了企业间 的竞争压力。为了在竞争舞台不处于劣势，企业要不断提高产品质量，缩短产品生产周期， 以降低成产生本。另外，控制产品的总拖期能够使企业在尽可能多的订单情况下，按时交 货，对企业的盈利和声誉都是一大保证。然而，在现实生产中，总会因为某些因素使订单 无法按期完成，造成企业严重的损失。总拖期最小化的目标就是提供将损失将到最低的方 案、和及时高效的应急的策略，重新安排生产，挽回企业的损失。 相比较而言，厂r 比1 胛更加贴进现实生活，更加具有现实意义。一般企业会为制造 流水线购入多台机器同时加工，而很少企业会只拥有一台加工机器的情况。随着企业效益 提高，企业家会不断的增加机器设备，而接受的订单数量也从而剧增，因此，问题是向着 复杂度加剧方向发展。所以，能够为多机情况提供更加有效的调度安排是众望所归。 ( 2 ) 探索求解调度问题的新算法 p 胆是总拖期问题中的基础类问题。在具体的实际生产中，还可能会出现不同的类型， 如提前拖期总拖期问题，带权重的总拖期问题以及有优先级别的总拖期问题等。以上不同 种类的总拖期问题都是在基础问题的一种扩展，本文研究基础类问题能给扩展问题奠定一 个好的基础，提供一种核心的算法，使扩展问题的研究重点转移到个性的差别中，而不拘 1 一 中山大学硕士学位论文 于基础的求解。 ( 3 ) 探索将蚁群优化算法具体应用的途径 a c o 对组合优化问题的求解性能得到许多学者的公认。但a c o 作为基本的求解算法， 应用到具体的问题，则应根据问题的实际情况进行修改，以及结合问题原有的性质，推论 进行改近。本文针对t 问题对算法做出修改与改进，为以后算法的应用提供了参考。 1 1 2t r p 的研究现状 1 r p l l l 研究调度工作加工使每一个工作尽可能准时交货或者将因为加工超期而造成的 延期时间降到最低。在制造加工业，几乎所有的加工任务都有相应的交货期限，企业为了 提高效益会尽可能多的接受订单，但同时不能按合同如期交货的现象也不断出现。总拖期 问题正是为企业解决此类问题，通过安排合理优化的调度，将拖期产生的损失降到最低。 t r p 是属于车间调度问题中的经典难题【2 3 1 。其中，研究最为广泛的是1 厂r 和p 厂r ，以 上两个问题皆被证明为n p - h a f d 难题。 从总拖期问题提出至今，许多学者就总拖期问题提出了不同的解决算法。从最初的精 确求解算法，调度规则算法，以及近代的启发式算法和元启发式智能算法都被应用于求解 此类问题。每一次算法的革新都使得总拖期问题的求解更加优秀，同时也意味着总拖期问 题还有很大潜在研究空间。 a c o 在单机总拖期方面已经得到了应用，实验结果表明虽然a c o 与迭代局部搜索 ( i t 啪t e dl d c a ls e a r c h ) 相比性能不分上下，但与其它启发式算法相比性能提高明显。经检索 查阅了国内外等著名学术数据库，如砸e e ，s c i ，a c m 等，并未发现目前有应用a c 0 求 解胛的相关文章。由于a c o 在求解组合优化问题的优秀性能，以及应用于1 厂r 所取得 的成果，本文将应用a c o 求解p 仃，并且根据具体的实际问题修改并改进算法，最后将 通过实验与其它算法比较，以及验证改进的性能。 1 2本文主要研究内容和贡献 本文主要针对如何应用a c 0 求解p 厂r 进行了研究，主要分两大部分：根据p 肌特性 改进a c o ，通过仿真对比实验验证算法性能及优化。其内容包括： ( 1 ) 对t 曙，p 胆的研究历史，现状进行了研究综述。总结了厂r 的最优解调度性质， 2 - 基于改进蚁群算法的总拖期问题研究 以及介绍了目前求解p 胆优秀算法。a c o 作为优秀的仿生智能算法，其杰出的搜 索寻优能力被广泛的用于组合优化问题。本文简单介绍了a c o 的发展历程以及主 要的改进算法，并介绍了a c o 求解1 厂r 的算法。 ( 2 ) 设计了将a c o 用于求解厂r 的复杂解构造模和简单解构造模型。复杂解构造模 型参照a c o 求解一般调度问题模型而提出，但由于p 厂r 的数学模型以及无差别 机器的特性使得复杂解构造模型中存在大量的冗余节点，简单解构造模型使用无 二义性规则很好的避免了此问题。 ( 3 ) 针对a c o 求解p 仃，提出了基于厂r 分解原则的侯选列表构造方法，信息素更 新策略以及改进局部搜索算法。 ( 4 ) 设计了求解p t 的改进a c o 算法实验，验证了算法的准确性，稳定性，和有效 性，并且和以往算法进行仿真实验对比。同时也对蚁群算法的参数设置进行了初 步的研究。 ( 5 ) 实验显示本文提出的改进a c o 算法比以往的算法在不同程度上有所提高。在本文 最后还展望了并行多机总拖期问题的前景和进一步的研究方向。 本文的主要贡献如下： ( 1 ) 提出了基于启发式规则的改进a c o 求解p 厂r 算法。 ( 2 ) 利用并行多机总拖期问题的数学模型以及无差别机器的特性，定义了适用于a c o 的复杂解构造图型模和简单解构造图模型。 ( 3 ) 提出了利用总拖期分解原则构构造侯选列表的方法。以及适用于p 厂r 的局部搜索 算法。 中山大学硕士学位论文 1 3本文技术路线 本文主要分成六章，其结构和相关章节的主题如下。 第1 章介绍了总拖期问题的现状、意义，阐述了本文的研究范围和组织。 第2 章对订p 进行综述，分析了总拖期的调度性质，以及介绍了以往的经典算法。 第3 章对a c o 以及其改进应用进行了综述，并简单介绍了a c o 求解单机带权重总拖 期问题的应用。分析了a c o 如何求解单机问题，以及提出了如何拓展问题到多机情况的 疑问。 第4 章和第5 章是全文的重点。第4 章在第3 章的基础上提出了求解并行多机总拖期 问题的算法，并给出简单解构造图，局部搜索等针对于总拖期问题的改进。 第5 章实验分析了第4 章提出的算法性能，以及验证了改进的有效性。并且针对a c o 的参数设置优化进行了分析研究。给出了参数设置的初始规则。 第6 章总结全文并讨论进一步的研究工作。 基于改进蚁群算法的总拖期问题研究 第2 章t t p 的研究现状及主要理论 在本章中，首先详细的介绍了总拖期问题的定义以及发展概况，区分了几种不同种类 的总拖期问题。并且对国内外的研究现状做了全面的总结，在此基础上对总拖期的重要性 质进行了初步介绍。最后，就几个常用的经典算法做出简单概要的介绍。 2 1总拖期问题 调度是一种具体有时间性的计划生产，详细的将有限的资源分派给任务加工从而满足 一个或多个预期目标。可使用的资源和工作任务有多种形式，资源可以是工厂中的机器， 运送货物的道路或是在计算环境中的一个处理单元。而工作任务可以是待加工处理的工 件，需要加工的工件，需要运送的货物或是要执行的代码。每一种任务都有其自身的特征 像所需要加工的时问，最早可能的开始时间和其交货的期限以及相关的优先级。预先的目 标也有多种形式，可以是完成所有任务的时间，最小的总拖期等。 调度模型可以分为确定型( d e t e 衄i n i s t i c ) 和随机型( s t o c h a s t i c ) ，确定性模型假设工作的 相关数据提前知道，而随机型只是知道部分分布数据。工作的加工时间，到达时间，交货 期限都是在完成一项加工后才被知道，或是在随机的情况下被告知。 本文中的总拖期问题属于确定型调度模型，大量的研究证明确定型的总拖期问题已经 是非常复杂的求解问题。除此之外，静态的确定型模型不会像第一印象一样看起来会很有 限制，因为许多动态的问题实际上可以被当成一系列静态的问题被处理。确定型机器调度 问题( d e s ) 一直都作为经典的组合优化问题研究。确定型机器调度在二十世纪六七十年代 开始广泛被关注。机器调度领域中各种不同问题的总集合。确定型机器调度问题涵盖甚广， 按处理问题的机器配置分为，总体上分为单机问题和多台机器问题，更详细的按加工性质 分为总拖期问题，车间调度问题，流水车间调度问题。针对不同的调度问题相应的工作也 被赋予了不同的特征，如总拖期的工作主要特征为加工时间( p r o c e s st i m e ) ，交货时间( d u e d a t e ) ，拖期的权重 ，e i 曲t ) 。各调度问题的目标函数也可细分，如求解总拖期的时间，总 拖期的惩罚代价，总拖期的工作数。总体而言，确定型机器调度问题主要包括三个重要的 元素：机器配置，工作性质和目标函数。确定型模型可以按等级顺序排序，一般表示为卅弘 其中提指机器配置环境，腚任务特征，堤目标优化标准。 气 中山大学硕上学位论文 1 曙是属于确定型器机调度问题中的经典问题之一，一直受到许多学者的关注与重视。 从最初精确求解算法到最近的智能后启发式算法，在每一次算法革新的时候，学者们都会 运用新的算法技术重新解决总拖期问题，并且取得了优秀的成绩。 1 曙又包含了很多不同的子问题，总体上根据机器的配置分为单机( s i n g l em a c h i n e ) 总 拖期和多机( m u l t im a c h i n e s ) 总拖期问题。作为研究的重点，单机总拖期问题的不同情况又 分相同到达时间( e q u a lr e l e a s et i m e ) ，不同到达时间( u n e q u a lr e l e a s et i m e ) 以及带权重的单 机总拖期问题( s i n 酉em a c h i n et o t a lw e i g h t e dt a r d i n e s sp r o b l e m s m w t p ) 。多机总拖期问 题包括并行多机( p a r a l l e lm a c h i n e ) ，流水车间( f l o ws h o p ) 和工作车间( j o bs h o p ) 总拖期。 本文重点研究的是并行多机总拖期问题，机器配置环境是朋台功能无差别的等同机器， 所有的机器在零时间就准备就绪，并且可连续的处理工作的加工，但是当机器正在加工一 工作时，不允许打断以及被优先级高的工作中断处理。关于工侮具有以下几个特性， 加工时间( p r o c e s s i n gt i m e ) p 盯：p 盯表示工佝在机器f 上所需要的加工时间。在并行多机 环境中由于各台机器是无差别的，所以都具有相同的加工时间。 到达时间( r e l e a s ed a t e ) o ：o 表示工作j 在到达系统的时间，即是工作最早可以加工的 时间。在本文研究的问题中到达时间皆是在零时刻。 交货期限( d u ed a t e ) 西：西是加工企业事先允诺客户的交货期限。按时完成的工作是可 以被接受的，可是如果超过预定好的交货期限则会被置于一定的惩罚。所以交货期限是工 作完工的最后期限( d e a d l i n e ) 。 权重( w e i g l l t ) 坳：工作的权重是指不同的工作因其重要性，对超过期限的时间在惩罚 上有一定的比例。越重要的工作在超期后会比一般的工作有更大的惩罚权重，在本文中各 个工作的权重都为1 ，是不带权重的总拖期问题。 p p t 的目标函数是求得最小化的总拖期值。工佝的拖期乃= m a x ( c ：吗，0 ) ，其中g 是工 佝的实际完工时间，当c ：牺时，产生拖期乃为正数，而当c ：s 西时，工佝按时完成工作或 提前完成工作都不会对结果造成影响。 2 2国内外研究现状 本文主要针对s m w 开和p l ( ，r 进行了研究，以上问题已证明为n p 难题【4 l ，超过5 0 个工作 的问题常常不能被分枝界限法等精确算法解决了。 基于改进蚁群算法的总拖期问题研究 在带权重单机总拖期问题方面，主要有三方面算法：精确求解算法，调度规则和启发 式算法。精确求解算法包括动态规划算法( d y n a m i cp r o 孕a m m i n g ，d p ) 【5 】和分枝界限法 ( b r a n c ha n db o u n d ，b a b ) 6 。以上两种算法都利用了优势规则( d o m i n a i l c er u l e ) 去限制对最 优解的搜索从而达到计算的实用性。然而，动态规划算法无法在可接受时间内解决超过3 0 个工作的问题。分枝界限法同样超过5 0 个工作时所用的时间也让人很难接受。不过近期研 刭7 l 在解决带权重和不带权重的总拖期取得了很好的结果。 由调度规则而得来的近似算法虽然可以很快的时间内得出结果，但是往往结果都非常 不够理想。p o t t s 等【8 j 就比较了各种规则如带权重的最短加工时间( w e i g l l t e ds h o n e s t p r o c e s s i n gt i m e ，w s p 叨，最早交货时间( e a r l i e s td u ed a t e ，e d d ) 和目前最紧急( a p p a r e n t u r g e n c y ，a u ) ，得出a u 是最好的规则，而w s p t 是其中最差的规则。 在后启发式算法( m e t a h e u r i s t i c ) 取得发展后，众多的求解总拖期的后启发式算法也相 继出现。如模拟退火s a 【9 j ，禁忌搜索t s ，遗传算法g a ，蚁群算法a c o 和粒子群算法p s o 。 c r a u w e l s 等比较了s a ，t s ，g a ，其中t s 比其它算法性能要优秀，尽管g a 也可以求解出比 较高质量的解。c o n g r a m 等【1 0 】提出了迭代动态搜索( i t e r a t e dd y n a s e a r c h ) 算法，在每一次迭 代局部搜索时不同于以往只单独移动一次，而是进行一系列的移动。并且实验表明迭代动 态搜索比t s 更加优秀。b e s t e n 等【1 1 l 和l i a n g 都使用蚁群系统( a n tc o l o n ys y s t e m ，a c s ) 算法求 解1 0 0 个工作的问题，并且实验的结果非常的成功。最近，t a s g e t i r e n 等【1 2 】应用目前较新的 粒子群算法( p a n i c l es w a 彻o p t i m i z a t i o n ，p s o ) 求解了s m w t p ，求解性能与a c o 相当。 在p t 方面，学者们对它的研究不如单机方面研究广泛和充分。但是也存在很多优秀 的算法成果。早期的精确求解算法方面是由g u p t a 和m a y k u t 【1 3 】给出了动态规划d p 优化算法， 但因为它的解空间包含了所有的可能的工作安排以及每台机台的工作序列，使解的维度激 剧增加，所以只能解决小规模的问题。所以又出现了一些特殊条件限制问题的算法，如r o o t ， k o v a l v o v 和w | e m e r 【1 4 】提出的求解具有相同交货时间的并行总拖期算法。其外，y a l a o u i 和 c h u 【1 5 】以及s h i m 和l ( i m 【1 6 】分别总结总拖期问题的优势性质( d o m i n a n c ep r o p e n i e s ) 提出了分 枝界限算法，并且在可接受的时间内能够算出规模为3 0 和5 0 个工作的最优值。 因为t t p 是n p 难题，精确求解算法很难在规模达到一定程度时求出解，所以根据调度 规则提出的启发式算法陆续出现。这个阶段提出的算法有一个相同的特征，通过求解单机 总拖期问题的算法将工作进行优先排序，再利用序列列表调度，将尽可能早的完工的工作 分派到不同的机器上加工。这种思想最早是由w i l k e r s o n 和h w i n 提出，但是由b a l 【e r 【1 7 】实现 中山大学硕士学位论文 了具体的w l ( w i l k e r s o n i 刑i n ) 算法。 w i 算法首先将工作按e d d 规则排序，接着选择最早的交货期限的未加工工作，通过以 下的规则指派机器加工： s t e p1 如果所选择的工作加入到已经存在的部份解调度序列之后不会产生超期， 则将期调度安排到尽可能准时加工完毕且加工完毕时间最靠近交货期限的机器。 s t e p2 如果将工作安排在任何机器上加工都会产生超期则将其安排在最尽可能最 早完成加工的机器加工。 w i 由于是最早实现的启发式规则算法，由于其简单的调度规则只是考虑了问题求解的 当前情况，只是满足于目前的最优解情况，具有贪婪特性，所以寻找到的最优值并非为全 局的最优值。不过w i 算也为其后的算法奠定了基础，所以其后的算也都按照将工作尽可指 派到能够即时完成加工的机器上加工的思想改进算法。 d o g r a m a c i 和s u r l 【i s f l 8 】提出了另一种针对于p t 列表启发式调度算法， d s ( d o g r a m a c i s u r k i s ) 算法，算法中使用了三种不同的调度规则分别指派工作，最终将最小 的拖期工作调度，算法步骤如下： d s 算法相对于w i 算法有一定的改进，其中不仅增加了调度规则使得多种调度规则共 同求解同一问题可以适应于不同的问题，其实在完成对工作的分派任务后，再使用单机上 的优化算法对工作调度序列重新优化。 h o 与c h a j l g 提出了更加复杂的启发式算法，t p i ( t r a f f i cp r i o r i t yi l l d e x ) 算法。算法同样 也首先将工作按照一种调度规则进行排序，不过不同于以上规则，h o 等提出了自己的调度 规则，t c r ( t r a f f i cc o n g e s t i o nr a t i o ) 规则。t c r 规则定义如下： r 基于改进蚊群算法的总拖期问题研究 础；竺 d ，靠 ( 2 1 ) 其中，万( 荟只) 刀，万= ( 著盔) 以。利用t c r 规则，t p i 算法为每一个工作计算了相 应的优先索引r ： 肌南+ ( 1 - 屹) 南 ( 2 - 2 ) 其中，= m a x m i n o 5 + 茎云笋，1 o ，o o ( 2 3 ) 匠黾一个常数参数。t p i 算法即使用尾对未加工的工作排序，并且按照d s 类似的调度方 式对工作指派不同的机器，最后t p i 算法还利用相邻工作交换方法单独对每一台机器的加 工序列重表调整。尽管t p i 算法在最后的采用了类似局部搜索的策略调整解，但是最终经 实验证明t p l 算法只比w i 算法提高了o 2 2 的性能。 以上三种早期的启发式算最主要的一个缺点是它们都孤立了资源分派和加工顺序的 内在联系，忽略了并行多机总拖期的多机之间的本质，单独的根据单机总拖期的问题的求 解算法排序待加工的工作，然后按此列表将工作指派到相应的器。然而，这种解决问题的 方法往往只能得到局部的最优值。 虽然这种方法不能求解到全局的最优值，但是也启发了不少学者提出新的改进算法解 决此类问题。不同于先确定工作顺序然后指派工作到机器的方，k o u l a m a s 混合了排序指派 的方法，开始将并行多机的特性考虑在求解的过程中，并在p s k 算法的基础上提出了k p m 算法。经实验证明k p m 算法是求解总拖期问题中的一种有效的而简单的算法。 由于分解原则在算法中得到了很好的应用，k o u l 锄a s 在之后的研究工作中将k p m 算法 和分解原则混合使用提出了p d e c 算法，利用k p m 算法估算最佳的七值对原有的加工序列 进行分解，然后递归的对子问题使用p d e c 算法直到将其问题分解到足够小从而可以容易 的求解。 最近，s “1 9 1 ，t s 【2 0 】和g 洲2 1 2 2 】都有被应用在总拖期方面。b e 柚提出了r a n d o mk e y 方法 将遗传算法可以运用于组合优化问题，并求解了两台机器的总拖期问题。国内的学者王成 尧等也提出了基于自然码编码和块解码算法的遗传算法，但是算法只比较了一种难易程度 的总拖期问题，并不能说明遗传算法对总拖期问题的求解能力。 中山大学硕士学位论文 2 3总拖期调度性质研究 总拖期属于车间调度问题，像j s p 问题一样，本身也具备某些最优解的性质。其中最 经典的是e m m o n s 【2 3 】提出的优势性质( d o m i n a n c ep r o p e n i e s ) 称之为经验优先关系 ( a p o s t e r i o f ip r e c e d e n c er e l a t i o n s ) 。这种关系后来被大量的使用在穷举方法中减少搜索量， 以及后来的调度规则也是利用了这种关系的弱化条件。 性质1 ( e m m o n s f i r s tn e o r e m ) 假设存在两个集合岛和彳f ，分别是工作巩之前和之后所 安排的工作集合。如果葡产研，并且西= m a x ( 七尉肌坳，呦，则至少存在一个最优解使 楸q ，即工佩优先秘加二。 性质2 ( e m m o n s s e c o n d1 1 h e o r e m ) 如果葡f - 研，并且西 m a x ( 麟风切，呦，扰+ a = & 副f 肌则至少存在一个最优解使得乃也，即工作乃优先于匆加工。 性质1 给出了较短优先于较长的工作加工的必要条件。而性质2 则给出了加工时间长的 工作优先于短工作的必要条件。根据以上两条基本性质可以很容易推出以下三条推论： 推论1 ( e l m a g l l r a b y sl e m m a 【2 4 1 ) 任何一个工作的交货期限如果超出了机器加工的总时 间，即磊 k 。n 肌，则可以工作在最后被调度。 推论2 如果按照s p t 规则排序加工的所有工作都超期，则s p t j | 顷序就是最优解。 推论3 如果按照e d d 规则排序加工的序列至多有一个超期，则e d d 顺序就是最优解 除了e m m o n s 的优势性质以外，另一个应用非常广泛的是由l a w l e r 提出并由p o t t s 和 i 越a r e v l 2 5 】等人拓展了分解原则( d e c o m p o s i t i o np f i n c i p l e ) ： 令= 1 ，2 ，以) = ，1 ，厶，其中西j = 勘。设有一经修改过的e d d 序列忍= u 1 ，厶- l 厶+ 1 ，丘，j ，m 1 ，厶) ，+ ，所心，其唧是加工时间最长的工作，将其从原来历位置放 置到七位置。则有 性质3 ( l a z a r e v2 0 0 7 ) 存在一个最优调度彳，存在一个七，对所有了 1 ，2 ，硌+ ) ， ，叫+ 并且对所有了弘+ 1 ，1 ) ，_ + q 。 以上适合用于单机总拖期问题的性质在某种程度上也适合于多机情况下，各台机器选 择时所运用的性质。不仅如此，州仃也存在自己的调度性质。如a z i z o 酉u 和尉r c a l 2 6 】提出的 以下一磐性质： 基于改进蚁群算法的总拖期问题研究 性质4 存在一个最优调度，每一台机器的总加工时间不会超过 砉( 砉见+ 伽一1 ) 吣饥m ( 2 4 ) 推论4 存在一个最优调度，工仰将在任何一台机最后加工，如果满足条件： d ，丢( 砉a + 伽一1 ) m a x ；饥) ) 下面给出一些特殊情况下的调度性质： ( 2 5 ) 性质5 【凋存在一个最优调度，如果研= 所，并且西= 面，则工作f 的调度不会晚于工俯。 证明： 假设存在一个最优调度硝足肼= 所，磊= 西并i 且s 蝎，其中研是工作i 开始加工 的时间。假设存在另一个调度，它是通过交换确工作f ，j 而得来。由于两工作的加工 时间相等，所以交换不会影响其它拖期。令4 丁为交换前后的差值，a 是工作f 被加工完毕的 时间在最优调度砷。 4 n m a x o ，c f 一盔 + m a x o ，q - 西) 一m a x o ，c j 一西) 一m a 】( o ，g - 西) 分两种情况讨论： a ) c ) 一西 o 则m a x o ，g - 盔 = g 一西 4 难c f 一画+ m a x o ，g 一西 - o + 西m a ) 【 o ，g 一西) = m a x g 磊，g - 盔+ q - 西) - m a x g 一西，o - 西+ c f - 西 0 ，因为g g b ) c ：- 西= o 则m a x o ，c ：一西) = o 4 a m a x 0 ，g - 磊) m a x o ，g 一西) = o ，因为西= 西 以上两种情况，t o 即，表示通过交换工作位置，不会增加拖期，即存在一个调度且 比原来更优且满足质性4 。 性质6 【2 2 】存在一个最优调度，它的任何一台机器的最后一个工作的开始加工时间都 小于等于其它机器最后一个工作的完工时间。，s = 风，j = k = m ，其中和伍表示最后 个工作的开始加工时间和完工时间。 证明：假设存在一个最优调度d 满足s 既，即有一个工作的开始加工时间大于七机器最 1 1 中山大学硕士学位论文 后一个工作的完工时间。假设存在另一个调度，它是通过将嘲工俯调度在机器尼加工 而得来。由于只是调度最后一个工作不会影响其它拖期。 乃( 矿) = m a x o ，c ：( 力西) = m a x o ，瞰力切西) 咖，转s t e p5 ，否则，指派到机器 f ，聊j = 聊f 切，将基因，从染色体 s ) 中删除。如果染色体侈) 为空，转s t e p8 。 s t e p4 如果胁豇口，转s t e p3 。 s t e p5i = f + 1 ，七出一1 ，如果；绷，转s t e p2 。 s t e p6 选择尼机器，a 唱泐= m i n 朋七i 七= 1 ，2 ， ，1 ) ，将第一个基因j 指派到机器k ， 历七2 祝七 研。 s t e p7 将基町从染色体中删除，如果染色体p ) 不为空，则转s t e p6 。 s t e p8 运用性质6 ，对指派结果进行调整。 遗传算法适值函数采用目标函数，种群设置为4 0 ，运用轮盘赌注法选择遗传染色体， 础第蚧染色体的选择概率为： 昂 ) ；东乒丝l 著( 厶一厂 ( 2 6 ) 其中，肛m a x 册) 是所有染色体中适值函数最大值。交叉方式为j 下规交叉因子，变异 方式采用随机抽取染色体，变异率为5 0 ，变异方式采用逆序变异。为确保经历过的最好 解能够遗传到下一代，采用历史最好解无条件遗传的方法( e l i t i s ts t r a t e g y ) ，终止条件为目 标函数为o ，或迭代次数大于等于1 0 0 0 。 2 4 3 局部搜索 随着对求解结果的要求越来越高，精确算法所要消耗的时间太多，而根据调度规则算 得的结果却又往往达不到要求，此刻局部搜索【2 8 1 就被广泛采用。即对调度算法的结果运用 局部搜索，细微的调整解中某些部分解的位置直到不出现更加优的解。但是标准的此类局 部搜索算法只针对于已有的解改进，所以最大的问题是类似于爬山算法一样，容易在寻找 到全局最优值之前陷入局部最优。尽管如此，许多学者将局部搜索于后启发式算法结合， 1 4 基于改进蚁群算法的总拖期问题研究 往往能够达到更好的寻优效果。 局部搜索最常使用的是邻接方法，即对相邻的部分解采用如调换，插入，交换等三种 方法。总拖期的解组成形式可表达为工作加工的顺序，如栉个工作的在单机总拖期最小问 题中的解可表达为对工作序号的排序，1 ，2 ，l 。 策略1 调换( t r a n s p o s e ) ：交换相邻的工作，如当前解为，万= ( 而，厕，+ l ，) 调换后为万= ( 乃，砺+ l ，砺，砣) 。 策略2 交换( i n t e r c h a n g e ) ：交换工作f ，的位置，如当前为万= ( 而，厕，巧，) 交换后万= ( 而，咱，厕，) 。 策略3 插入( i l l s e r t ) ：设o ，j f ) 是一对工作的位置。如当前为万= ( 田，砺_ 1 ，面，面+ l ， 巧- l 巧，巧+ 1 ，) 。插入后，如果i ，进行左插入( 乃，巧1 ，踊，巧，砀- l 砺+ 1 ，而) 。 卫 三 图2 1 邻接搜索算法的三种基本方法 t m n s p o i n s e n i n t e r c h a n g e 如图2 1 ，第一行的图例是第一种方法调换，将相邻的工作互换位置。这是一种最基本 的操作。第二行实际上是插入方法中的右插入方法，将工作2 插入至工作3 的右侧，工作3 左边的工作相应的向左边平移。而第三行的图是指交换，交换不同于调换，可以中间间隔 几个工作互换。 以上三种基本方法也存在着联系，调换其实质上相邻对的交换( a d j a c e n tp a i 刑i s e i n t e r c h a n g e ，a p i ) ，而交换是调换的一般形式，插入等同于平移。邻接法的属性使得或多或 少的适合调度问题，因为首先各种邻接法不同于在规模上( s i z c ) ，调换，插入，交换的规模 分别为，l - 1 ，o - 1 ) 2 和，1 0 - 1 ) 2 。其次，邻接结构的基本拓扑性质直接影响着解的质量。 1 s 中山大学硕士学位论文 在局部搜索算法中，轴线规则是决定哪一个由邻接法得到的更优解替换当前解。常用 到的有首次改进规则( f i r s ti i l l p r o v e m e n tr u l e ) 和最优改进规则( b e s ti m p r o v e m e n tr u l e ) 。首 次改进规则是每次邻接法如果能找到比之前更优的解，即替代当前优，直到不能再找出更 优的解才停止。而最优改规则在每一步完整的搜索后只使用最优的解替代当前解。后者往 往可以更早的得到更优的解，但是需要更大的代价，所以一般根据实际的问题选择。 基于改进蚁群算法的总拖期问题研究 第3 章a c 0 的相关理论研究 在本章中，首先简