第1章 绪论
1.1 引言
据美国英格索尔（Ingersoll）铣床公司统计，在不良的生产过程中，从原材料进厂到产品出厂，一个机械零件只有5％的时间是在机床上，其余95％的时间在不同的地方和不同的机床之间传输或处于等待状态［1］。而在这5％的时间中仅有30％是切削时间，其余70％消耗于定位、装夹等辅助（启动准备）动作上。由此可见，零件在车间的通过时间（lead time）中实际只有1.5％是有效的加工时间。零件在系统中大量无效的通过时间是导致在制品库存增加、资金积压，从而引起系统效率低下的根本原因之一。因此，一味依靠设备改型升级、缩短机器加工时间并非上策，采取改进组织管理、对生产过程进行合理的计划与调度，更容易取得成效。如何利用现有的资源，在各种制约条件下，快速、高质量地完成生产任务，是现代企业在急剧变化的环境中生存和取得竞争优势的关键。
生产调度是影响生产系统性能的主导因素之一，它的敏捷性在很大程度上决定着整个生产系统的敏捷性。它与企业准时交货、设备利用率和库存量有直接的影响，还与生产计划的可行性分析、销售部门接受订单的提前期、生产线的人力调配、设备保养维修、物料采购供应计划等经营管理活动密切相关。有鉴于此，国内外对生产过程的计划和调度的研究非常活跃，主要目标是研究减少生产过程中存在无效空闲时间以及能源浪费等的方法、技术和手段，研究成果层出不穷［2，3］。
实际生产中，生产企业处理的通常都是多品种、批量产品生产任务。由于生产调度问题的本质是组合优化问题，如果把单个产品或零件作为一个独立的个体参与调度排序优化，那么问题规模会变得很大，算法在存储空间和计算时间上需要花费很大的代价。因此，在制订生产计划时，可将交货期相同的整批同一产品或零件作为调度问题中的一个工件。经典的调度是在一个工件所含的批量全部加工完成后再安排别的批量。考虑到离散加工任务的可分性以及实际车间可能存在并行加工资源的情况，为了增加调度的灵活性，加工时可将整批工件划为若干较小的批次，允许分批生产和分批传输，则可使后续工序提前开工，从而可达到缩短完工时间、促进企业生产资源合理分配的目的。由此出现了分批优化调度问题（production scheduling with Lot streaming/Lot splitting）［4-6］，它是实际生产中迫切需要解决的一类问题，具有极其广泛的应用前景和较好的学术价值。以表1.1所述的2×3流水车间调度问题为例（表中数据表示单件加工时间），图1.1给出了经典调度中成批生产和传输的示意图（工件J1、J2的批量大小分别为20和50），图1.2为分批传输示意图。书中所使用的各算例，若无时间单位说明的，表示算例所涉及的时间单位统一但不限定。
表1.1 2×3流水车间调度问题
图1.1 成批生产和传输示意图
图1.2 工件J2分批传输示意图
分批优化调度问题考虑了工件批量性，更贴近实际生产，可适应现代经济发展所呈现的多品种和中小批量生产的特点。它同时涉及批量划分和排序优化，是比传统调度问题更加复杂的组合优化问题。合理的分批优化调度方案可以有效地提高生产效率、均衡资源利用率、降低物料和能耗、减少在制品库存、缩短交货期，促进车间生产管理的发展和企业资源的合理分配，对提高企业在市场的竞争力、改造传统的物料需求计划（material requirement planning，MRP）和制造资源计划（manufacturing resources planning，MRPⅡ）有十分重要的意义［7-9］。
1.2 分批优化调度问题
1.2.1 分批优化调度问题描述
分批优化调度问题可以描述为：N种批量生产任务（工件）需要在M台机器上完成加工，将可分解的批量工件进行批量划分，根据需要可按子批量分别组织加工和工序间的传输，对划分所得各子批进行资源分配、加工排序以及传输，在满足约束条件的同时优化某些指定的生产指标，*终目的是要产生能够指导实际生产的排产方案。问题涉及批量划分和排序优化，其中批量划分需要确定批量工件划分的子批数、各子批的批量大小，而排序优化则是为各子批分配资源并实现子批的加工排序，使得所选的生产指标*优。
问题涉及的基本要素有生产任务、制造资源、约束条件和生产指标。
（1）调度问题中的工件是被加工的对象，即生产任务，是在规定时间内需要生产的一定批量的产品，这些产品既可以是用户订购的产品，也可以是企业根据市场需求计划生产的产品。它是被调度的对象，在调度时一般根据产品工艺路径将其分解成若干道工序或操作进行。
（2）所涉及的制造资源主要包括：①机器类资源，如车床、铣床、加工中心、注塑机和烘箱等，是提供加工操作的对象；②刀夹具、模具类资源，用于辅助加工操作；③传输类资源，用于工件在各台机器间的传输操作，如搬运工、传送带和AGV（automated guided vehicle）等。此外，还有其他资源，如原料、人力、资金和能源等。调度时根据工序对资源的需求情况进行资源分配。
（3）分批优化调度问题一般受以下约束条件限制。
① 批量划分约束：要求划分所得各子批任务的批量大小总和保持不变，为批量工件的加工批量大小；
② 与生产任务关联的约束：在按子批量分别组织加工和工序间的传输时，应满足工艺顺序约束、投产期、交货期（完成期）和批量大小等约束；
③ 与制造资源关联的约束：在为各子批进行资源分配时，凡生产过程中所涉及的用于加工操作的机器类资源、用于辅助加工操作的刀夹具类资源、传输类资源、原料、能源和人力资源等，应根据任务的具体加工要求进行分配。若有资源使用冲突时，应按加工顺序依次处理，满足同一制造资源在同一时刻只能处理一个任务的约束。此外，还需满足资源的可用性、生产能力、存储容量、传输能力、原料的供应约束等。对于能源类资源，可能存在用能峰值限制、间歇性供能约束（如太阳能、风能）等。
(4) 生产指标的制订是为了尽可能获得*大的经济效益和社会效益，因此生产指标一般定为成本*低、生产周期*短、生产能耗*少、生产切换*少、设备利用率*高以及三废*少等［10］。生产指标大致可分为两类：①基于代价的指标，包括为了实现调度方案所消耗的各种费用和所造成的损失，如投资成本、运行费用（生产成本、能耗、碳足迹）、传输费用、存储费用（库存成本）、缺货损失、提前或延期交货损失等；②基于性能的指标，主要包括设备利用率、负载均衡性、*大完成时间、延期生产任务的百分比等。
1.2.2 分批调度策略
针对问题中存在的工件批量性，现有研究在处理分批优化调度问题时，采取区分准备操作（setup）与加工操作、分批传输、分批生产等策略来达到缩短生产周期、均衡资源利用率的目的［11-14］。
1. 区分准备操作与加工操作
在离散生产环境中，批量任务在某台机器上的加工时间等于该批所含单元的加工时间之和。除了加工操作，如机床调整、更换夹具等辅助操作，要求在工件加工之前完成且对于批量任务只需要进行一次，此类操作应该与加工操作分开考虑。加工过程中，对同一台机器上的下一个同类的紧邻批次，无须重复进行准备操作。对于与加工任务可分离的准备操作，机器可提前进行准备，如此当批任务到达时可立即进行加工操作，缩短完工时间。
2. 分批传输
批量生产环境中，在工件所含批量较大的情况下，如果等该批工件在当前机器上全部加工完后再一起传输到下一台机器，则会造成后续机器等待时间过长。实际生产中，为了缩短机器等待时间或者由于受到传输设备容量的约束，可将批量工件划分成若干较小的传输子批（transfer sublot/batch），允许各传输子批在完成当前工序后，无须等待其余子批即可直接传输到下台机器上进行加工，可使后续工序提前开工、缩短生产周期、减少在制品库存，如图1.2所示。进行分批传输时，需要综合考虑传输设备可用性、传输能耗、传输容量/能力等约束。
3. 分批生产
考虑到实际生产车间可能存在多功能机、并行机的情况，将批量工件划分成若干较小的生产子批，通过将这些子批任务分配到不同的机器上进行加工以平衡机器负荷，或者将不同工件的生产子批进行混排加工以充分有效地利用各机器上的空闲时间，能达到缩短生产周期、提高生产系统灵活性的目的。
1.2.3 批量划分对系统性能的影响
批量生产环境下的车间生产调度问题中，子批批量的大小对生产系统性能指标（生产周期、负载平衡、能耗等）的影响如下：
（1）在将批量工件进行分批生产时，子批的批量过大，不利于机器间的负载平衡，较大批量占有当前机器，导致后续机器长时间处于等待状态，降低了工作效率，延长了生产周期；考虑到批量准备时间的存在，过小的生产子批会导致过多的子批数，使得机器准备操作次数增加，生产周期和机器的准备能耗也增加。
（2）在将批量任务进行分批传输时，过小的传输子批量会导致过多的子批数，使工件在工序间的传输次数增加，增加传输能耗；而过大的传输子批会导致后续工序等待时间过长，延长了生产周期。
可见，子批批量与生产系统的一些性能指标存在U形关系［15］，过大或过小的子批量都不利于缩短生产周期或节约能耗。分批优化调度问题中，批量划分与加工排序对系统性能起着同等重要的作用，因此应该与加工排序一样给予重视。
1.2.4 分批优化调度问题分类
根据机器数量的不同，分批优化调度问题可以分为单机问题和多机问题。前者指所有生产任务只在一台机器上完成；后者指有两台以上的机器可被使用，它根据加工流程的不同又可分为流水车间（Flow-shop）、作业车间（Job-shop）、开放式车间（Open-shop）和多机并行加工（并行机）问题［16，17］。其中，Job-shop问题是*一般情况下的问题类型，*有代表性，其他问题类型可以看作特殊情况下的Job-shop问题。
根据需求产品的种类（工件数），可将分批优化调度分为单一产品和多产品分批优化调度。此外，根据问题的分批排序特点，分批优化调度问题还有以下分类方法：
（1）根据批量划分策略的不同，有等量分批和非等量分批两种方式。对于多阶段作业，可进一步分为均等子批（equal sublots）、一致子批（consistent sublots）和可变子批（variable sublots）三种批量划分类型［18-21］。其中，均等子批划分策略表示将工件划分成均等批量的传输子批或生产子批，且一类工件在各道工序上保持相同的划分方案，如图1.2所示；一致子批划分策略表示工件各子批的批量可不同，但一类工件在各道工序上仍需保持相同的划分方案，如图1.3所示；可变子批划分策略表示工件的划分方案根据情况可灵活多变，在各道工序上不必保持相同，如图1.4所示。图1.4中，工件J2在第三道工序上分成批量为40、10的两批，表示从第二道工序（加工机器E2）传输到第三道工序（加工机器E3）时，工件J2分成批量为40、10的两批分别进行传输，其中批量为40的子批在第三道工序的开始加工时间为320（假设传输时间忽略不计），此时正好是J2在第二道工序上完成40个任务量的时间，满足子批的工序顺序约束。在这三种方式中，均等子批是一致子批划分策略的一种特例，可变子批划分策略涵盖的范围*广且灵活性*大，然而其生产管理比前两种策略复杂。
图1.3 一致传输子批
图1.4 可变传输子批
（2）根据子批加工排序类型，可分为混排（intermingling sublots）和非混排（non-intermingling sublots）两种［20-23］。混排的问题类型表示机器在加工一类工件的各个子批任务之间允许加工其他工件的子批，如图1.5所示。考虑到不同工件在各台机器上加工时间的不均衡性，对不同工件的生产子批进行混排加工能
展开
