（机械工程专业论文）中小型制造企业车间生产调度问题的分析与研究.pdf

南京理工大学硕士学位论文 中小型制造企业车间生产调度问题的分析与研究 摘要 本文从车间生产调度理论与方法的研究入手，探索如何应用先进实用的调度方 法，以实现均衡生产、缩短零件加工周期、提高设备利用率的优化目标。结合九江机 电设备厂机加工车间的生产实际，本文对车间生产调度与管理现状进行了分析，指出 了现有调度与管理模式的不足。并根据机加工车间现有的设备布局、生产类型和产品 特点等，按成组生产单元优化设计原则，提出了一种面向成组技术的车间改造设计方 案。 在研究生产调度优化方法和建立成组单元的基础上，根据企业自身特点，开发生 产调度系统模型，以成组技术为核心进行系统总体设计。在设计中，以典型零件组偏 心块为研究对象，采用彼得罗夫哈姆算法和实现均衡生产的启发式方法进行排 产，并通过实例验证了调度算法的可行性和系统的实用性，输出了零件的排产甘特图， 对设备利用率进行了计算和显示。该系统的建立和应用，有效地提高了企业的生产管 理效率和水平。 关键词：生产调度；成组技术；算法；系统设计 第1 页 妻室里三盔兰堡主兰丝丝茎 尘皇型丝垒兰兰兰塑竺主塑垦塑垦竺坌堑皇里塞 a b s t r a c t t h i sa r t i c l ee x p l o r e sh o wt oa p p l yt oa d v a n c e da n dp r a c t i c a ls c h e d u l i n ga p p r o v e s t o r e a l i z eb a i a n c e dp r o d u c t i o n , s h o r t e nt h ec y c l eo ft h ep a r t s p r o c e s s i n ga n di n c r e a s et h er a t e o fn l ce q u i p m e n t su t i l i t yb a s e do nt h er e s e a r c ho nt h ew o r k s h o ps c h e d u l i n gt h e o r i e sa n d a p p r o a c h e s t h ec u r r e n ts t a t u so fs c h e d u l i n ga n dm a n u f 蛐g m a n a g e m e n ti sa n a l y z e d a n dt h e i rd i s a d v a n t a g e sa r ep o i n t e do u tb yc o m b i n i n gt h ep r o d u c t i o nr e a l i t yo ft h e m e c h a n i c a lp r o c e s s i n gw o r k s h o po f j i u j i a n gm e c h a n i c a la n de l e c t r i c a le q u i p m e n t p l a n t a r e b u i l d i n gs c h e m eo f w o r k s h o pi sb r o u g h tf o r w a r db a s e do nt h ep r e s e n te q u i p m e n tl a yo u t , m a n u f a c t u r i n gt y p e sa n dp r o d u c t sf e a t u r e s e t c i nt e r m so fd e s i g np r i n c i p l e so fg r o u p w o r k i n g u n i t a c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h ep l a n ti t s e l f , as c h e d u l i n gs y s t e mm o d e li s d e v e l o p e da n dt h eo v e r a l ld e s i g no f t h es y s t e mh a sb e e nm a d ew i t hg r o u pt e c h n o l o g ya si t s c o r eo nt h eb a s i so f s t u d y i n gs c h e d u l i n go p t i m i z e da p p r o a c h e sa n db u i l d i n gg r o u pu n i t s i n t h ed e s i g n , p e t r o v - h a ma l g n r i t h ma n dh e u r i s t i cr u l e sa r ea d o p t e df o rs c h e d u l i n g t h e 掣o u p so fc l a s s i cp a r t s e c c e n l 五cb l o c k sa r t h eo b j e c t sw h i c hh a v ev c r i f i e d t h e f e a s i b i l i t yo ft h es c h e d u l i n ga l g o r i t h ma n dt h ep r a c t i c a b i l i t y o ft h es c h e d u l i n gs y s t e m t h es c h e d u l i n gc h a r t sa r eo u t p u ta n dt h ee f f i c i e n c yo ft h ee q u i p m e n ti sc a l c u l a t e da n d d i s p l a y e d t h ep r o d u c t i o nm a n a g e m e n te f f i c i e n c y a n ds t a n d a r dh a v eb e e ni m p r o v e d e f f e c t i v e l yb ys e t t i n gu pa n da p p l y i n gt h i ss y s t e m k e yw o r d s ：s c h e d u l i n g , g r o u pt e c h n o l o g y , a l g o r i t h m , s y s t e md e s i g n 第页 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学位论文中，除 r 加以标注和致谢的部分外，不包含其他人已经发表或公布过的研究成果，也不包含我 为获得任何教育机构的学位或学历而使用过的章孝科。与我同工作的弼事对本学位论文 做出豹贡献均己在论文中侔了明确的说明。 研究生签名： 彬年艄弘目 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，町以借阅或上网公布本学位 论文的全部或部分内容，可以向宵关部门或机构送交并授权其保存、借阅或上两公布本 学位论文的全部绒部分疮容。对于保密论文，按保密的有关蝮定和程序处理。 研究生签名： 年，月圳j 熄 南京理t 大学硕士学位论文中小型制造企业车间生产调度问题的分析与研究 1 绪论 1 1 车间生产调度问题概述 1 1 1 车间生产调度问题的涵义 车间生产调度就是对一个可用的加工机床集在时间上进行加工任务的分配，以满 足一个性能指标集。典型的车间生产调度问题包括一个要完成的作业集，每项作业由 一个作业集组成。各操作的完成需要占用机床或其它资源，并且必须按一个可行的 工艺次序进行加工；每台机床可加工零件的若干操作，并且在不同机床能加工的操作 集可以不同。在约束条件下，调度的目标足将作业合理地安排到各机床，并合理安排 作业的加工次序和加工开始时间，同时优化一些性能指标。在实际车间生产调度中， 一般需要考虑两个方面的调度问题，一是生产作业的调度，二是生产资源的分配。目 前大部分研究集中在生产作业调度上，没有考虑资源分配，而将资源作为约束处理。 厂级编制的车间作业计划，给出了各种零件、部件的投入产出进度安排，但还不 是车间的执行计划。车间还要对各项任务的作业顺序合理安排，分派各班组、各工作 地的任务，以便在完成计划任务的前提下，缩短生产周期，均衡设备负荷，提高操作 人员的工作效率，取得良好的经济效益。生产作业的这种细节安排是车间生产调度控 制的重要一环，它建立了计划与生产控制间的直接联系，是厂级各车间生产管理人员 所必须研究的一个更重要的课题。 1 1 2 车间生产调度的分类 生产调度主要是在生产作业计划的基础上确定生产任务的加工顺序以及各种制 造资源的实时动态调度。确定生产任务的加工顺序为作业排序问题，它有不同的分类 方法。最常用的分类方法是按机器、工件和目标函数的特征分类。按机器的种类和数 量的不同，可以分为单台机器的排序问题和多台机器的排序问题。对于多台机器的排 序问题，按工件加工路线的特征，可以分为单件作业( j o b - s h o p ) 排序问题和流水作 业( f l o w - s h o p ) 排序问题。工件的加工路线不同，是单件作业排序问题的基本特 征；而所有工件的加工路线完全相同，则是流水作业排序问题的基本特征。 按工件到达车间的情况不同，可以分为静态的排序问题和动态的排序问题。当进 行排序时所有的工件都已到达，可以一次对它们进行排序，这是静态的排序问题。若 工件是陆续到达，要随时安排它们的加工顺序，这是动态的排序问题。 按目标函数的性质不同，也可划分不同的排序问题。譬如，同是单台机器的排序， 目标是使平均流程时间最短和目标是使误期完工工件数最少，实质上是两种不同的排 序问题。按目标函数的情况，还可以划分为单目标排序问题与多目标排序问题。以往 第l 页 南京理工大学硕士学位论文中小型制造企业年问生产调度问题的分析与研究 研究的排序问题，大部属于单目标排序问题，而对多目标排序问题则很少研究。另外， 按参数的性质，可以划分为确定型排序问题与随机型排序问题。所谓确定型排序问题， 指加工时间和其它有关参数是已知确定的量；而随机型排序问题的加工时间和有关参 数为随机变量。这两种排序问题的解法本质上不同“1 。 1 i 3 车间生产调度问题的特点 ( 1 ) 复杂性。一是生产因素的多样与复杂，二是车间生产调度问题是在等式或不 等式约束下优化某些性能指标。因此，在求解车间调度问题上，一些常规的优化方法 无能为力。 ( 2 ) 动态随机性。生产中会出现设备故障、急件插入、人员误操作等不可预见因 素，生产调度需要根据生产情况做出动态调整。 ( 3 ) 多目标。车间生产调度往往是多目标的，可分为基于作业交货期的目标、基 于作业完成时间的且标，基于生产成本的目标等”。 1 1 4 车间生产调度问题的研究现状 早在1 9 5 4 年，j o h n s o n 就对两台机床的f l o ws h o p 型调度问题进行了研究，其后 人们开始对生产调度问题进行了更加深入和广泛的研究。在研究方法上，最初是集中 在整数规划、多目标优化、仿真和简单的规则上，这些传统的调度方法在应用中存在 很大的局限性，如难以建立准确约束条件下的数学模型，并且求最优解时间随问题规 模呈指数倍增长，因此只能对小规模的系统求解。近年来，许多专家、学者对启发式 方法进行了更广泛和深入的探讨，因其求解相对简单，实用性好，因而得到大家的普 遍重视。同时，随着各种新的相关学科与优化技术的建立和发展，出现了许多新的优 化方法，如神经网络、遗传算法、基于知识的方法、基于离散事件系统( d e d s ) 的 解析模型和方法等。值得关注的是，人们将这些优化方法有机地结合起来，如遗传算 法与调度规则、仿真与基于知识的方法等相结合，产生了良好的应用前景。 目i j 仃，国内外对生产调度问题的研究已有几十年的历史，我国从八十年代也开始 了对此问题的研究。各种排序理论与算法层出不穷，在理论研究上取得了很大进展， 可是，在如何使这些算法走向实用化方面进展缓慢。其主要原因有两点：一是生产的 复杂性大，企业之间的生产状况千差万别：二是生产技术的飞速发展与新的制造策略、 制造理念的提出，如加工中心、柔性制造系统( f m s ) 、并行工程、敏捷制造等，改 变了人们对生产过程与生产系统的认识。 然而，由于资金、生产状况的制约，当前我国机械制造行业中的绝大多数企业仍 在使用六、七十年代的加工设备，沿用着原有的生产管理模式。九江机电设备厂就具 有很强的代表性，对这类企业的生产调度问题研究是具有重要意义的。 近年来，国内外的一些高校及研究机构相继开发了一些针对此类企业的生产调度 第2 页 南京理工大学硕十学位论文中小型制造企业车间生产调度问题的分析与研究 系统，国外如俄罗斯、日本，国内如清华大学、华中理工大学、西安交通大学等。这 些系统均采用了先进的生产调度算法，但其推广速度落后于c a d 、c a m 系统。究其 原因，除了生产因素的复杂性与多优化目标外，还有一个至关重要的原因是生产调度 系统必须结合生产实际，不可能建立一个通用的生产调度系统。但随着人们对生产调 度问题研究的不断深入和计算机技术的快速发展，计算机辅助生产调度与管理系统的 开发工作将逐步从理论研究阶段走向应用阶段，并日臻完善。 1 2 车间生产调度在企业生产管理中的重要性 1 2 1 制造系统的生产管理及其主要任务 制造系统的生产管理是指对制造过程的管理。制造过程是指从原材料投入生产开 始到产品生产出来准备交付使用的全过程，它分为设计、加工、装配、检验、运输、 储存等诸多环节。在每一个环节中，对生产过程的组织和运行都要进行计划、调度、 协调与控制。生产管理的主要任务是“1 ： ( 1 ) 保证制造系统按产品品种、质量、数量、生产成本和交货期要求，完成计划 规定的生产任务； ( 2 ) 合理配置和利用生产资源( 资金、设备、人力) ，不断提高生产率，降低物 耗，降低成本： ( 3 ) 合理组织生产过程，缩短产品周期，减少在制品，降低库存，加速资金周转。 1 2 2 生产过程组织的基本要求 合理组织生产过程就是在保证按质按量完成生产任务的i ； 提下，尽可能地以最少 的消耗来获得最大的经济效益。为此，组织生产过程必须满足以下五点基本要求”1 o ( 1 ) 连续性。指劳动对象在生产过程中各阶段的运动自始至终在连续不断地进行 着，没有或很少有中断现象。提高生产过程连续性的程度可以缩短产品生产周期，减 少在制品数量，提高设备或生产面积利用率，加速流动资金周转等，一般来说，提高 生产过程连续性可以采取各种技术组织措施。对于中小型制造企业而言，因生产批量 不大，可组建成组生产单元，使其运输线路短而流畅。 ( 2 ) 比例性。指生产过程各工艺阶段、各工序之间在生产能力上及各工种人员配 备上应有适应于产品制造要求的比例，以减少或消除忙闲不均和制约生产的“瓶颈” 现象。 ( 3 ) 平行性。指生产过程中的各项活动在时间上实现平行交叉作业，以缩短生产 周期。同一产品的各种零件在配套的前提下，应尽可能组织平行生产。 ( 4 ) 均衡性。指生产过程的各个阶段和各道工序都要按照规定的节奏，在相同的 时间间隔内生产和交付等量的产品，使各工作地的负荷保持相对稳定，避免发生时松 第3 页 南京理丁大学硕士学位论文中小墅制造企业车间生产调度问题的分析与研究 时紧或前松后紧的现象，以均衡地完成生产任务。实现均衡生产，有利于保证设备、 人员的负荷均衡。 ( 5 ) 适应性。指企业生产过程中对产品品种的变动要有较强的应变能力。 上述各项要求不是彼此孤立的概念，而是相互关系、相互制约的。适应性是比例 性的前提，比例性、平行性是连续性的保证，而均衡性又是比例性、平行性和连续性 的集中反映。因此，企业生产调度人员必须应用系统工程的思想和方法，权衡利弊， 科学地寻找出一个比较令人满意的生产过程组织方案。 1 2 3 车间生产调度的重要性 质量( q u a l i t y ) 、成本( c o s t ) 、交货期( d e l i v e r y ) 是衡量企业生产管理成败的 关键。车间生产调度是制造系统生产管理的核心。生产管理任务顺利实现与完成，最 终要靠合理的生产调度来保证。它研究的是如何合理地步配置加工过程的各种资源， 确定最优的加工流程，减少零件的加工准备、等待与传送时间，从而提高设备利用率 与生产效率，降低生产成本。因此，及时准确的生产调度对生产系统的高效进行有着 重要的影响。一方面，生产调度可以保证生产计划和生产作业计划的有效实施，高效 低耗地使用资源；另一方面，生产调度可以均衡生产，减少在制品的资金占用，提高 企业的经济效益。 1 3 本论文研究的主要内容 车间生产调度问题是企业生产运作管理中最复杂、最棘手的问题。从理论上讲， 人们经过长期的实践摸索出了许许多多的生产调度方法，而本论文的研究不可能也不 必要穷尽一切理论，课题研究的关键在于在正确理论的指导下，针对九江机电设备厂 机加工车间生产调度管理的实际情况，摸索如何应用先进实用的生产调度方法去解决 企业长期存在的一些问题。其主要研究内容可概述为： ( 1 ) 分析和研究面向成组技术的启发式调度方法。 在介绍一般车间生产调度理论与方法的基础上，以缩短零件加工周期、实现均衡 生产、提高设备利用率为优化目标，从求解的最优性和经济性方面比较和分析多种调 度方法，探讨实用的优化算法。 ( 2 ) 建立成组生产单元。 在分析企业现状、设备布局、设备性能、车间生产调度管理模式的基础上，依据 成组单元的设计原则，对九江机电设备厂的机加工车间进行改造设计，零件按加工族 来安排生产，优化物料流程，提高排产效率。 ( 3 ) 建立车间生产调度原型系统。 对车间生产调度系统进行总体设计，建立加工基础数据库，选择彼得罗夫哈 第4 页 南京理工大学硕士学位论文中小型制造企业车间生产调度问题的分析与研究 姆算法和实现均衡生产的启发式算法，对生产作业进行优化排序，输出排产甘特图和 设备利用率，实例验证调度算法的可行性与实用性。 1 4 本论文研究的应用价值 车间生产调度在生产系统中起着重要的作用，随着市场竞争的加剧和产品向多样 化、个性化发展，制造业中单件或多品种，小批量生产占多数并且有逐渐增加的趋势。 缩短产品生产周期、确保产品交货期、降低生产成本，以适应多变的市场需求，对企 业来说是至关重要的，在多品种、中小批量的生产环境下如何组织车间生产调度问题 显得更加复杂和重要。正是基于这一思考，本论文以九江机电设备厂为研究对象，针 对车间生产调度与管理现状，依据零件加工工艺的相似性，将车间改造设计为若干成 组生产单元。在分析启发式方法的基础上，采用成组技术与启发式方法相结合的调度 方法，零件在机床上加工的连续性好，能实现均衡生产，提高设备利用率，缩短零件 的加工周期。并通过开发和应用车间生产调度系统，在提高九江机电设备厂生产管理 水平的同时，也为整个企业建立管理信息系统提供基础条件。 第5 页 南京理工大学硕士学位论文中小型制造企业车问生产调度问题的分析与研究 2 车间生产调度理论与方法 2 1 生产计划调度与控制 生产计划调度与控制的目标是通过对制造过程中物料流的合理计划、调度与控 制，缩短产品的制造周期，减少在制品，降低库存，提高生产资源的利用率。 在制造系统中，零件在系统中的“通过时间”( 称l e a dt i m e 或t h r o u g h p u t ) 主 要由四部分组成：加工准备时间( s e t u p t u n e ) 、加工时间( p r o c e s s t u n e ) 、排队时间 ( q u e u e t u n e ) 和运输时间( t r a n s f e r t r i n e ) 。零件在系统中大量无效的通过时间是导 致库存增加，从而引起生产效益降低的根本原因之一。生产计划调度与控制的主要目 标就是减少这部分非加工时间。 2 1 1 生产作业计划 根据生产与市场需求情况，生产计划一般可分为年度、季度、月、旬或周生产计 划。在此基础上，根据各种资源的实时状态数据，制订工序级生产作业计划，该计划 将确定计划期内各种制造设备的具体使用情况和每日，班内加工的零件种类及数量 等。通过制定和执行生产计划应实现以下目标”1 ： ( 1 ) 合理利用各种生产资源，按品种、质量、产量和交货期等要求制订可实施的 生产计划； ( 2 ) 建立良好的生产秩序，保证生产过程组织符合连续性、均衡性要求。 ( 3 ) 优化某些指标参数，如缩短产品的加工周期、减少在制品数量、加速资金周 转等。 生产计划的主要功能有： ( 1 ) 对生产任务进行最优分组( 批) 。它将生产作业计划分解成日或班次计划， 将生产任务( 待加工零件) 进行最优分组，以减少加工的准备时间，同时提高系统内 各种资源的综合利用率。分组的方法一般是按成组工艺原理将工艺相同或相似的零件 分成一组，使加工过程中刀具和其它资源的调整减少。制订生产任务最优分组策略的 标准有： 生产任务的交货期( d u e - d a t e ) 限制； 组数尽可能少； 为每组生产任务实现最优均衡负荷提供条件； 以系统内其它辅助资源需求限制( 如刀具、夹具、托盘等) 作为约束条件。 ( 2 ) 生产设备的负荷均衡。在生产实际中，零件往往具有多种加工路线，即某一 道工序可由多台可选设备中的一台来完成，在生产任务分组后，必须能平衡各加工设 第6 页 南京理工大学顾士学位论文中小型制造企业车间生产调度问题的分析与研究 备的负荷，使它们尽可能同时完成生产任务。因此，设备负荷均衡的目标是，系统中 设备的负荷尽可能相等，从而使零件通过系统的流通时间最短。 ( 3 ) 生产系统资源需求计划。生产任务的最优分组和设备负荷均衡的主要目标是 考虑满足交货期的前提下，合理利用加工设备。此外，在制订生产计划时，必须同时 制订出系统资源需求计划，如原材料、刀具、夹具、人力资源及外协加工零件等需求 计划，以保证生产作业计划的顺利实施。 2 1 2 作业排序 生产调度是在生产作业计划的基础上确定生产任务的加工顺序以及各种制造资 源的实时动态调度。一般可将生产调度分解为生产任务的静态排序、动态排序和系统 资源实时动态调度三个子问题”1 。 ( 1 ) 生产任务的静态排序是在系统开始加工之前确定每个零件的加工先后顺序， 保证系统以最优( 或近优) 的方式完成加工任务，它一般包括零件组自j 排序与组内零 件排序。一般情况下静态排序不再考虑原材料供应、人员及其它生产资源的约束情况， 因为这些部由生产作业计划所保证了。 ( 2 ) 生产任务的动态排序是在系统加工过程中根据系统当前的实际状态，实时动 态地安排零件在系统内的流动过程。制造系统中随时会出现一些不可预见的扰动，如 加工零件因交货期的改变而导致零件优先级别的改变，急件插入、设备故障、刀具损 坏等，这些扰动会打乱原先静态调度时的零件排序，有时甚至会影响生产任务的负荷 平衡。此时要根据系统的状态做出适当的调整，改变零件的加工顺序和加工路径。 ( 3 ) 生产任务在制造系统中的流动与加工都必须依靠系统资源运行来实现，这些 资源包括加工设备、物料储运设备、刀具、夹具、原材料及人员等。虽然在上述生产 作业计划、生产任务的静态排序与动态排序中已将系统资源作为制订计划与调度策略 的约束条件，即考虑了系统内各种资源的优化利用问题，但由于加工过程中系统状态 的多变与不可预料性，使得系统并不能完全保证在适当的时间为生产任务提供所需的 系统资源，因此需要在加工过程中对系统资源进行实时动态调度。 2 1 3 生产作业控制 上述的生产计划与生产调度都只是为系统内物料的流动做出计划，计划时期望系 统能运行在最优( 或近优) 状态，但实际系统中总会出现各种随机扰动，从而使系统 的实际状态与期望状态之间产生偏差。造成这些偏差的原因主要包括”： 对未来生产活动的预测方法不完善； 生产计划是按照不准确的预测值制订的； 制订工艺规划、日程计划是按标准值来计算的，与实际情况有差别； 在生产过程中，出现随机扰动，如加工设备故障； 第7 页 南京理丁大学硕士学位论文中小型制造企业车间生产调度问题的分析与研究 原材料或其它生产要素短缺： 出现不合格品。 实施生产作业控制的控制者是各级生产指挥与调度人员。被控制者是各生产单元 和生产作业人员。控制范围包括生产全过程，控制的目标是校正系统状态的偏差，使 物料流动和资源利用等尽可能与生产计划与调度所期望的状况相吻合。通过事前控 制，保证按质、按量、按时、成套地投入各生产要素；通过事中控制即现场生产控制， 保证各生产环节按计划要求完成各项生产作业任务：事后控制，即按项目或计划期， 对整个生产活动进行投入、产出及其效益分析：反馈控制，即把信息反馈给下一轮生 产管理工作，以便改进。生产作业控制的过程由系统实时状态数据采集、数据分析与 决策支持组成。它根据系统实时状态对生产活动进行再调度( r e s c h e d u l i n g ) ，再调度 虽然与前述的生产调度在调度策略、目标等方面有相似之处，但再调度的重点是有偏 差的生产任务。生产作业控制所采用的方法因企业的生产类型不同而有所不同。 ( 1 ) 连续生产方式的生产控制方法 在连续生产中，工序、加工时间、材料需要量和操作人员都是预先确定的，对于 进度控制，只需掌握最终工序的完成数量就行了。 ( 2 ) 单件生产方式的生产控制方法 单件生产中生产控制的主要目的是。保证交货期”。在单件生产中，每种产品的 规格，数量、步骤不同，总负荷量及各工序的负荷状况也不相同，结果是材料和工夹 具等准备工作往往不能按计划完成，或者某一工序上的某一品种的进度变化影响到其 他品种或其他工序的进度，这时就需要调整。为此，要正确地掌握各工序、各机床、 各操作人员的加工余力，还要依靠工票和调拨单掌握各产品和每道工序的进度，并提 前发现延迟原因，及早采取措施，以保证交货期。 2 2 传统的优化理论与方法 ( 1 ) 整数规划 通过对车间调度问题建立一个整数规划模型，采用基于枚举思想的分技定界法、 割平面法和0 1 整数规划法进行求解”1 。这类方法虽然从理论上能求得最优解，但由 于其计算复杂性，并不能获得实际应用。 ( 2 ) 多目标优化 多目标优化方法是同时考虑不同目标的共同作用，对于给定的多个目标按各自的 重要程度，分别乘以不同的权数，然后相加作为目标函数，再对此目标函数在多目标 的约束集合上求最优解，也可以选择一个优化目标作为主要目标，而将其它目标作为 约束处理，转化为一个新约束条件下，求主要的单目标的最优化问题。多目标优化能 第8 页 南京理丁大学硕士学位论文中小型制造企业午间生产调度问题的分析与研究 体现不同目标的重要程度，但它通常只能寻找满足约束条件的满意解“1 。 ( 3 ) 动态规划 由于车间生产过程的动态性，系统运行只要任何约束条件发生改变，都可能使原 先求得的最优解失效。利用动态规划法，将车间生产调度过程按时间分为若干相互联 系的阶段，列出各阶段决策过程的函数方程，并利用动态规划的最优化原理进行求解， 使整个过程的总效果达到最优。动态规划将求解问题分解成多阶段进行，使复杂问题 简化，在求解过程中可以利用实际经验，以提高求解效率“。 2 3 启发式方法 启发式方法因易于实现、计算复杂程度低等原因，能够用于动态实时调度系统中， 一直受到人们的关注，并进行了广泛的研究。 2 3 1 优先调度规则 优先规则是按时间进程逐次为每台设备安排一个加工对象时，按照某种优先原 则，从候选的等待作业中选取优先级最高的作业安排加工的方法。优先规则可根据不 同的优化目标制定，不受零件数、工序数与工艺路线的限制，因此应用也较广泛。它 最主要的优点是可以根据最新的实际运行情况信息来决定下一步要做的工作。优先顺 序规则也可预先存入计算机化的排序系统，利用它自动产生工作的调度清单和工件加 工的优先顺序，以便管理者用来为工作地分配工作。在实际中，常用的作业排序规则 有以下几种”1 ： f c f s ( f 妇c o m ef i r s ts e r v e d ) 规则 优先选择最早进入可排序集合的工件。 e d d ( e a r l i e s td u ed a t e ) 规则 优先选择完工期限最紧的工件。 s p t ( s p o r t e s tp r o c e s s i n gt u n e ) 规则 优先选择加工时间最短的工件。 s c r ( s m a l l e s tc d t i c a lr a t i o ) 规则优先选择临界比最小的工件。临界比为工 件允许停留时间和工件余下加工时间之比。 m w k r ( m o s t w o r kr e m a i n i n g ) 规则优先选择余下加工时间最长的工件。 l w r k ( l e a s tw o r kr e m a i n i n g ) 规则 优先选择余下加工时间最短的工件。 m o p n r ( m o s to p e r a t i o n sr e m a i n i n g ) 规则优先选择余下工序数最多的工 件。 l p t ( l o n g e s tp r o c e s s i n gt i m e ) 规则 优先选择加工时间最长的工件。 s o 规则优先选择平均松驰时间最短的工件，松驰时间是零件的交货期与 剩余时间之差，当零件的松驰时间为负时，表明其不能按期交货，松驰时间 除以剩余工序数( 包括当前工序) 则为平均松驰时间。 毗卅d o m 规则随机地挑选下一个工件。 第9 页 南京理工大学硕士学位论文中小型制造企业车间生产调度问题的分析与研究 迄今为止，人们已提出了1 0 0 多个优先调度规则，上面只介绍了其中的十种，这 十种优先规则各有特色。没有哪一条规则各方面都好，要按照目标函数进行评价。最 常用的业绩评价指标有； 作业流动时间。指作业在某车间中的特定工作区或工作中心流动所花费的时 间长度。不仅包含实际加工时间，还包含等候加工时间、各操作之间的运送 时间，以及与设备故障，不可用零件、质量问题等有关的等候时间。作业流 动时间是指作业从到达车间、工作区或工作中心开始，到离开车间、工作区 或工作中心时结束的时间长度。一组作业的平均流动时间等于作业总流动时 间除以作业数。 作业延期时间。指预期的作业完成日超过作业预定日期或向顾客许诺的日期 的时间长度，是实际完成时间与预定日期之差。如果我们只记录完成时间超 过预期日期的作业差异，而不记录提前完成的作业，使用的术语就叫作业拖 延时间。 时间跨度。指完成一组作业所需的全部时间，是从组中第一项作业开始到组 中最后一项作业结束的时间长度。 平均作业数。车间中被认为是在制品存货的作业数。一组作业的平均在制品 数可由下式求出：平均作业数= 总流动时间时间跨度。假如作业表示同等数 量的存货，平均作业数也就能反映平均在制品存货。 下表是在某工作中心等候加工的6 项作业的加工时间与预定日期。假设工件到 达顺序与表中顺序相符，按f c f s 、8 p t 、e d d 、8 c r 四种规则求解作业顺序、平均 流动时间、平均延期天数、工作中心的平均作业数”。 ( 1 ) f c f s 顺序是简单的a b c d e f 。实效性分折为( 见下表) ： 平均流动时间：1 2 0 1 6 = 2 0 天 平均延期天数：5 4 1 6 - - - 9 天 时间跨度是4 1 天，工作中心内作业平均数：1 2 0 4 1 = 2 9 3 第l o 页 南京理t 大学硕士学位论文中小型制造企业车间生产调度问题的分析与研究 ( 1 ) ( 2 )( 3 ) ( 2 ) 一( 3 ) 顺序 延期天数( 如果为 加工时间流动时间预定日期 负则赋值0 ) a2 27o b81 01 6 o c 41 441 0 d1 02 41 77 e52 91 5 1 4 f1 2 4 l1 82 3 4 11 2 0 5 4 流动时间列表示累积加工时间，因此将此列数值加总，再除以待加工作业数6 ， 就是每项作业在此工作中心花费的平均时间。类似地，流动时间总数除以总加工时间 可得工作中心内的平均作业数。 ( 2 ) 使用s p t 规则，作业顺序是a - c e b d f ( 见下表) 。求得的实效性评价指 标值为： 平均流动时间：1 0 8 6 = 1 8 天 平均延期天数：4 0 6 = 6 6 7 天 工作中心内作业平均数：1 0 8 4 1 - - 2 6 3 ( 1 )( 2 )( 3 ) ( 2 ) 一( 3 ) 顺序 延期天数( 如果为 加工时间流动时间预定日期 负则赋值o ) a227o b 4 6 42 c51 11 5o d81 9 1 63 e1 02 91 71 2 f1 24 11 82 3 4 11 2 0 4 0 ( 3 ) 用最早预定日期e d d 作选择标准的作业顺序是c a - e b d f ，实效性评价 指标值为( 见下表) 平均流动时间：1 1 0 6 = 1 8 3 3 天 平均延期天数：3 8 6 = 6 3 3 天 工作中心内作业平均数：1 1 0 4 1 - - 2 6 第l l 页 南京理工大学硕十学位论文中小型制造企业车同生产调度问题的分析与研究 ( 1 )( 2 )( 3 ) ( 2 ) 一( 3 ) 顺序 延期天数( 如果为 加工时间流动时间预定日期 负则赋值0 ) c444o a2 67o e51 11 5o b81 91 63 d1 02 9 1 71 2 f1 24 11 82 3 4 11 2 03 8 ( 4 ) 用关键比率s c 取预定日期一当前日期) 加工时间，作业顺序为c f d - b e - a ， 实效性评价指标值为： 平均流动时间：1 6 0 6 - - 2 6 6 7 天 平均延期天数：8 5 6 = 1 4 1 7 天 工作中心内作业平均数：1 6 0 4 1 = 3 9 0 ( 1 )( 2 )( 3 )( 4 ) ( 2 ) 一( 3 ) 顺序 延期天数( 如果 加工时间流动时间预定日期预定日期 为负则赋值o ) c1 0444o f1 51 21 61 8o d1 71 02 61 7 9 b2 083 4 1 6 1 8 e3 053 91 52 4 a3 524 173 4 4 11 6 08 5 在上述例子中，s p t 规则有两项实效性评价指标优于e d d 规则，只是平均延期 时间比后者稍微差了一点，旨在降低车间在制品占用量为目标的作业排序一般都用 s p t 。其主要缺点是让耗时长的作业等候，且等候时间可能会相当地长( 特别当新的 时间短的作业不断添加到系统中时) ，容易造成加工量大的作业产生延误，而加工量 大的作业往往是生产中的关键零件，因而对生产计划的完成产生较大影响。而e d d 规则直接提出预定日期，往往能使延长期降至最小。尽管e d d 规则有一种可能结果： 有的作业等很长时间，使得在加工存货与车间拥挤程度增加。然而，s p t 通常都会因 为使流动时间降至最少，进而使工作中心平均作业数和总时间数降至最少，而优于其 他规则。在选择使用哪一种规则时，车问或组织最好先认真考虑一下自己的经营环境， 以及自认为重要的实效性评价指标等。 一般而言，s c r 规则与f c f s 规则是效率较低的两种规则。s c r 规则的每一项 评价指标值都较差。f c f s 规则的局限在于长时间作业常会使其他作业延期。如果一 道工序由许多机器上的工作组成，那么下游工作区的机器空闲时间就会增加。然而， 第1 2 页 南京理t 大学硕士学位论文中小型制造企业车间生产调度问题的分析与研究 对于顾客直接参与其中的服务系统来说，f c f s 则是迄今为止占据绝对优势的一项规 则。这主要是出于固有的公平理念，以及无法对个别作业的加工时间做出实际估计 f c f s 规则还有一个优点：简单。如果出现关系密切的顾客，而其他评价指标又很重 要时，公司可能会采用把处理工作转移到“后屋”去的策略，这样就不必遵循f c f s 规则了。 l p t 与s p t 相反，优先考虑加工时间长的零件，但又显著地增加了零件在生产 中的平均等待时间，即增大了生产中在制品占用量“。 m w k r 规则使不同工作量的工件完工时间尽量接近，因而对剩余加工量大的作 业优先安排。对于要成套地投入装配的零件，可以有效地缩短零件组装的总生产周期。 l w k r 则是使加工进度快的零件加速完成。 m o p n r 是优先安排剩余工序数最多的作业，与m w k r 相似，目标是缩短零件 组装的生产周期。所不同的是它考虑了工序间转移和等待时白j ，这部分时间往往比加 工时间长得多，m o p n r 与m w k r 相似，其目标也是减少车问内的在制品量。 有些时候，运用一个优先规则还不能唯一地确定下一个应选择的工件，这时可使 用多个优先规则的组合。例如s p t + m w k r 十凡埘d o m ，它的含义是，首先按s p t 规 则选择下一个工件，若有多个工件具有相同的优先级，则运用m w k r 规则再选择。 如仍有多个工件满足条件，再运用r a n d o m 规则随机地选择一个“1 。 以上这些优先调度规则的简单性掩饰了排序工作的复杂性。实际上要将数以百计 的工件在数以百计的工作地( 机器) 上的加工顺序决定下来，是一件非常复杂的工作， 需要有大量的信息和熟练的排序技巧。对于每一个准备排序的工件，调度人员都需要 两大类信息：有关加工要求和现在的状况。加工要求信息包括预定的完工期、工艺路 线、标准的作业交换时间、加工时间、各工序的预计等待时自j 、各工序的可替代设备 以及各工序所需的原材料和零件等等。现状信息包括工件的现在位置( 在某台设备前 排队等待或正在被加工) ，现在完成了多少工序( 如果已开始加工) ，在每一工序的实 际到达时间和离去时间，实际加工时间和作业交换时间，各工序所产生的废品( 它可 以用来估计重新加工量) 以及其它的有关信息。优先顺序规则就是利用这些信息的一 部分来为每个工作地决定工件的加工顺序，其余的信息可以用来估计工件按照其加工 路线到达下一个工作地的时间、当最初计划使用的机器正在工作时是否可使用替代机 器以及是否需要物料搬运设备等等。这些信息的大部分在一天中是随时改变的，所以， 用手工获取这些信息几乎是不可能的或效率极低的。从这个意义上来说，计算机是用 来进行有效的、优化的作业排序的重要工具。 2 3 2 随机抽样法 用穷举法和分枝定界法，考虑了全部能动作业排序。而采用优先调度规则方法， 实际上只选择了一种作业排序。随机抽样法是介于两者之间的一种方法，它从全部能 第1 3 页 南京理工大学硕七学位论文 中小型制造企业车间生产调度问题的分析与研究 动的作业排序集中抽样，得出多个排序方案，经过比较，从中选优。随机抽样法实际 上是对一个问题多次运用r a n d o m 法则，从而获得多个排序方案，它不一定能得到最 优解，但计算量比穷举法或分枝定界法小，又比优先调度舰则只取一个子样的方法所 得的结果要好。其效果与样本大小有关，样本越多，获得较好解的可能性越大，但花 费时间也越多。 2 3 3 概率调度法 随机抽样法实际上是从k 个可供选择的工序中以等概率的方法挑选，每道工序 挑选的概率为i k ，这种方法没有考虑不同工序的特点。由于优先调度规则中一些规 则对一定的目标函数的效果较好，因此，可以给不同的工序按某一优先调度规则分配 不同的挑选概率，这样得到的结果会比随机抽样法更有效“。 2 4 其他调度方法 近年来，随着相关学科与各种优化方法的建立和发展，车间生产调度领域出现了 许多新的优化方法。如，仿真调度方法、基于知识的调度方法、遗传方法、模拟退火 法等，这些方法为求解车间调度问题开辟了新的途径。 仿真调度方法通过对仿真模型的运行收集数据，对实际系统进行性能、状态方面 的分析。这种方法在产生可行性调度方案和方案评估方面显示了优越性，但由于仿真 中不采用优化算法，难以得到能指导生产的优化结果“。 基于知识的调度方法是用人工智能与专家系统自动产生调度或辅助调度，称为智 能调度“。它克服数学规划与仿真方法的不足，能根据系统当前状态和给定的优化 目标，对知识库进行有效的启发式搜索和并行模糊推理机制，避开了繁琐的计算，并 选择最优的调度策略，为在线决策提供支持。 模拟退火法适合求解大规模优化问题，当优化问题有很多局部极值又很难求出 时，模拟退火法尤其有效“”。模拟退火法的核心思想类似于金属的退火方法，以往 处理问题的方式都是从初始点开始，沿下降的方向前进，走得越远越好，以期求得问 题的最优解。但是，正如金属的冷却过程，所有缓慢冷却的系统都可以自然达到最低 能量状态，而如果某种液体金属被迅速冷却，那么它只能达到具有较高能量的非结晶 状态。传统的求解方式往往只能求得局部极小值点，而不能达到全局最优。模拟退火 法每次使参数t ( 类似于温度) 下降一个幅度，对解进行一定次数的调整，如果某次 调整使目标函数e ( 类似于能景) 下降，则接受它，反之，则以概率e x p ( 一e 厂r ) 接受。 遗传算法简称g a ( g e n e t i c a l g o r i t h m ) ，它最早是由b a g l e y j d 在1 9 6 7 年提出的。 遗传算法模拟生物自然选择过程，对解进行类似于基因重组与突变的调整，保留其中 第1 4 页 南京理工大学硕士学位论文中小型制造企业车间生产调度问题的分析与研究 最好的解，进行下一轮调整、选优。其优点是避免了求解过程停留在局部最优解上“。 以上介绍了一些主要的调度方法。应用传统的优化理论与方法求解车间生产调度 问题，存在很大的局限性，如建模困难、求解复杂等，因此很难获得实际应用。而启 发式方法则求解迅速、易于实现，因而在实际生产中得到广泛应用。启发式调度规则 很多，各具特点，它们对交货期、在制品数、零件的加工周期等性能指标的优化结果 也不相同。 2 5 本章小结 本章首先从总体上介绍了生产调度与