1.1目的及意义

在我国，多数装备制造企业已经建立了现代化生产线，但同时大量传统设备与先进设备共存，多品种混线生产长期存在。工件的加工路径跨多个单元，产生跨单元协作的生产模式^[1]。跨单元调度问题的研究不仅仅存在于我国装备制造企业中，在国外制造业中也会面临同样的问题。据统计，有72%的企业实施了单元制造模式，其中工件的平均跨单元率达20%以上，且只有10%的单元无需其他单元协作^[2,3]。

在我国，以综合传动装置为代表的复杂产品生产中，有50%以上的工件需要跨单元协作完成^[4]。关于跨单元调度的研究可以分为两类， 即跨流水单元调度(Flow shop scheduling) ^[5,6]和跨作业单元调度 (Jobshop scheduling) ^[4,7,8]。

在实际生产实际中，考虑车间生产实际情况，设备机床的台套数往往是一定的，而加工任务的时间往往会有长短不同，带来设备加工能力负荷的约束从而带来瓶颈约束。同时多品种小批量的单元制造系统虽然在零件族的种类上具有更多的生产柔性，但是由于生产过程中的任务负荷不平衡产生的瓶颈使其调度计划相对更加困难^[9]。

基于此问题，探寻适用于瓶颈工序触发的跨单元动态调度求解方案，使得车间调度系统能根据任务和设备实际情况及时调整原调度方案，把对系统性能的影响降到最低，同时还应保证原方案和新方案之间合理地衔接，保证实时生产的高效性及其对系统扰动反应的灵活性。

1.2国内外研究现状

目前在单元制造领域，国际上很多学者致力于单元构建方法的研究^[10-11]。如： WANG等^[11]从目标的角度对单元构建问题进行了分类研究； WANG 等^[10]研究了市场需求变动情况下的多目标动态构建方法。在流水线布局的生产单元中，关于单元内零部件调度的一些启发式算法^[12-14]、分支定界算法^[15]以及一些亚启发式算法^[16-17]被提出和比较。同时，在功能布局的生产单元中，一些关于单元内零部件调度算法也被提出^[18-20]。

在零部件跨单元生产存在情况下的单元管理问题。YANG 等 ^[21]和SOLIMANPUR等^[22]分别对此问题进行了研究，并提出了启发式算法，对于同一生产单元内零部件生产工艺可能不相同的情况，异常件须跨单元进行生产，WANG等^[23]研究了跨单元生产的零部件存在前提下的单元管理问题。

瓶颈移动方法（ShiftingBottleneck Procedure， SBP）由 Adams 等^[24] 在1988年提出，是目前作业车间调度问题中最有效的构造算法之一。该方法是第一个得到FT10实例最优解的启发式方法，对近似方法的发展带来巨大影响，并引领近似方法进入研究的繁荣期。瓶颈移动方法是按照每台机器解的大小顺序对机器进行排列，有着最大下界的机器被确定为瓶颈机器。SBP首先对瓶颈机器工件进行排序，保持其它机器的排序不变。每次对瓶颈机器进行排序后，所有以前排序的机器都要进行重新局部优化。重新局部优化过程都是基于求解单台机器排序的问题，而单台机器排序是通过Carlier^[25]在1982 年提出的方法迭代解决。瓶颈移动方法的主要贡献是采用了单台机器的松弛方式来决定机器排序的顺序，其难点在于重新局部优化和不可行解的产生。Dauzere-Peres和Lasserre^[26]、Demirkol等^[27]、Huang 和 Yin^[28]后来提出了较详细的改进研究方法。瓶颈移动启发式方法虽然能比优先分配规则提供质量更好的解，但算法实施较复杂，计算时间较长。

2. 研究的基本内容与方案

2.1基本内容