摘 要

当前单元制造系统内存在工件在单元间转移的情况，由此带来跨单元调度问题。网络制造环节中，加工任务和加工单元的动态加入和减少，如何协调这类动态调度问题正被广泛关注。经典的调度算法主要针对的是静态的环节，而实际的生产环境是动态的，比如新的订单的加入和取消，设备取消等都会影响调度的结果。因此，本文考虑了跨单元的动态调度问题，基于相关领域研究现状的调研，分析了跨单元动态调度问题的复杂性和重要些。

首先，通过问题假设、符号定义、目标函数和约束条件，详细描述了跨单元动态调度，并针对问题特点建立了数学模型。然后，利用蚁群算法分析了动态调度的实例情况，在动态调度中采用了周期性调度分析，所得结果对于跨单元动态调度具有一定指导意义。

论文主要研究了跨单元动态调度问题中加工任务的动态加入和加工机器的退出情况，研究结果表明：在该类调度问题中所构建的数学模型具有一定普遍意义，算法求解具有较好效果。

关键词：单元制造；跨单元；动态调度；蚁群算法

Abstract

The existence of intercell transfers has made the idea of creating independent cells impossible,intercell scheduling therefore comes into being. Owing to the case of dynamic joing of tasks and the exit of machine in the network manufacturing environment, how to coordinate this kind of dynamic scheduling problem is now being widely concerned. The actual environment that will influence the effect of the scheduling is filled with dynamic events such as the arrival of the new orders,the cancellation of the original orders and the malfunction of machines. In this paper, an intercell dynamic scheduling prolem is considered. the complexity of the problem is analyzed and it is worth an effort to study.

Firstly， the intercell dynamic scheduling is described and mathematically formulated given the constraints in practice. Then, ant colony algorithm are applied to analyze the case of dynamic scheduling. Periodic scheduling analysis are used in dynamic scheduling in this paper. The results are of great significance to the dynamic scheduling of intercellular units.

The paper mainly studies the dynamic joining of machining tasks and the exit of machines in the intercellular units dynamic scheduling problem. The results show that the mathematical model constructed in this type of scheduling problem has certain universal significance,and the algorithm has a good effect.

Key Words：cellular manufacturing,intercell move, dynamic scheduling,ant colony algorithm

目 录

第1章 绪论 1

1.1 选题背景 1

1.2 单元制造系统描述 1

1.3 车间动态调度概述 2

1.3.1 动态调度问题分类 2

1.3.2 车间动态调度问题的特点 3

1.3.3 动态调度研究方法 4

1.4 跨单元调度问题概述 5

1.4.1 跨单元调度的特点 5

1.4.2 跨单元调度问题研究现状的特点 5

1.5 论文结构 6

1.6 本章小结 6

第2章 蚁群调度算法的设计与实现 7

2.1 蚁群算法寻优原理 7

2.2 蚁群算法优缺点 7

2.3 蚁群算法关键技术简介 8

第3章 跨单元动态调度问题的分析与建模 12

3.1 跨单元调度问题的描述 12

3.2 数学模型 13

3.3 本章小结 15

第4章 基于蚁群算法的跨单元动态调度求解 16

4.1 模型构建 16

4.1.1 问题描述及目标函数 16

4.1.2 算法流程 16

4.2 仿真实验 17

4.3 本章小结 20

第5章 总结与展望 21

5.1 总结 21

5.2 展望 21

参考文献 22

致 谢 24

第1章 绪论

1.1 选题背景

伴随着全球化智能制造，多数装备制造企业已经建立了现代化生产线，大量传统机加工设备与先进智能设备共同存在，多品种混线生产长期存在。随着加工需求不断变化，各单元功能有限，某些工件不能在一个单元中完成所有加工，为避免为特殊工件购买专门设备，工件加工过程跨多个单元，形成跨单元协作的生产模式。^[1]

车间调度作为制造系统的基础和核心，优良的调度系统能减少车间库存，提高效率，减少成本，提高产品交货期。生产调度对提高制造业生产效率和竞争力十分重要，同时动态调度更加符合实际生产的状况，对突发的扰动进行重调度，具有相当的研究价值。

1.2 单元制造系统描述

