基于动态瓶颈的启发式算法生产流程优化研究∗

王绍伟 金文祥

（大连交通大学 大连 116028）

1 引言

生产过程中那些生产能力小于生产需求的生产设备往往会导致生产瓶颈的出现，生产瓶颈设备是决定生产系统生产能力的关键因素［1］。由于混合生产类型车间的产品加工流程相对复杂导致容易出现生产瓶颈的问题。如何高效地解决生产加工瓶颈问题，不断提高整体的生产效率及质量是生产企业必须解决的难题。本文提出一种瓶颈指向的启发式算法的生产加工排产算法，解决以往人工排产效率低、容易产生生产瓶颈的问题，优化资源配置，提高整体的生产加工能力［2］。

2 问题描述

在现实的车间生产环境中，存在着动态随机因素，如产生临时订单、物流线路的改变、生产设备发生故障、物料短缺以及订单交付日变动等，这些动态的因素都会导致生产过程的瓶颈资源发生漂移现象［3］。如何充分考虑生产瓶颈漂移的情况确定生产系统的瓶颈阶段是解决生产排产问题的关键。

本文充分考虑实际生产过程中的生产装配优先原则、加工工序的作业时间、紧后作业工序等问题，模拟真实生产情况设计工件装配过程，确定加工机床在整个生产过程中的机床负荷情况［4～5］。根据生产工件对加工机床的占用率情况确定生产过程的瓶颈阶段。Johnson规则是利用工件在两台不同的生产机床上加工时间不相等的特点将加工工序分成两类：能快速通过该加工机床的工序排在生产阶段前列，通过速度较慢的排在生产阶段后列［6］。本文依据Johnson规则根据工件工序在瓶颈机床的加工时间的不同分为生产上游和生产下游两个阶段，分别对生产上游和生产下游的工序按照一定规则排序，优化生产工艺流程。

3 算法描述及实现步骤

3.1 生产机床独立需求概率

为方便问题描述，引入如下符号：

工件集合I，I=｛1，2，…，n｝；工件编号i，iϵI；工序阶段集合J，J=｛1，2，…，s｝；工序编号j，jϵJ；Sij表示工件i的j生产工序。Tij表示Sij工序标准加工时间。

假设工序Sij需要在机床m上进行加工，则将Sij在时间t占用机床m的可能性定义为Sij在t时间对m的独立需求概率［7］。工序Sij在其候选开工时间集的某一时刻开始加工的事件具有互斥性，并且可以根据工序标准作业时间表可以确定工序Sij占用机床m的时间。根据概率规范性及有限可加性可以得到利用工件工序开工时间确定工序Sij在机床m上的开工概率，从而计算得到工序Sij在t时刻对机床m的占用程度［8～9］。因此，工序Sij在时间t对机床m的独立需求概率为

则全部工件及加工工序对机床m的独立需求概率为

机床累计需求概率和描述了整个生产过程中，各机床随着时间变化生产负荷情况，也反映了待调度工序在不同时间点对同一机床的竞争情况［10］。

3.2 瓶颈指向的启发式算法

基于生产瓶颈指向的启发式算法主要考虑生产设备的位置布局及各工件的加工时间的因素［11］：

1）机床累计需求概率最大的机床即认定为此设备为生产的瓶颈阶段，标记为瓶颈。按照瓶颈前后将生产流程分为上游工序和下游工序，分别用π 1、π2表示。

2）瓶颈上游工序集π1排序：根据工件加工开始时间表及工序标准作业时间表，按照能够最先到达机床m的工序优先开始加工，当出现两个（多个）到达瓶颈阶段时间相同时，选择较短时间通过m机床的工序优先。

3）瓶颈下游工序集π2排序：瓶颈下游工序排序规则按照瓶颈后续工序时间长的工序优先开始加工。

4）将上游工序集合π1第一条工序插入到π的第一工序位，同时删掉下游工序集合π2中的该工序，将下游工序集合π2的最后一条工序插入到集合π的最后工序位。重复该操作直至上游工序集及下游工序集π1、π2中工序全部排入新的工序集π中，根据优化后的工序集π，改进初始的工件的机床指派和加工顺序。

4 数据和实验结果分析

图1给出了简单的生产调度情况：车间目标生产6个工件，每个工件包含若干工序，生产过程中使用5台加工机床。本文默认一台机车床只能同时加工单一工件某个工序，工件在车床上需保证从加工开始一直到该工序加工完成，不允许在加工过程中暂停而进行其他工件或者工序加工的情况［12］。

工序标准作业时间表如图1所示。

图1 工件加工工序流程图

图2 机床占用利用率变化示意图

从图2的各机床独立占用率可以得知机床2的独立需求概率最高，故机床m2为瓶颈机床。根据各工件到达机床m2的时间以及通过m2之后的后续加工时长对工件加工顺序进行调整优化。机床加工流程优化结果如表1所示：

表1 不同判断条件的工序顺序集合

机床生产流程甘特图如图3、图4所示。

分析该模拟生产案例，通过计算工件J1-J6加工时间和空闲等待时间得到工件加工时间总和为机床的总生产时间为T，为工件加工时间与等待时间之和。以平均生产负荷最大机床作为瓶颈机床排产的总生产时间T1=358，以独立占用率最大的机床作为瓶颈机床排产的生产时间T2=360。不同判决条件情况的装配线生产效率分别为计算两者数值分别为机床独立占用最大的机床作为瓶颈阶段对于以机床平均负荷率判断瓶颈阶段的最大作业时间优化比例为装配线平滑指数S为计算得到S1≈ 8.31、S2≈2.49。通过仿真结果可以说明以工件对机床的独立需求概率为条件判断生产过程瓶颈阶段能够更好识别真实的生产瓶颈，缩短整个过程的最大完工时间，但由于工序的生产关联性，初始状态的工序生产车床的分配情况会对装配线的平滑指数产生影响，本算例的排产对装配线的平滑指数影响较小，且该问题可以通过初始的生产机床分配解决［13～14］。

图3 平均负荷最大为生产瓶颈甘特图

图4 独立占用率最大为生产瓶颈甘特图

5 结语

混合型生产过程往往存在并行生产设施，且由于并行生产设备耗损的不同，导致每台机床的生产能力不同而出现生产瓶颈问题［15］。如何准确地找到生产过程中的瓶颈阶段，优化生产流程是提高生产质量和效率的关键。本文提出了一种基于动态生产瓶颈的生产排产算法能够更准确地识别生产过程中的瓶颈阶段，优化工件加工流程，缩短作业时间表长，提高生产效率，具有一定的实用性。