（机械制造及其自动化专业论文）电镀车间自动小车动态调度策略研究及应用.pdf

重庆大学硕士学位论文 中文摘要 摘要 电镀生产专业性强，过程复杂，采用传统的手工操作会导致生产率低、产品 质量差、经济效益低，无法满足对多品种小批量的生产要求。落后的电镀生产管 理模式更无法满足现代化的企业管理要求。 生产调度问题是电镀企业生产信息管理系统的核心，因此本课题结合横向课 题“全自动电镀生产线的研制”，重点讨论了电镀车间调度问题。分析了电镀企业 生产管理的特点、任务和要求，以及生产管理信息化的现状和发展；介绍了生产 调度问题的概念、分类和性能指标，以及电镀车间调度问题的特点；描述了电镀 车间现场的设备、布局和组成，以及电镀产品的生产过程。 系统地论述了在车间调度问题中小车排序问题的分类以及前人的经验总结和 算法。提出一种基于自动小车顺序多目标优化动态调度的算法，将n p 的组合优 化动态调度问题分解成两个自动小车顺序调度问题，运用随机算法，设定特殊的 约束条件得出最优解，并对结果进行了分析验证。 本文设计了适合贵州某公司的生产管理系统，给出了其系统工作流程，开发 出电镀车间生产管理系统，并详细介绍了该系统各功能模块及其作用，该软件在 该公司的生产应用中取得了良好的效果。 关键词：车间调度，电镀生产，动态调度，随机排序 a b s t r a c t e l e c t r o p l a t i n gp r o d u c t i o n i s p r o f e s s i o n a l a n dc o m p l e x t h et r a d i t i o n a lm a n u a l o p e r a t i o nn o to n l y w i l ll e a dt ol o wp r o d u c t i v i t y 、p o o rp r o d u c tq u a l i t ya n dl o w e c o n o m i cb e n e f i t s ，b u ta l s oc a n tm e e tt h ev a r i e t i e so fs m a l lb a t c hp r o d u c t i o n r e q u i r e m e n t s f u r t h e r m o r e ，t h ep o o re l e c t r o p l a t i n gp r o d u c t i o nm a n a g e m e n tm o d e c a n ts a t i s f yo fm o d e r ne n t e r p r i s em a n a g e m e n tr e q u i r e m e n t s p r o d u c t i o ns c h e d u l i n gp r o b l e mi st h ec o r eo ft h ee l e c t r o p l a t i n gp r o d u c t i o ne n t e r p r i s e i n f o r m a t i o nm a n a g e m e n ts y s t e m t h i sp a p e rd i s c u s so nt h ee l e c t r o p l a t i n gw o r k s h o p s c h e d u l i n gp r o b l e mi sd i s c u s s e db a s e do nt h ep r o je c t“d e s i g na n dm a n u f a c t u r eo f a u t o m a t i ce l e c t r o p l a t i n gl i n e s f i r s t l y ，t h ec h a r a c t e r i s t i c s 、t a s k sa n dr e q u i r e so f e l e c t r o p l a t i n gp r o d u c t i o nm a n a g e m e n ta r ea n a l y z e d m o r e o v e r ，t h es t a t u sa n d d e v e l o p m e n to fp r o d u c t i o nm a n a g e m e n ti n f o r m a t i z a t i o ni sr e s e a r c h e d s e c o n d l y , t h e c o n c e p t 、c l a s s i f i c a t i o na n dp e r f o r m a n c ei n d i c a t o r so fp r o d u c t i o ns c h e d u l i n gp r o b l e m i si n t r o d u c e d t h en e x t ，t h ec h a r a c t e r i s t i c so fe l e c t r o p l a t i n gw o r k s h o ps c h e d u l i n g p r o b l e mi s d i s c u s s e d o n c em o r e ，t h ee q u i p m e n t 、l a y o u ta n dc o m p o s i t i o no f e l e c t r o p l a t i n gw o r k s h o p s i t ei s d e s c r i b e d f i n a l l g t h e p r o d u c t i v ep r o c e s s o f e l e c t r o p l a t ep r o d u c ti se x p o u n d e d t h ec l a s s i f i c a t i o no ft h eh o i s ts c h e d u l i n gp r o b l e m sa n dp r e v i o u se x p e r i e n c ea n d a l g o r i t h m a r ed i s c u s s e ds y s t e m a t a c i a l l y a na l g o r i t h mb a s e do ns i n g l e v e h i c l e m u l t i o b j e c t i v eo p t i m i z a t i o nd y n a m i cs c h e d u l i n g i sp r o p o s e d n pc o m b i n a t o r i a l o p t i m i z a t i o ns c h e d u l i n gp r o b l e mi sd e c o m p o s e di n t ot w o o r d e rs c h e d u l i n gp r o b l e m s o p t i m a ls o l u t i o ni ss o l v e db yr a n d o ma l g o r i t h m ，a n dt h er e s u l t sa r et h ea n a l y z e da n d t e s t e d c o m b i n e dw i t ht h ep a r t i c u l a r i t yo fp l a t i n gp r o d u c t i o nm a n a g e m e n t ，p r o d u c t i o n m a n a g e m e n ts y s t e mo ft h eg u i z h o uc o m p a n yi sd e s i g n e d s y s t e mw o r kf l o wa n d f u n c t i o nm o d u l ea r ei n t r o d u c e d k e y w o r d s ：s h o ps c h e d u l i n g ，e l e c t r o p l a t i n gp r o d u c t i o n ，d y n a m i cs c h e d u l i n g ， s t o c h a s t i cs c h e d u l i n g i i 重庆大学硕士学位论文1 绪论 1绪论 1 1 制造车间自动化 1 1 1 国内外制造车间自动化现状 自动化技术广泛用于工业、农业、军事、科学研究、交通运输、商业、医疗、 服务和家庭等方面。采用自动化技术不仅可以把人从繁重的体力劳动、部分脑力 劳动以及恶劣、危险的工作环境中解放出来，而且能扩展人的器官功能，极大地 提高劳动生产率，增强人类认识世界和改造世界的能力【l 】。 1 9 4 6 年，美国福特公司的机械工程师d s 哈德最先提出“自动化”一词， 并用来描述发动机汽缸的自动传送和加工的过程。5 0 年代，自动调节器和经典 控制理论的发展，使自动化进入以单变量自动调节系统为主的局部自动化阶段。 6 0 年代，随着现代控制理论的出现和电子计算机的推广应用，自动控制与信息 处理结合起来，使自动化进入到生产过程的最优控制与管理的综合自动化阶段。 7 0 年代，自动化的对象变为大规模、复杂的工程和非工程系统，涉及许多用现 代控制理论难以解决的问题【2 】。这些问题的研究，促进了自动化的理论、方法和 手段的革新，于是出现了大系统的系统控制和复杂系统的智能控制，出现了综合 利用计算机、通信技术、系统工程和人工智能等成果的高级自动化系统，如柔性 制造系统、办公自动化、智能机器人、专家系统、决策支持系统、计算机集成制 造系统等【3 j 。 机械制造自动化是机械化、电气化与自动控制相结合的结果，处理的对象是 离散工件。早期的机械制造自动化是采用机械或电气部件的单机自动化或是简单 的自动生产线。2 0 世纪6 0 年代以后，由于电子计算机的应用，出现了数控机床、 加工中心、机器人、计算机辅助设计、计算机辅助制造、自动化仓库等。研制出 适应多品种、小批量生产型式的柔性制造系统( f m s ) 【4 】。以柔性制造系统为基 础的自动化车间，加上信息管理、生产管理自动化，出现了采用计算机集成制造 系统( c i m s ) 的工厂自动化。 1 1 2 制造车间自动化 车间自动化主要包括设备自动化、管理自动化、控制自动化。 设备自动化 数控机床、加工中心和机器人就是比较典型的自动化设备和系统。 1 ) 数控机床 数控机床是数字控制机床的简称，是一种装有程序控制系统的自动化机床。 该控制系统能够逻辑地处理具有控制编码或其他符号指令规定的程序，并将其译 重庆大学硕士学位论文 1 绪论 码，从而使机床动作并加工零件【5 1 。与普通机床相比，数控机床的特点见图1 1 ： 图1 1 数控机床的特点 f i g 1 1c h a r a c t e r i s t i c so ft h en u m e r i c a lc o n t r o lm a c h i n e 自从1 9 5 2 年美国麻省理工学院研制出世界上第一台数控机床以来，数控机 床在制造工业，特别是在汽车、航空航天、以及军事工业中被广泛地应用，数控 技术无论在硬件和软件方，都有飞速发展。 2 ) 加工中心 加工中心是带有刀库和自动换刀装置的一种高度自动化的多功能数控机床。一 工件在加工中心上经一次装夹后，能对两个以上的表面完成多种工序的加工，并 且有多种换刀或选刀功能，从而使生产效率大大提高。按其加工工序分为镗铣和 车削两大类，按控制轴数可分为三轴、四轴和五轴加工中心【6 】。 3 1 机器人 联合国标准化组织采纳了美国机器人协会给机器人下的定义：“一种可编程 和多功能的操作机：或是为了执行不同的任务而具有可用电脑改变和可编程动作 的专门系统。”在工业制造车间中的机器人主要是指机械手臂，其臂部一般采用 空间开链连杆机构，其中的运动副( 转动副或移动副) 常称为关节，关节个数通 常即为机器人的自由度数。根据关节配置型式和运动坐标形式的不同，机器人执 行机构可分为直角坐标式、圆柱坐标式、极坐标式和关节坐标式等类型。机器手 臂可以帮助工人处理一些人力难以处理的加工程序，如抓取重物，控制加工精度， 以及在高温、高压和真空中作业等。 管理自动化 管理自动化主要包括产品数据管理和管理信息系统。 1 ) 产品数据管理 产品数据管理( p d m ，p r o d u c td a t am a n a g e m e n t ) 是基于分布式网络、主从结 构、图形化用户接口和数据库管理技术发展起来的一种软件框架( 或数据平台) ， 2 重庆大学硕士学位论文1 绪论 见图1 2 ，p d m 对并行工程中的人员工具、设备资源、产品数据以及数据生成过 程进行全面管理【7 1 。p d m 技术的发展可以分为以下三个阶段，配合c a d 工具的 p d m 系统、p d m 产品产生和p d m 的标准化阶段。 图1 2p d m 结构图 f i g 1 2s t r u c t u r ec h a r to fp d m 2 ) 管理信息系统 管理信息系统是用系统思想建立起来的，以电子计算机为基本信息处理手 段，以现代通信设备为基本传输工具，并能为管理决策提供信息服务的人机系统。 强调以企业管理系统为背景，以基层业务系统为基础。并且强调企业各业务系统 间的信息联系，以完成企业总体任务为目标。为企业各级领导提供管理需要的信 息，但信息的范围还更多的侧重于企业内部。 控制自动化 控制自动化主要包括p c 控制系统、p l c 控制系统和计算机网络控制系统。 1 ) p c 控制系统 个人计算机一词源自于19 7 8 年i b m 的第一部桌上型计算机型号p c ，在此 之前有a p p l ei i 的个人用计算机。能独立运行、完成特定功能的个人计算机。个 人计算机不需要共享其他计算机的处理、磁盘和打印机等资源也可以独立工作。 今天，个人计算机一词则泛指所有的个人计算机、如桌上型计算机、笔记型计算 机、或是兼容于i b m 系统的个人计算机等。以个人计算机作为控制中心，将输 入输出装置以板卡的形式连接到系统总线，如s t d 卡、i s a 卡和p c i 卡。由于 重庆大学硕士学位论文1 绪论 计算机的工作环境不同，还有为了特殊工况需要的工控机，比起普通个人计算机 要更加稳定与可靠。 2 ) p l c 控制系统 可编程逻辑控制器( p r o g r a m m a b l el o g i cc o n t r o l l e r ，p l c ) ，它采用一类可 编程的存储器，用于其内部存储程序，执行逻辑运算、顺序控制、定时、计数与 算术操作等面向用户的指令，并通过数字或模拟式输入输出控制各种类型的机 械或生产过程。2 0 世纪7 0 年代初，微机技术与继电器常规控制概念相结合产生 了可编程逻辑控制器。2 0 世纪9 0 年代，p l c 已经具有处理模拟量、数字运算、 人机交互和网络的能力。2 0 世纪末，p l c 更加适应于现代工业的需要，发展出 了各种具有特殊功能单元、人机界面和通信单元峭j 。 3 ) 基于计算机网络的集散控制系统 在复杂的大规模过程控制领域，大多采用集散控制系统( d c s ) ，见图1 3 。 d c s 本质上是一种基于计算机网络的分层的计算机监控系统，其基本结构如图 所示，主要组成有工程师站、操作员站和现场控制站，通过通信网络相连【9 1 。控 制站实施对现场设备的控制，操作员站主要作为操作人员与系统的人机界面。工 程师站主要用于对系统进行离线或在线的系统组态、控制组态、显示组态和报警 组态，并在运行过程中完成系统和网络管理、文件请求管理、数据库管理等【l 。 o 寸o 口0 口 过程 图1 3 集散控制系统结构图 f i g 1 3s t r u c t u r ec h a r to fd i s t r i b u t e dc o n t r o ls y s t e m 4 重庆大学硕士学位论文1 绪论 1 2 电镀生产管理概况 1 2 1 电镀生产管理特点 电镀生产与大部分制造业相比有一定的不同之处，电镀企业在接到客户订单 后，根据产品的技术工艺要求，制定电镀工艺流程，并且将任务分配到相应的生 产车间，车间根据生产计划开始操作，同时企业根据实际生产情况，收集生产过 程中的数据，为企业管理者和客户提供所需要的信息【1 1 1 。可见电镀生产是一类专 业性强、综合性高、复杂性大的系统生产，无论是专业电镀加工单位，还是综合电 镀加工企业，其生产特点如下： 镀种多样：根据不同的电镀材料来分，有镀锌、镀铜、镀镍、镀铬、镀 银、混合镀等；根据镀层的厚度来分，有单层或多层镀；根据电镀的方式来分， 有挂镀、滚镀、装框镀、振动镀等；根据电源种类分，有直流、脉冲、恒压、恒 流等。 品种繁多：根据产品的材料、尺寸、几何形状、质量、数量不同等等， 随产品不同和质量要求不同，其生产过程，工艺条件等亦各不相同。 工序复杂：电镀前处理( 化学除油、水洗、酸洗、活化等) ，电镀，电镀后处 理( 钝化、保护、干燥等) 。不同的基体其前处理、电镀和后处理亦工艺各异。 过程连续性：产品经过电镀前处理，电镀，再到电镀后处理，直至成品 检验、计量、包装的整个生产过程需要连续地进行，间断或停顿需要最大限度地 减少【1 2 】【13 1 。根据一些特殊的电镀工艺要求，工件在一些镀槽加工完毕后必须立 即转移到下一镀槽加工，比如工件在经过酸洗后必须立即水洗，否则会侵蚀零件 的表面氧化层导致产品报废，所以中间停顿的时间除了转运外要尽可能地减少。 布局合理性：在电镀过程中，部分槽的加工时间比起其他槽要长，主要 是电镀主槽，一般工件都需要在主槽中停留几十分钟，保证镀层厚度。除此之外 有的槽的加工时间又很短，如工件在酸洗槽中的停留时间一般是十几秒，保证工 件表面的镀层不会被侵蚀。为了提高生产效率，在电镀生产线设计时，加工时间 较长的工序，需要安排几个平行设备，以消除生产“瓶颈”，尽量使生产线能够顺 利运行而不会阻塞。 不稳定因素多：如原材料、工艺配方、操作条件、设备正常程度，乃至水、 电、汽、三废治理等等，每一因素均直接影响产品质量。 生产节奏性：生产节奏性是合理安排上下料的时间，上料间隔过长会降 低生产效率，上料间隔过短会受生产设备制约，造成工件堆积，工序受阻，造成 产品报废。保证从毛坯投入生产到电镀成品完成，均能按质、按量、按时地有规 律、有步骤、有节奏正常运行【1 4 】。即：每一工序定时，定量进出槽，每一生产 节拍能正常出品，按生产计划正常运转。 重庆大学硕士学位论文 1 绪论 镀液重要性：电镀镀液在电镀生产中至关重要，决定电镀产品的质量。 在电镀生产管理中，必须定时检测镀液浓度，定量添加电镀药剂，定期净化处理。 根据电镀生产的特点，为满足不同产品及不同镀种的要求，生产管理系统中 必须能够合理组织生产，确保产品质量，控制加工成本。 1 2 2 电镀企业生产管理的任务和要求 为满足电镀产品的质量和工艺要求，针对以上电镀生产的特点，在生产过程 的每一个环节中，都要进行合理的计划和调度【1 5 】。电镀企业生产管理的主要任 务是： 按时性 电镀生产系统要保证根据客户的需求，在交货期限前保质保量地，以最低的 生产成本，提供优质的产品。 连续性 产品在电镀的整个过程中，应处于连续正常地进行，间断或停顿需要最大限 度地减少，使得设备得到充分利用，有效控制工艺流程，尽可能地减少消耗，缩 短生产周期。由于毛坯、原材料、水电气供应不足，设备故障，员工安排不当等 都会导致生产中断，而影响产品的质量【1 6 。 平行性 电镀生产过程中的各项操作在时间上实现平行交叉作业，以缩短生产周期， 同一产品的各种零件在配套的前提下，应尽可能组织平行生产。对于中小型电镀 制造企业而言，因生产批量不大，可建立成组生产单元，使其运输线路短而流畅 【1 7 】 0 比例性 生产设备和人员应按工艺要求严格按比例配置，从而使整个生产中各道工序 等比，达到无空闲设备，无零件堆积，无多余人员。设备能力不协调、人员设置 不妥、工艺安排不合理等都会造成比例失调，从而影响正常生产。 抗干扰性 电镀企业生产过程中对现场环境和不确定因素的变动要有较强的应变能力 1 7 】 0 节奏性 从毛坯到电镀成品完成，均能保质、保量、按时地有规律、有步骤、有节奏 正常运行。生产计划不当、设备故障、工艺失当、操作不当等都会导致生产节奏 混乱。 1 2 3 电镀生产管理信息化现状 我国的电镀工业随着改革开放以来，已经得到了巨大的发展，成为了制造业 6 重庆大学硕士学位论文1 绪论 的重要行业。但是与发达国家相比我国的电镀行业信息化水平低下，生产管理水 平落后，员工专业素质不高等都制约了整个行业的发展。作坊式生产方式，无控 或失控的管理现状，给不少电镀企业带来重大影响，导致生产效率不高，直接成本 增加，最终是企业的经济效益下斛1 9 】。 国家对电镀工业的重视不足，用于技术改造和技术引进的投资非常缺乏，这 必定限制了电镀工业技术的发展。电镀工业分布零散、规模小、组织缺乏、技术 落后，导致生产效益落后。而且企业的管理水平低，大多沿用粗放型管理模式或 者手工作坊的形式，导致管理效率低、产品质量差 2 0 】。 综上所述我国电镀制造企业还处于不发达阶段，主要表现在以下几个方面： 大部分电镀企业规模小，手工操作，缺乏自动化设备，缺少现代化管理 体系，生产效率较低； 企业各自为战，比较分散，行业整体联系不够紧密，与国外现代化的大 型企业合作缺乏，导致关键技术不发达，信息闭塞，先进的生产技术不能为国人 所用； 电镀工艺与操作流程不规范，操作人员没有进行专业的技术培训，电镀 化学知识学法，只懂得怎么做但不明白为什么做，导致产品质量低； 电镀企业没有先进的管理体系，生产管理流程不规范，不能对制造成本、 生产过程、产品质量进行有效控制。 电镀企业的信息化程度较低，管理体系不科学是电镀企业发展的“瓶颈”。如 果每道工序都根据工人的经验，操作过程没有适当的监督，产品质量交货时间没 有合理的控制，都会导致电镀工厂的经济效益和声誉受到影响，从而制约电镀制 造业的发展。 1 3 论文研究的背景、意义和主要内容 1 3 1 论文研究背景和意义 电镀( e l e c t r o p l a t i n g ) 就是利用电解原理在某些金属表面上镀上一薄层其它 金属或合金的过程，是利用电解作用使金属或其它材料制件的表面附着一层金属 膜的工艺从而起到防止腐蚀，提高耐磨性、导电性、反光性及增进美观等作用【1 4 】。 电镀时，镀层金属或其他不溶性材料做阳极，待镀的工件做阴极，镀层金 属的阳离子在待镀工件表面被还原形成镀层。为排除其它阳离子的干扰，且使镀 层均匀、牢固，需用含镀层金属阳离子的溶液做电镀液，以保持镀层金属阳离子 的浓度不变【l8 1 。电镀的目的是在基材上镀上金属镀层，改变基材表面性质或尺 寸。电镀能增强金属的抗腐蚀性( 镀层金属多采用耐腐蚀的金属) 、增加硬度、防 止磨耗、提高导电性、润滑性、耐热性、和表面美观。 重庆大学硕士学位论文1 绪论 电镀在表面处理行业中，有重要的地位，是制造业的基础行业。随着生活水 平的提高，对电镀技术的要求不断提高，电镀产品的需求也随之增加。人们对产 品的美观度和质量要求也逐渐提高。 电镀自动生产线将镀槽、转运装置、通讯设备、电气元件、计算机核心处理 器有机的结合起来，根据生产工艺使所有设备有序的运作起来，互相配合、互相 协调，完成电镀产品的制造。电镀生产线较手工操作有极大的优势，不但提高了 劳动效率，加大生产力，而且还保证了产品质量，降低了劳动强度，同时实施了 生产过程监控，数据记录，保证生产信息有据可查，有源可溯。许多专业的客户 有特殊的要求，比如航空航天工业，对产品的生产过程必须可控、可追溯，有的 生产过程记录需要保存很久，直至产品寿命终止或者被废弃，一旦过程中由于产 品本身质量导致的事故，需要向制造方追究责任，故生产过程的记录十分重要。 许多电镀企业的生产管理落后，没有先进的管理系统，直接影响到企业的成 本管理、设备资源利用、交货期限的设定、以及员工的分配等。间接影响到产品 的生产率、公司的经济效益、声誉等。 电镀产品的需求有时是大量的，有时是小批量多品种的，且每种产品的工艺 差别很大，工序数量有多有少。若由人工进行操作出错率高、工艺质量把握不精 确、劳动强度大。所以自动化电镀生产线是十分必要的。 车间生产管理是企业生产管理的基础。本课题在正确理论的指导下，针对贵 州航天精工制造有限公司的车间生产调度管理的实际情况，摸索如何应用先进实 用的生产调度方法去解决该企业长期存在的一些问题。该公司已有的电镀生产线 基本是手工生产线和半自动生产线，任务派发、设备控制、工件运输、镀液检测、 温度p h 的监控是都靠人工实现。为了提高生产效率、降低员工劳动强度、提高 产品质量，该公司要将原本的手动生产车间改造成为全自动的电镀生产线，要求 重要的加工数据可以存储和监控。 针对该公司的要求，本课题研发了一套针对电镀生产特点的电镀车间生产管 理系统，加强生产过程的监控，提高生产车间的任务调度能力、现场控制能力。 运用现场总线技术、网络技术、p l c 控制等，实现电镀生产线的自动化控制。针 对车间最关键的生产调度问题进行深入的研究。 1 3 2 主要内容 本文主要探讨电镀生产管理系统的发展，阐述了车间调度问题的方法分类和 数学模型，对贵州某公司的电镀车间调度问题建立了模型，设计出一种自动小车 顺序生产多目标优化动态调度算法，设计出适合该电镀车间的生产管理系统。本 文的主要章节如下： 第1 章分析和研究车间自动化的现状，对电镀企业的生产管理现状展开讨 重庆大学硕士学位论文1 绪论 论，阐述了本文的研究背景和意义。 第2 章研究电镀企业生产车间调度的特点、分类及不确定因素，例举了电 镀生产的主要过程，深入探讨了生产调度问题的研究方法，对电镀企业生产车间 调度问题建立了模型。 第3 章讨论小车排序问题的多种情况下的算法，分析了生产过程中出现动 态不确定因素时的特殊情况，提出基于自动小车顺序生产多目标优化动态调度算 法来求解该特殊情况下的车间调度问题。 第4 章简述了电镀生产过程管理模式，电镀车间的布局和组成，提出了系 统的总体设计，介绍系统功能模块。 第5 章结论与展望。 9 重庆大学硕士学位论文 2 电镀企业生产车间调度问题建模 2电镀企业生产车间调度问题建模 2 1 生产调度问题 2 1 1 车间调度问题概述 生产调度问题是系统内对可用资源的合理分配和任务排序，以满足某些指定 的性能指标，即按照目标函数来分配资源最优完成生产任务的问题。换句话来说， 是指在一定的约束条件下，合理安排所需资源，加工时间，使得总加工时间最短 以及成本最优。 生产调度位于计算机集成制造系统c i m s 的中间一层调度层，见图2 1 ，上 层是负责企业决策的管理层，下层是负责生产过程控制的监控层，调度层起到承 上启下的作用，是将上层的管理方针贯彻到生产的纽带，是计算机集成制造系统 不可或缺的关键性的一层。 亟巨匮 决策信息 = 剖经营决策烬= 爿 效益最大 管理信息 = = 剖管理系统 生产管理 经营管理 调度信息 = 刮生产调度比= 刊 优化调度 工况信息 = = 剖监控系统 测量信息 = = 刮控制系统 生产过程 图2 1 计算机集成制造系统结构图 f i g 2 1t h e s t r u c t u r eo fc i m s 1 0 复杂控制 常规控制 重庆大学硕士学位论文2 电镀企业生产车间调度问题建模 2 1 2 车间生产调度问题分类和性能指标 车间生产调度问题分类 车间调度问题可描述为：n 个工件在m 台机器上进行加工，每个工件可分为 k 道工序，生产过程中有两大约束，分别是机器占用约束：每道工序可以在若干 台机器上加工；工件加工顺序约束：每个工件必须完成了上道工序后才能进入下 道工序的加工。 生产调度问题，按照不同的分类标准，分类如下： 1 ) 根据系统的复杂性可分为单机调度和多机调度。 单机调度问题：所有的加工任务都在一台机器上完成，只有一道加工工序， 合理安排加工任务的顺序。 多机调度问题：生产系统上有多台机器，多个任务有多个工序，各工序在各 机器上加工，合理安排加工任务的顺序，每道工序的顺序，以及每道工序的加工 时间。包括f l o w s h o p 调度问题和j o b s h o p 调度问题。f l o w s h o p 调度问题是指假 设所有任务都在相同的设备上进行加工，并且有一致的加工顺序和加工操作。 j o b s h o p 调度问题是指有有多台机器和多个工件，合理安排每个工件的加工顺序， 且加工路线不同，使得某个指标最小。 2 ) 根据生产环境可分为静态调度和动态调度。 静态调度问题：不考虑各种动态不确定因素，只考虑工序和设备约束，且各 个工件的加工工艺、加工顺序、加工开始时间、每台机器的加工时间已知。 动态调度问题：考虑各种动态不确定因素，如原材料供应不足、设备故障、 交货期补丁、人员操作不当等，导致加工时间不定，顺序不定。 3 ) 根据调度性能可分为代价调度和性能调度。 代价调度问题：使调度过程中的成本最低。 性能调度问题：使设备利用率最高或者总力n - r _ 时间最短。 4 ) 根据目标函数数量可分为但目标函数和多目标函数调度。 单目标函数调度问题：只有一个目标函数，如总完工时间，总拖期时间和加 权完工时间等。 多目标函数调度问题：有多个目标函数，可以通过对多个函数加过进行加权 来判断是否最优，先将多目标函数转化成多个单目标函数求解后加权。 生产调度的性能指标 性能指标是调度方案的评价标准，生产调度主要有三大性能指标，分别是最 大能力指标、成本指标和客户满意度指标。 1 ) 最大能力指标 最短生产周期、最大生产率、最高设备利用率等。最大能指标可以使得企业 重庆大学硕士学位论文 2 电镀企业生产车间调度问题建模 的生产周期缩短，经济效益最大化。 2 ) 成本指标 最小投资、最少运输费用、最低仓库费用、最省设备维护等。通过成本指标， 可以降低生产成本，提高经济效益。 3 ) 客户满意度指标 最早交货期、最小延迟交货时间、最少延期工件、最高产品质量等。通过客 户满意度指标，可以提高企业信誉、塑造品牌、增加企业订单等。 2 1 3 生产调度中的动态不确定因素 不确定因素的产生 在生产过程中，实际生产与静态的调度会有差异，不论在调度之前是否尽可 能的对实际情况进行了预测，生产过程中有许多因素总是难以预料的，所以需要 进行动态的调整。由于生产调度环境发生变化，而需要进行动态调度的事件称为 动态事件。动态事件的种类有很多种，根据生产调度过程中发生的各种扰动异常， 不确定因素由4 种源头引起，分别是产品、原材料、设备和人员2 1 1 。具体分类 见图2 2 。 不确定因素分类 由产品引起的不 由原材料引起的 确定因素 确定因素 图2 2 不确定因素分类表 f i g 2 2u n c e r t a i n t yc l a s s i f i c a t i o ne l e m e n tc r a f t 1 2 一一一 一一一一 一一一 一一一一一一。一一一一一 一一 一一 一一 一一 一一 一 一一 一一 一一 一一 一一 一一一 一一 一 重庆大学硕士学位论文2 电镀企业生产车间调度问题建模 不确定因素的调度模型 不确定因素的调度模型根据不同的条件可分为三类 2 1 ，见表2 1 表2 1 不确定因素的调度模型 t a b l e2 1s c h e d u l i n gm o d e lo fu n c e r t a i n t yc l a s s i f i c a t i o ne l e m e n t 服从统计分布的调度模型服从隶属函数的调度模型 在某一区间内变化的调度模型 鸦 ，仁，工，d 8 强 恕斗，工，4 。纠 嬲，( c 尚d 口) “暑c 。工，d ，口) o“井而z 矿k 0豇暑( c ，工，d ，口) 套o 矗( c ，工d ，一) - 0 诈，4 歹) 0 c ，工，i ，o ) - o c s c ，z e x ，d e d ，一e c 毫c ，x z ，d e d ，p 9 cq e c ，工z 。d e d ，口e 0 珥慨。，岛一】。 决策系数：c i ( i - 1 ，2 ，n ) ；决策变量：x i ( i - 1 ，2 ，n ) ； 离散的量：d i ( i _ 1 ，2 ，n ) ；不确定参数：0i ( i _ 1 ，2 ，n ) ： 2 1 4 车间生产调度问题研究方法 生产调度问题经过历代研究，方法已经拓展了多种方法，包括经典算法和现 代智能算法，理论体系已经越来越健全。 数学规划方法： 数学规划方法包括线性规划，非线性规划，整数规划，二次规划，多目标规 划等等，已经广泛应用于生产调度问题。 1 ) 分枝定界法 分枝定界法是一种枚举方法，常以广度优先或以最小耗费优先的方式搜索问 题的解空间树。分枝定界法在调度问题的求解上应用比较广泛。2 0 世纪6 0 年 代l a n d d o i g 和d a k i n 等人提出用分枝定界法来求解整数规划或者混合整数规 划的问题。gh b r o o k s 和c r w h i t e 2 2 】首次将分支定界法应用到了调度问题的 求解，解决了优化问题。p o t t sc n 2 3 又提出了一种改进的分枝定界法，该方法 在定界机制、上界产生和分析规则上进行了改进。分支定界法复杂性高并且搜索 效率比较低，随着问题规模的增大，求解难度呈指数规律递增，在解决较大较复 杂的生产调度问题时需要花费大量的时间，不具有实用性。 2 1 拉格朗日松弛法： e v e r e t t 提出的拉格朗日松弛法，可以克服分支定界法只能用于整数约束的 弊端，在可行域里提供次优解，并能对解的次优性进行定量评估，目前已经将拉 氏松弛法应用到了单机和多机调度问题，通过加入更多的拉氏乘子，松弛了操作 的顺序约利2 4 1 。f i s h e rm l 2 5 3 在解决j o b s h o p 调度问题中使用了拉格朗日松弛 算法，在理论上证实了可行性。拉格朗日松驰法在计算过程中存在数值振荡，因 重庆大学硕士学位论文2 电镀企业生产车间调度问题建模 此比较耗时。 启发式方法 启发式方法针对调度问题的n p 特性，并不是在多项式时间内求得问题的最 优解，而是在计算时间和调度性能之间进行折中，以较小的计算量来得到近优或 满意解。1 9 7 7 年，p a n w a l k a r 等总结了1 1 3 条启发式调度规则，将调度规则分为 了简单规则、复合规则和启发式规则三类。m mo n t a z e l i 等列举了常见的2 0 条 规则 2 6 1 ，并对一个实际的f m s 模型，分析了这些规则对系统性能的影响。最常 用的调度规则是分派规则，在动态调度系统中，调度规则由于计算量小、效率高、 实时性好，因而得到得到广泛应用，但是它仅考虑单一目标或局部信息，缺乏对 全局信息的有效把握和预见能力，在实际应用中常与其它方法结合使用【2 2 1 。人 们经过摸索找到了更近似的调度方法移动瓶颈启发式方法，是目前最有效地启发 式方法。启发式规则具有全局敏感性，使用不同的规则可获得不同的调度方案， 而且规则在不同的应用场合所起的作用也不同，生产调度的性能取决于规则的选 择。因此，规则的选择成为基于规则调度方法的主要障碍。 人工智能方法 1 ) 模拟退火方法 模拟退火方法源于对固体退火过程的模拟，采用m e t r o p o l i s 准则，并用一组 称为冷却进度表的参数控制算法进程，是算法在多项式时间里可给出一个近似最 优解。1 9 5 3 年，m e t r o p o l i s 等人【2 7 】就提出了经典的模拟退火算法的思想，到了 1 9 8 3 年，ki r k p a t r i c k 等人【2 8 】提出了现代的模拟退火算法，都很好得应用于车间 调度问题。模拟退火方法高效稳健，较局部搜索算法，它可在较短时间内求得更 优近似解，且不受初始解和随机数序列的影响，不会因问题不同而蜕变，但是难 用于实时动态调度。 2 ) 禁忌搜索算法 禁忌搜索算法最早是g l o v e r 在1 9 8 6 年提出的，是一种亚启发式 ( m e t a h e u r i s t i c ) 随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜 索方向( 移动) 作为试探，选择实现让特定的目标函数值变化最多的移动。为了避 免陷入局部最优解，t s 搜索中采用了一种灵活的“记忆”技术，对已经进行的优 化过程进行记录和选择，指导下一步的搜索方向，这就是t a b u 表的建立。禁忌 搜索算法局部搜索能力强，但是过于依赖初始解，对于不确定性的车间调度能力 较差。 3 ) 遗传算法 是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算 模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国m i c h i g a n 1 4 重庆大学硕士学位论文 2 电镀企业生产车间调度问题建模 大学j h o l l a n 教授于1 9 7 5 年首先提出来的，并出版了颇有影响的专著( ( a d a p t a t i o n i nn a t u r a la n da r t i f i c i a ls y s t e m s ) ) ，g a 这个名称才逐渐为人所知，j h o l l a n d 教授 所提出的g a 通常为简单遗传算法( s g a ) 。1 9 9 1 年，n a k a n o 等 3 1 首先将遗传 算法应用到了一系列的经典j s p 问题中。遗传算法主要有两种变换方法：变异和 杂交。遗传算法容易产生局部最优解，导致过早收敛，收缩效率低。 4 1 神经网络 f o o 和t a k e f u j i 提出了波尔兹曼机3 5 【3 6 1 ，一种随机h o p f i e l d 神经网络，同 时又提出一种整数线性规划神经网络i l p n n 了7 】来解决j o b s h o p 调度问题。之后 r e m u sw ( 1 9 9 0 ) 提出用b p 神经网络来求解j o b s h o p 调度问题，神经网络得到世 人的关注。虽然神经网络是解决j o b s h o p 问题的最成功的应用之一，但是该方法 计算过程无法保证得到可行解，计算时间较长。 5 ) 专家系统 8 0 年代f o x 和s m i t h 提出的i s i s 是最早提出针对车间调度的专家系统。专 家系统由两部分组成：知识库和推理机。专家系统是一个智能计算机程序系统， 其内部含有大量的某个领域专家水平的知识与经验，能够利用人类专家的知识和 解决问题的方法来处理该领域问题。根据车间工况信息的选择最好的调度规则。 但是由于历史经验的不完整，对新的调度环境的适应性较差，缺乏与工况的藕合， 只能产生可行解，却不能保证解最优。 基于仿真的方法 仿真方法不是一种单项技术，而是一种求解问题的方法。它可以运用各种模 型和技术，对实际问题进行建模，通过模型采用人工试验的手段，来理解需要解 决的实际问题。通过仿真，可以评价各种替代方案，证实哪些措施对解决实际问 题有效。k i r a n 3 8 回顾和总结了在动态环境下基于纯仿真模型的j o b s h o p 调度 问题的研究状况。由于调度系统极为复杂，很难用精确的解析模型来进行描述和 分析。仿真的结果费用高、可信度低、缺乏理论基础，无法保证通过实验找到最 优或次优解。 2 2 电镀生产车间调度特点 根据前文对电镀生产过程的分析，电镀生产过程多镀种、多工序、多品种、 多因素、综合性高、复杂性大、专业性强。对车间调度的特征进行如下归类： 约束多 一般来说，车间生产调度的进行是有许多约束的，如工件交货期、设备资源、 劳力数量、加工工艺和加工顺序等都是约束条件。除此外还有一些特定的约束， 如要求各机器上负荷要平衡、人员工作时间固定、设备定时启停维护等。约束越 重庆大学硕士学位论文 2 电镀企业生产车间调度问题建模 多建模难度就越大。 目标多 评价车间生产调度优劣的指标往往是多样的，如生产周期尽可能短、设备利 用率尽可能高、客户满意度尽可能好、库存尽可能少等。根据实际生产情况，对 应不同的指标，有相应的生产调度目标。主要包括降低平均延误率、缩短生产周 期、提高设备利用率、减少平均完成时间等，有时不同的目标会相互制约，从而 导致建模的复杂度增加。 环境杂 环境杂是指在动态调度过程中车间环境和计算的复杂性。车间里各种设备、 工件、人员、刀具数量和缓冲区之间是相互制约的，其次操作人员的操作经验、 工件的特殊紧急程度、工厂整体调度、水电气等突发状况、设备故障等都是不确 定因素，都会提高车间系统的复杂性。计算的复杂性是指车间调度问题是一个在 若干约束下的组合优化问题，不但计算时间长，调度规模大，可行解的数量大， 所以求解是很难的，需要先进的计算方法。 随机性 产品、原材料、设备和人员都会造成不确定因素，工件到达延误、紧急工件 插入、原辅材料短缺、机器故障等都会造成系统的随机性提高，调度效率大大降 低。原有的调度方案可能失效或者不是最优，因此新的调度方案需要对随机事件 做出响应，重新进行调度，使得系统在随机情况发生时都能高效良好的运作。 2 3 电镀生产车间调度问题建模 一些典型电镀种类的生产工艺流程，在某些设备上是公用的，为了减少资源 的浪费，对那些公用的渡槽，可适当增加其数量，以保证几种不同的工件同时加 工。在生产过程中如主槽的加工时间一般较长，为了避免工件堆积，也可适当增 加设备数量。这类设备称之为平行设备k ，假设设备k 具有n 个平行单元。 为了提高生产效率，对生产任务进行优化排序是很必要的，可以使得总