单元制造系统（Cellular Manufacturing System，CMS）是在成组技术的基础上发展起来的，思想是把具有相似工艺的一组工件聚成一个工件族，能够生产该工件族的机器放在一起组成一个生产单元。

单元生产能够提高制造系统的柔性，适用于多品种小批量的短交期市场需求，能够提升制造系统的生产效率和制造系统对于外部变化的适应性，实现了效率和柔性的统一。并且单元生产方式还具有设备准备时间短，大型设备投资少等特点，能够快速容易地建立，方便地调整生产系统。^[2]

实现单元制造系统包括三个阶段，分别为单元构建（Cell Formation，CF），单元布局（Cell Layout，CL）和单元调度（Parts Scheduling in Cells，CPS）。^[3]

单元构建主要解决相似零件及设备的分组问题，该问题的设计方法主要分为两大类：一类是面向设计，另一类是面向生产。其中面向生产还可细分为层次法、矩阵法、数学规划法、非层次法、启发式算法和图论法等。

单元布局解决设备的布置问题。目前，国内外已有诸多文献对单元布局问题进行了广泛而深入的研究。单元内设备的布局方式分为两种，一种是流水单元布局，面向产品的布局方式，适用于大批量少品种的生产模式；另一种是作业单元布局，面向工艺过程的布局方式，适用于小批量多品种的生产模式。

单元调度，主要解决零部件在单元内和单元间的调度问题，是指在一定时间内，利用有限的资源对生产任务进行排序，以满足指定的性能指标，这个问题被证明属于NP问题。目前研究主要集中于单元内的生产调度，不能跨单元调度，而在实际生产环境中，某些零部件需要跨单元生产，需要多个单元相互协作才能完成生产任务，这些需跨单元生产的零部件称为异常工件（Exceptional parts，EP）。^[4]因此，我们有必要研究零部件跨单元生产情况下的生产调度问题。

本论文就是为了解决存在异常工件的单元调度问题，以现有的调度技术为基础，结合单元制造系统中实际生产情况，研究跨单元调度问题。

1.3 车间动态调度概述

调度问题可以描述为为了实现一个或多个目标对任务共同使用的有限的资源进行合理的时间分配。调度问题受到广泛研究，在实际生产中，车间调度类型往往是动态Job shop型的。因此，本文研究作业车间调度问题（Job Shop Scheduling Problem）。

动态调度和静态调度的概念最早由Jackson于1957年做了区分。^[5]最初的研究主要采用启发式方法或仿真方法，与实际应用有较大的距离。近年来，以计算机技术为代表的新方法的产生和发展，为动态调度的研究开辟了新思路，目前动态调度已成为生产调度研究中的热点之一。

根据作业的加工特点，动态调度是指作业依次进入加工系统进行加工，完成加工的作业依次离开，同时还要考虑实际加工环境中不断出现的动态扰动，如作业加工超时、机床故障，紧急订单的加入或者原来订单的取消等。

1.3.1 动态调度问题分类

按照对问题的处理方式，动态调度问题可分为三种类型：完全反应式调度、预测反应式调度和鲁棒调度。^[6]

（1）完全反应式调度

在这种调度方式中，预调度方案不生成，根据可得局部信息实时地进行调度，工件的优先权由工件和机器属性决定，采用分派规则从等待加工的工件中选择优先权高的工件进行加工，也被某些学者称为动态调度、在线调度或实时调度。

特点包括计算量小、直观及易于执行，缺点是不能使用全局信息，是短视的，不能保证系统维持较好性能运行。能取得较好的性能是在干扰事件频繁发生的环境中。

（2）预测反应式调度

大部分文献将其称为重调度或反应调度，它是制造车间最常用的动态调度策略。首先不考虑可能的突发事件，在预测反应式调度中，然后生成优化某一目标的预调度。利用反应调度修正预调度方案，当执行过程中发生突发事件时来保持调度的可行性或者改善调度性能。

（3）鲁棒调度

在满足性能需求的情况下预先考虑未来的干扰生成调度方案称为鲁棒调度，方案应具有鲁棒性和稳定性。鲁棒的是指—个调度在干扰情况下依然保持良好的性能。稳定的是指一个调度与干扰情况下的实际调度之间偏差很小。

