（机械电子工程专业论文）模具企业热处理批调度研究.pdf

摘要 摘要 对于模具生产，热处理是保证模具性能的重要工艺过程，是模具生产过程中 必不可少的关键环节，它对模具的制造精度、强度、使用寿命和制造成本都有着 直接的影响。因此，在整个模具生产制造过程中，实现热处理车间的合理优化调 度对保证模具的质量、模具的项目计划进度和模具的交货期等具有重大意义。 调度问题一直以来就是一个热点问题，它大量存在于各个生产领域，在模具 企业的热处理车间，经过调研发现，该车间的生产调度是一类比较特殊的调度， 本文称之为热处理批调度。热处理批调度问题包含分批和排序两个阶段，在分批 阶段，它是一个要考虑多约束影响的分批组合问题，在排序阶段，则是一个存在 多机、多阶段、设备多功能的批排序问题。 本论文以广卅i 市某模具制造有限公司热处理车间为主要研究对象，同时借鉴 国内外关于批量调度的研究成果，研究以模具企业热处理车间为背景的批量调度 问题。提出了以主零件为中心的启发式装箱算法来解决热处理的分批问题，同时 在解决分批问题以后，设计了带启发式控制检测遗传算法来解决热处理批排序问 题，并通过m a t l a b 进行数据仿真，证明了算法的有效性。最终实现整个热处理车间 的调度优化。 关键词：热处理，批组合，批排序，f f d 算法，启发式控制检测遗传算法 广东t 业大学工学硕二l ：学位论文 a b s t r a c t h e a tt r e a t m e n ti sak e yp r o c e s st oe n s u et h ed i e sp e r f o r m a n c ei nm o u l d p r o d u c t i o n ，i th a sad i r e c ti m p a c to np r e c i s i o n ，i n t e n s i t y , l i f e t i m ea n dm a n u f a c t u r i n g c o s t so fm o l d s t h e r e f o r e ，i nt h ew h o l ep r o c e s so fm o l dm a n u f a c t u r i n g ，t om a k ea o p t i m a la n dr e a s o n a b l es c h e d u l i n go fh e a tt r e a t m e n ti sv e r yi m p o r t a n tt oe n s u r et h e q u a l i t y , t h ep r o g r e s so f p r o j e c t sp l a na n dt h ed u ed a t eo f m o u l d s c h e d u l i n gp r o b l e mh a sa l w a y sb e e nah o ti s s u e ，i te x i s t si nal a r g en u m b e ro f v a r i o u sp r o d u c t i o na r e a s ，a sar e s u l to fr e s e a r c hi nt h eh e a tt r e a t m e n tw o r k s h o po fa m o l de n t e r p r i s e w ef o u n dt h i sw o r k s h o p ss c h e d u l i n gi sar e l a t i v e l ys p e c i a lt y p eo f b a t c hs c h e d u l i n g ，w en a m e di ta sh e a tt r e a t m e n tb a t c hs c h e d u l i n g h e a tt r e a t m e n t b a t c hs c h e d u l i n gp r o b l e mi n c l u d et w os t a g e s o n ei sb a t c h i n g ，t h eo t h e ri ss c h e d u l i n g i n t h e b a t c h i n gp h a s e ，i t i sap r o b l e mw h i c hs h o u l d c o n s i d e rt h e i m p a c t o f m u l t i c o n s t r a i n e d i nt h es c h e d u l i n gs t a g e ，i ti sap r o b l e mw h i c hi sm u s tc o n s i d e r m u l t i - m a c h i n e ，m u l t i s t a g e ，a n dm u l t i f u n c t i o no fm a c h i n e i nt h i sp a p e r , w et a k i n gam o l dm a n u f a c t u r i n gc o l t do f g u a n g z h o ua sr e s e a r c h o b j e c t a tt h es a m et i m e u s i n gr e s e a r c hr e s u l to fn a t i o n a la n di n t e r n a t i o n a lf o r r e f e r e n c e r e s e a r c h e dt h eb a t c hs c h e d u l i n gp r o b l e mo fh e a tt r e a t m e n tw o r k s h o pi n m o u l de n t e r p r i s e p u tf o r w a r da p a c k i n gh e u r i s t i ca l g o r i t h mw h i c h i st a k et h em a i n p a r t sa st h ec e n t e rt os l o v et h eb a t c hp r o b l e m a f t e rb a t c h i n g ，w ed e s i g n e dah e u r i s t i c c o n t r o la n dd e t e c t i o ng e n e t i ca l g o r i t h m st os o l v et h eh e a t t r e a t m e n tb a t c hs c h e d u l i n g p r o b l e m ，a l s ow et h o u g hd a t as i m u l a t i o nw h i c hi su s em a t l a bt op r o v e t h e e f f e c t i v e n e s so ft h ea l g o r i t h m e v e n t u a l l yr e a l i z e dt h eo p t i m i z a t i o no ft h es c h e d u l i n g i nt h ee n t i r eh e a t - t r e a t m e n tw o r k s h o p k e yw o r d s ：h e a tt r e a t m e n t , b a t c h i n g ，b a t c hs c h e d u l i n g ，f i r s tf i td e c r e a s i n g a l g o r i t h m s ，h e u r i s t i cc o n t r o la n dd e t e c t i o ng e n e t i ca l g o r i t h m s 广东t 业大学t 学硕l ：学位论文 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 5 8 指导老师签名： 论文作者签名： 叫年否 第一章绪论 1 1 研究背景及意义 第一章绪论 本课题研究是根据广州某一家历史悠久、专门生产压铸模具的中型模具企业的 实际情况，同时借鉴国内外关于批量调度的研究成果，研究以模具热处理车间为 背景的批调度问题。 经过大量的现场调研和归纳分析，我们发现，模具热处理车间的调度类型为批 调度问题，但是与一般批调度相比，其复杂程度更高，解决难度更大。 1 1 1 一般批调度的特点 一般批调度常见于钢铁企业冷轧厂的热处理车间、线路板企业的腐蚀印刷车 间、半导体生产以及电镀车间等。文献【l 】对一般的批调度进行了详细的概述和说明， 它可简单的描述为：将n 个工件分成m 个批次，然后将m 个批次安排到多道工 序的多台设备上，并进行加工顺序排序。在分批时，一般批调度通常只需考虑加 工能力限制，多约束限制分批的情况比较少见；在排序时，一般批调度往往只涉 及单阶段的多机批调度问题，有的甚至只是单阶段的单机批调度，当然，也有少 量是多机多阶段的批调度，比如冷轧厂的热处理车间批调度问题，但是在多机多 阶段基础上的工序多次重复、设备存在多功能的批调度问题十分罕见。 1 1 2 模具热处理批调度问题的特点 热处理调度问题也由分批和排序组成，它可描述为：将n 个工件分成m 个批 次，在分批时要充分考虑到上层模具项目计划的影响，同时兼顾材料、炉容等多 重约束限制，使得分完批后的每批工件符合分批规范同时又保证不耽误项目进度； 在排序时，m 批零件都要经过4 道工序加工，分别为淬火+ 回火、回火、回火，很 广东t 业大学t 学硕l ：学位论文 明显，这4 道工序可以看成3 个阶段，即为多阶段加工形式( 在后面的内容中本 文把这3 个阶段看成是3 道工序进行处理) 。在设备存量和功能方面，有k ，台淬 火设备，有k ，台回火设备，其中淬火设备可以用来进行淬火加工和回火加工，而 回火设备只能用来进行回火加工，在工时方面，同批次工件具有相同的开始时间、 加工时间和完工时间，所以不需考虑批内工件之间的排序，同时由于淬火设备与 回火设备的产能相同，所以，避免了不同工序时工件进行重新批组合。目标是如 何合理的安排各批的生产加工计划以使得企业成本最低。 图1 5 热处理批调度流程 f i g 1 5s c h e d u l ef l o wo fh e a tt r e a t m e n t 在热处理车间的加工生产中，主要存在以下几个特点： ( 1 ) 每个批次包含多个相关约束影响的零件。 2 第一章绪论 在零件进行热处理加工之前，需要将各个零件组合成批，在组合的过程中， 我们需要按照多重约束条件来指导组批，使得只有符合约束条件的零件才能放到 同一批次中。其中，多重约束条件主要有：材料约束、炉容约束、时间约束等。 在热处理加工过程中，一个批次可以看成是一个独立的零件，批次内的零件则可 看成是部件。 ( 2 ) 加工过程存在多个阶段，且存在重复的加工工序。 在热处理的加工过程中，加工过程包含淬火+ 回火一空冷一回火一空冷一回 火，即一次淬火和三次回火，有时候还会有第四次回火。即存在多阶段生产，且 为不可连续性生产( 需要空冷) 。 ( 3 ) 加工设备的功能存在多样性。 在热处理加工设备中，回火设备是只能用来进行回火工艺的加工，而淬火设备 则可兼顾淬火工艺和回火工艺。因此，与一般批调度问题中设备只具有单功能的 特点相比，热处理生产调度中淬火设备的多功能必然会导致热处理车间调度存在 比普通批调度更好的优化值。 经过对比，我们知道，热处理批调度比一般批调度问题明显复杂，其学术研究 价值和实际生产意义也显而易见、不言自明。 1 1 3 存在的问题 经过数个月的企业调研，我们发现模具热处理车间主要存在以下几个问题： 1 批组合规则不规范，经验成分多，偶然性强。 由于在工件进行批组合时，受交货期、材料、设备产能、热处理加工时间和 装卸时间等诸多条件的约束，调度人员很难考虑全面。该企业现行的批组合制定 都是由调度人员根据自己的经验来对工件进行分批，其中存在很多偶然因素，得 广东丁业人学t 学硕 j 学位论文 出的批组合也往往不是最佳组合，由于分批不佳，使得设备的生产效率不高、零 件的质量不过关、某些关键零件的工期延误等问题时有发生。 2 热处理车间批调度也是凭经验在调度，人工估算很难实现最优调度。 热处理车间的批调度不同于一般的批调度，后两个加工阶段相同且设备有限， 存在明显的资源受限问题，而且第一道工序设备可用来担当后续工序的加工设备， 使得调度优化的预期更优，而调度人员一般都是根据生产计划凭主观经验来设计 批与批之间的调度方案，由于问题的复杂程度和人工估算能力之间的差异太大， 使得在实际生产中，出现调度不合理的情况较多，某些应该优先排产的任务被排 后，从而导致某些零件的完工期偏晚，影响模具交货期。 3 企业目前的调度主要只是考虑了交货期，对热处理加工成本不够重视。 如果能够在尽量保证交货期的条件下让热处理加工成本最小，必然能够降低企 业生产成本，在当前日趋激烈的竞争环境下，对企业是大有裨益的，这也是企业 管理人员所期盼的。但至今该企业没有考虑如何将热处理成本和交货期成本联系 起来以使得总成本最小这个问题。 因此，热处理车间的主要问题表现为：生产计划性不强，生产效率不高，对工 件的组批和批间的排序缺乏科学的方法指导，主要凭工人的经验来进行生产调度， 上述各种因素都可能影响模具的质量、交货期和生产成本。 1 2 研究现状 车间作业调度问题( j o b - - s h o ps c h e d u li n g p r o b l e m ，简称j s p ) 是一类典型的 n p 组合优化问题【2 。3 1 。 在算法研究方面，传统的j s p 问题求解方法主要包括分支界定、整数规划与调 度规则等方法【4 巧】随着对j s p 问题研究的不断深入以及智能算法的日渐成熟，对 4 第一章绪论 该问题求解算法的研究逐渐转向使用启发式智能优化算法，包括遗传算法 ( g e n e ti ca l g o r it h m ，g a ) 、模拟退火算法( s i m u l a t e da n a e li n g ，s a ) 、人工神 经网络以及蚁群算法等【6 7 】 在批调度研究方面，近年来批量调度问题成为p p c 领域的一个热点。并且国内 外的学者提出了不少集成模型、规则和解决算法。 在国内，唐立新等研究了轧钢厂的精轧工序轧制批量调度的优化模型，并采 用遗传算法和分支定界法解决这类问题【8 1 。魏法杰、周艳、严芳对我国飞机制造企 业热加工车间的计划体系模式进行了深入的探讨，提出了热处理车间如何根据自 身的生产特点，有效地做好计划工作的方法【9 1 。熊红云，何钺针对多级、多资源 约束的柔性生产线，建立了一种分批与调度集成的通用模型( g l s p ) 。他们提出了 解g l s p 问题的算法( 遗传启发算法) ，并设计了特定编码和算子1 1 0 】。陈昌领等【1 1 1 2 】 利用时间间隙的概念和连续时间的表达，建立了混合整数线性规划( m i ip ) 的数学 模型，并表达了单阶段多产品批处理过程的调度问题，他们还进一步提出一些有 效的启发式规则，用来加快模型的求解速度。白宏斌、杨建军、王健研究了在设 备产能、交货期等约束条件下，以加工周期与拖期惩罚之和最小为优化目标的批 量计划问题【1 3 】。李莉，乔非，吴启迪研究了半导体生产线批加工设备的调度规则【1 4 1 。 王晓峰、谷寒雨研究了半导体生产线上有加工类型限制的并行批处理机组调度问 题，提出了一种改进的a t c _ b a t c 调度规则【1 5 】。文献【1 6 1 研究了批量计划的约束满足 问题，提出了组批率的概念。文献【1 7 l 和文献研究了分批排序中最优解的问题。 在国外，1 9 9 9 年h u r i n ku 9 1 提出利用指数邻域来解决单机批调度问题，将优 化问题分成批设计和批调度，采用遗传算法优化批设计，启发式算法优化批调度， 但没有考虑顺序约束j o r d a n 2 0 1 研究了包括顺序建立时间的批调度问题o v a c i k 等研究了建立时间与顺序相关的批次调度问题p i n t o 2 2 彩1 研究了多阶段批处理 过程的调度，他的方法是采用双时间轴：其中一个时间轴表示订单生产，另一个 气 广东t 业人学下学硕f j 学位论文 时间轴则表示设备的分配，然后匹配这两个时间轴，从而建立了多阶段批处理过 程的数学模型。1 9 9 9 年a l ia l l a h v e r d i ，j a t i n d e rn d g u p t a 2 4 1 发表了关于排序 问题的综述，总结从1 9 6 0 s 至u 1 9 9 9 年以来的调度的研究发展情况。c e r d 6e ta l 2 5 1 在考虑订单发布时间、到期时间、设备准备时间、顺序相关建立时间和产品生产 约束等基础上建立了具有并行处理设备的多产品批处理过程调度数学模型，调度 的目的是使生产时间( m a k e s p a n ) 、订单总体延迟( o v a l lt a r d i n e s s ) 或延迟订单个 数最小在此工作的基础上，m a n d e ze ta l 2 6 1 将设备分配和排序分别表达成两类 o 一1 变量，重新表述了该模型，并且根据订单大小和设备的生产能力建立了分批模 型( b a t c h i n gm o d e l ) 以确定每个订单需生产的批次数量及相应批次的太小l e e 2 7 1 认为分批和调度是生产计划与控制( p p c ) 的两个基本问题，传统的m r p 在计划阶段 运用递阶分解方法，即先进行分批( 确定生产批量) ；再根据分批结果安排具体的 加工顺序，即计划的调度实现问题由于分批阶段考虑的调度约束非常有限，难 以保证生成的计划找到一个具体可行的调度策略。 虽然国内外已总结了许多的调度模型、规则和算法。但没有一种能适应所有 的制造环境，因为调度的性能在很大程度上取决于生产环境、目标等因素，选用 不同的模型、规则和算法，其结果也差异很大。 1 3 本文总体介绍 1 3 1 本文的研究目标 本文以广州某压铸模具制造有限公司的热处理车间的实际情况为背景，研究 了基于模具项目计划的热处理车间的批调度问题，并在此基础上设计开发了一套 模具信息管理系统，用以指导该模具企业整个生产运作流程，优化排产，缩短热 处理时间，从而减少项目拖期的可能性，最终提高企业的核心竞争力。 6 第一章绪论 1 3 2 本文的研究内容 本文以广卅i 某压铸模具制造有限公司的热处理车间的现状和该企业的热处理 加工原则为研究对象，将热处理批调度分为以下三个部分进行研究： 1 ) 批组合：根据车间的常见成批原则，总结出正确合理的热处理零件成批规则， 并在此基础上，考虑模具项目计划进度、设备产能、加工成本等条件影响，采 用启发式算法寻求批组合的最优解。 2 ) 批排序：在批组合的基础上，充分考虑每个零件的交货期、车间生产能力等条 件影响，采用遗传算法将各批零件进行排序，从而使得惩罚成本最小。 3 )以w i n d o w s 2 0 0 0 为开发平台、m i c r o s o f tv i s u a ls t u d i o n e t 为开发环境、c 群为 开发语言、s q ls e r v e r 2 0 0 0 为后台数据库，开发一个基于c s 架构的具有辅助 决策功能的热处理车间生产调度原型系统。 1 3 3 本文的章节 本文的章节设计如下： 第一章：绪论。指明了本论文研究的背景、目的、意义及国内外研究的现状。 第二章：基于模具项目计划的热处理批组合数学模型。 第三章：f f d 算法求解热处理批组合问题。 第四章：模具热处理车间的批排序数学模型。 第五章：求解批排序问题的遗传算法。 第六章：系统设计与开发。 全文的总结与展望。 7 广东t 业人学1 二学硕f ：学位论文 第二章基于模具项目计划的热处理批组合数学模型 批组合，也称分批，它是按照一定的约束规则将不同零件归集在一起，组合成 一个或者多个批次( b a t c h ) 。随着科学技术的发展和生产实际应用需求的提高，批 组合的研究也不断深入，并取得了大量的科研成果，其研究成果在半导体、p c b 等行业也得到了广泛应用。 2 1 问题描述 热处理批组合优化问题的数学模型可以描述为：有 个工件要在热处理炉中进 行热处理，每个工件都有它独自的已知属性，这些属性包括重量、材料、尺寸、 计划开工时间、预计到达时间等，管理者需要寻找一种策略将n 个工件分成同时满 足热处理炉装炉量要求、材料组合要求、炉空间尺寸要求和工件加工进度要求等 多个约束条件的m 个批次，目标是在保证计划进度的条件下使得每一炉都装得尽 可能地多，即使得装炉量最大，从而批数m 最少( n 、m 为正实数，刀 m ) 。 首先，根据车间实际情况，我们可以做以下基本假设t l 、每个工件的尺寸都小于炉的尺寸空间。 2 、每个工件的重量都小于最大装炉量。 3 、工件的各属性都已知，这些属性包括重量、材料、尺寸、计划开工时间、预计 到达时间，但是工件同类属性的取值可以彼此不同。 2 2 批组合约束条件 所谓热处理的批组合，就是指按照一定的约束规则，把可以构成一批的工件放 到一起，组成一批进行热处理。热处理的批组合约束分为：材料类型约束、装炉 量约束( 重量约束) 、尺寸约束与时间约束( 计划进度约束) ；考虑到同一种加工 8 第一二章基于模具项目计划的热处理批组合数学模型 种类的工件重量与外形尺寸成j 下比，当工件的重量小于最大装炉量时，外形尺寸 也基本满足约束条件，因此本文经过简化，没有考虑尺寸约束。 为了便于说明，我们需要首先定义主零件的概念。所谓主零件，就是指在某 一工件集合中优先级最高的那个零件，也可称为种子零件。本文中的优先级指标 主要是时间指标。 设有个零件，零件f 的时间指标为t ，预计到达时间为p 缸，计划开工时间为 d 缸，卢 1 ，2 ，3 ，n ) 。则有下述结论： 情形1 ：当工件仇p 记时，即工件正常到达，不考虑设备能力限制的情况， 则可在预计到达时间和计划开工时间之间的任意时间段加工该零件，相对于其它 零件而言，在只考虑保证计划进度的条件下，只要它们的预计到达时间都在该零 件的计划开工时间之前或者同时到达，则它们都可以与该零件进行组批。因此， 对于提- 日, t n 达的工件，我们将计划开工时间作为时间指标，即t i = 见。 情形2 ：当工件的巩 仇时，即工件延误，不考虑设备能力限制的情况，最 佳的预期只能是能够保证该工件在预计到达时间时刻加工，相对于其它零件而言， 在只考虑保证计划进度的条件下，只要它们的预计到达时间都在该零件的预计到 达之前或者同时到达，则它们都可以与该零件进行组批。因此，对于延误的工件， 我们将预计到达时间作为时间指标，即t i - - - - - 巩。 基于上述论述，有： t i = m a x ( d f c ，巩) ( 2 1 ) 比较各零件的时间指标t ，t i 最小，则该零件具有最高的优先级，即m i n ( t ) 零件为主零件。 2 2 1 材料约束 工件在组批时是受到材料约束影响。一般来说，同种材料完全可以放在起 9 广东t 业大学t 学硕i ：学位论文 进行组批，但不同种材料的组批情况如下表： m l 类：日1 3 、暇0 2 、1 2 3 4 4 、8 4 0 7 m 2 类：h l l 、s m v 3 1 2 3 4 3 m 3 类：、a d c 3 m 。类：d a c 5 5 、d i e v a r 即只要是相同材料类就可组批。 由于只有同类材料的零件才能组批，因此，我们可先将要分批的所有零件归 入所属的零件类中，即将g 赋值为m 七：q = m 。( e 为工件f 的材料，m 。为工件 f 的材料种类) 。这样即满足了本身的约束限制，同时也为后面的算法缩小了搜索 空间，提高了搜索效率。 2 2 2 时间约束 各批中的零件原则上应该不影响同批主零件的计划加工进度。 i f ( d 缸d 七c )则玩d b ( 2 2 ) 即如果主零件提前到达，每批次所有零件的预计到达时间应该在该批主零件的 计划开工时间之前到达。这样就可以保证该批次的零件都能在主零件的计划开工 时刻可以开工；同时，由于主零件的优先级最高，所以其它零件的计划进度也不 会受到影响。 i f ( d b ：主零件为每批中计划 开工时间最早的零件。形为工件i 的重量；c ，为工件i 的材料，m 。为工件i 的材料 种类。u 。为设备的能力上限；u ：为设备的能力下限；d 如为工件f 的预计到达时问； 疋为第尼批中主零件的时间指标，若工件f 被选中，则x ，= 1 ，否则x f = o ；f 。 组批率表示单批零件的总重量与设备能力上限的比值。 分( 组) 批模型： 目标函数： 肋彬正u ( 2 6 ) 广东丁业人学t 学硕f ：学位论文 s t c t = mk d 缸瓦 u 2 彬置u i 一 ( 2 7 ) ( 2 8 ) ( 2 9 ) 上述各式中：( 2 6 ) 式表示分( 组) 批率最大，即每批装的最多，从而批数最 少。( 2 7 ) 式表示材料约束。( 2 8 ) 式表示时间约束。( 2 9 ) 式表示装炉量约束。 2 4 本章小结 本章主要描述了模具热处理批组合的目标，同时介绍了批组合过程所存在的多 重约束，并对其进行了详细的分析，最后建立了热处理批组合的数学模型。 1 2 第三章热处理批组合问题的启发式求解算法 第三章热处理批组合问题的启发式求解算法 由于在不考虑动态时间约束的情况下，工件热处理工序的分( 组) 批问题属于 一类装箱问题，所以在这里，有必要先简单介绍一下装箱问题及其常见求解方法。 3 1 装箱问题 装箱问题可简要地描述为：将刀个物品装入m 个箱子( n m ) ，其中每个物品 的重量为彬，每个箱子的最大装载量为u j ，在满足每个箱子都不超载的条件下， 如何使得所使用的箱子数所最小【2 8 】( 刀、m 、彬和u j 均是正实数，i 以，歹m ) 。 当重量限制u j 为常值【，时，装箱问题可等价于： m a x e 形墨c a 彬鼍c ( 3 1 ) 五= l ，表示物品f 被放入箱中；置= o ，表示物品i 没被放入。 从计算复杂性理论来讲，装箱问题( b i np a c k i n g ) 是n p 问题，在短时间内 无法得到较大规模问题的精确解【2 9 1 。因此在实际应用场合，往往采用启发式求解 方法近似求解，常见的启发式求解方法有：n f ( n e x tf i t ) j 匠似算法、f f ( f i r s tf i t ) ：i 匠 似算法、f f d ( f i r s tf i td e c r e a s i n g ) 近似算法、b f ( b e s tf i t ) 近似算法等3 0 1 。而 文酬3 1 1 对降序首次适应算法( f f d ) 进行了定义和描述。 本文所面对的问题比一般装箱问题更为复杂，首先主零件是必须放入箱中的， 即主零件不参与f f d 算法过程而直接装箱；其次一般装箱问题的装箱物品数是确 定不变的，而本文中每次分批都会因为主零件的变化而有新的零件插入，主零件 通过约束决定着工件集合的组成，每一次新的分批，其主零件都不同，其进行装 箱的工件对象也不同，即还存在动态的时间约束。虽然如此，其装箱问题的本质 广东丁业人学t 学硕一i ：学位论文 并未改变。 3 2f f d 分批算法 基于上述的不同点，我们对热处理的分批问题采取如下启发式策略：每次分批 只拿出一个箱子( 炉子) ，首先直接装入主零件，然后采用f f d 规则对其他工件排 序依次进行装箱，不能装入当前箱子中的工件则返回到待加工工件集合中等待参 与下一次装箱。 基于f f d 规则的热处理零件启发式分批算法原则可以描述为： 1 、将主零件放入箱中； 2 、将零件按重量大小降序排序； 3 、按照降序进行装箱，不能装入的放回。 算法步骤如下 步骤1零件归类：根据零件的材料信息将待分批的零件归入其所属的材料类中； 步骤2 选取主零件：对于某一材料类的零件集，比较各零件的时间指标六，选出 主零件； 步骤3 更新可装箱零件集：根据主零件的时间指标将能满足时间约束的零件选出， 从而得到可以与主零件一同装箱的零件； 步骤4 将主零件放入箱中； 步骤5降序t ：l l ；n ：将可装箱零件集中的零件按照重量大小降序排列； 步骤6 装箱：按照降序依次将各零件装箱，不能装入的放回可装箱零件集中，如 果装箱结果小于u ，则取消该次装箱，该次装箱转为人工操作，由车间人 员进行研究处理，如果结果大于u ，则转步骤7 ； 步骤7 得到一批，并将该批中的所有零件从零件集中删除： 步骤8 如果主零件不为空，则转步骤2 ；如果属于其他情况，则转步骤3 。 1 4 3 3 计算实例 本文根据广州市某模具企业热处理车间的实际情况，选取了热处理车间的某 段历史数据作为实例对象，进行有效性验证。根据车间设备的实际能力，装炉量 约束取值为：【，一= 5 0 0 k g ，【，：= 2 0 0 k g ，材料如材料约束中所述，、d 如、仇、 e 、彬与数学模型中同义，e 表示第_ ，批，j 为正整数，3 1 9 表示时间为3 月1 9 日，历史数据及原始分批方案( 热处理车间的实际分批方案) 如表3 1 所示，经过 本文优化方法得到的新分批方案如表3 2 所示，表3 3 为对表3 1 和表3 2 的数据 统计。 表3 1 历史数据及原始分批方案 t a b l e3 - 1h i s t o r yd a t aa n ds c h e m eo fi n i t i a ls c h e d u l e i n g n ) 一 ) bp眈pc ，w 丐p p 1 p3 1 9 )a 一2 a ，h 1 3 2 0 0 ， p 1 03 2 0 p3 2 3 ph 1 3 2 0 0 p p 2 3 2 2 】a 一2 5 )w 4 0 3 p吕5 一 p 2 13 2 1 j3 2 5 )h 1 a 31 1 0 p 2 1a 一2 2 p3 2 5 一w a 0 2 p1 1 0 - ， p 3 j3 2 3 oa 一2 7 )w 4 0 3 p1 5 0 + j p a p3 2 4 p3 2 7 ph 1 a p1 1 0 ， p 4 p4 2 】3 2 9 一w 4 0 0 pa 6 0 ， p 5 j3 2 1 5 p3 3 1 pw 4 0 0 - 02 2 0 p p 5 ja 一2 6 ) 3 3 1 jw 4 0 0 p1 6 0 p 6 ，3 2 7 j o4 2 + j1 心0 0 p1 7 5 p p 6 3 2 8 p 4 2 一 w 4 0 0 p1 0 2 ) p 6 p3 2 7 o4 2 pw 4 0 0 p1 1 2 p p 7 3 2 9 p 4 4 pd 工e v a r 一1 2 0 - ， p 7 j3 3 0 p4 4 1d 工e v a r p1 2 0 ， p 8 + j3 3 1 p4 6 一d a c 5 5 p1 2 0 ， p 日一4 1 p4 6 舻 d 工e v a r 一 1 2 0 p 表3 2 新分批方案 t a b l e3 - 2s c h e m eo f n e ws c h e d u l e i n g 广东下业人学t 学硕 j 学位论文 n p眈妒e x spc tp 习踞一 p 1 一a 一1 9 p3 2 a h 1 3 2 0 0 1 p 1 p3 2 0 p3 2 3 - 3h 1 3 p 2 0 0 p p 】p3 2 2 p3 2 5 一w 4 0 3 )8 5 一 p 2 pa 一2 1 p3 2 5 ph 1 3 p1 1 0 p p 2 j 3 一z 3 pa 一2 7 p w 4 0 3 p1 5 0 j p 2 p3 2 2 p3 2 5 w 3 0 2 1 1 0 p 2 p a 一2 4 p3 2 7 p h 1 3 p1 1 0 】 p 3 p4 2 p3 2 9 w 4 0 0 p3 6 0 p p 4 p3 2 5 p3 一a l pw 4 0 0 p2 2 0 、 p 4 p3 2 6 p4 2 pw 4 0 0 p1 7 5 p p 4 p a 一2 8 4 2 )w 4 0 0 p1 0 2 p p 5 p3 2 7 p3 3 1 pw 4 0 0 1 6 0 p p 5 3 2 7 p4 2 pw 4 0 0 pi 1 2 j p 6 p3 2 9 妒4 4 pd 工e v a r p1 2 0 p p 6 a a o 一4 4 pd 工e v a r p1 2 0 p p 6 pa a 1 )4 6 pd a c 5 5 p1 2 0 p p 6 )4 1 p4 6 一d 工e v a r p1 2 0 一 表3 数据统计 t a b l e3 3d a t as t a t i s t i c s 矿 p 1 )p 2 0p pp 如p 和p p 和p 髓 原始黝黜磨 8 0 秘 6 1 弦5 2 j i ) 7 2 7 c 37 蛳7 7 。8 i 34 8 弦 哇8 如 新方案缀批垂 9 7 静 9 6 x # 7 既p9 9 4 f5 1 4 淞9 6 淞 pp 从表3 3 的数据统计可以看出，新方案所得的批次数比原始分批方案的批次数 明显减少了2 批。总体来说，新方案的组批率也有显著提高，这充分说明新方案 明显实现了目标优化，降低了成本，缩短了热处理工序的总工期，说明了这一启 发式算法的有效性。 ：主! 纠3 - 2 0 3 - 2 1 3 - 2 23 - 2 33 - 2 4 ：蟪i 臻l 黧 控i 丝l 主型| 塑! l 曼= ! l 缝i 蝴| 终i 蠛i 缝l 盟l ! 曼l 一 图3 1 原始数据甘特图 f i g 。3 - 1g a n t tc h a r to f t h eh i s t o r ys c h c d u l e i n g 1 6 第三章热处理批组合问题的启发式求解算法 1 3 2 1 3 - 2 2 3 2 33 一翻3 - 为i3 - 益 3 - 2 t 3 - 2 b ：3 - d 口l2 3 0 3 - 3 1 | 卜l 4 - 2 t - 3 一l4 5 4 6i tl _ l _ ll l 一 一 l i 图3 2 新方案甘特图 f i g 3 - 2g a n t tc h a r to ft h ei i c ws c h e d u l e i n g 对于分批排序问题，批次数的优化对排序也会起到优化作用。然而批次的优化 又会改变各批的某些指标属性，比如各批的可开工时间( 可理解为每批中工件预 计到达时间的最大值) 会延后，而且允许的加工时间范围也会缩小，如图3 1 、3 2 中所示。所以在批次数最少的条件下，可以针对各指标进行二次优化，将各批中 的零件在满足约束条件的限制下进行置换，以提高批的相应指标属性。 3 4 本章小结 本章节对装箱问题及其常见求解方法进行了简要的介绍，同时把热处理批组合 问题转化一类复杂的且带多重约束的装箱问题，并采用f f d 算法对其进行了算法 设计，最后通过实例计算对算法的有效性进行验证，验证结果表明该算法有效。 1 7 广东t 业大学t 学硕l ：学位论文 第四章模具热处理车间调度的批排序数学模型 排序问题是一类与生产、生活非常密切的问题，小到个人的生活时间安排， 大到国家紧急事务的调度，都可以看成是排序问题。现代科学技术很早就开始了 对排序问题的研究，并取得了大量硕果。当前，仍有大量专家、学者对该问题进 行深入研究，这直接推动着排序问题向更高层次、更广领域发展。 4 1 问题描述 热处理批排序问题可描述为： 1 有n 批要加工的工件，每批有多个工件，每个批次都必须经过以下加工流程加 工：淬火+ 回火一空冷一回火一空冷一回火，即一道淬火+ 回火工序和两道回火 工序，共三个阶段。 臣銮至至口空冷吐 亘口空、冷叶j 习一空冷一 图4 1 热处理加工流程图 f i g 4 - 1p r o c e s s i n gf l o wc h a r to fh e a tt r e a t m e n t 2 在设备使用方面：每道工序都有多台设备，执行一次加工任务只能使用一台设 备，对于单台设备而言：淬火炉即可以用来进行淬火加工，又可以用来进行回 火加工，具有多功能特点；而回火炉只能进行回火加工，不能用来进行淬火工 艺。 1 8 第阴章模具热处理乍间调度的批排序数学模型 图4 2 热处理的设备功能 f i g 4 - 2f u n t i o no fh e a tt r e a t m e n te q u i p m e n t s 3 在加工能力方面：淬火炉的加工能力与回火炉相同，因此不须对各批次的工件 进行重新拆分组合。 4 每批有多个工件，热处理加工时同批次的工件是同时开工，同时完工，加工过 程中不允许中断。 5 在每道工序，各批次的加工工时不完全相同；对于每个批次，其在各道工序的 加工工时也不完全相同。 6 由于每次回火完多必须经过空冷一段时间，因此，热处理各阶段的加工不可连 续。 7 就整个生产系统而言，服从计划指导，执行计划进度，对保证企业生产的稳定、 有序具有重要意义，而且热处理是模具粗加工和精加工的中间关键工序，因此， 任务的超前完工和滞后都会带来不稳定因素。 综上所述，热处理批排序问题是一类多机多阶段( 带重复工序) 且设备多功能 的批处理问题。目标是将各批次在各个阶段的各台设备上进行排序，以使各批次 工件的提前拖期成本之和最小化，即总的提前拖期成本最少。 在研究该问题之前，我们做了以下假设： 1 假设批次数量和工件数已知并确定。 2 每个工件的交货期已知并确定。 3 每个批次的在每道工序的加工时间、冷却时间已知且确定。 4 假设每个零件的提前、拖期惩罚系数已知并确定。 5 每个批次到达热处理车间的时间已知并确定。 6 任务一旦开始加工，中途不允许中断。 7 一台设备一次只能加工一个批任务。 1 9 广东1 = 业人学工学硕 j 学位论文 8 各工件之间不存在优先约束关系，可独立加工。 9 各批次的加工准备时间忽略不计。 1 0 每个批次的装卸时间和开停机时间相同，且都计算入各批次的加工时间 中。 4 2 数学模型 首先有以f 定义： s i 为各批次的集合，扣 1 ，2 ，3 ，n ) ，n 为批数；弓为第f 批的第个零件， 歹= 1 ，2 ，3 ，u ，u 为第f 批中的零件数；h 为工序数，h = 1 ，2 ，3 ，v ，v 为总工序 数；为批次f 在第h 道工序的开始时间：第f 批在第五道工序的加工时间为， 冷却时间为毛。；d 驴为第f 批的第，个零件的交货期；c ：f f 为第f 批中第个零件的完 工时间；为工件提前完工惩罚系数；屈为工件拖期完工惩罚系数， 0 ， 屈 o ；k c 为淬火设备数量，k h 为回火设备数量，k 为第h 道工序可使用的设备数； m 从为在第h 道工序第k 台机器上加工的批数；q 为第f 批的完工时间。 跺= 佬掣工件在第膛工序的第殆设备上第研拗旺 目标函数： s t 删g = 口f ( d 咖一c 驴) + 孱( c 扩一d 拈) ( 4 1 ) i = l ( 4 2 ) s = 1 ( 4 3 ) i = 1 t ( h - i 弦+ 五汩+ 五) c 瓢 ( 4 4 ) n n 磷附1 一蹄( 凰+ + 死。) o ( 4 5 ) 如= l = l 司 砌胁 s “ 一 第四章模具热处理中间调度的批排序数学模型 m 从= n ( 4 6 ) c u = 乃3 ，+ 乃3 p + 互3 。= c ：f ( 4 7 ) 七：jt 拈1( 4 8 ) + k h e l s e 上述各式中：式( 4 1 ) 为目标函数：目标值为工件的提前、拖期成本之和 最小。式( 4 2 ) 表示：批次f 在每道工序必须加工一次。式( 4 3 ) 表示：批次f 在 每道工序必须选择一台设备进行加工。式( 4 4 ) 表示：同一批次必须在冷却好后 才能进行后序加工。式( 4 5 ) 表示：在同道工序的同台设备上，后一批必须等前 一批加工完才能进行加工。式( 4 6 ) 表示：在某道工序中所有设备加工的批数之 和为总批数。式( 4 7 ) 表示：批次f 中零件的完工时间为批次f 的开工时间、加工 时间和冷却时间之和，且等于该批的完工时间。式( 4 8 ) 表示：不同工序阶段可 使用的设备数。 4 3 本章小结 本章节在已确定分批结果的基础上，对热处理批排序问题进行了描述、分析和 归纳。并建立了热