已阅读5页,还剩86页未读, 继续免费阅读
(系统工程专业论文)基于智能优化算法的Job+Shop调度问题的研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
中文摘要 本文主要研究了三类j o bs h o p 调度问题,分别为传统的j o bs h o p 调度问题、 一类柔性的j o bs h o p 调度问题、不确定条件下的j o bs h o p 调度问题,分别采用 不同的优化算法进行了求解,主要工作如下: 首先,介绍了各种调度问题的描述及分类,总结了目前有关车间调度问题的 优化算法。 其次,针对传统的j o bs h o p 调度问题,分别采用改进了的自适应模拟退火 算法和蚂蚁算法进行了优化。在采用自适应模拟退火算法时,设计了专门的温度 更新函数,当算法陷入某一局部最优解时,通过小范围内升高温度,在一定程度 上使搜索跳出局部最优。还设计了专门的蚂蚁算法来求解j o bs h o p 调度问题, 将工序的最早开始加工时间( e a p t ) 作为蚂蚁搜索时的启发式信息,该蚂蚁算 法具有分工的功能,在选择策略上具有确定性和随机性两种特性,同时将变异操 作引入到蚂蚁算法中,给出了相应的流程;分别采用两种算法对不同类型的标准 问题进行仿真,并进行了结果比较。 另外,研究了一类柔性j o bs h o p 调度问题,介绍了柔性j o bs h o p 调度问题 的模型,设计了求解的遗传算法,并结合两个实例进行了仿真,得到了相应的结 果。 最后,考虑了加工时间为连续变量且服从正态分布的一类随机j o bs h o p 调 度问题。绍了该随机j o bs h o p 调度问题的模型,提出了解决该问题的思路:采 用随机模拟的方式产生输入输出数据,并训练神经网络,将该训练过的神经网络 嵌入到遗传算法中,用来求解j o bs h o p 调度问题。给出了该算法的流程,并进 行了算例仿真实验。 关键词:j o bs h o p ,蚂蚁算法,遗传算法,随机模拟,神经网络,模拟退火 算法 a b s t r a c t i nm o d e mm a n u f a c t u r e ,s h o ps c h e d u l i n gi sm o s ti m p o r t a n tt oe v e r ya s p e c to ft h e p r o d u c t i o na n dm a n a g e m e n ts u c ha sp r o m o t i n gt h eq u a l i t yo fp r o d u c t i o n ,d e c r e a s i n g c o s t ,p r o m o t i n gt h er a t eo fp r o d u c t i o n ,r e s p o n d i n gt od e m a n da tt h ef i r s tt i m ea n ds o o n m a n yp e o p l eh a ss t u d i e do ns h o ps c h e d u l i n gf o rm a n yy e a r s ,b u tt h e r ei sm u c h w e n e e d t od o i nt h i st h e s i s ,t h ec l a s s i c a lj o bs h o p ,ak i n do ff l e x i b l ej o bs h o pa n dt h ej o bs h o p u n d e ru n c e r t a i n t ya r es t u d i e dt h r o u g l ld i f f e r e n to p t i m a la l g o r i t h m s i nt h ef i r s tc h a p t e r , t h ed e s c r i p t i o na n dc l a s s i f i c a t i o no fp r o d u c t i o ns c h e d u l i n g a n ds h o ps c h e d u l i n gi sp r o m o t e d ,a n dt h e na l m o s ta l lt h eo p t i m a la l g o r i t h m sa p p l i e d t os h o ps c h e d u l i n ga r es u m m a r i z e d i nt h es e c o n dc h a p t e r , t h ec l a s s i c a lj o bs h o pr e s p e c t i v e l yb a s e do na d a t i v e s i m u l a t e da n n e a l i n ga n da n ta l g o r i t h mi ss t u d i e d i nt h ep a r to fa d a t i v es i m u l a t e d a n n e a l i n g ,as p e c i a lu p d a t i n gf u n c t i o no ft e m p e r a t u r ei sp r o m o t e d ,w h e nt h es e a r c h f a l l si nal o c a lo p t i m i z a t i o n ,t h et e m p e r a t u r ew i l lb ei n c r e a s e da f t e ras o r t ,t h e r e f o r e t h es e a r c hc a nl e a v et h el o c a lo p t i m i z a t i o nl os o m ee x t e n t t e m p e ri sa l s oa p p l i e dt o t h ea d a t i v es i m u l a t e da n n e a l i n g i nt h e p a r to fa n ta l g o r i t h m ,t h eb a s i cp r i n c i p l e , m o d e la n dt h ee v o l u t i o no fa n ta l g o r i t h ma r ei n t r o d u c e df i r s t l y , t h e nas p e c i a la n t a l g o r i t h ma p p l i e dt ot h ec l a s s i c a lj o bs h o pi sp r o m o t e d i nt h ea n ta l g o r i t h m ,t h e e a r l i e s ta l l o w e dp r o c e s s i n gt i m e ( e a p t ) i sc o n s i d e r e da st h eh e u r i s t i ci n f o r m a t i o n ,a l l a n ts t a r ta td i f f e r e n tp l a c ea n dc a ns e l e c tt h el a t t e ro p e r a t i o nd e c i d e d l yo rs t o c h a s t i c l y a c c o r d i n gt os i t u a t i o n a f t e rt h a t ,t h ep r o c e s so ft h ea n ta l g o r i t h mi sp r o m o t e d a tl a s t , s e v e r a lk i n d so fb e n c h m a r k sb a s e do nt l l i st w oa l g o r i t h m sa r es t u d i e da n dt h i st w o a l g o r i t h m sa r ec o m p a r e d i nt h et h i r dc h a p t e r , ak i n do ff l e x i b l ej o bs h o pi ss t u d i e d a tf i r s t ,t h em o d e lo f t h ef l e x i b l ej o bs h o pi si n t r o d u c e d ,t h e nt h ep r i n c i p l e ,s t r u c t u r e ,f e a t u r ea n dp r o c e s s o ft h eg e n e t i ca l g o r i t h mi si n t r o d u c e d a f t e rt h a t ,t h r e eg e n e t i ca l g o r i t h m sa r ea p p l i e d t ot h r e es u b - p r o b l e m so ft h ef l e x i b l ej o bs h o p ,a n dt h ep r o c e s si sp r o m o t e d l a s t l y , t w oe x a m p l e sb a s e do nt h ea l g o r i t h mi ss t u d i e d i nt h ef o u r t hc h a p t e r , ak i n do fs t o c h a s t i cj o bs h o pi nw h i c ht h ep r o c e s s i n gt i m e s o fa l lj o b sa r eu n i f o r m l yd i s t r i b u t e dv a r i a b l e s f i r s t l y , t h em o d e lo ft h es t o c h a s t i cj o b s h o pi si n t r o d u e d ,t h e nt h et h o u g h to ft h ea l g o r i t h mi sp r o m o t e d ,i tc o n c l u d e st h r e e s t e p s :o b t a i n i n gt h ed a t u mn e e d e di nt h en e u r a ln e t w o r kt h r o e g hs t o c h a s t i cs i m u l a t i o n , t r a i n i n gt h en e u r a ln e t w o r kt h r o u g hg e n e t i ca l g o r i t h m a f t e rt r a i n i n gt h en e u r a l n e t w o r k ,i n s e r t i n gt h en e u r a ln e t w o r ki n t oa n o t h e rg e n e t i ca l g o r i t h ma n da p p l y i n gt h e s e c o n dg e n e t i ca l g o r i t h mt oj o bs h o p s e c o n d l y , t h ep r i n c i p l e so fs t o c h a s t i cs i m u l a t i o n a n dn e u r a ln e t w o r ka r ei n t r o d u c e d ,t h e nt h ea l g o r i t h ma p p l i e dt ot h es t o c h a s t i cj o b s h o pa n di t sp r o c e s si sp r o m o t e d l a s t l y , ae x m p l ei ss t u d i e d i nt h ef i f t hc h a p t e r , a l lt h ew o r ki n t h i sp a p e ri ss u m m a r i z e da n dt h ep r o s p e c t a b o u tj o bs h o pi sp o m o t e d k e yw o r d s j o b s h o p ,a n ta l g o f i t h r a ,g e n e t i ca l g o r i t h m ,s t o c h a s t i cs i m u l a t i o n n e u r a ln e t w o r k ,s i m u l a t e da n n e a l i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果,除了文中特别加以标注和致谢之处外,论文中不包含其他人已经发表 或撰写过的研究成果,也不包含为获得鑫洼盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名:签字日期: 年月目 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘堂有关保留、使用学位论文的规定。 特授权鑫洼盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索,并采用影印、缩印或扫描等复制手段保存、汇编以供套阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名: 藩孙 导师签名 签字日期:年月目签字日期:年月日 第一章绪论 1 1 引言 第一章绪论 自2 0 世纪9 0 年代以来,伴随着科学技术的进步,特别是信息技术和网络技 术的发展,人类生活的方方面面都发生了前所未有的变化,以计算机技术为基础 的信息技术成为推动社会发展的强大动力,传统产业面临着适应市场新需求模式 的强大挑战,制造业作为我国的基础产业,同时也是满足市场需求最为直接和重 要的产业,也受到信息技术和网络技术所带来的影响,正经历着由传统的制造模 式向现代制造模式的转变过程。客户对产品的要求越来越高,不仅仅希望能够获 得质量可靠,价格低廉的产品,而且对企业能够在最短的时间内生产出其所需要 的“个性化产品”提出了更高的要求。从企业的角度来说,如何能够快速响应客 户需求,在最短的时间之内、以最低的成本生产出顾客满意的产品成为了企业能 否赢得顾客,从而在激烈的市场竞争中立于不败之地的关键。而企业的生产计划 与调度对于提高产品质量、降低成本、提高生产率、快速响应市场需求等生产管 理的各个层面都起着至关重要的作用。因此对于调度问题的研究具有重要的理论 和实际意义。 生产管理一般分为生产计划、生产调度、生产控制三个阶段【1 。企业的生产 活动是按照生产计划来进行的,生产计划是根据企业内部的生产能力和环境、外 部市场的情况以及企业长期发展目标等因素,对企业生产发展及年度和季度经营 作出的决策,以及对产品需求和原料供应情况而作出的预测,并根据生产装置的 运行情况,编制中长期生产计划,合理地安排计划期内企业生产的产品品种、数 量和完成的期限,充分地利用企业的资源,包括时间、设备、劳动力、原材料和 能源等,保证按时完成定货合同,满足用户的要求,提高企业的效益。 生产计划的实施由生产调度系统来完成。生产调度层根据经营决策层制定的 长期生产计划,分解为便于执行的短期计划,结合生产装簧运转的情况,针对工 艺切换以及生产设备的运转等情况,进行合理的分配与安排,协调从原料、能源 供应、生产到产品发货的各工序环节,对生产过程进行平衡与控制,并及时调整 偏差,以达到生产过程连续不间断,降低生产成本,获得最大利润的目的。生产 调度的任务是在满足装置设备和工艺要求的条件下,根据市场的需求,合理地、 最佳地安排与组织生产过程,以提高过程系统的操作最优性,为企业带来显著的 第一章绪论 经济效益。一个好的、快速、准确、合理的生产调度方法,可以提高制定作业计 划的速度,加强企业的应变能力,从而提高企业在国内外的竞争能力,给企业带 来巨大的经济效益,使企业达到高效低耗敏捷快速地生产制造的目的。 1 2 生产调度问题的描述及分类 1 2 1 生产调度问题的描述 调度问题虽然最早是由生产过程提出,但是现在在其他领域也有着广泛的应 用,如交通运输、航空航天、企业管理和医疗卫生等行业。 生产调度问题是在一定的时间内,进行可用共享资源的分配和生产任务的排 序,以满足某些指定的性能指标【2 】,简单地说,生产调度问题就是按时间分配资 源来完成任务的问题。 生产调度问题一般可以描述为:针对某项可以分解的工作,在一定的约束条 件下,如何安排其组成部分所占用的资源、加工时间及先后顺序,以获得产晶制 造时间或者成本等指标的最优。 影响调度问题的因素很多,正常情况下有:产品的投产期,交货期,生产能 力,加工顺序,加工设备和原料的可用性,批量大小,加工路径,成本限制,这 些都是所谓的约束条件。有些约束条件是必须满足的,如交货期,生产能力等, 而有些约束条件达到一定的满意度即可,如生产成本等。这些约束在进行调度时 可以作为确定性因素来考虑,而对于设备故障、原料供应变化、生产任务变化等 非正常情况,都是事先不能预见的,在进行调度时一般作为不确定因素来考虑。 生产调度中涉及的工厂资源包括:原料,设备( 加工、存储、运输) 、人力、 资金、能源等。资源的详细分配受到产品的生产工艺的限制。 生产调度的性能指标可以是成本最低、库存费用最少、生产周期最短、设备 利用率最高等。实际生产调度的性能指标大致可以分为三类1 3 】: 1 最大能力指标 包括最大生产率、最短生产周期等,它们都可以归结为在固定的产品需求下, 最大化生产能力以提高经济效益。调度问题的主要目标为提高生产设备的利用 率,缩短产品的生产周期,使工厂生产能力最大。 2 成本指标 包括最大利润、最小运行费用、最小投资、最大收益等等,其中收益指产品 销售收入,运行费用包括库存成本、生产成本和缺货损失等。 3 客户满意度指标 第一章绪论 包括最短延迟时间、最小提前拖后惩罚等。 在传统的调度理论中,常用的有最小化制造周期、最小提前拖后惩罚、拖 后工件数最小等一些指标。 1 2 2 生产调度问题的分类 生产过程一般按照其输出的产品是呈现连续的产品流、离散的批量、离散的 数量三种情况分为连续生产过程、间歇生产过程( 也称批处理过程) 和离散生产 过程。与之对应,生产调度也就分为流程工业生产调度、间歇生产调度和车间作 业调度。 在离散生产过程中,产品通常是分批( 原料相同、加工工序相同的一组产品) 制造的,一定数量的产品作为一个工件组,在各个工件台之间传输,每个工件都 具有相对的独立性。典型的例子有机械加工、汽车装配过程等等。针对离散生产 过程的调度问题,其模型中变量一般为离散的变量。 在间歇生产过程中,生产过程由一系列生产工序组成,每道工序包括一个或 多个并行的生产装盖,工序间允许有储存装置,各生产装景可在不同的工艺规程 下加工不同的品种、不同批量的产品,生产装置从一种生产产品切换到另一种生 产产品需要过渡过程( 通常包括设备的更换、设备的清洗等过程) 。通常间歇生 产过程可以分为两类:一所有产品在一条固定的工艺路径上生产,通过操作时 间表与工艺条件的调整,可以生产不同规格的产品,称为m u l t i p r o d u c t ( 多产品 型) ;二每一中产品都有多条工艺路径,通过操作时间表与工艺条件以及物料 流动路线的调整,可以生产不同类型的产品,称为m u l t i p u r p o s e ( 多目的型) 。 典型的间歇生产过程如造纸、食品加工、纺织等等。对于间歇生产过程,其优化 模型中往往既含有连续的变量,如过程反应;也包含离散的变量,如生产方案的 切换,调度指令的下达等等。 在连续生产过程中,原料经过不同的专用设备加工转变为产品,每个设备都 是在稳定的工作状态下,完成一项规定的操作,产品从以原材料进入生产系统开 始到生成最终产品为连续不断的过程,典型的例子包括化工、冶金、电力等行业。 连续生产的调度问题中,其模型的变量一般为连续变量。 生产调度也可以分为静态调度和动态调度两类【“,静态调度是在已知调度环 境和任务的前提下的所谓事前调度方案;动态调度是指在调度环境和任务存在着 不可预测的扰动情况下的调度方案,它不仅依赖于事前调度环境和任务,而且与 当前状态有关。在实际的生产系统中大多数为动态加工环境,如工件连续到达, 在加工工程中有机器故障,操作工人的误操作,工件的市场需求发生改变等偶然 事件,采用静态调度方法显然不能很好的解决这些问题,通常是在前面已作出的 第一章绪论 调度方案的基础上进行重调度或者滚动调度。重调度分为连续调度和周期性调 度,连续调度指当引起系统的状态变化的事件发生时,就立即进行重调度,因而 能极快地跟踪系统的变化,但此方法计算量很大,对于复杂系统的实适性要求较 难掌握【5 l 。周期性调度指在间隔一定的生产时间后进行重调度,但在这段时间区 间内,对“未预期事件”并不敏感,积累该时间段内各种偏差,可能导致系统整 体性能的恶化,其优点是计算量小,易于实现在线重调度【5 | 6 】。 1 3 车间调度问题的描述及分类 车间调度问题可以简单的描述为,1 个工件在历台机器上进行加工的问题, 每一个工件都有其特定的若干个加工工序,每个加工工序都可以在某一台或几台 固定的机器上面进行加工,且相应的加工时间已知。只有当前一个工序加工完毕 之后,后一个工序才能开始加工,称为工件的工艺约束;在某台机器上面进行加 工的所有工序,只有当前一个工序加工完毕之后,才能进行另一个工序的加工, 即一台机器不能同时加工多个工件,称为机器能力约束。 车间调度问题的目标就是在满足工件的工艺约束和机器能力约束的条件下, 合理的安排每个工件的各工序所需要的机器,同时确定在每台机器上进行加工的 所有工序的先后顺序,使相应的性能指标达到最优。 车间调度问题一般分为单机调度问题、并行机调度问题、f l o ws h o p 调度问 题和j o bs h o p 调度问题。 单机调度问题指车间加工环境中只有一台机器,它是最简单的一类调度问 题。 并行机调度问题可以描述为加工环境中,有m 台完全一样的机器,1 个工件 均只有一个工序,此,1 个工件都能在m 台机器上中的任何一台上进行加工。 f l o ws h o p 调度问题指所有工件的工艺路线一致,但在每台机器上加工的工 序的先后顺序不同。对于每台机器上加工的工序的先后顺序相同的一类f l o w s h o p 调度问题,则称为置换f 1 0 ws h o p 调度问题。 j o bs h o p 调度问题描述为各工件的工艺路线也不同,是比f l o ws h o p 更为广 泛的一类调度问题。 以上几类调度问题都经过了一定程度的简化,在实际的车间调度中,往往存 在着更复杂的情况,如带有并行机的j o bs h o p 调度问题,混合f l o ws h o p 调度问 题,此两类问题综合了并行机问题和j o bs h o p 调度问题、f l o ws h o p 调度问题的 特点,既要考虑每个工件的每个工序所选用的加工设备,同时还要考虑每台设备 上工序的加工顺序,其模型的建立和求解比单一问题更加复杂。 第一章绪论 随着科学技术的发展,在生产过程中计算机集成制造系统的出现,加工设备 具有了越来越高的柔性,一台加工中心上可以通过更换刀具而从事多个加工工序 的操作,这样就使得工件在加工时存在多条可供选择的工艺路线,即所谓的柔性 调度,柔性调度一般分解为两级子问题,上一级子问题为:亡件对于加工路径的选 择,下一级子问题为加工路径确定之后,每台机器上工序加工顺序的确定。上述 几类更般的调度问题在实际的应用中具有更广泛的实际意义。 车间调度问题的表示方法可以为三参数表示法( 口伊y ) 和四参数表示法 ( n 蝴) 吲。 在三参数表示法( a 伊y ) 中口表示机器加工环境,口= a ,a ,其中 a , o ,p ,q ,r ,g ,x ,0 ,j ,f ,若q e 0 ,p ,q ,r ) 则每个工件仅包含一个工序。 若吼一0 ,则每个工件必须在一个规定的机器上加工。 若q e 0 ,p ,q ,r ) 则表示并行机加工环境。其中q - p 表示相同并行机,即 所有机器具有相同的加工速度。6 t 1 q 表示均匀并行机,即所有机器加工速度不 同,但与各工件无关。口,- r 表示不相关并行机,即机器的加工速度取决于各个 工件。 若口, o ,j ,f ) 则表示多工序类型,同时所有机器是专用性的,且各工序间 存在优先顺序。其中- 0 表示各工件可以不考虑自身的工艺顺序约束。a ,f 表示f l o w s h o p 调度类型,口,。j 表示j o b s h o p 调度类型。 声- 媚,, e s ,岛,成,展,成表示工件的加工特性,届用来表示加工方式,包括 抢占式或非抢占式。抢占式加工工序在加工过程中可以被打断,再在原机器或别 的机器上重新开始;非抢占式工序则在加工开始后不能被打断。最;p m t n 表示 抢占式。 反表示工件间的加工优先关系,该优先关系可用非循环有向图表示,若该 有向图为任意非循环有向图,则反- p r e c ,若该有向图为树,则晟1 t r e e 等。 屈表示工件的加工准备时间。若加工准备时间0 ,晟t 。 反表示工序加工时间的限制,p j p 表示每个工件的加工时间均为p , p cp 。tp 表示每个工件的加工时间在【p ,p 】之内。 威表示交货期信息,若反一d 。表示工件有交货期要求。 凤表示批量信息,即工件是否成批联合进行加工。羼一p b a t c h 表示批量 长度等于该批量中所有工件的加工时间的最大值,凤- s b a t c h 表示批量长度等 于该批量中所有工件的加工时间之和。 y 表示加工性能指标。 车间调度常用的性能指标可分为三类: 1 基于加工完成时间的指标: 第一章绪论 最大完成时间c m 。,( m a k e s p a n ) :c m 。- m a x c , ,其中c i 表示工件i 的 完成时间。 最大流经时间,m 。;。m a x f i ) ,其中f 一( j 一,表示工件的开 始加工时间。 总流经时间y f 。 平均流经时间三v f 等等。 2 基于交货期的性能指标 拖后工件数n ,( 完成时间大于交货期的工件个数) ; 最大推迟完成时间l 。:l 。- m 蟹( q d f ) ,其中d t 表示工件i 的交货 期。 最大拖后时间k :k m a x m a x 0 , c ;一吐 ,。 总拖后时间善瓦“。 3 基于库存的性能指标 平均末完成工件数m 。 平均待加工工件数。 定义1 3 1 对于一个调度问题,称性能指标函数r 是正规的,若对于满 + 足不等式关系c 1 车c l ,e 宣c 的任意两组加工完成时间 c j ) 和 d ) , 对r 必满足r ( c 1 ,c as 尺( q 。q ) 。 经过验证,c m 。,f m 。,l 一,z k ,b 等指标均属于正规性能指标。 在四参数表示法中,甩表示工件数,小表示机器数,爿表示工件流经机器的 类型( j o bs h o p 用g 表示,f l o ws h o p 用f 表示,置换f l o ws h o p 用p 表示) ,曰 表示性能指标( 如c 。,l 一) 。 另外,在企业实际的生产和运营环境中存在着许多不确定的因素,这些不确 定的因素放映在企业生产的各个方面,如在制定计划时要考虑某一产品可能因滞 销而减产,另一产品因旺销而增产;各种原材料的价格、某一产品产生的单位利 润也不是一成不变的:在企业的生产过程中,产品的加工时间往往是呈现一定规 律变动的,某些设备可能由于突发性故障而不能正常使用,工人有时候也会出现 操作失误等等,这些都构成了企业生产过程的不确定因素。因此,在生产调度的 研究中充分考虑这些不确定的因素,往往具有更加现实的意义。目前,国内外对 于不确定环境下的生产调度的研究还只是处于起步阶段,大部分的工作集中于鲁 棒调度和适应性调度方面的定性研究 5 8 】,鲁棒调度一般建立确定性的模型,利 第一章绪论 用调度系统监测生产过程对调度方案的执行情况,将其反馈给调度器,一旦生产 过程发生不确定的变化,如处理时间的变化,调度器及时修正调度策略,以保证 整个调度系统的稳定性,鲁棒调度适合于不确定因素变化频繁,但变化幅度较小 的情况:适应性调度适合于不确定因素变化幅度较大,如处理单元失效,重要的 仪器发生故障,处理时间大幅度改变等情况,分为重调度、滚动调度等等。目前 对于定量研究不确定性j o bs h o p 的文献资料还很少,有关不确定j o bs h o p 问题 的文献将在第四章详细介绍。 1 4 车间调度的优化算法 所谓优化算法,其实就是一种搜索过程或规则,它是基于某种思想或机制, 通过一定的途径或规则得到满足用户要求的问题的解【9 】。 对于调度问题的研究经历了一个较长的发展时期,自5 0 年代初期开始,应 用数学、运筹学、工程技术等领域学者就对调度问题进行了大量的研究。5 0 年 代早期,j o h n s o n 提出了解决删c 。和部分特殊的n 3 f c m 。问题的有效的优 化算法,标志着调度理论研究的开始。考虑到调度问题本身的复杂性,后来人们 逐渐着手开始寻找有效的求解策略。到了6 0 年代,调度理论主要围绕着线性规 划、整数规划、混合整数规划、动态规划、分支定界等方法,研究并解决了一系 列有代表性的调度问题。随着问题规模的扩大,人们越来越深刻地认识到传统的 精确算法已不能满足求解的需要,特别对于大规模问题,采用精确算法往往是不 可能的。于是在6 0 年代中期开始,人们开始着手研究调度问题的复杂性,并且 证明了许多调度问题诸如最简单的f l o ws h o p 和j o bs h o p ( 除了少数小规模问题 之外) 都是n p 难问题,对于这类问题,并不存在有效的多项式求解方法,因此 开始寻求有效的近似方法来解决它们,如基于优先规则的方法、基于瓶颈的启发 式方法、遗传算法、模拟退火算法、禁忌搜索算法、阈值接受算法、人工神经网 络、专家系统、蚁群系统等等o 】。 求解调度问题的方法统称为调度优化算法,可以把调度方法分为精确求解方 法和近似求解方法。其中精确方法包括解析方法、枚举方法;近似方法包括构造 性方法、领域搜索方法、人工智能方法等等【7 1 1 1 。 1 4 1 精确算法 ( 一) 解析方法 解析方法是对于特定的目标,能在多项式时间内得到最优调度的一类方法。 这类方法虽然搜索效率很高,但是适用问题很小,只对特定问题有效,对于一般 第一章绪论 用调度系统监测生产过程对调度方案的执行情况,将其反馈给调度器,一旦生产 过程发生不确定的变化,如处理时间的变化,调度器及时修正调度策略,以保证 整个调度系统的稳定性,鲁棒调度适合于不确定因素变化频繁,但变化幅度较小 的情况;适应性调度适合于不确定因素变化幅度较大,如处理单元失效,重要的 仪器发生故障,处理时间大幅度改变等情况,分为重调度、滚动调度等等。目前 对于定量研究不确定性, j o bs h o p 的文献资料还很少,有关不确定1 0 bs h o p 问题 的文献将在第四章详细介绍。 1 4 车间谒度的优化算法 所谓优化算法,其实就是一种搜索过程或规鲰! j ,它是基于某种思想或机制, 通过一定的途径或规则得到满足用户要求的问题的解吼 对于调度问题的研究经历了一个较长的发展时期,自5 0 年代初期开始,应 用数学、运筹学、工程技术等领域学者就对调度问题进行了大量的研究。5 0 年 代早期,j o h n s o n 提出了解决n ,2 ,f c ;。和部分特殊的n j 3 f f c m 。问题的有效的优 化算法,标志着调度理论研究的开始。考虑到调度问题本身的复杂性,后来人们 逐濒着手开始寻找有效的求解策略。到了6 0 年代,调度理论主要围绕着线性规 划、接数规划、混合整数规划、动态规划、分支定界等方法,研究并解决了一系 列有代表性的调度问题。随着问题规模的扩大,人们越来越深刻地认识到传统的 精确算法已不能满足求解的需要,特别对于大规模问题,采用精确算法往往是不 可能的。于是在6 0 年代中期开始,人们开始着手研究调度问题的复杂性,并且 证明了许多调度问题诸如最简单的f l o w s h o p 和j o b s h o p ( 除了少数小规模问题 之外) 都是n p - 难问题,对于这类问题,并不存在有效的多项式求解方法,因此 丌始寻求有效的近似方法来解决它们,如基于优先规则的方法、基于瓶颈的启发 式方法、遗传算法、模拟退火算法、禁忌搜索算法、闽值接受算法、人工神经网 络、专家系统、蚁群系统等等【4 , 1 0 。 求解调度问题的方法统称为调度优化算;去,可以把调度方法分为精确求解方 法和近似求解方法。其中精确方法包括解析方法、枚举方法;近似方法包括构造 性方法、领域搜索方法、人工智能方法等等【7 1 ”。 1 4 1 精确算法 ( 一) 解析方法 解析方法是对于特定的目标,能在多项式时间内得到最优调度的一类方法。 这类方法虽然搜索效率很高,但是适用问题很小,只对特定问题有效,对于一般 这类方法虽然搜索效率很高,但是适用问题很小,只对特定问题有效,对于一般 第一章绪论 问题,除了小规模的几个问题外,很难找到解析方法【1 2 】。 ( 二) 枚举方法( e n u m e r a t i v e m e t h o d ) 1 ,分支定界法( b r a n c ha n db o u n d ) 分支定界法的基本思想f 1 3 】是通过枚举优化问题的所有可行解以得到可能的 所有属性类型,并尽早发现为所有最优解都不具备的属性。其一般步骤为:针对 优化问题的解空间,建立对应的一个数据结构即搜索树,并在其上定义出所有可 能的属性,对每个属性定义由此属性的所有可行解所组成的一个子集。对于每个 子集,放宽原优化问题的某些约束条件来导出求解过程上易于原优化问题的一个 新优化问题,把求解新优化问题所得到的最优性能值作为原优化问题对应子集的 一个最优性能值下界,如果该最优性能值下界超过了目前所找到的最优性能值上 界,则说明此子集对应的属性不是最优解所具有的属性,在以后的搜索中将不被 考虑;对属于最优解的那些属性子集,要进行细分,需要引入附加的属性以对搜 索集合做进一步的细分,并进行继续搜索。在分支定界法中,属性的确定和最优 性能值下界的确定是两个重要的环节,直接影响到算法的性能。分支定界法只适 合于小规模的问题,对于大规模的问题,往往需要相当长的时间,因此限制了它 的使用。 2 数学规划法( m a t h e m a t i c a lp r o g r a m m i n gm e t h o d ) 数学规划法包括线性规划、非线性规划、整数规划、混合整数规划、l a g r a n g i a r , 松弛方法、动态规划等,此类方法只适合于少数小规模的问题,对于大规模的问 题,由于会产生所谓的“组合爆炸”现雾,因此此类方法不适合于大规模问题的 求解。 1 4 2 近似算法 ( 一) 构造性方法( c o n s t r u c t i v em e t h o d ) 一个优化问题的解是由若干个构造元素组成的,构造性方法通过逐步增加解 的构造元素来求得一个可行解。“贪婪法”就是典型的例子,在旅行商问题中, 每次从未走过的城市中选择与现在所处城市距离最近的城市作为解的一个构造 性元素,如此循环,直至一个较短的路线产生。构造性方法通常只能产生优化问 题的一个可行解,并不能保证所的解为最优。 1 优先分配规则( p r i o r i t yd i s p a t c hr u l e ) 规则性调度的基本思路是,针对所要优化的调度问题,先制定或选取相应的 优先规则,并且按相应规则对生产过程中的每个操作决定下一个需要加工的作 业。规则性调度的优点是直观、简单实用、花时较少。目前常用的优先分配规则 有s p t 、l p t 、l w k r 、m w k r 、f i f o 、l i f o 等。p a n w a l k a r s 总结了1 1 3 个调 第一章绪论 度规则,将其分为简单规则、复合规则、启发式规则3 类,并指出最好的优先分 配规则算法是几种优先分配规则的组合方法。k u r i y a nk e t a 1 分析了优先规则 对周期最短的生产调度问题的影响。对于多机置换f l o w s h o p 调度问题,文献( 郑 大钟) 提出了几种规则性方法,如p a l m e r 方法、g u p t a 方法、d a n n e n b r i n g 方法 等等【1 5 】。 2 基于瓶颈的启发式方法( b o t t l e n e c kb a s e dh e u r i s t i c s ) a d a m s 在1 9 9 8 年提出的移动瓶颈过程( s h i f t i n gb o t t l e n e c kp r o c e d u r e ) 是第 一个解决f t l 0 标准问题的启发式算法【”l 。移动瓶颈过程的思路是把优化问题化 为m 个单一机器问题,即m 个子问题,每次解决每一个子问题,把每个子问题 的解与所有其它的子问题的解比较,每个机器依它们的解的好坏排列,对优化指 标( 如最小化最大完成时间) 影响最大的机器被认为是瓶颈机器。移动瓶颈过程 对瓶颈机器排序,留下被忽视的未被排序的机器,固定已排序的机器。当每次瓶 颈机器排序后,每个先前被排定的有接受改进能力的机器,通过解决单一机器问 题方法,再次被局部重新优化。而单一机器问题的排序是用c a f l i e r 的方法旧通 过迭代来解决,此方法能快速给出一个精确解。文献 1 8 】提出了一种基于移动瓶颈 过程和禁忌搜索算法的混合算法,在算法中,利用移动瓶颈过程产生个初始解, 同时对禁忌搜索算法所产生的近优解进行局部优化,获得了满意的结果。 ( 二) 邻域搜索算法( l o c a ls e a r c hm e t h o d ) 邻域搜索算法的原理是以优化问题的一个初始可行解作为当前鳃,通过预 先设置解的邻域结构,在当前解的邻域内搜索比当前解更好的邻域解,并以此作 为新的当前解,重复上述移动,知道搜索到全局最优解。 邻域搜索算法一般包括遗传算法、模拟退火算法、禁忌搜索算法、闽值接 受算法等等。 1 遗传算法( g e n e t i ca l g o r i t h m ) 遗传算法( g a ) 是由j h o l l a n d 于1 9 7 5 年受生物进化论的启发而提出的。 它是一种基于“适者生存,劣者淘汰”原理的高度并行、随机和自适应的优化算 法,它将问题的求解表示成“染色体”的适者生存过程,通过“染色体”群的一 代代不断进化,包括复制( r e p r o d u c t i o n ) ,交叉( c r o s s o v e r ) ,变异( m u t a t i o n ) 等操作,最终收敛到最优个体,得到问题的最优解。其基本流程如下: s t e p l :令k o ,随机产生n 个初始个体构成初始种群p ( o ) ; s t e p2 :评价p ( k ) 中各个体的适应度( f i t n e s sv a l u e ) ; s t e p3 :判断算法收敛准则是否满足。若满足则输出搜索结果;否则执 下面步骤; 第一章绪论 s t e p4 :根据适应度大小以一定方式执行复制操作,从p ( k ) 中选取两个个 体; s t e p5 :产生随机数亭,若亭p 。,p 。为交叉概率,则对步骤4 所选出的两 个体执行交叉操作并将所得染色体放入临时种群中,否则直接将 它们放入临时种群中。重复步骤4 ,5 直至临时种群中染色体数目 为; s t e p6 :以概率n 对临时种群中个体执行变异操作,令k tk + 1 ,记此临时 种群为p m l ,返回步骤2 ; 尽管遗传算法具有并行搜索能力,在总体上把握了进化的方向,但是其局 部搜索能力较差,容易出现“早熟”现象。目前有很多对于遗传 算法进行改进的研究【1 9 , 2 0 1 。 2 模拟退火算法( s i m u l a t e da n n e a l i n g ) 模拟退火算法是基于固体退火过程由k i r k p a t r i c k 于1 9 8 2 提出的种邻域搜 索算法【2 1 】,采用了m e t r o p o l i s 接受准则,以一定概率接受当前解的劣质邻域解, 降低了算法陷入局部最优解的可能性,但是模拟退火算法对初始解很敏感,同时 依赖于控制参数的选取。l a a r h o v e n 和m a t s u o 于1 9 8 8 年首先把模拟退火算法用 于j o bs h o p 调度问题,y a m a d a 在1 9 9 6 年用模拟退火算法首次得到了f t i o 问题 的最优解。模拟退火算法的基本流程如下: s t e p l :产生一初始解x o ,当前解t 。:- x o ,最优解x l ,最优目标值 ( x + ) 净f ( x o ) ,确定初始温度t ,0 ; s t e p2 :设每个温度下丁迭代次数为n ( r ) : a :从当前解t 。的邻域 。) 中随机产生一个解_ 蚶; b :计算t ,帆。l g ) 一,( w ) ; b l :若 0 ,则k ,x n 耐; 否则,产生随机数亭( o ,1 ) ,若亭 e x p ( - a t ) ,则t 。,蛳; b 2 :若f ( x n 。枷) f ( x ) ,x i 矗耐,o ) 厂阮耕) 5 重复步骤2 共n ( t ) 次; s t e p3 :t 一6
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年黑龙江能源职业学院高职单招笔试语文历年参考题库含答案解析
- 2026年黑龙江农业经济职业学院高职单招笔试职业技能测验历年参考题库含答案解析
- 2026年驻马店职业技术学院高职单招笔试化学历年参考题库含答案解析
- 2026年长沙民政职业技术学院高职单招笔试职业技能测验历年参考题库含答案解析
- 2026年长春健康职业学院高职单招笔试职业技能测验历年参考题库含答案解析
- 2026年金肯职业技术学院高职单招笔试语文历年参考题库含答案解析
- 2026年郑州黄河护理职业学院高职单招笔试化学历年参考题库含答案解析
- 2026年郑州商贸旅游职业学院高职单招笔试英语历年参考题库含答案解析
- 水产品原料处理工岗前行业知识考核试卷含答案
- 系统护理对糖尿病肾病患者实验室指标的影响分析
- 2026年中国出口信用保险公司招聘笔试大纲及备考指南
- 中小学以体育强化为核心落实“健康第一”教育理念实施方案
- 间羟胺药物课件
- 2026年深泽县辅警招聘考试备考题库必考题
- 江苏省南京市玄武区2025-2026学年九年级上学期期中历史试卷(含答案)
- 上海交易集团秋招面笔试题及答案
- 整县屋顶分布式光伏项目绿色施工方案
- GB/T 4337-2025金属材料疲劳试验旋转弯曲方法
- 手术室精益管理汇报
- T/CAR 10-2022食品速冻装置隧道式速冻装置
- 景区团建合同协议书范本
评论
0/150
提交评论