1.3.2 车间动态调度问题的特点

Blazewicz详细分析了单台机器、多台并行机器、以及Job-shop调度问题在不同的约束和指标下的具体表述。^[7]

（1）复杂性。车间中的搬运系统、作业、加工设备之间往往是相互作用的，同时到达时间、操作顺序、安装时间、加工时间、以及交货日期对于每个作业都要考虑，由于车间调度问题是在等式或不等式约束下求性能指标的优化，在计算量上往往是NP完全问题，即随着问题规模的增大，对于求解最优化的计算量呈指数增长，因而使得一些常规的最优化方法往往无能为力。

（2）动态随机性。动态随机性表现在动态事件上，引起调度环境变化从而需要进行动态调度的事件称为动态事件。动态事件的种类有多种，Suresh等^[8]将动态事件分成以下4类：

①与工件相关的事件：工件随机到达。工件加工时间不确定，交货期变化，动态优先级和订单变化；

②与机器相关的事件：机器损坏负载有限，机器阻塞/死锁和生产能力冲突；

③与工序相关的事件：工序延误、质量否决和产量不稳定；

④其它事件：操作人员不在场、原材料延期到达原材料有缺陷动态加工路线等。

（3）多约束。在研究调度问题时，不仅要考虑机器约束和加工过程的时间约束，同时还要考虑其它约束条件，如人员、工具、物流系统等。

（4）多目标。调度的目标多种多样，在实际的调度中需要综合考虑各种目标。一次调度往往具有多个目标，如加工时间最短、利润最大、生产成本最低等，而且这多个目标之间有时互相冲突，需要对不同目标加以协调，再次调度时，目标可能变化，因此需要动态调整目标。

1.3.3 动态调度研究方法

目前，针对生产过程中的动态事件和随机环境，研究者们主要总结了三种动态调度方法：

（1）利用滚动窗口再调度方法

主要思想是：就是滚动优化利用滚动窗口将不确定性的调度问题分成一系列动态但确定的调度问题，通过将调度过程分为连续静态调度区间，在线优化每个滚动区间，使系统在此区间内达到最优状态，滚动调度策略既克服了动态加工时的不确定因素的影响，又可以把系统状态的变化反映到调度方案中。

（2）人工智能（AI）方法

人工智能和专家系统的出现对解决调度过程的实时性与智能性提供了重大的帮助。专家系统将领域知识和现场的约束生产知识库，根据当前状态和给定的优化目标从知识库中产生相应的调度方案，并能对突发状况采取相应的措施。这种调度机制克服了数学规划和仿真方法的不足，避开了繁琐的数学计算，并能生成最优调度目标，支持了调度的在线决策。

主要优点在于，它能充分利用决策过程中所有定量与定性的知识来生成比传统启发式算法更好的调度方案。但是还存在一些不足：①这种系统的开发、验证、维护与修改的成本较高。②对新的调度环境适应能力差。③对现场调度人员的调度知识与经验有很高的要求。同时由于人工智能方法本法发展水平的限制，很难及时对外部事件产生回应。

（3）仿真方法

侧重于对实际生产环境的模拟，通过对实际调度环境的模拟，收集仿真相关数据，对系统的动态性能以及系统状态进行分析，从而选择合适的调度控制方法。

优点在设计、运行控制系统方面非常有效，具有很强的可行性与说服力，并且试验不受时空的约束，实验效率高，时间段，对于大多数调度而言具有较好的效果。不足：本身具有实验的特点，因此从确定目标到数据采集，到实验验证往往要花费很多时间，并且通用性不好，当环境变化了，仿真方法就需要根据变化了的环境来重新建立模型，这就加大了仿真实验的应用难度，很难提炼出一般规律。

1.4 跨单元调度问题概述

理想的单元制造系统（CMS）是通过建立各自相对独立的生产单元实现的。但是由于市场需求不断变化，产品种类趋向于多样化，而CMS中单元内生产能力有限，某些工件的部分工序需要在其他单元的机器上完成加工，这样的特殊工件在单元间的转移形成跨单元移动问题（inter-cell move），由此产生了跨单元调度问题（inter-cell scheduling）。

根据车间类型的不同，跨单元调度可分为跨流水单元调度（Flow shop scheduling）和跨作业单元调度（Job shop cheduling）。^[9]

