江苏惠通集团厂级基于TOC的订单排产问题与改善

江苏科技大学经济管理学院毕业论文（设计）专业： 学号： 姓名： 指导老师职称： 年 月 日 II江苏惠通集团厂级基于 TOC 的订单排产问题与改善摘要生产订单的排序是生产作业计划的重要部分，不同的订单对企业有不同的影响，重要的订单关系到企业的发展力和竞争力，因此必须保证其交货期，同时使得生产成本尽可能地降低。本文研究了基于 TOC 的订单排产问题，先对生产过程中的瓶颈进行分析和管理，再通过建立各个订单的优先级别，来保证重要订单在瓶颈工序上的按期完工，而非瓶颈工序配合瓶颈工序投产。本文将订单排产的问题模型化，以总成本最小为目标，采用遗传算法进行最优求解，模型计算结果证明本文提出解决订单排产问题的有效性，为编制生产作业计划提供了重要的依据。最后本文还分析了订单的动态调整情况。关键词：约束理论；瓶颈；优先级；订单排产；遗传算法IIIStudy & Improve on Order Scheduling Based on TOC of HUITONG FactoryAbstractSequencing of production orders is an important part of production planning and scheduling. Different orders have different influence on the enterprise, the important orders in relation to the development and competition of enterprises, thus to guarantee the delivery time of these important orders is essential. Meanwhile the production cost is reduced as much as possible. This thesis studied the order scheduling problem based on the TOC, analysis and management of the bottleneck in the process of production in the first place, and then through the establishment of priority of various orders to ensure orders in the bottleneck procedure are completed on schedule, and the non-bottleneck process to manufacture according to the bottleneck process. In this thesis, the problem of order scheduling is described as a model, the minimum total cost as the goal, using genetic algorithm to provide the optimal solution, the calculation results of the genetic algorithm testifies the effectiveness of the order scheduling problem solving, and provides the important basis for compiling the production planning and scheduling. Finally, this paper analyzes the dynamic adjustment of orders.Key words： theory of constraint; bottleneck; priority; order scheduling; genetic algorithmIV目录1 引言.11.1 问题的提出及背景 .11.2 国内外研究动态 .21.2.1 生产作业计划 .21.2.2 约束理论 .31.2.3 遗传算法 .61.3 研究内容与结构 .72 理论基础.82.1 约束理论 .82.1.1 约束理论与瓶颈资源 .92.1.2 瓶颈识别与管理 .102.2 遗传算法 .112.2.1 遗传算法理论 .112.2.2 遗传算法的基本流程 .122.2.3 遗传算法参数和运算 .132.3 订单优先级和排产 .142.3.1 订单分类 .142.3.2 优先级规则 .152.3.3 生产订单的排产问题 .153 企业作业计划工作的现状及问题分析.163.1 企业介绍 .163.2 企业现状 .163.3 企业关键问题分析 .174 企业应用 TOC 的作业计划制定流程 .184.1 流程图 .184.2 TOC 对生产作业计划的管理与控制 .194.2.1 基于 TOC 的生产作业计划 .194.2.2 瓶颈识别和瓶颈管理 .234.2.3 排产相关指标 订单优先级评价指标 .254.2.4 确定相关指标权重 .254.2.5 订单具体排产方式 .275 遗传算法优化订单排产.285.1 问题描述 .285.2 数学模型 .295.3 遗传算法求解 .315.4 具体操作 .315.5 结论 .336 生产作业计划动态调整.346.1 紧急订单处理 .34V6.2 变更订单处理 .356.3 订单的延期、挂停与返工 .36结论.38致谢.40参考文献.41附录.43江苏科技大学经济管理学院毕业论文（设计）1江苏惠通集团厂级基于 TOC 的订单排产问题与改善1 引言本文以江苏惠通集团为背景，以它的生产计划为研究对象，该厂是面向订货的生产方式，结合约束理论的思想，运用遗传算法的方法，最后得出订单的在瓶颈工序上的排产结果，从而证明了该方法的可行性，并且具有实际的指导意义。1.1 问题的提出及背景依据 TOC 理论 1可以知道企业的生产能力并不是无限的，任何一个生产系统都存在着某种资源限制或者约束，我们称之为瓶颈，该瓶颈决定了这个生产系统的产出效率。这种瓶颈可以是必需的专业机器、工具或者技术熟练的工人，若想提高一个系统的产出效率，就必须充分利用或者打破该瓶颈。生产中，瓶颈工序往往决定订单的交付时间，决定着系统的有效产出，企业无法保证每个订单的生产都能够按时按量交货，所以企业安排生产时，生产系统的其他部分要服从于瓶颈部分，按照瓶颈的产出效率来安排非瓶颈部分的生产，强调沟通协作，保证整个生产流程顺畅并满足客户的交货期。另外，在市场复杂性和变数增加的大环境下，对订单的合理分配是实现对企业资源合理利用的关键、是提高企业利润最大的关键、是合理的提高各个下属子公司或者子厂的生产积极性的关键 2，因此当企业接到订单的时候必须要优化订单分配。面向订单生产的作业计划是非常重要的。计划做得好，既可以提升客户的满意度，又可以提高生产的效率，同时保持库存在一个合理的水平。计划做得不好则会造成库存很高，但生产线还是断线，客户交货达不成。由于计划不完备导致的频繁的缺料断线，大大吞噬了企业的生产效能和利润。还有就是各加工部门步调不一，使得最后的装配部门经常是“前松后紧”：前半周或前半月没有活干，后半周或后半月加班加点还是干不完。并且订单企业具有多品种、少批量、制造周期短等特点，导致工件随机到达、客户插单或撤单频繁等不确定因素较其它类型企业要多，生产作业计划与控制非常复杂。江苏惠通集团的分配订单往往是以交货期为排序依据，在相同交货期内依据订单到达的先后顺序为投产依据，这样可能会导致重要订单不能按时按量交货，这些客户关乎到企业的发展和竞争力，对企业的影响是不可估量的。所以需要重新制定订单分江苏科技大学经济管理学院毕业论文（设计）2配的方式，使企业将损失控制在最小，并且确保企业在将来的发展。 为了在激烈的市场竞争中获得竞争优势，江苏惠通集团必须能够对动态变化的市场需求做出实时的、迅捷的生产调整，以便在最大程度上满足顾客的需要。合理地对生产过程中的任务进行计划，合理利用企业生产资源，有效地组织生产，快速寻找企业生产系统中的瓶颈资源，将企业有限的资源依据订单优先级用于对生产过程中瓶颈的突破，同时对生产过程进行有效的控制，最大限度地提高企业的有效产出，成为企业赢得竞争的关键。因此，如何能够更加合理地制订生产计划，分配关键资源，安排订单生产顺序，满足不同客户的个性化需求，同时充分利用企业现有产能，成为惠通集团现阶段需要解决的关键问题之一。可见，深入研究瓶颈上的订单排产问题，不但具有重要的理论价值，而且也具有一定的实践指导意义 3。1.2 国内外研究动态伴随着计算机的发展，生产管理理论与技术也得到了极大的改进。从MRP、MRP到 ERP，以及 JIT 和 OPT 生产方式。在 OPT 生产方式中，有许多新的作业计划优化理论与方法，本文主要选用的是邻域搜索法中的遗传算法（GA） 。1.2.1 生产作业计划作业计划问题 Johnson 研究了两台设备的流水车间作业计划问题后开始进行大量的研究。优化生产技术 OPT(Optimized Production Technology)4是 20 世纪 70 年代出现的，主要处理逻辑是分清主次，找到“瓶颈”工序，并使“瓶颈”上的资源得到充分利用，同时安排好非“瓶颈”工序的资源配置，使之能与“瓶颈”工序生产率保持同步，将在制品积压减少到最低程度。 。目前主要的算法有：(1)运筹学方法。其中 Mcmahon 和 Florian(1975)提出的改进分枝定界方法在相当长的时间内一直是最好的精确求解方法。之后魏师甲 5和吴志铭 6提出了两种不同的分枝定界法，差异主要在于分析规则、定界机制和上界的产生这三方面。此类方法虽然从理论上能求得最优解，但这种纯数学方法有模型抽取困难、运算量大、只能用来求解小规模作业计划问题，因而不能很好地满足实际应用的需要。(2)基于规则的算法。此种算法规则简单、易于实现、计算复杂度低，多年来一直受到学者们的广泛研究，由 Languna 、Manuel、J.Wesley Barnes 和 Fred Glover7提出的移动瓶颈算法(Bottleneck Procedure)是目前最有效的启发式算法之一，它通过江苏科技大学经济管理学院毕业论文（设计）3不断地对移动的瓶颈设备进行单机调度，来获取更好的次优解。但是研究表明并不存在一个普遍适用的规则，规则的有效性依赖于对特殊性能的需求标准及生产条件，该方法是局部优化算法，不能对得到的结果进行次优性的定量评估，难以保证所得的解是最优解或次优解。(3)神经网络方法。Cheung J.Y8描述了一些主要的用于求解作业计划问题的神经网络结构：搜索网络(Hopfield 网络)、纠错网络(多层感知器 )、随机网络(Boltzman 机)。Y.P.S.FOO 和 Takefuji 较好地把 Holpfield 神经网络解决 TSP 的方法移植到 Job Shop上来。Jain A.S.et.al9提出的改进的 BP 神经网络模型克服了传统的 BP 网络模型在处理包含复杂的输入输出问题时会训练不成功并收敛于局部极小解的不足。由于神经网络方法存在会产生大量不可行解，计算时间较长，容易陷入局部最优解等不足，因此在解决实际问题时单独使用情况的并不多见。(4)邻域搜索方法。近年来各种邻域搜索算法在作业计划中得到了广泛的应用，邻域搜索算法是基于其随机和启发式的搜索方法，在“邻域搜索”框架中，从一个(一组)初始解出发，通过邻域函数产生若干邻域解，按接受准则更新当前状态，然后按参数修改准则控制参数，如此重复以上搜索过程直至满足算法终止条件。这些算法具有全局优化性能，通用性强、无需问题的特殊信息等优点。研究较多的有模拟退火算法(SA ，Simulated Annealing)、禁忌搜索算法 (Ts，Tabu search)、遗传算法(GA，Genetic Algorithms)等 10。但此类算法也存在各自的不足，如 GA 容易早熟，SA 收敛到全局优化解需要很长的计算时间，并且算法效果的好坏对初始解和控制参数的选取有较大的依赖性。1.2.2 约束理论TOC 是英文 Theory of Constraint 的首字母缩写，中文译为“约束理论” 。TOC 是由以色列物理学家、企业管理顾问 Dr.Eliyahu M.Goldratt1在他开创的优化生产技术OPT(Optimized Production Technology)的基础上发展起来的管理哲理，该理论提出了在制造业经营生产活动中定义和消除制约因素的一些规范化方法，以支持持续改进，是对 MRP和 JIT(Just in Time)的继承和发展 11。TOC 首先作为一种制造管理理念出现，后来几经改进，发展出以“产销率、库存、运行费”为基础的指标体系，逐渐形成一种面向增加产销率而不是传统的面向减少成本的管理理论和工具，并最终覆盖到企业管理的所有职能方面。Blackstone J.H 12、江苏科技大学经济管理学院毕业论文（设计）4Robert E.stein、H.Steyn 等人研究了 TOC 在诸如供应链、营销、质量、项目成本管理等方面的应用；NAVE Dave 也将 TOC 与 6sigma、精益生产等其他技术方法进行了对比。Blackstone12在 1997 年描述了美国福特汽车电子部在应用了 TOC 后，出货时间从原有的 10 天降为 16 小时，Bal Sea 公司导入 TOC 后出货时间从原油的 6 周降为 8天，准时交货率从 80%-85%提升至 97%，在制品减少 50%以上。Cook13在 1994 年运用仿真对 TOC、传统排程、JIT 三种生产计划与控制方法对在制品数量、平均流程时间、流程时间波动及总产出数量进行比较，结果发现 TOC的产品加工流程时间波动较小，总产出数最多，平均流程时间及在制品数量则略高。沈昭 14在传统的制造资源计划(MRP)的基础上，引入了约束理论(TOC)的概念和方法，建立了基于 TOC 与 MRP集成的敏捷制造计划与控制系统体系结构。并采用改进的时段划分方法，实现了系统中瓶颈资源的识别，针对单一瓶颈资源条件下的瓶颈排产问题，以任务延期交工时间最短及计划期内误期任务数最少为目标，分别采用单目标和多目标启发式算法对瓶颈资源上的关键任务进行排序，完成了相应的排序算法。陈建华和彭鸿广 15构建了基于 TOC 的以 MRP生产计划系统为主导的“Push”体系和以 JIT 生产控制系统为主导的“Pull”体系相结合的集成化生产计划与控制模型。Daniel16将 DBR 应用在海军航空站翻修作业(Remanufacturing) 生产计划上，有效缩短了返回交货期，另外使用动态缓冲的观念，将瓶颈作业站前的加工时间总和乘上一个固定缓冲常数，寻求装配件的最佳缓冲常数以决定装配件的投料时间点，来降低外购物料的存货水平。陈栋 17在研究了约束理论、建模与仿真的基础上，构建了基于离散事件系统建模与仿真的改进的 DBR 生产计划与控制方法。孙凌云 18对基于 TOC 理论的车间作业管理系统进行了研究，提出了基于 TOC理论的车间作业管理系统模型，对车间作业调度问题进行了分析，将问题转化为一般单件车间调度，然后运用 TOC 理论提出瓶颈资源排产方式。对 ERP 的车间作业管理系统进行优化设计，完善了传统 E 好中车间作业管理系统不足之处。侯晓光 19将约束理论引入到构建制造企业物流系统评价指标体系，运用层次分江苏科技大学经济管理学院毕业论文（设计）5析法，对各指标进行分析、排序和提炼，从中找出制约制造企业生产物流运行效率的“瓶颈” 。将 TOC 理论的思维逻辑和指标评价方法同经典的层次分析法相结合，以定性分析和定量计算相结合的方式，来挖掘生产企业物流系统运营中的瓶颈，提出了消除约束的方法，为物流系统进行持续优化和改进，提供理论依据。王军强 20博士针对传统约束理论产品组合优化运作逻辑存在的问题，构建了新型约束理论运作逻辑：充分利用产能；辨识系统瓶颈；其他资源服从优化决策安排；提升系统瓶颈；打破系统瓶颈，辨识新的系统瓶颈，克服惰性持续改进。新型运作逻辑减少了传统约束理论仅就系统已有的生产能力讨论产品组合而造成规划的保守和接单的损失，改变了产品组合必须依赖产品优先级的思维定势，保证了系统各瓶颈资源的充分利用，使产品组合优化方案整体最优。李浩、沈祖志和邓明荣 21基于约束理论，对订货型企业的客户订单优势因素与瓶颈资源确定准则进行了分析，引入了“虚拟订单”概念；通过对客户订单进行分解，建立了“虚拟订单”的数据结构和优势准则；基于该准则给出了订单投产排序优化的启发式算法。王红娟 22在研究混合流水线生产调度时引入了 TOC 理论，采用基于约束理论的HFS(混合流水线) 分层调度系统，将整个调度系统按照控制的目标和实现方法的不同分为上层整数规划层、中层缓存控制层和下层设备加工调度层。1.2.3 遗传算法遗传算法是由美国 Michigan 大学的 Holland 教授于 1969 年提出，后经DeJong、Goldberg 等人归纳总结所形成的一类模拟进化算法 23。其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。遗传算法最早应用于一维地震波形反演中，其特点是处理的对象是参数的编码集而不是问题参数本身,搜索过程既不受优化函数联系性的约束,也不要求优化函数可导,具有较好的全局搜索能力；算法的基本思想简单,运行方式和实现步骤规范,具有全局并行搜索、简单通用、鲁棒性强等优点,但其局部搜索能力差, 容易出现早熟现象 24。目前已有一些将模拟退火算法与遗传算法相结合的方法。比如江雷 25研究的并行遗传算法中，通过模拟退火方法来控制变异概率（ ）的选取，通)/exp(TmP江苏科技大学经济管理学院毕业论文（设计）6过模拟退火方法来控制交叉后子个体替代父个体的概率，但是这两种办法均不能充分的利用模拟退火算法强大的局部搜索能力。陈亮 26利用遗传算法的特点来改变模拟退火的性能，首先通过 GA 来进化一个种群，然后再通过 SA 进一步调整优化解，这是对整个种群进行退火，没有能很好的利用 GA 得到的全局信息。而国内的遗传退火进化算法，大多数是使用正交实验法 27。1.3 研究内容与结构企业集团的订单排产已成为研究的一个热点，但是江苏惠通集团和大多数企业一样，订单的生产顺序仍是以交货期为排序依据。事实上，订单的排产是个非常复杂的问题，它会受到很多因素的影响。例如：企业集团的管理层、集团的管理模式、销售模式、企业集团的发展计划，还有不同的部门对订单排产的要求也不相同。针对本文研究主题和研究目的，通过对企业集团订单排产优先级因素的梳理，提炼出订单排产的一般规律，得出安排订单排产的数学模型，指导集团合理安排订单的生产。基于此，本文提出了以客户重要程度、订单数量、订单利润、订单交货期等为依据的订单排产优先级规则，以生产费用、库存费用、惩罚费用为主的模型，采用遗传算法求得近优或者最优的订单排产。文章的结构如图 1-1：江苏科技大学经济管理学院毕业论文（设计）7实例应用提炼问题模型 ， 进行定量分析分析问题中存在的影响因素 ， 采用相应的解决办法理论基础 总结展望分析企业的现状 ， 找出相关的企业中存在的问题学习归纳研究课题所需的知识研究课题的目的和意义图 1-1 文章内容结构图2 理论基础本章罗列了解决惠通集团在瓶颈工序上的订单排产问题所需的主要理论部分和方法简介。2.1 约束理论如果没有约束，系统的产出将是无限的。现实当中任何系统都不能无限地产出，所以，任何系统都存在着一个或者多个约束。而任何的企业和组织均可视为系统，因此，要想提高企业和组织的产出，必须尽可能打破各种约束。因此约束理论（TOC）提出了在制造业经营生产活动中定义和消除制约因素的一些规范化方法，以支持持续改进。2.1.1 约束理论与瓶颈资源TOC 是关于进行改进和如何最好地实施这些改进的一整套管理理念和管理原则，江苏科技大学经济管理学院毕业论文（设计）8可以帮助企业识别出在实现目标的过程中存在着哪些制约因素(TOC 称之为约束)，并进一步指出如何实施必要的改进来消除这些约束，从而更有效地实现企业目标。约束理论是一个很多方法和理论所形成的综合体系，其结构主要分为五个层次 1，如图 2-1： 目 标 作 业 指 标 管 理 原 则项 目 管 理营 销生 产 分 销 战 略 设 计 有 效 沟 通双 赢 思 想团 队 合 作 持 续 改 进 DBR系 统思 维 流 程 （ TP） 图 2-1 TOC 的概念层次结构约束理论的特点：TOC 将生产系统中的工序分为瓶颈工序和非瓶颈工序，以瓶颈为核心组织生产管理。TOC 不需要预先设置提前期，因为它以瓶颈工序的生产安排为依据，提前期由加工时间、批量、生产能力等因素来决定。TOC 认为，瓶颈资源的利用率应达到 100%，而非瓶颈资源不一定要 100%地利用。TOC 中，计划控制生产，而生产往往反过来作用于计划。TOC 认为，任何一个生产系统都存在着某种资源限制或者约束，我们称之为瓶颈，该瓶颈决定了这个生产系统的产出效率。这种瓶颈可以是必需的专业机器、工具或者技术熟练的工人，若想提高一个系统的产出效率，就必须充分利用或者打破该瓶颈。企业安排生产时，管理层不应强调局部最佳化，不应有非瓶颈部分满负荷生产的想法，因为这样会造成生产线上在产品积压，不但不能提高生产系统的产出效率，反而增加了存货成本。最好的办法是，生产系统的其他部分服从于瓶颈部分，按照瓶颈的产出效率来安排非瓶颈部分的生产，强调沟通协作，做到“抓住重点，以点带面” 。因此要想是整个生产流程顺畅并满足客户的交货期，瓶颈工序的生产作业计划是首先要解决的问题。江苏科技大学经济管理学院毕业论文（设计）9TOC 关于“瓶颈”的定义可以形式化描述如下：对于生产中的 n 项资源： ，企业的实际产出能力、外部需求量分别nX,21为 和 。某些资源之间存在互为输入和输出的关联关系C,21 nMR,21R(注意：这里输入、输出的可以是在制品等有形资产，也可以是信息等无形资产，或是与系统最终产出有关的彼此制约、彼此影响的前后因果关系)。假设与资源 相关iX联的资源 标号所组成的集合为 S，即 。那么，当且仅当jX ),(),jiXRji时，资源 为瓶颈。)(,jCMinRiCi iX2.1.2 瓶颈识别与管理瓶颈环节是由各种条件变化引起的 29，如机器故障、在制品的耽搁、定单的变化等。要判别一个资源是否为瓶颈，应从该资源的实际生产能力与它的生产负荷来考察，然后列出各工序负荷比较表。从前面的瓶颈问题分析中可以看出，瓶颈环节就在主要的关键资源上。瓶颈环节具有动态性的特点，表现在不同的任务在不同的时间周期内，瓶颈环节可能在不同地方，而且在系统的运行过程中，特别是在关键任务和非关键任务相互转化的时候,瓶颈环节可能还会发生移动。制定计划时的瓶颈环节属于静态的，这时部分关键任务是已知的，根据关键任务在各资源上的分布，通过不断调整，就可以确定出哪些是关键资源，然后通过比较确定系统的瓶颈环节，而在系统运行后，应保证各关键任务的顺利流动， 但是由于一些意外的因素和系统固有的误差，关键任务会发生一些变化，那么应该重新进行计算。另一方面，瓶颈问题贯穿于调度系统控制的整个过程。在系统开始运行之前，必须首先找到系统的瓶颈环节，这样确定的期望输出即计划才能反映或近似反映系统的目标。“瓶颈”控制了库存和产销率 30。因为，产销率指的是单位时间内生产出来并销售出去的产品所创造的利润额，所以，很明显它受到企业的生产能力和市场的需求量这两方面的制约，即它们受由资源瓶颈和市场瓶颈所控制的。如果“瓶颈”存在于企业内部，表明企业的生产能力不足，相应的产销率也受到限制；而如果当企业所有的资源都能维持高于市场需求的能力，那么，则市场需求就成了“瓶颈” 。这时，即使企业能多生产，但由于市场承受能力不足，产销率也不能增加。江苏科技大学经济管理学院毕业论文（设计）10编排作业计划时考虑系统资源瓶颈 31。提前期是作业计划的结果，而不是预定值。 MRP制定作业计划的方法是按预先制定的提前期，用无限能力计划法编制作业计划。但当生产提前期与实际情况出入较大时，所得的作业计划就脱离实际难以付诸实施。 瓶颈管理与 MRP正好相反，即不采用固定的提前期，而是考虑计划期内的系统资源瓶颈，用有限能力计划法，先安排瓶颈资源上加工的关键件的生产进度计划，以瓶颈资源为基准，把瓶颈资源之前、之间、之后的工序分别按拉动、工艺顺序、推动的方式排定，并进行一定优化，接下来编制非关键件的作业计划。所以，瓶颈管理中的提前期是批量、优先权和其他许多因素的函数，是编制作业计划产生的结果。“瓶颈”上一个小时的损失则是整个系统的一个小时的损失。一般来说，生产时间包括调整准备时间和加工时间，但在瓶颈资源与非瓶颈资源上的调整准备时间的意义是不同的。 “非瓶颈”的利用程度不由其本身决定，而是由系统的“瓶颈”决定的。瓶颈资源制约着系统的产出能力，而非瓶颈资源的充分利用不仅不能提高产销率，而且会使库存和运行费增加。由于“瓶颈”控制了产销率，所以企业的“非瓶颈”应与“瓶颈”同步，它们的库存水平只要能维持“瓶颈”上的物流连续稳定即可，过多的库存只是浪费，这样， “瓶颈”也就相应地控制了库存。2.2 遗传算法达尔文的进化论思想是：“适者生存，劣者淘汰” 。将达尔文的进化论应用到企业生产作业计划中，可以得到近优甚至最优计划。2.2.1 遗传算法理论遗传算法是借鉴生物自然选择和遗传机制的随机搜索算法。遗传算法之所以能够增强解决问题的能力，是因为自然演化过程本质就是一个学习与优化的过程。该算法的核心思想是：生物进化过程(从简单到复杂，从低级到高级)本身是一个自然的，并行发生的，稳健的优化过程，其目的就是要适应环境。生物种群通过“优胜劣汰”及遗传变异来达到进化，生物的进化通过繁殖，变异，竞争和选择实现的。生物遗传物质的主要载体是染色体，而基因是控制生物性状的遗传物质的功能单元和结构单位。多个基因组成染色体，染色体中基因的位置叫做基因座，而基因的取值叫做等位基因。基因和基因座决定染色体的特征，也就决定生物个体的性状。此外，江苏科技大学经济管理学院毕业论文（设计）11染色体具有两种模式，即基因型和表现型。基因型是染色体的结构特征，而表现型是生物个体表现出来的性状。同一个基因型在不同的环境下可以有不同的表现型，因此表现型是基因型与环境条件相互作用的结果。在标准的遗传算法中，通常将染色体表示为一维的二进制串结构，串上各个位置对应基因座，各个位置上的取值对应等位基因。遗传算法处理的是染色体，又叫做基因型个体。一定数量的个体组成群体，群体中个体的数目为群体规模。遗传算法中通常有一个目标函数与生存环境相对应，由它来确定各个个体的适应度。在遗传算法中需要进行数据转换操作，一个是表现型到基因型的转换，把问题空间的参数转换成遗传空间中的染色体；另一个是基因型到表现型的转换，它执行相反的操作。2.2.2 遗传算法的基本流程遗传算法的流程如下：（1） 令 k=0，随机产生 N 个初始个体构成初始种群 P(0)；（2） 评价 P（k）中各个体的适配值（ fitness value） ；（3） 判断算法收敛准则是否满足。若满足则输出搜索结果；否则执行以下步骤；（4） 令 m=0；（5） 根据适配值大小以一定方式执行复制操作来从 P（k）中选取两个个体；（6） 若交叉概率 ，则对选中个体执行交叉操作来产生两个临时个1,0cp体；否则将所选中父代个体作为临时个体；（7） 按变异率对临时个体执行变异操作产生两个新个体放入 P(k+1)，并令m=m+2；（8） 若 mN，则返回步骤 5；否则令 k=k+1，并返回步骤 2。遗传算法的流程图：江苏科技大学经济管理学院毕业论文（设计）12随 机 产 生 N个 个 体 构 成 初 始 种 群 P（ 0） ， 令 k=0对 种 群 P（ k） 中 各 个 体 进 行 评 价算 法 终 止 条 件满 足 否 ？令 m=0执 行 选 择 操 作 从 父 代 种 群 中 选 取 两 个 体交 叉 概 率 Pc大 于 0,1将 所 选 中 父 代 个 体 作 为 临 时 个 体对 两 临 时 个 体 以 变 异 概 率 Pm执 行 变 异 操 作 产 生 两 新 个 体 并 放 入 P（ k+1） ， 令 m=+2对 选 中 个 体 执 行 交 叉 产 生 两 临 时 个 体判 断 mN？令 k=+1输 出 优 化 结 果NNYYY图 2-2 标准遗传算法框图 322.2.3 遗传算法参数和运算（1）个体编码遗传算法的运算对象是表示个体的符号串，所以必须把变量编码为一种符号串。（2）初始群体的产生遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始群体数据。江苏科技大学经济管理学院毕业论文（设计）13（3）适应度汁算遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。（4）选择运算选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。（5）交叉运算交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。（6）变异运算变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法 33。2.3 订单优先级和排产2.3.1 订单分类一般订单：这种订单占企业订单中的绝大部分，时间、产品、数量、要求上等方面不存在过高的要求，按照标准编制作业计划原则就可以编制生产作业计划。紧急订单：该订单往往表现在交货时间紧迫，需要加班加点赶工来完成。每个企业都应该对紧急订单有明确的要求，比如是重要客户的急需订单，或者大利润的订单。另外，已生产完的订单若质检不合格，需要返工重新生产，这时的订单还有排在后面的订单都可能从一般订单转化成紧急订单。交货时间紧迫是指在最迟交货期前，加班加点生产，每天的产品生产率依然十分接近甚至超过实际生产率，也可以说根据实际生产率生产，订单在交货期完工或者会延期完工。所以生产情况必须不断更新，以及时识别出紧急订单。变更订单：指客户对订单有新的要求，比如订单产品数量的增多或减少，订单产品品种的改变，交货日期的提前或延迟。也可能是产品数量、产品品种和交货日期的同时变更或两两变更。取消订单：指由于某些原因，原本已经收到的订单被生产商或者客户取消。这时，江苏科技大学经济管理学院毕业论文（设计）14如果订单已经开始生产，则造成了企业生产力和生产资源的浪费；如果订单还未投入生产，需要迅速撤销所有相关订单，调整生产作业计划，将资源分配到其它订单中。2.3.2 优先级规则订单优先级决定订单的生产顺序，从而决定企业在生产中的收益情况。许多企业对订单进行排产采用的优先级规则是按交货期的先后顺序，但是这种生产方法很容易造成生产的不平衡，生产过程过紧或者过松。而且不一样的部门对订单的排产要求也不同，例如销售部门要求按客户的重要性和交货期要求来安排订单投产顺序，财务部门要求按订单利润的大小来安排，生产部门则希望能尽可能满足生产均衡的要求，等等。所以需要确定一个统一的优先级原则，建立一个统一的目标。在本文中采用的优先级原则是生产总成本最小。在安排生产作业计划时，首先是对订单生产排序，有 m 个订单，会有 中排序方式。但是由于交货期、库存、不在mA交货期窗内交货所收到的惩罚等等因素约束着订单排序，本文研究的是在众多排序中，以总成本最小为原则进行排产，找到瓶颈工序上的最优或者近优排产顺序。另外对于紧急订单和变更订单的排产采用相对简单的优先级别，因为追加订单和修改订单如果都采用遗传算法来重新排产，排产结果很可能与原先顺序不同，这样生产作业计划会被频繁的打乱，造成生产混乱不堪，反而耽误所有订单的生产。因此，安排特殊订单的生产考虑简单的办法。2.3.3 生产订单的排产问题订单排产都是以按照优先级别编制生产作业计划为主，由于生产企业在安排生产计划时，一般根据需求预测和订单量来进行安排，针对在生产过程中的突发事件(如接受新订单、退单等)处理起来比较困难，而基于约束理论的计划与控制方式能够寻求顾客需求与企业能力的最佳配合，在处理动态系统中生产计划与控制问题时引入约束理论将会取得较佳的效果 34。一般对生产排产的研究往往是以单瓶颈资源静态系统的排产为主，即在订单信息已知，需求预测不变的条件下来进行生产排产，对动态生产系统中生产排产的研究很少。在当前多品种、小批量的生产方式下，在外界需求要求及时、迅捷的条件下，现实中的制造企业基本都是动态的生产系统。即在实际生产中，经常会出现紧急插单或者订单取消