单元制造系统(Cellular manufacturing systems, CMS)作为现代一种十分有效的生产方式，在制造企业中得到了广泛的应用，它是在成组技术的基础上发展起来的一种生产模式。在这样一种制造系统中, 一系列的零部件根据成组技术被划分为零件族，而需要相似生产工艺的工件被组合在不同的制造单元中。因为相似的工件可以用相似的设备、夹具等进行处理，这种相似性可以减少加工的准备时间，也能够提高生产制造的柔性，使得企业能够快速响应市场对多品种、小批量的需求，同时基于单元制造方式的设备布局是实现精益生产的重要硬件支撑。CMS还具有减少在制品库存、缩短订单响应时间、降低物料搬运成本、提高质量、柔性的生产控制、生产物流量小以及生产费用低等优点。^[1-4]

理想情况下，每个工件的加工都被安排在一个单元内，并把加工相似工件的机器划分到一个单元，也就是说一个工件族的所有工序均可以在同一个单元内完成。但这只是一种理想情况，随着现代制造业的发展，现代化生产中产品需求越来越多样化，而单个单元的加工能力有限，可能无法完成对某些工件的某些工序的加工，这些工件的某些工序可能需要某些特定的机器来进行加工，然而一个企业的实际预算和空间是有限的，为某些工件的特定需求而购置额外设备也显得不太可行。因此，便形成了一些工件需要跨多个单元加工的情况，也便产生了跨单元转移。^[3]根据国外研究学者的研究报告，72.9%的大规模的工厂（共调查1025家工厂）采用了单元制造^[5]。然而，在实际生产中，只有10%的被调查的车间加工的零部件完全没有单元间转移，单元间移动的中位数高达20%^[6]。Li等也在中国对装备制造业进行了相关的调查，发现对于一些如合成传输设备等的复杂产品的生产过程中， 51% 以上零件的加工路线中均有跨单元现象的发生。^[7]

跨单元转移的现实存在也增加了单元调度问题的复杂性，一方面单元间依赖关系加深，协同加工变得愈发困难，另一方面，单元生产能力不均，加剧物流的不均衡。跨单元问题已经成为制约现代制造业发展的瓶颈。^[8]早在上世纪 90 年代初，Garza 和 Smunt指出跨单元转移难以避免, 理想的CMS将难以实施，须定量分析跨单元转移对生产系统产生的影响。^[6]

从企业角度来说，要想减少固定资产的投入，实现对市场需求的快速响应，提高资源的利用率，也需要进行跨单元调度的优化研究。因此，有必要研究跨单元调度问题。

单元调度主要包括确定工件加工顺序、加工任务分配、确定加工的开始时间和完成时间等工作。目前单元调度问题的研究主要分为两种：一种是流水单元调度问题（flow-shop scheduling problem，FSP）的研究；一种作业单元调度问题（job-shop scheduling problem，JSP）的研究。^[9]

对于flow-shop，其特点便是所有工件都以相同的处理顺序在机器上加工。国外学者Joseph Bukchin等^[10]研究了一种只含两个机器的flow-shop问题，并通过使用批量分割技术缩短平均流程时间。但其实真实的生产环境并非如此简单，少有一个单元只包含两台机器的情况，大多数单元内都包括许多台加工设备。潘玉霞等^[11]研究了较复杂的批量流水线调度问题，以提前/拖后惩罚指标为优化目标,提出了离散蛙跳算法。

由于本毕业设计更倾向于对JSP的研究，因此笔者更关注于JSP相关的文献。Job-shop的特点便是工件可以有不同的加工顺序。张超勇等^[12-14]和刘爱军等^[15]则分别提出了多种改进的遗传算法来解决柔性JSP，而Tsung-che^[16]用Pareto 方式求解多目标柔性作业车间调度问题，并提出了一种只需要两个参数的多目标进化算法。随着生产水平与技术的不断提高，人们越来越关注环境保护问题，因此绿色生产也被考虑到调度问题中。如刘琼等^[17-18]提出了以车间制造过程总碳排放和总完工时间最小为优化目标的多目标集成优化模型，张晓星等^[19]也发展了改进的混合蛙跳算法解决以最大完工时间和总加工能耗最小为优化目标的多目标调度问题。以上的研究都考虑了加工的柔性，即各工件工序路径不是唯一的，但是这些研究都没有考虑到跨单元转移这种普遍存在于加工中的现象，而目前对于跨单元问题的研究还并不多。

Solimanpur 等人^[4]提出了一种SVS启发式算法来求解具有单元间移动的单元调度问题，并将其性能与LN-PT方法进行了比较。Halat 和 Bashirzadeh^[20]提出了一种基于GA的启发式算法，用于考虑单元间运输时间的跨单元调度。

尽管以上提到的这些研究在他们的模型中包括了跨单元的运动，但是他们假设这种运动是已知固定的。但实际上，单元间路径通常是灵活的，因为不同的单元可能存在着机器能力部分重叠的情况，这样在跨单元时便产生了多种可供选择的跨单元路径，即所谓具有柔性路径。考虑这点的研究目前还不多。Feng等人^[21]考虑了一个具有柔性路径和机器共享的动态跨单元调度问题，建立了以最大完工时间和总工作量最小化为目标的混合整数规划模型，并提出了一种三层染色体遗传算法，能很好的描述工件、机器以及单元间的关系。但在他们的模型中假设的跨单元运输时间是相同的，没有考虑到运输时间受两单元间距离的影响。李冬妮等 ^[22-23]考虑了运输距离的影响，建立了基于多Agent的单元制造系统模型，提出了冗余单元的概念，建立了多 Agent之间的协商机制，并将 ACO 中信息素的思想引入到 MAS(Multi-agent system)的协商机制中以求解柔性跨单元调度问题。以上研究都有效的提高了算法的计算效率和求解性能，但均未考虑运输能力的问题，均假设工件需要跨单元时便可直接运输到对应的单元，即假设运输能力是充足的。但是在实际生产中，运输能力受限是普遍存在的现象。

本毕业设计将针对运输能力受限下具有柔性路径的跨单元调度优化问题进行研究。所谓运输能力受限指的是运输跨单元工件的车辆的容积以及车辆数量是有限。因为在实际生产中，各制造单元分布在不同的位置，跨单元工件需要车辆来运输，运输车辆的数量和容积是有限的，而工件的体积、重量是无法忽略的，所以工件在跨单元时，必须等待空闲车辆才能进行运输。