跨流水单元调度的特征是所有的工件都以相同的处理顺序在机器上加工。跨作业单元调度的特征是工件可以以不同的加工路径访问机器。

1.4.1 跨单元调度的特点

（1）加剧了物流不平衡。大型生产系统中的车间之间通常存在生产能.T力差异。时长最长的加工单元极易成为工艺路线上的窄口（即瓶颈）。

（2）增加了排产问题规模。CMS调度局限于单元内部，而跨单元调度使零件调度必须面向多个调度组成的平面结构，导致问题规模急剧增加，且在跨单元条件下不能分解为针对各个单元的子问题独立求解。因此，一般的算法很难满足计算效率的要求。

（3）跨单元使各单元排产相互依赖和制约。单元之间的依赖和制约，使得各单元的作业计划无法与其他车间割裂而独立存在。

1.4.2 跨单元调度问题研究现状的特点

（1）跨流水单元生产调度问题的研究

Shaw^[10] 1997.提出了一种流水单元生产系统的零部件调度方法，该方法考虑了新加入的零部件生产、异常故障等问题，对多个生产单元间的零部件进行生产调度。Yang 和 Liao^[11]以 flow-time 最短为目标，采用分支定界法和启发式算法，解决每个流水单元内工序的加工顺序。Reddy^[12]以最小化延迟时间和延迟作业数量为目标，考虑了作业切换时具有次序依赖的机器启动时间来解决该问题。

（2）跨作业单元生产调度问题的研究

Tang^[13]使用分散搜索方法解决特殊工件解决了作业单元制造系统的调度问题。Elmi^[14]等人在 Tang 等人问题模型的基础上，允许可重入工件，即一个工件的不连续工序可以在同一台机器上加工。采用模拟退火的方法，编码方式和 Tang 等人的方案相同，同时利用邻近结构优化最终解。

1.5 论文结构

本论文共分五章，各章内容安排如下：

第一章：本章首先指明了本论文的选题背景，然后详细描述单元制造系统和车间动态调度，跨单元动态调度的研究现状，接下来又介绍了本文研究的意义，指出在当前激烈的市场竞争中进行跨单元动态调度的研究具有重要的实践和理论意义。

第二章：本章主要介绍了蚁群调度算法。详细介绍了蚁群算法的寻优原理和优缺点，蚁群算法的关键技术和结构。

第三章：本章对跨单元调度问题进行了概括性的描述，然后论述了问题的模型及其性能指标。

第四章：本章对蚁群算法求解跨单元动态问题进行了仿模型构建，并通过设计实例证明了求问题的可行性。

第五章：本章对论文进行总结与展望。

1.6 本章小结

本章首先对课题的研究背景作了简要介绍。其次阐述了单元制造系统和车间动态调度问题及其特点，总结了跨单元动态调度问题的国内外研究现状和发展趋势。最后结合课题来源，提出了本文的研究内容和论文的结构。

第2章 蚁群调度算法的设计与实现

蚁群算法（ant colony optimization，ACO）是一种寻找最优路径的几率型算法。它由意大利学者Dorigo于1991年首次提出，其灵感来源于蚂蚁在寻找食物和绕过障碍物的过程中表现出来的群体行为。由于蚂蚁在觅食过程中表现的自组织性与自反馈特性，且不同蚂蚁的搜索又相对独立，因此能够很好的用于路径规划问题、排序问题等具有一定问题结构的动态优化问题。^[15]

2.1 蚁群算法寻优原理

有一定数量的蚁群从某些点出发寻找食物时，它们总能找到一条当前起点与食物之间的最优路径，并且一旦这条最优路径中出现障碍，蚁群可迅速的调整继续搜索最优的路径，巧妙的避开障碍的影响，从而得到新的最优的路径。之所以能在不同的环境里总能搜索的最优路径，依赖于蚁群间的协调合作，这样也就是蚁群算法特有的信息素的概念。且在搜寻食物的过程中，所有的蚂蚁都遵循一点的规律，这就是蚁群算法的原理。

（1）蚂蚁在寻找食物时，将在走过的路上释放一定量的信息素，且随着时间的流逝，信息素会成一定比例挥发。