（技术经济及管理专业论文）多品种、小批量、订单式生产系统优化研究.pdf

摘要 摘要 本文研究我国中小型制造企业多品种、小批量、订单式生产系统的优化问题。 包括五个部分： 第一部分介绍了本文的研究背景及意义，综合论述了国内外对多品种、小批 量、订单式生产系统的研究现状，并概述了研究此类生产系统的理论方法。 第二部分采用同步器模拟工具，模拟了多品种、小批量、订单式生产系统流 程，在其基础上分析了该类生产系统流程的瓶颈。 第三部分研究了多品种、小批量、订单式生产系统的非流水型生产调度问题。 采用赋时库所p e t r i n e t 对非流水型的生产作业建立一般的调度模型，然后对模型 进行数学的描述，同时论述了非流水型生产调度的问题是n p 完全难题：难以用 解析法求得最优解。因此，运用深度优先规则和最短优先处理规则来搜索局部最 优而得到一种算法。这种算法是最短路径一深度优先的启发式调度算法。 第四部分研究了多品种、小批量、订单式生产系统的交货期预测问题。由于 b p 神经网络具有自适应、自学习和高度容错性的等特点，尤其对非线性、离散性 的动态系统具有模拟仿真的能力。因此，本文采用改进的b p 神经网络建立多品 种、小批量、订单式生产系统的生产完工期预测模型对交货期进行预测，从而解 决了该类生产系统交货期难以确定的问题。 第五部分研究了多品种、小批量、订单式生产系统的生产批量问题，主要包 括投产批量优化问题和订货批量优化问题。在投产批量优化问题中，研究了多品 种、小批量、订单式生产系统计划投产批量的决策问题，分析了产品实际产量大 于或小于顾客的订货批量对企业效益带来的影响，并分析了导致生产过程产品合 格率的随机波动的原因。设产品合格率在一定范围内服从正态分布，以损失期望 值最小化为目标，建立产品计划投产批量优化的决策模型。并应用m a t h c a d 对 该模型进行仿真，分析了该模型的敏感性，得出最优的计划投产批量方案，证明 了该决策模型的有效性。 在订货批量优化问题中，采用作业成本分析法分析了多品种、小批量、订单 式生产系统的成本结构，在此基础上列出了八个数学公式计算其不同类型的作业 成本并以利润最大化为目标函数和顾客的订货批量为可控决策变量，建立利润优 广东- t 业人学管理学硕 ：学位论文 化模型。最后采用遗传算法( g a ) 对某企业的部分数据进行仿真，结果表明，该 企业在一定范围内调整顾客的订货批量可增加其利润。 关键诃：订单式生产系统；p e t r in e t ；遗传算法：b p 神经网络 a b s t r a c t a b s t r a c t t h eo p t i m i z a t i o np r o b l e m so fm u l t i - v a r i e t y ，s m a l lb a t c ha n do r d e rp r o d u c t i o n s y s t e mf o rm e d i u ma n ds m a l l s i z e de n t e r p r i s e si nc h i n aa r es t u d i e di nt h i sp a p e r i t i n c l u d e sf i v ep a r t s i nt h ef i r s tp a r t ，i n t r o d u c i n gt h i sp a p e rs t u d yb a c k g r o u n da n dm e a n i n g ，d i s c u s s i n g t h ed o m e s t i ca n df o r e i g ns t u d ya c t u a l i t ya n ds u m m a r i z i n gt h e o r ya n dm e t h o do f m u l t i v a r i e t y ，s m a l lb a t c ha n do r d e rp r o d u c t i o ns y s t e m i nt h es e c o n dp a r t ，u s i n gt h es y n c h r o n i z e rt os i m u l a t et h ef l o wo fm u l t i v a r i e t y ， s m a l lb a t c ha n do r d e rp r o d u c t i o ns y s t e m ，a n a l y z i n gt h i ss y s t e m sf l o wb o t t l e n e c ki n i t sf o u n d a t io n i nt h et h i r dp a r t ，t h ej o b - s h o ps c h e d u l i n gp r o b l e mo fm u l t i v a r i e t y ，s m a l lb a t c h a n do r d e rp r o d u c t i o ns y s t e mi ss t u d i e d f i r s t ，u s i n gt i m ep l a c ep e t r i - n e tt ob u i l du p j o b s h o ps c h e d u l i n gm o d u l e ，a n dt h e nd e s c r i b i n gt h em o d u l ew i t ha l g e b r a ，d i s c u s s i n g t h a tt h ej o b - s h o ps c h e d u l i n gp r o b l e ms o l u t i o ns p a c ei sn o n - p o l y n o m i a lc o m p l e t e p r o b l e m ss ot h a tg e t t i n gt h eo p t i m a ls o l u t i o ni si m p o s s i b l eb ya n a l y t i c a lm e t h o d ，s o u s i n gt h ed e p t h f i r s tr u l ea n dt h es h o r t e s tp r o c e s s i n gt i m er u l et og e tt h es o l u t i o n ， w h i c hi sas h o r t e s tp r o c e s s i n gt i m e - d e p t h f i r s th e u r i s t i cs c h e d u l i n ga l g o r i t h m i nt h ef o u r t hp a r t ，t h ed e l i v e r yd a t ef o r e c a s tp r o b l e mo fm u l t i - v a r i e t y ，s m a l lb a t c h a n do r d e rp r o d u c t i o ns y s t e mi ss t u d i e d b e c a u s eo ft h ec h a r a c t e r i s t i c so fb pn e u r a l n e t w o r k ss u c ha s s e l f - a d a p t ，s e l f - s t u d ya n da l t i t u d i n a lf a u l tt o l e r a n c e ，e s p e c i a l l y h a v i n gt h ea b i l i t yo fs i m u l a t i o nf o rt h en o n l i n e a r , d i s c r e t e n e s sd y n a m i cs y s t e m ，s o b u i l d i n gu pt h ep r o d u c t i o nf i n i s h i n gd a t ef o r e c a s tm o d e lo fm u l t i v a r i e t y ，s m a l lb a t c h a n do r d e rp r o d u c t i o ns y s t e mb ya m e l i o r a t e db pn e u r a ln e t w o r k st of o r e c a s tt h eo r d e r d a t e ，w h i c hc a ns o l v et h eo r d e rd a t ep r o b l e mo fb e i n gd i f f i c u l tt oa s c e r t a i n i nt h ef i f t hp a r t ，p r o d u c t i o nb a t c hp r o b l e mo fm u l t i - v a r i e t y ，s m a l lb a t c ha n do r d e r p r o d u c t i o ns y s t e m i s s t u d i e d ， m a i n l yi n c l u d i n g t h e o p t i m i z a t i o n s o f p u t - i n t o p r o d u c t i o nb a t c ha n do r d e rb a t c h i nt h eo p t i m i z a t i o no fp u t i n t o p r o d u c t i o n b a t c hb a t c h ，s t u d y i n gt h ei s s u eo fd e c i s i o n m a k i n go fp l a n n i n gp u t i n t o p r o d u c t i o n b a t c hi nm u l t i - v a r i e t y ，s m a l lb a t c ha n do r d e rp r o d u c t i o ns y s t e ma n da n a l y z i n gt h e e f f e c to fo u t p u te x c e s sa n do u t p u ti n s u f f i c i e n c yo np r o d u c t i o nc o s t d u et od i f f e r e n t r e q u i r e m e n t s f o r t e c h n i q u e ，p r o c e d u r ea n dm a t e r i a l i nc l i e n t so r d e r sa n dt h e u n c e r t a l m yo fp r o d u c t i o np r o c e s s ，s ot h a tt h er a t e so fq u a l i f i e dp r o d u c t sf l u e t u a t e s t o c h a s t i c a l l y t a k i n gt h em i n i m u me x p e c t a t i o no fl o s s e s a st h ec r i t e r i o no f d e c l s l o n - m a k i n ga n ds u p p o s i n gt h eq u a l i f i e d p r o d u c t s r a t e s s u b m i t t e dt on o 咖a 1 d i s t r i b u t i o n , d e v e l o p i n gad e c i s i o n 。m a k i n gm o d e lo fp u t i n t o p r o d u c t i o nb a t c h t h e r e s u l t so fn u m e r i cs i m u l a t i o n a n ds e n s i t i v i t y a n a l y s i sp r o v et h a tt h em o d e li s l nt h e o p t i m i z a t i o no fo r d e rb a t c h ，u s i n g a c t i v i t y b a s e dc o s t i n gm e t h o dt o a n a l y z et h ec o s tm u l t i 。v a r i e t y , s m a l lb a t c ha n do r d e rp r o d u c t i o ns y s t e m ，s s t r u c t u r e g l v m ge l g h tm a t h sf o r m u l at o c o m p u t et h ed i f f e r e n t k i n d s a c t i v i t yc o s ti ni t s f o u n d a t l o n ，a n dt h e nb u i l d i n gu pt h ep r o f i to p t i m i z em o d e l ，i nw h i c ht h em o s tp r o f i t 1 st h eo b j e c tf u n c t i o na n dt h ec u s t o m e r so r d e rq u a n t i t i e s a r ed e c i s i o n v a r i a b l e a t l a s t , a p p j y i n gg e n e t i ca l g o r i t h mf o ri m i t a t i o nb ys o m ee n t e r p r i s e ，s p a r td a t a ，t h e r e s u l t ss h o wt h a te n t e r p r i s ec a ni n c r e a s ei t s p r o f i ta tt h ec o n d i t i o no fa a ju s t i n gt h e c u s t o m e r so r d e rq u a n t i t i e s 。 k e y w o r d s ：o r d e rp r o d u c t i o ns y s t e m ；p e t r in e t ；g e n e t i ca l g o r i t h m ；b pn e u r a l n e t w o r k s i v 广东t 业人学管理学硕j 二学位论文 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的科研成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果，不包含 本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学攻读研究生期间在导师的指导下取得 的，论文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指导教师签字：勺够彰坳 论文作豁字：绷幂 留郴年t , - 月邪日 7 4 第一章绪论 1 1 研究背景及意义 1 1 1 研究背景 第一章绪论 随着市场竞争日趋激烈，质量、价格和速度已成为企业赢得顾客1 订单的三大 重要因素。许多企业为了提升自身的市场竞争力，纷纷从传统的备货式生产方式 转为订单式生产方式；同时，个性化、多样化和易变性的顾客需求也驱动企业从 单一、大批量的流水型生产模式转变为多品种、小批量的非流水型生产模式。多 品种、小批量、订单式( m u l t i v a r i e t y ，s m a l lb a t c ha n do r d e r ，m s o ) 生产系统正 是在这样的环境下产生的。 满足多品种、小批量、多批次、随机订货的要求，缩短生产周期、按时交货、 稳定的质量、合理的价格等，成为实施m s o 生产系统企业赢得顾客订单的重要 条件。然而实施此生产系统的我国中小型制造企业面临的问题是：任务不均衡、 品种繁多、顾客常改单、交货期急、价格低、成本难以控制等情况；m s o 生产系 统受到人员素质低、激励效果差、人员流动率大的影响，运行稳定性差。面对这 种境况，现有精确、严密的生产组织、计划和控制策略及方案往往难于凑效【- 】， 先进的m r p i i e r p 系统无法发挥作用，管理人员往往靠经验和感觉来组织生产。 生产效率低、交货期不准时、质量不稳定、生产成本高成为这类企业的通病。这 既是企业本身管理水平的问题，更是目前的管理理论和方法的适用性问题，因此 有必要结合我国中小制造企业m s o 生产系统的特点，研究m s o 生产系统的优化 问题。 1 1 2 研究意义 据有关资料统计，在我国工业企业中，中小型企业占9 9 以上，工业总产值 和实现利税分别占6 0 和4 0 左右，就业人数占全国工业企业劳动力的8 5 左右， 在食品、造纸、印刷、服装、金属制品、木材和家具等行业中，中小型制造企业 为了表示统一，本文将用户、客户统称为顾客。 广东t 业大学管理学硕i j 学位论文 的产值更是占到8 0 以上【：l 。可见我国中小型制造企业对国民经济的发展起着非 常重要的作用。m s o 的生产系统是我国中小型制造企业( 如：五金、服装、制鞋 等制造业) 广泛采用的生产组织模式。本文以我国中小型制造企业的m s o 生产 系统为研究对象，综合了生产管理理论、优化理论与算法以及计算机仿真技术， 通过实证研究、系统建模和仿真等研究手段研究该类系统的流程、生产调度、交 货期与生产批量的理论和方法。这有助于提高我国中小型制造企业的管理和竞争 力水平，推动我国的经济发展。 1 2 相关理论综述 1 2 1 生产系统优化研究现状 1 2 1 1 生产流程优化生产流程优化是生产系统优化的重要组成部分，它可分 为以下两个方面的研究：一方面是通过分析具体某间公司的生产流程状况，对现 有的生产流程进行重组。这方面的研究始于2 0 世纪3 0 年代初美国麻省理工学院 教授迈克尔哈默( m i c h a e lh a m m e r ) 和c s c 顾问公司的董事长詹姆斯钱皮( j a m e s c h a m p y ) 提出的企业业务流程再造，不少企业如：福特、西门子、摩托罗拉、诺基 亚等的高层管理员根据他们的思想和方法应用于企业流程重组上，使得企业的生 产成本大大地降低、生产效率明显地提高。同时，各国学者对业务重组的研究也 很多。例如，文献 3 采用瓶颈模型对g 公司生产流程的瓶颈进行了分析，并提出 改进措施。文献 4 基于约束理论：生产作业与管理的原理对g 公司生产流程进行 分析，找出该企业生产流程中存在的问题，利用约束理论的相关知识与概念提出改 善g 公司生产流程基本途径。另一方面是通过模拟工具对生产流程进行分析。例 如，文献 5 采用将i d e f o 与p e t r in e t 相结合的建模方法，对生产流程：订单审 核子流程、车间顺序生产子流程和车间制造子流程进行了模型分析，在对生产流 程模型描述的基础上，提出了基于p e t r in e t 关联矩阵进行生产流程再造的方法。 荷兰学者a a ls t 在赋时变迁p e r tin e t 的基础上提出了工作流网( w f n e t ) ，并借 用p e r tin e t 关于活性和有界性等的概念定义了工作流网的安全性和健全性。本 文在a a l s t 的w fn e t 工作逻辑关系图的基础上，采用同步器模拟工具，模拟了 多品种、小批量、订单式生产系统流程，在其基础上分析该类生产系统流程的瓶 颈。 2 第一章绪论 1 2 1 2 生产调度优化生产调度优化是生产系统优化研究的重点内容之一，也是 最早研究和取得成果最多之一。在多种产品的生产过程中，由于资源的共享与冲 突产生了调度问题。调度就是确定产品输入的顺序和资源分配方案的问题，是保 证每一个产品在适合的时间加工和完工而产生的优化排序问题。 早在19 5 4 年，j o h n s o n 对两台机床的流水型调度问题进行了研究，并取得了满 意的结果，但对于具有3 台机床的这类问题，被证明是n p 困难。由于调度问题的复 杂性，导致研究人员从不同的角度研究调度的某一方面问题，随着对各类调度问 题研究的深入及各种交叉学科的发展，已涌现出了许多新的调度理论与方法。目 前主要有启发式搜索算法、神经网络” 、遗传算法、p e t r in e t 等理论和方法 9 1 研 究生产调度问题。本文采用最短路径一深度优先的启发式调度算法研究了非流水 型生产调度问题。 1 2 1 3 交货期优化交货期决策，是根据顾客订单的要求、考虑订单产品的技术 工艺特点、生产系统状态，预测订单的完工期，进而确定合理的订单交货期。这个 决策的好坏不仅影响到企业的市场竞争力，而且还影响到企业上游和下游企业的 各种计划安排。交货期的决策在国内外是颇受关注的研究课题。文献 1o 12 用 模拟实际生产情况的方法确定交货期，文献 13 l4 在保证按时交货期的前提下研 究最优排序的问题，文献 15 在动态规划方法的基础上提出一个在交货期已定和 未定的情况下均适用的排序问题的优化方法。文献 16 分析了交货期决策的重要 性，建立了以损失费用最小化为目标的最优交货期时区模型、最优最早交货期模 型、最优完工时间偏差控制模型。文献 17 1 9 利用各种算法对交货期的进行预测。 本文采用改进了的b p 神经网络建立了m s o 生产系统交货期预测模型，对交货期进 行预测。 广东t 业大学管理学硕l ：学位论文 1 2 1 4 生产批量优化生产批量优化研究的理论基础是运筹学库贮论。在库贮论 库中，其中一个研究的焦点是建立数学模型求解经济生产批量，使得库存费用和 订货费用之和达到最少。近几年，各国学者不仅考虑必要的库存费用和订货费用， 还考虑在其他条件下的生产批量问题。例如：文献 2 0 在优化物流批量时是从生 产系统的整体出发，考虑了销售、生产和物料转移等的费用建立了物流批量优化模 型，文献 2 1 在供应链背景下提出了一种生产批量与定价的联合决策模型，在分析 了最优联合决策的性质后，开发了求解模型的算法，以有效地辅助供应链协调管 理。文献 2 2 2 3 从数量折扣定价问题的研究了生产批量优化问题。文献 2 4 建立 批量优化模型并用遗传算法求解最优的生产批量。本文研究了生产批量的投产批 量和订货批量两个问题。 1 2 2 生产系统优化研究方法 m s o 生产系统是离散事件动态系统( d i s c r e t ee v e n td y n a m i cs y s t e m ，d e d s ) 的一种。因此，d e d s 方法和算法也适合m s o 生产系统。d e d s 是由哈佛大学教 授y c h o 在8 0 年代首次提出1 2 s l ，自此，各国的学者十分重视d e d s 的分析方法 与算法研究，并取得了很多研究成果。目前，d e d s 的主要研究如下： 1 2 2 1d e d s 分析方法由于d e d s 的动态性、离散性和随机性，传统的线性、微 积分和差分方程难以对这类系统进行建模和分析。但是这类生产系统却广泛地存 在于现实的生产系统中，因此各国学者花费了大量的心血研究这类问题，也取得 了很多的成果，其中极大一加法代数、排队论、马可夫链以及p e t r in e t 是比较 有效的分析方法。现分别介绍如下： 1 极大一加法代数( m a x p l u sa 1 9 e b r a ) 极大一加法代数方法的目的是建立 d e d s 的时间化线形模型。在极大- a n 法代数方法中，引入2 种基本运算： “加 和“乘”，但是，它们与一般代数中的加法和乘法是完全不同的。这2 种运算定 义为： 加法： 童国b 篁砷啦籼hl ( 1 1 ) 乘法：- 囝b = + h ( 1 2 ) 对于线形时不变系统的离散时间模型： 4 第一章绪论 x ( k + l1 = a x ( k ) + b u ( k ) ( 1 3 ) 用极大_ 力口法代数表示为： x 阻1 ) l 磊囝x 国跳鳓 ( 1 4 ) 由公式( 1 4 ) 就是极大加法代数表示d e d s 的时间化线形模型。极大- 力口法 代数方法已用于多品种、小批量的建模与控制问题、物料搬运系统动态特性建模 与分析以及生产调度与计划等方面，。 2 排队论( q u e u i n gt h e o r y ) 排队论也是研究d e d s 的一种重要模型，它研究 的是排队系统与排队网络问题。在生产控制中经常遇到资源冲突与共享的问题， 这些问题可以概括为网络问题。在建立该类模型时，必须定义三类参数：1 ) 顾客 到达与服务的随机过程概率分布类型及参数；2 ) 模型的结构参数，如队列的存储 容量、服务员的个数等等；3 ) 操作规则，如接纳到达的顾客的条件。队列模型可 表示为： a b m q d k p( 1 5 ) 其中： a 一顾客到达间隔时间概率分布； b 一服务时间概率分布； m 一服务员个数( m = 1 ，2 ，) ； q d 一描述队列规则，其中有以下几种规则：f c f s ( 先到先享受服务) 、l c f s ( 后到先享受服务) 、s i r o ( 享受服务的顺序为随机的) 和g d ( 一般排队规则) ； k 一队列存储容量( k = l ，2 ，) ，容量为无穷时，省去； p 一顾客抽样的群体大小，当无穷大时，省去。 排队论研究的是解决资源共享与冲突的问题。因为排队论仅仅是d e d s 的描 述工具，所以不能对动态的d e d s 行为进行控带l j 2 7 1 。 广东t 业人学管理学硕l j 学位论文 3 马可夫链( m a r k o vc h a i l 3 ) 马可夫链研究的是某事件过程中在某一点上事 件发生所产生的下一状态值仅仅与当前状态相关，而与过去发生的事件不相关( 无 记忆性) 。对于状态x 与x ，及2 个时刻t 。t ，可以采用条件概率p ( x ( t ) = x ，x ( t 。) = x ) 来表示从x 至x ，的状态转移概率，从而描述了过程的随机性他”。因 此，只要给定所有状态的转移概率与初始状态下的概率分布，就可以确定状态在 任意时刻的概率。马可夫链在d e d s 的随机性分析与建模都有广泛的应用。 4 p e t r in e tp e t r in e t 是1 9 6 2 年由德国科学家c a p e t r i 先生在其博士 学位论文“用自动机通信”中首次建立的。p e t r i 先生当初建立的模型实际上是 一类特殊网一安全网，并理解为一种新的自动机模型，主要用于描述通信机制， 后经p e t r i 本人及其追随者们的不断努力，使之逐渐形成一门崭新的学科分支。 在此发展过程中，几个关键时期应该被指出。起点是1 9 6 2 年c a p e t r i 先生的 其博士论文，2 0 世纪6 0 年代末至7 0 年代初，美国a d r 公司信息系统理论组的 a w h o l t 及其同事们将此模型弓 入美国，并进一步丰富和发展相应的理论、记号 及表示法。与此同时，m i t ( 麻省理工学院) 的j b d e n n is 教授领导的计算机结构 课题在p e t r in e t 理论方面做了许多工作，包括几篇博士论文。l9 7 0 年的w o o d s h o l e 会议和1 9 7 5 年的m i t 会议是两次最早的与p e t r in e t 有关的重要学术会议， 对p e t r in e t 知识的传播起到了重要的作用。随着逐渐被计算机科学家们所认识 和重视，p e t r in e t 引起了广泛的注意，成为计算机界、自动化界的热门研究课 题。 1 2 2 2d e d s 优化算法建立了d e d s 模型还要对模型进行求解，由于d e d s 的模 型是用p e t r in e t 、马可夫链等建立的，难以再用线性规划，解微分以及解差分 方程来解决，但可采用智能化的算法求解，例如：神经网络、遗传算法、启发式 搜索算法和模拟退火算法等。 1 神经网络神经网络是以神经细胞模型为基础的分布式网络结构。它是一 种并行处理的多输入多输出的结构。由于它是对人的神经系统智能活动过程的研 究和模拟的结果，所以神经网络物理结构及信息传递处理过程是仿照人的神经系 统智能行为的结构和形态。神经网络的基本因素是神经元，神经元有信息综合、 多输入、非线性的特点，以神经元组成的神经网络通过各个相互连接的神经元之 间的权系数存储信息。这种分布式存储的特点使神经网络有很好的容错能力。 6 第一章绪论 通过学习训练可以不断地改变它的权系数，不断适应新的变化。这是神经网络与 其他智能算法最大的区别，也是它的最大优点。 2 遗传算法( g e n e tica ig o rit h m s g a ) 遗传算法是由美国m ic h ig a n 大学 的j o h nh o ll a n d 与其同事、学生们在2 0 世纪6 0 年代末首次从解释自然系统中生 物的复杂适应过程入手，模拟生物进化的机制来构造人工系统模型，并形成了一 个比较完整的理论和方法。从19 8 5 年在美国卡耐基梅隆大学召开的第一届国际遗 传算法会议( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ca 1 9 0 r i t h m s ：i c g a ，8 5 ) ， 到1 9 9 7 年的i e e e 的t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o i l 创刊，遗传 算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。 遗传算法是模仿自然生物进化机制发展起来的一类随机全局优化算法。类似于自 然进化那样，它通过作用于染色体上的基因，使染色体产生变异和不同个体的染 色体之间交叉完成群体的变化，再通过适应度函数对染色体进行筛选得到比上一 代更加优化的群体，从而完成进化。具体地说是通过选择、交叉和变异三个基本 的操作，产生一群更加适应环境的个体，使群体一代代地不断进化，最后收敛得 到最适应环境的个体。 遗传算法包括三个基本操作：选择、交叉和变异。 ( 1 ) 选择根据每一个个体的适应度函数得到的适应度值，按照一定的选择规 则从上一代群体中选择一些优秀的个体遗传到下一代群体中。遗传算法中的选择 算法正是体现了这样的思想，如果个体的适应度值大的话，则它为下一代贡献后 代个体的概率就大。 ( 2 ) 交叉将群体内的每一个个体随机搭配成对，对于每一个个体，以预先设 定的概率交换它们之间的部分染色体。通过交换操作可以得到新一代个体，新一 代个体组合了父辈个体优秀的基因。交叉操作体现了信息交换和进化的思想，它 是遗传算法中最主要的操作。 ( 3 ) 变异在群体中随机选择个体，对于被选中的个体以一定的概率随机改变 染色体中某些基因的某些值。该概率一般都是很低的，这与自然界发生的变异相 符，但它却可为新个体的产生提供了机会。 广东t 业大学管理学硕i ：学位论文 3 启发式搜索算法启发式搜索算法首先应用于智能化的空间搜索，它利用 计算机快速运算的特点，通过比较全部的可能解得到最优解。由于n p c o m p le t e 问题的可能解是以指数方式递增的，随着需排序的产品品种及加工产品机器的增 加，要解出全部解且要对每一个解进行比较变得不现实，所以国内外研究者相继 研究出各种各样的启发式搜索算法。如：a 、广度和深度启发式搜索算法等。虽 然这些算法得到的解可能是局部最优，而不是全局的最优，但可用于解决资源有 限与实时解的实际问题，因而得到广泛的应用。 启发式搜索就是在解空间中的搜索，对每一个搜索的位置进行评估，得到最好 的位置，再从这个位置进行搜索直到目标，从而可省略大量无谓的搜索路径提高 效率。在启发式搜索中，对位置的估价十分重要。采用了不同的估价可以有不同 的效果。启发中的估价是用估价函数表示： f ( 1 3 ) = g ( n ) + h ( n ) ( 1 6 ) f ( n ) 一节点n 的估价函数。 g ( n ) 一实在状态空间中从初始节点到1 2 节点的实际代价。 h ( n ) 一是从n 到目标节点最佳路径的估计代价。g ( n ) 是已知的，h ( n ) 主要是 体现搜索的启发信息。 1 3 课题来源与研究内容 1 3 1 课题来源 本课题主要来源于张毕西教授主持的国家自然科学基金项目“中小型制造企 业人机工序混合系统组织计划与控制研究 和广东省自然科学基金项目“订单生 产人一机工序混合系统组织、计划与控制”。 1 3 2 研究内容 本文共分为六章，分别对m s o 生产系统中的生产流程、生产调度、交货期以 及生产批量进行了优化。 第一章介绍m s o 生产系统的研究背景、意义、现状和方法。 第二章研究m s o 生产系统流程，采用同步器模拟工具，模拟了m s o 生产系统 8 第一章绪论 流程，在其基础上分析该类生产系统流程的瓶颈。 第三章研究m s o 生产系统生产调度优化问题，采用赋时库所p e t r in e t 对该 类生产系统建立调度模型，然后对模型进行数学的描述，并采用最短路径一深度 优先启发式算法得到局部的最优。 第四章研究m s o 生产系统交货期预测优化问题，利用改进的b p 神经网络， 建立了m s o 生产系统交货期预测模型对交货期进行预测。 第五章研究m s o 生产系统投产批量优化问题，分析了产品实际产量大于或小 于顾客的订货批量对企业效益带来的影响。设产品合格率在一定范围内服从正态 分布，以损失期望值最小化为目标，建立了产品计划投产批量优化决策模型。 第六章研究m s o 生产系统订货批量优化问题，采用作业成本分析法分析了m s o 生产系统的成本结构，并以利润最大化为目标函数和顾客的订货批量为可控决策 变量，建立利润优化模型。 9 广东丁业人学管理学硕卜学位论文 第二章m so 生产系统流程模拟分析 2 1 生产系统流程概述 制造企业的生产流程是指从生产材料准备和零部件配套到零部件生产、生产 总装或按一定工艺流程连续制造加工出产品的一个完整的产品制造生产过程。生 产流程决定着产品的性能、质量、成本和交货期等因素，因而它不仅是企业正常 运行的基础条件和必要条件，也是企业提高应变能力和竞争能力的重要保证托。 荷兰学者a a l s t 从2 0 世纪9 0 年代开始研究业务流程，他在传统的赋时变迁 p e t r i n e t 基础上提出了工作流网( w fn e t ) 。这一工作流网可简单地表达各种的 业务流程关系。a a t s t 的w fn e t 的定义如下 3 0 1 ： 有向网p n = ( p ，t ，f ) 为w fn e t 的充分必要条件是： p n 有一个源库所( s o u r c ep l a c e ) i p ，使得t = 巾。 p n 有一个漏库所( s i n kp l a c e ) o p ，使得t 。2 由。 每一个库所x e put 都属于从i 到o 的一条路径上。 t 中的变迁代表业务流中的业务，业务之间的依赖关系f 通过库所的连接表 示。业务的执行可能顺序地执行，也可能在一个业务之后是几个业务的并行，也 可能是从几个业务选中一个或多个执行。 2 2m s o 生产系统流程模拟 2 2 1 流程逻辑关系图 a a l s t 的w fn e t 逻辑关系图如图2 1 所示 3 0 1 。 a n ds p l i t 一并行激发，上一步的t o k e n 激发同时可以并行激发下一步； a n d j o i n 一激发合并，上一步的t o k e n 同时并行激发才可以激发下一步； o rs p l i t 一选择激发，上一步的t o k e n 激发可以选择激发下一步： o ri o i n 一激发选择，上一步的t o k e n 选择激发可以激发下一步： 为了简化复杂的流程过程可以用同步器等价代换以上四个w fn e t 。同步器定 义是【3 1 ： p = ( t i ，t 2 ，( a l ，a 2 ) )( 2 1 ) i o 第二章m s o 生产系统流程模拟分析 避s p l i t 图2 1a a l s t 的w fn e t 逻辑关系图 f i 9 2 - 1l o g i cr e l a t i o n s h i pf i go ft h ea a l s t sw f n e t t i = t li ，t i m l ，t 2 = t 2 ，t 2 m i 是任务溉，魂集合；规定t 。与t 。= 0 ； a l p 要求t l 中发生的变迁个数，重觏篓随l 暑隅； a 2 一p 要求t 2 中发生的变迁个数，重篓怒墨豫z i 喾魄。 若变迁t l i 1 与t 2 i 是顺序关系，t 1 1 变迁完之后将激发t 2 i ，若t l i i 之后有a 2 个并行的变迁，则经过t l i - l 变迁后同步器p 中需要有a 2 个托肯激发t 2 。若t 2 i 之 前有a 1 个并行的变迁，则在t 2 i 之前的同步器需要有a 1 个托肯表示t l 中的变迁已 经全部激。那么要使得t 2 的激发则需要p 中含有a 2 a 1 个托肯。可以用t o k e n ( p ) = a 2x a l 表示，而t l i i 与t 2 i 的同步关系的加权则为t l i - i = a 2 ，t 2 i = a l 。如图2 2 所示。 如果t o k e n ( p ) 1 ，则p 表示并行，否则p 表示或行。关键库所是在并行库所之 中，并且，是最后激发的变迁对应着的库所。同时，关键变迁与关键库所相对应。 根据同步器定义，可以把 图2 2 同步器 广东工业大学管理学硕士学位论文 p = ( t l ，t 2 ( 2 ，1 、1 ) ) ，t l i e t l ，t 2 l 、t 2 2 t 2 ，t o k e n ( p ) = 2 等价a n d s p l i t ； p = ( t 1 ，t 2 ( 1 、1 ，2 ) ) ，t 1 2 、t t l c t i ，t 2 1 e t 2 ，t o k e n ( p ) = 2 等价a n d _ j o i n ； p = ( t l ，t 2 ( 1 ，1 、1 ) ，t l l e t l ，t 2 i 、t 2 2 e t 2 ，t o k e n ( p ) = t 等价o r s p l i t ； p = ( t l ，t 2 ( 1 、1 ，1 ) ) ，t 1 2 、t l le t i ，t 2 1e t 2 ，t o k e n ( p ) = l 等价a n d s p l i t 。 w f n e t 的四种工作逻辑关系图与同步器等价关系图如图2 - 3 所示。 心i ) s p l i t 图2 - 3 同步器与w f n e t 的逻辑图的等价关系 f i 9 2 3e q u i p o t l e n c er e l a t i o n s h i pb e t w e e ns y n c h r o n i z e ra n dw f n e t sl o g i cf i g 第二章m s o 生产系统流程模拟分析 2 2 2 流程逻辑模拟 m s o 流程可用同步器表示，如图2 4 所示： 蘑t 17 1 2 毒t 3 奄厂j j o j o 一、 ，。、l t l 表示顾客下单； t 2 表示生产； t 3 表示发货； p 3 表示结束； t i ，t 2 ，t 3 又可以进一步细分为订单、生产和发货三个流程。 2 2 2 1 订单流程模拟分析 顾客锖售人员生产人员物蠢人员顾客 图2 5m s o 生产系统订单流程 f i g2 - 5o r d e rf l o wo ft h em s op r o d u c t i o ns y s t e m 简单的m s o 生产系统订单流程可用框图表示如图2 5 所示。用同步器对订 单流程进行模拟，如图2 - 6 所示。 tl l 、tl2 tl ，tl l 表示顾客网上下单，t l2 表示顾客网下下单； t 2 1 t 2 ，t 2 表示录入订单； t 3 l e t 3 ，t 3 l 表示审核顾客的信用度； 广东工业人学管理学硕十学位论文 p s ! b m 1 蓼潍! 长溉 留 峨 、 沁该库 图2 6 订单流程模拟 f i g2 - 6s i m u l a t e st h eo r d e rf l o w t 4 l 、t 4 2 t 4 m ) e t 4 ，其中t 4 l 表示价格的谈判，t 4 2 表示交货日期的谈判，其它略； t 5 l e t 5 ，t 5 l 表示签订订单合同： t 6 1 e