（控制理论与控制工程专业论文）智能优化算法在车间生产控制中的应用研究.pdf

摘要 智能优化算法在车间生产控制中的应用研究 硕士研究生：陈琳导师：严洪森教授 东南大学 摘要 随着经济全球化发展，市场竞争越来越激烈，企业要想在这样的环境中生存并取得成功，就迫 切需要加强企业的信息化建设。论文研究了敏捷制造环境下，智能优化算法在车间生产控制中的应 用问题，同时论述了计算机集成制造环境中，n e t 平台下基于c s 三层体系结构的车间生产控制系统 的开发。 论文重点探讨了车间生产控制中的两个方面问题：一是汽车装配车间生产计划与调度的集成优 化问题，二是并行机生产环境下的模糊生产车间调度问题，然后分别对这两个问题进行了数学建模， 并选择与设计算法来求解模型。 首先，针对车间生产计划与调度的集成优化问题，将汽车装配线简化为一个f l o w s h o p ，并建立 其混合整数规划模型，求得问题的粗生产计划，在此基础上考虑装配线的细节，用改进的模拟退火 算法和快速调度仿真相结合的方法使生产计划与调度同时得到优化。然后，根据三种不同的寻优组 合论述了该算法的实现。通过具体算例研究，对算法进行了比较和性能分析。 其次，针对并行机生产环境下的模糊生产车间调度问题，论文在同时考虑了模糊加工时间和模 糊交货期的基础上建立了该问题的数学模型，利用混合模糊遗传算法使生产调度得到了优化。同时 通过具体算例研究，对该算法进行详细地分析。 接着，论文进行了车间生产控制系统的总体架构设计、开发工具的选择、u m l 建模和数据库设 计，给出了设计过程中的部分用例图、类图、顺序图、协作图以及数据库模型。同时，针对该系统 实现时出现的难点，本文还具体研究了系统开发过程中的一些关键技术，如存储过程的设计、查询 优化设计、权限管理等等。 最后，对论文的内容进行了总结，并讨论了需要进一步研究的一些问题。 关键词：生产控制，计划与调度，模糊调度，模拟退火算法，遗传算法，u m l 东南大学硕士学位论文 a p p l i c a t i o nr ese a r c hi n t o i n t e l l i g e n to p t i m i z a t i o n a l g o r i t h m sf o r p r o d u c t i o n c o n t r o l 烈w o r k s h o ps m a s t e rc a n d i d a t e ：e l l e nl i n s u p e r v i s e db yp r o f y a nh o n g - s e n s o u t h e a s tu n n 翟r s i t y a b s t r a c t w i t ht h ed e v e l o p m e n to fe c o n o m i cg l o b a l i z a t i o n ，t h em a r k e tc o m p e t i t i o ni s b e c o m i n gf i e r c e r e n t e r p r i s e sp r e s sf o ra c c e l e r a t i n gt h ea p p l i c a t i o no fi n f o r m a t i o n i z a t i o nt os u r v i v ea n ds u c c e e di n t h i s e n v i r o n m e n t t h ea p p l i c a t i o no fi n t e l l i g e n to p t i m i z a t i o na l g o r i t h m sf o rp r o d u c t i o nc o n t r o li na g i l e m a n u f a c t u r i n gi ss t u d i e dh e r e t h ed e v e l o p m e n to fw o r k s h o pp r o d u c t i o nc o n t r o ls y s t e mi si m p l e m e n t e do n c st h r e el a y e r sa r c h i t e c t u r ei nc o m p u t e ri n t e g r a t e dm a n u f a c t u r i n g ，b a s e do n n e tp l a t f o r m t w oa s p e c t so ft h ep r o d u c t i o nc o n t r o l p r o b l e ma r ef o c u s e d l yd i s c u s s e d ：o n ei st h ei n t e g r a t e d o p t i m i z a t i o np r o b l e mo fp r o d u c t i o np l a n n i n ga n ds c h e d u l i n go na u t o m o b i l ea s s e m b l yw o r k s h o p ，a n dt h e o t h e ri st h e 呦s c h e d u l i n gp r o b l e mu n d e rt h ec i r c u m s t a n c eo fp a r a l l e lm a c h i n e si nw o r k s h o p t h e m o d e l so ft h e s et w op r o b l e m sa r ep r e s e n t e ds e p a r a t e l y , a n dt h e nt h ea l g o r i t h m sa r ec h o s e na n dd e s i g n e di n o r d e rt os o l v et h em o d e l s f i r s t l y ，a i m i n ga tt h ei n t e g r a t e do p t i m i z a t i o np r o b l e mo fp r o d u c t i o np l a n n i n ga n ds c h e d u l i n gi n w o r k s h o p ，t h ea u t o m o b i l ea s s e m b l yl i n ei ss i m p l i f i e di n t oaf l o ws h o ps ot h a ti t sm i x e di n t e g e r p r o g r a m m i n gm o d e lc a nb ef o r m u l a t e dt oo b t a i nar o u g hp r o d u c t i o np l a n b a s e do nt h i sp l a n ，t h ei m p r o v e d s i m u l a t e da n n e a l i n ga l g o r i t h mw i t hq u i c ks c h e d u l es i m u l a t i o ni su s e dt oo p t i m i z et h ep r o d u c t i o np l a n sa n d s c h e d u l e ss i m u l t a n e o u s l y t h ei m p l e m e n t i n go ft h ea l g o r i t h mi sp r e s e n t e da c c o r d i n gt ot h r e ed i f f e r e n t o p t i m i z i n gs e a r c hc o m b i n a t i o n s t h r o u g hs e v e r a lc o m p u t a t i o n a le x a m p l e s ，t h ea l g o r i t h m sa r ec o m p a r e d a n da n a l y z e d s e c o n d l y , a i m i n ga t t h e f u z z ys c h e d u l i n gp r o b l e m ，am a t h e m a t i cm o d e l i se s t a b l i s h e dw h i l e c o n s i d e r i n gt h ef u z z yp r o c e s s i n gt i m ea n df u z z yt a r d i n e s ss i m u l t a n e o u s l y b yu s i n gt h eh y b r i df u z z y g e n e t i ca l g o r i t h m ，t h eo p t i m i z e ds c h e d u l e sa r eo b t a i n e d t h r o u g hs o m ec o m p u t a t i o n a le x a m p l e s ，t h e a l g o r i t h mi sa n a l y z e di nd e t a i l t h i r d l y ，t h es t r u c t u r ed e s i g no ft h es y s t e m ，t h ec h o o s eo ft h ed e v e l o pt o o l s ，t h eu m lm o d e l i n ga n d t h ed a t a b a s ed e s i g na r ea d d r e s s e dh e r e s o m eu s ec a s ed i a g r a m s ，c l a s sd i a g r a m s ，s e q u e n c ed i a g r a m sa n d d a t a b a s em o d e l so ft h es y s t e ma r ep r e s e n t e d a c c o r d i n gt ot h ed i f f i c u l tp o i n t si nt h ed e v e l o p m e n tp r o c e s s ， s o m ec r i t i c a lt e c h n i q u e sa r es t u d i e dd e t a i l e d l y , i n c l u d i n gt h ed e s i g no fs t o r e dp r o c e d u r e ，t h ed e s i g no f o p t i m i z e dq u e r ym e t h o d ，t h ej u r i s d i c t i o nm a n a g e m e n t , a n ds oo n f i n a l l y 。t h et h e s i si ss u m m a r i z e da n dd i s c u s s e da b o u ts o m ea s p e c t st h a ts h o u l db es t u d i e di nt h e f u t u r e 。 k e yw o r d s ：p r o d u c t i o nc o n t r o l ，p l a na n ds c h e d u l e ，f u z z ys c h e d u l e ，s i m u l a t e da n n e a l i n ga l g o r i t h m ， g e n e t i ca l g o r i t h m ，u m l i l 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 研究生签名：坪日 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容 和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以 公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办 理。 研究生签名：砰导师签名： 日期： 第一章绪论 1 1 课题背景 1 1 1 车间生产控制技术概述 第一章绪论 一个企业的生产目的主要是制造产品、提供服务，满足社会需要，以此获得经济效益。因此， 生产是企业活动的中心，而车间生产控制是企业活动的重要环节。在车间生产控制过程中，企业按 照预先确定的产品数量、质量和完成期限，运用科学的方法，经过周密的计划与安排，以特定的工 艺流程，生产出合乎标准满足用户需要的产品。 车间生产控制系统1 1 】是生产管理信息系统的一个子系统，主要任务包括生产过程的基础信息管 理，综合生产计划的制定，车间生产调度的实现等技术及其在企业生产中的应用等方面。 车间生产计划主要任务包括：生产准备的检查、生产任务的排定以及生产能力的细致核算与平 衡。具体来说，就是根据下达的订单及零部件的工艺路线，以及车间的实际生产能力制定车间生产 计划，并按照一定的规则进行生产调度，安排日常的生产，及时了解生产进度，预测和发现生产中 的问题，并加以解决，使实际生产接近计划。按照计划周期长短，一般把生产计划分为年度计划、 季度计划、月计划、周计划和日计划。究竟将生产任务下达到哪台设备，哪个工人，何时下达，下 达多少，就是生产调度所要解决的问题。 车间生产调度【2 】是整个车间生产控制系统的核心，主要任务是对可用的加工设备集合、操作者 集合以及原料集合在时间上进行加工任务分配，通过任务调度来解决资源的最优安排，为计划的执 行和控制提供指导，实现生产能力的综合平衡。车间生产调度是生产计划工作的继续，是企业生产 计划的具体执行。它根据上级生产计划规定的产品品种、数量及大致的交货期的要求对每个生产单 位( 工段、班组、工人等) ，在每个具体时期( 月、日、班等) 内的生产任务做出详细规定，使生产 计划得到具体落实。实际生产过程中，生产计划调度实行的成功与否，对减少在制品库存、提高交 货期满意率、缩短供货周期和提高生产率都有重要作用。 随着经济全球化的发展，企业的生产特性发生了根本性变化，客户需求的个性化，市场变化的 动态化，导致市场竞争越来越激烈。因而生产控制系统作为企业上层计划和底层调度控制的纽带， 其重要性也愈加凸显。一个好的生产控制系统能够对车间级生产计划和调度的优化、生产过程的改 进工作起到重要的促进作用，大大简化企业的生产控制工作，并能提高控制的精确度和企业资源的 利用率，从而最终实现提高企业经济效益的目的。 1 1 2 智能优化算法概述 2 0 世纪8 0 年代以来，一些新颖的优化算法，如人工神经网络、混沌、遗传算法、进化规则、 模拟退火、禁忌搜索及其混合优化策略等，通过模拟或是揭示某些自然现象或统计力学等方面，为 解决复杂问题提供了新的思路和手段。在优化领域，由于这些算法构造的直观性与自然机理，因而 通常被成为智能优化算法( i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ) 或现代启发式算法( m e t a - h e u r i s t i c a l g o r i t h m s ) 1 3 。 智能优化算法【4 】是借鉴和利用自然界中自然现象或生物体的各种原理和机理而开发并具有自适 应环境能力的计算方法，与传统数学规划方法相比，其优越性主要体现在：1 具有一般性且易于应 用；2 搜索最优解的速度快且易于获得满意的结果。 智能优化算法的主要应用对象是优化问题中的n p ( n o n d e t e r r n i n i s t i cp o l y n o m i a l ) 困难问题，目 前已被广泛应用于车间控制问题中。当机器数m 3 的刀个工件的生产调度问题一般是n p 困难 东南大学硕士学位论文 ( n p h a r d ) 的，随着工件和机器数量的增加，问题的搜索空间随之成指数性增大，当达到一定规模 时就很难在可接受的时间内得到较优的解。而借助于待求解问题的相关专家知识，或结合问题的特 有知识和特征以确定算法的搜索方向，往往能够有效地减少搜索空间，简化搜索从而提高算法的搜 索能力，极大地提高找出较优解的机会，减少求解问题所需要的计算时间，从而获得更好的计算性 能。 常用的智能优化算法包括禁忌搜索、遗传算法、模拟退火算法、蚁群算法、人工神经网络等等。 本文主要研究模拟退火算法和遗传算法在车间生产控制中的应用。 1 1 3 车间生产计划与调度系统的现状与趋势 在汽车装配线的敏捷制造环境中，要实现敏捷响应用户需求而不增加生产成本，就需要生产成 本与批量无关，即要求汽车装配线能够装配任意混批甚至单辆汽车。由于汽车的品种、批量、混批 经常会发生变动，因此必须要综合考虑汽车装配线的生产计划与调度，控制整个装配工位的装配节 奏，使其负荷均衡并保持与大规模生产线一样的资源利用率【5 】。 目前比较常见的车间生产管理软件大多从财务管理和物料管理的角度出发，对车间生产控制这 一部分涉及不深，基本不能给出详细的工序级作业计划，往往还是要在车间现场根据经验进行生产 调度，没有科学性的保证，从而也很难实现提高生产效率和经济效益的目的。而即使考虑到优化设 计的车间生产控制系统软件，也通常把优化的重点都放在生产调度的优化上，忽略了生产计划的优 化，从而很难使计划与调度达到同时优化，从而也就难以实现真正的敏捷制造。 因此，要想为企业带来巨大的经济效益，车间生产计划与调度系统应充分考虑到车间生产中的 各种信息，为企业生产提供优化的计划调度方案，做到既满足生产要求，又降低生产成本。 1 1 4 模糊生产车间调度问题的现状与趋势 在过去几十年里，研究工作主要集中于精确的作业车间调度问题。在精确的作业车间问题中， 工件加工时间和交货期都是已知的确定量，而在实际的生产加工过程中，由于大量的随机和不确定 因素的存在，如机器故障、环境参数、新产品开发等，特别当涉及到人力等主观因素的情况时，如 操作工人的熟练程度等，致使包括时间在内的相关知识无法用精确数据对其进行描述。因此，把加 工时间和交货期按模糊数处理更加符合生产实际，这类作业车间调度问题，称为作业车间模糊调度 问题1 6 1 。 随着模糊数学的发展，模糊数学规划的思想被运用到调度领域，形成非确定性调度的一个重要 分支模糊调度1 7 j 。由此，模糊交货期、模糊加工时间的调度问题就开始逐渐得到重视，由于作 业车间调度问题本身的难处理性和复杂性，许多学者对此进行了研究，并提出了多种解决方法。近 年来，智能优化算法的发展，引起了人们用该方法求解作业车间调度问题的研究。但是，对这方面 问题已有的研究，往往单独考虑模糊加工时间或模糊交货期，因此，综合考虑两者的研究就更加具 有重要的现实意义。本文针对并行机生产环境下的模糊生产车间调度问题，提出拖期可信度指标， 并以此为调度优化目标，建立其混合整数规划模型，最后设计算法进行求解。 1 2 课题介绍 本课题是国家8 6 3 计划先进制造技术领域现代制造集成技术专题探索导向类课题“混批生产车 间作业计划与调度的集成优化和仿真系统”( 2 0 0 7 a a 0 4 2 1 1 2 ) 和国家自然科学基金资助项目“制造 系统成品需求短期预测模型研究及应用”( 5 0 8 7 5 0 4 6 ) 。 课题的主要内容是研究智能优化算法在车间生产控制中的应用，主要侧重于两个课题敏捷 制造模式下汽车装配车间生产计划与调度的集成优化问题，及并行机生产环境下的模糊调度优化问 题，分别构建了其数学模型，针对问题各自不同的特点，选择并设计算法求解模型。同时，完成了 2 第一章绪论 计算机集成制造环境中，汽车装配车间生产控制总系统的开发，下分两个子系统计划与调度集 成优化子系统和模糊生产车间调度子系统，分别对应于本文研究的两个主要课题。并通过大量算例 分析验证了智能优化算法在车间生产控制中的应用能够极大地提高企业生产控制的效率和准确度， 并因此能为企业取得显著的经济效益。 因为该系统的应用主要在企业决策层，故采用c s 结构，相对b s 结构可以减小系统运行的复 杂性同时缩短算法运行时间。与n e t 相比v c + + 的运行速度更快，因而选择使用v c + + 6 0 编制算法。 程序中的参数的读取等操作采用通过m f c 访问o d b c 的方法实现。考虑到n e t 的用户界面制作简 单美观，对数据库的连接及操作更加简洁高效，所以总系统用户界面和基础数据管理模块均采用 c 撑n e t 开发。运行子系统算法软件时，可以从n e t 界面按钮链接到m f c 的已编译的程序，这样 做可以综合两者的优点。 开发过程中同时考虑了软件的开放性，提高了系统的可扩展性、高质量和稳定性。系统结构清 晰，维护方便，可适应不断变化的业务要求。 由上可见，本课题的研究，既是保障当前企业生产经营活动的需要，也是企业适应市场变化， 不断寻求进一步发展的需要。 1 3 论文结构 本文研究了在敏捷制造环境下通过智能优化算法实现汽车装配车间计划与调度的集成优化，以 及模糊生产环境下生产调度的优化方法。针对这两个侧重点分别建立了优化模型，选择、设计了相 应的算法予以求解，然后提出了装配车间生产控制系统的整体架构，在此基础上分析、设计、实现 了此生产控制总系统，总系统下根据研究的侧重点不同构建了两个优化子系统，并对子系统的设计 也做了进一步详细地分析。论文结构如下： 第一章绪论：简要介绍了课题的背景及其研究意义。 第二章装配车间生产计划与调度集成优化方案研究：根据某总装厂装配车间的实际情况，研 究了f l o w s h o p 车间生产计划和调度的集成优化问题。 第三章模糊生产环境下生产调度问题的优化方案研究：根据总装厂装配车间的实际情况，研 究了并行机生产环境下模糊调度的优化问题。 第四章车间生产控制系统的总体设计：研究了系统整体架构，数据库管理系统的选择，系统 开发平台和开发工具的选择等等。介绍了车间生产控制系统的概况、总体目标以及设计原则；然后 主要以生产计划与调度集成优化子系统为例，给出了需求分析及u m l 建模，其中包括用例图、类 图、顺序图、协作图等等；最后详细讨论了数据库的概念结构设计和逻辑结构设计。 第五章系统开发过程中的实现技术：对上一章的分析结果进行细化，针对车间生产控制系统 实现时出现的难点，详细研究了系统开发过程中的关键技术，如存储过程的设计，数据统计多样性 技术等等。 第六章总结与展望：总结论文中的工作，并提出了有待进一步研究的问题。 3 东南大学硕士学位论文 第二章装配车间生产计划与调度集成优化方案研究 2 1 生产计划与调度研究概述 企业的生产计划1 1 1 是根据市场需求和企业生产能力的状况，对生产系统的产出品种、产出速度、 产出时间、劳动力和机器设备以及库存等冈素所预先进行的考虑和安排。在现代企业中，如果没有 一个严密的计划，企业的生产经营活动就会陷入混乱。计划是执行的依据，又是实行控制的标准。 生产计划的主要内容包括：确定生产指标；核算生产能力，并与生产任务进行平衡；合理安排产品 生产进度；组织和检查生产计划完成情况，提出改进生产的建议等等。 生产计划问题的一般提法是，在一定的时间范围内，确定每个周期内每种产品( 包括产品类型 ( p r o d u c tt y p e ) 、产品族( p r o d u c tf a m i l y ) 、单个产品( p r o d u c ti t e m ) 、部件( c o m p o n e n t s ) 、零件( p a r t ) 等) 的生产数量，使得总的生产成本最小( 生产成本包括在制品库存成本( w o r ki np r o c e s si n v e n t o r y ) ， 最终产品库存成本( f i n i s h e dg o o d si n v e n t o r y ) ，最终产品欠产成本( b a c k l o g ) ，设备使用成本，加班 成本( o v e r t i m e ) ，生产准备成本( s e t u p ) 等) ，同时满足生产系统动态方程，生产能力约束，递阶 关系约束等约束条件。 按照计划周期的长短，般可将生产计划划分为长期计划、中期计划和短期计划三类j 1 长期生产计划主要解决的是企业在较长一段时间的发展规划，时间跨度以年为单位，至少为 1 年或更多，一般受市场环境影响比较大，不确定性因素多，很难建立一个合适的数学模型进行定 量优化，多数是定量和定性分析相结合。 2 中期生产计划是企业在近期内的一个生产规划，时间跨度以月为单位，主要确定最近几个月 或半年左右的生产任务，比长期生产计划考虑的不确定因素要少，但是考虑的生产因素更细致。中 期生产计划通常使用一些简单的方法( 如绘制相应图形或表格、计算机仿真和启发式规则) 来解决， 如果费用结构比较简单时也可以采用建立数学模型的方法来解决。 3 短期生产计划是中期生产计划的一个分解，主要是制定数个工作日或工作周内的生产任务， 通过该计划可以清楚地知道每个工作日生产何种产品和产品的生产数量。短期生产计划考虑的生产 环节最细致，不确定性因素也最少，因此可以建立详细的生产计划模型，并采用相应优化方法进行 解决。 而生产调度问题则通常被描述为：“在某一时间期限内分配一组机器来执行生产订单任务”p j ， 是针对一项可分解的生产任务，探讨在尽可能满足约束条件( 如交货期、工艺路线和资源情况等) 的前提下，通过下达生产指令，安排其组成部分( 操作) 使用哪些资源、其加工时间及加工顺序， 以获得生产任务执行时间或成本的最优化。调度问题( s c h e d u l i n gp r o b l e m ) 属于n p 困难问题，其 求解有相当的难度。生产调度问题也可以看成是一个排序问题【l0 1 ，在己知生产任务的边界条件下( 即 生产区间) ，如果生产任务的加工顺序确定了，那么生产任务的开始时间也就确定了。 调度问题分类方法很多，主要有以下几种【2 】： 1 根据资源类型、被调度工件的工序数量及工序问相互顺序，生产调度可以分为：作业车间调 度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，j s s p ) 、流水车间调度问题( f l o w - s h o ps c h e d u l i n gp r o b l e m ， f s s p ) 、机器调度问题( m a c h i n es c h e d u l i n gp r o b l e m ，m s p ) 等几个基本类型。f s s p 是指刀个工件 要在m 台机器上加工，每个工件需要经过m 道工序，每道工序要求不同的机器。刀个工件在m 台机 器上的加工顺序相同。工件i 在机器歹上的加工时间为岛。问题的目标是求栉个工件在每台机器上 的最优加工顺序使最大流程时间达到最小；j s s p 是指给定一个工件的集合和一个机器的集合，每个 工件包括多道工序，每道工序需要在一台给定的机器上非间断地加工一段时间，每台机器一次最多 4 第二章装配车问生产计划与调度集成优化方案研究 只能加工一道工序。调度的目标就是将工序分配给机器上的某个时段，使所有工件在最短的时间里 完成加工；m s p 是指有小台机器，要加工疗个彼此无关的工件；每个工件可以在任何一台机器上用 一道工序加工完成，且加工时间一定。调度的目标是在给定的机器上分配加工任务并安排任务的加 工顺序，使一些性能的度量最优，例如加工的流程时间最短，所有工件在制定交货期内完工或平均 拖延时间最小等。实际的调度问题通常是上述几种调度类型的复杂组合。 2 根据优化准则，可以分为基于代价和基于性能的调度两大类。基于代价包括为了实现调度方 案所消耗的各种费用和所造成的损失，如存储费用、延期交货损失等。基于性能主要包括设备利用 率、最大完成时间等。 3 根据生产环境的特点，可将调度分为确定性调度和模糊调度。前者指加工时间等参数是已知 的、确定的量；而后者的加工时间等参数是不确定的模糊数。 4 根据加工任务或被加工工件的特征，可分为静态调度和动态调度。静态调度是指所有待安排 加工的工件均处于待加工状态，加工过程中不会改变；动态调度是指作业依次进入待加工状态，各 作业不断进入系统接受a l t o ，同时完成加工的作业又不断离开，作业环境中还有可能出现其他不可 预测的动态扰动。 在对调度问题进行研究的方法上，最初是集中在整数规划、仿真和简单的规则上1 1 1 | 。随着各种 新的相关学科与优化技术的发展，智能优化算法越来越多地应用在了调度领域中，比如神经网络、 模拟退火、遗传算法、禁忌搜索等，使得调度问题的研究向多元化方向发展。 由上面的分析可知，生产计划和调度问题是紧密关联。生产计划的分解结果是进行调度的前提 条件，而调度的结果则可以反映一个生产计划制定的优劣，如果生产计划制定不合理，则很有可能 得不到可行的调度解。但是由于生产系统的复杂性，传统的解决方法一般是将它们分开单独求解的， 这样做很难实现整体优化，因此许多学者纷纷转向生产计划与调度的集成优化理论的研究上来，这 也已经成为作业管理研究的一个新热点。实现生产计划与调度的整体优化是目前这一领域的主流研 究方向之一。 2 2 装配车间生产计划与调度集成优化模型 2 2 1 问题概述 生产计划与调度的合理与否，是能否实现汽车装配线敏捷制造的关键。如果生产计划与调度不 好，各装配工位的负荷严重失衡，有些工位负荷过重引起阻塞，另一些工位负荷过轻出现空闲，势 必造成整条装配线的资源利用率严重低下，从而引起生产成本远远高于预计成本的严重后果。 因此，为解决敏捷制造环境中汽车装配线生产计划与调度的整体优化问题，实现计划与调度的 “无缝”集成，使各装配工位的负荷均衡性达到整体优化，本文提出一种解决方法。其基本思想是： 将汽车装配线简化为一个f l o w s h o p 问题，建立其混合整数规划模型，并由此求得使各装配工位的 资源利用率和准备成本达到整体优化并尽可能满足需求的粗生产计划l l 引，然后在粗生产计划的基础 上，考虑装配线的细节，建立求解生产计划与调度整体优化问题的数学模型。用模拟退火( s i m u l a t e d a n n e a l i n g ) 算法 1 3 , 1 4 与快速调度仿真1 1 5 , 1 6 相结合的方法使生产计划与调度达到整体优化。 2 2 2 集成优化模型及其约束 假设一条装配线共有m 个装配工位，计划区间内依据装配订单一共需要装配”种汽车，并且第 f 种汽车需要4 辆。再将装配线简化为一个f l o w - s h o p 问题。同时，最优计划的目标是最大限度地 满足产品需求，并使各装配工位的准备成本和空闲时间尽可能少。由此可建立求解最优粗生产计划 的混合整数规划模型t 1 6 口t ： 5 东南大学硕士学位论文 式中 n埘m m i n j = a ( x j 一碣) + + 町( 碣一) + 】+ b us g n ( x , ) + c j r j ，= 1 j = l i = l j = l 虬t e t , j x , + f ，s g n ( ) + 乃= 局 ，= ii = 1 t o 且为整数，乃0 ，= 1 ，2 ，m 行为计划区间内需装配的汽车种类数； m 为汽车装配线上的装配工位数； 靖为计划区间内装配第f 种汽车的产量，是整数； s g n ) 为符号函数，当蚌加时，s g n ( x f ) 取l ，否则取o ； 盔为计划区间内对第f 种汽车的需求，是整数； ( 2 1 ) ( 2 2 ) ( 2 3 ) 弓为计划区间内第_ ，个装配工位的空闲时间； 历为计划区间内第j 个装配工位的可用时间，是从计划区间内的生产总时间中扣除设备故障维 修时间等所剩的时间； 式中 a i + 为超产一辆第f 种汽车的存储及占用流动资金的成本； a i 一为欠产一辆第i 种汽车而违约受罚的成本； 为第f 种汽车在第，个装配工位上的准备成本； c ，为与第，个装配工位资源闲置有关的成本系数； ，f ，为第，个装配工位装配第f 种汽车所需要的时间； 出，为第i 种汽车在第，个装配工位上的准备时间。 式2 1 2 3 的混合整数非线性规划模型可转化为混合整数线性规划模型如下： m i n j = ( 彳+ 而+ 口一五) + 乃+ 勺乃 i = 1j = li = lj = l h s t f 薯+ 勺咒+ 乃= 历 f = li = 1 x i 一公x i + a x l = d l b y i 2 x i t 0 且为整数，乃( 0 ，1 ) ，乃o ，a + 薯0 ，a 一葺0 ，= l ，2 ，m 乃是布尔变量，当薯 0 时为l ，否则为o ； b 是一个大的正数。 6 ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) 第二章装配车间生产计划与调度集成优化方案研究 式2 4 2 8 的混合整数线性规划模型可用分枝定界法或单纯形法求解【17 1 ，得到使各装配工位的资 源利用率和准备成本达到整体优化并尽可能满足产品需求的粗生产计划。这样设计可以加快问题的 求解速度。另外，考虑细节的装配线调度往往是一个非结构化问题，很难用解析的方法求解，较为 可行的办法是使用基于可变时间流的快速调度仿真1 1 6 】。最后，利用模拟退火算法搜索来解决最优计 划与调度的选择问题。 为节省汽车装配准备时间，同种汽车集中装配，不分割成多个装配任务，并在调度时仅占用一 个排序位置。参照式2 1 2 - 3 ，则求解汽车装配车间生产计划与调度集成优化问题的数学模型可描述 如下： 吵g ( 擗哮 私即，( x ( s , 0 - - ，) + 以即，) + + 气印) s g n ( x ( 鼬) ) + 勺乃+ r i ( x ，s ) j = ti = l= l + g 姜 ( 局一乃) 一去芸( 岛一勺) 2 ) s t e t u ( s , o j ( 即) + ms g n ( x ，, ( 劫+ 乃= 岛 h ( 4 s ，f ) ) 虬( s ，i ) ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) ( s ，) 0 且为整数，一0 ，- ，= l ，2 ，m ( 2 1 2 ) 式中 ( s ，f ) 为疗种汽车或其中部分通过装配线的顺序( 调度) s 中的第f 个位置所对应的汽车种类， 如果对于k i 玎有( s ，f ) = 0 ，则表示调度s 中最多只包含k 1 种汽车； 气( s ) 为第4 s ，f ) 种汽车在第_ ，个装配工位上的准备成本； 0 ( s ，f ) j 为第( s ，f ) 种汽车在第，个装配工位上的准备时间； 办( ( s ，功为第( s ，f ) 种汽车的下线时间； 虬( s ，f ) 为第( s ，f ) 种汽车的交付期； x = ( ( s 。1 ) ，( s ，2 ) ，( s ，。) ) 7 为生产计划向量： f ( x ，s ) 为汽车装配任务全部完成的时间，由相应计划和调度共同决定； ，为任务完成时间权系数； g 为各装配工位负荷均衡权系数。 粗生产计划的求解方法介绍如下( 程序框图如图2 1 所示) ： 7 东南大学硕士学位论文 图2 1 粗生产计划求解程序框图 在这里直接使用o d b ca p i 编制应用程序，实现数据的读取、插入以及修改功能。根据平滑定 单给出的需求计划r g n 】( 需求的汽车种类为 ，需求分别为d 【o 】，d 【l 】，d i n l 】) ，通过单纯形法求 得一个最优值，但这个值不一定就是最优的整数解，所以需要对获得的最优解判断其是否为整数解。 若为整数解，则将其作为粗生产计划；否则对其进行分枝定界： 第一步：分枝，假设原模型问题为问题a ，任选其中的一个非整数解x i 】，其值为d 刀，如 d i 1 = 1 7 5 ，构造两个约束条件： d i 】1 7 ；d i 】1 8 将这两个约束分别加入到原问题a 上，则分解为两个子问题a 1 和a 2 ( 即两支，左右分枝) ，左分 枝增加约束条件d 【f 】1 7 得到问题a l ，右分枝增加约束条件d 【刀1 8 得到问题a 2 ，求此两个后继 子问题的解。 定界，以每个后继问题为一分枝表明求解的结果，与其它问题的解的结果相比较，找出性能指 标最好的作为新的上界。 第二步：比较与剪枝，各分枝中的性能指标值若有大于上界的，则剪掉此枝，否则重复第一步 骤。一直到求得整数解为止。 分枝定界法求得的粗生产计划是最优的整数解，但随着问题规模的增大，分枝会越来越复杂， 其个数以2 的指数增加，最多的分枝节点个数为2 ”。这样问题的复杂度也随之增大，求解的速度明 显下降，故当问题复杂度大时( 在装配线上指当需求的汽车种类超过1 0 时) ，直接采用单纯形法求 解，然后对求得的解取整。 2 3 模拟退火算法原理及设计 2 3 1 模拟退火算法理论 模拟退火算法【1 8 , 1 9 】( s i m u l a t e da n n e a l i n g ，s a ) 是1 9 8 3 年由k i r k p a t r i c k 首次提出的一种组合优 化算法。该算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部 粒子随温度上升变为无序状态，内能增大。而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态， 最后在常温时达到基态，内能减为最小。s a 算法借鉴热力学中的能量方程，同时又引入了m e t r o p o l i s 接受准则，是用一组称为冷却进度表的参数控制算法进程的一种解大规模组合优化问题的有效近似 算法。粒子在温度t 时趋于平衡的概率为e e ( k t ) ，其中e 为温度t 时的内能，e 为其改变量， 8 第二章装配车间生产计划与调度集成优化方案研究 k 为b o l t z m a n n 常数。算法的基本思想是从一给定解开始，从邻域中随机产生另一个解，接受准则 允许目标函数在有限的范围内变坏，以一定概率接受较差的解。用固体退火模拟组合优化问题，将 内能e 模拟为目标函数值，温度t 演化成控制参数f ，即得到解组合优化问题的模拟退火算法：由 初始解i 和控制参数初值t 开始，对当前解重复“产生新解一计算目标函数差_ 接受或舍弃”的迭 代，并逐步衰减t 值，算法终止时的当前解即为所得近似最优解，s a 已经被证明是一种依概率l 收 敛于全局最优解的优化方法。 s a 算法流程图如图2 2 所示： 图2 2s a 算法流程图 s a 的迭代搜索过程以b o l t z m a n n 分布概率接受目标函数的“劣化解”，所以s a 具有脱离局部 最优陷阱的能力，能以较高的精度收敛于整体最优解，而且具有高效、鲁棒、通用、灵活的优点。 s a 算法的应用很广泛，在求解最大截问题( m a xc u tp r o b l e m ) 、0 1 背包问题( z e r oo n ek n a p s a c k p r o b l e m ) 、图着色问题( g r a p hc o l o u d n gp r o b l e m ) 、调度问题( s c h e d u l i n gp r o b l e m ) 等方面效率较 高。 2 3 2 算法的设计和实现 根据上述的分析，本文选择使用s a 算法来解决生产计划与调度的集成优化问题。另外，针对 问题的复杂性和具体研究对象的特殊性，本文对该算法做出了相应地改进设计： 1 首先考虑到我们需要同时优化生产计划和调度，因此需要优化算法中相对应的两条编码，因 此需要两个s a 算法，互相组合已实现计划与调度的同时优化； 9 东南大学硕士学位论文 2 由于s a 算法的搜索过程是随机的，并且当退火的控制参数，值较大时可以接收部分恶化解， 因而，在算法中设计增加一个记忆器1 2 0 , 2 1 】，以记住搜索过程中遇到过的最好结果。退火过程结束时， 将所得的最终解与记忆器中的解比较并取较优者作为最后结果。由此，对算法改进得到带有记忆的 s a 算法； 3 同时，在当前解搜索的邻域中，引进t a b u 搜索算法机制，即通过嵌入t a b u 搜索算法的记忆 过程将搜索过的解保存在记忆近期操作的t a b u 表中，找到一个较优的解，然后在新解的邻域中，继 续搜索较好的解。这样设计可以避免很多无效的搜索，达到快速寻优的目的。 4 最后，关于两种s a 算法基于生产计划和调度不同寻优组合的方法，具体分析可以得到三种 设计方法，对应地可以将集成优化问题分为三种模式：串行式、交替式和嵌入式。其中串行式最简 单，嵌入式最复杂。具体设计思路如下： 2 3 2 1 嵌入式s a 算法( e s a a ) 嵌入式s a 算法的基本思想是以本章第二节中根据给出的需求计划求得的粗生产计划为初始 解，在计划层用s a 算法进行搜索，寻找最好的计划，并对计划层m a r k o v 链中随机产生的相邻计划 用另一个s a 算法搜索经过快速调度仿真计算具有最好性能指标的调度，直至生产计划与调度同时 达到优化。 嵌入式s a 算法的流程图如图