典型车间调度问题的分析与研究

罗哲 夏余平 米双山

摘  要：文章针对目前车间调度问题中的两种典型问题展开研究，即流水车间调度问题、作业车间调度问题，其中，对流水车间调度问题的基本原理和研究方法进行了详细阐述;对作业车间调度问题的基本原理、调度策略以及研究方法等做了分析与总结。通过文章的论述，为进一步拓展这两个典型车间调度问题的深入研究提供了有益参考。

关键词：流水车间调度;作业车间调度;调度策略;调度方法

中图分类号：TP391         文献标志码：A         文章编号：2095-2945（2020）09-0054-02

Abstract： This paper studies two typical problems in the current job shop scheduling problem， namely， the flow shop scheduling problem and the job shop scheduling problem， in which the basic principles and research methods of the flow shop scheduling problem are described in detail. The basic principles， scheduling strategies and research methods of the job shop scheduling problem are analyzed and summarized. Through the discussion of this paper， it provides a useful reference for further expanding the in-depth study of these two typical job shopscheduling problems.

Keywords： flow shop scheduling; job shop scheduling; scheduling strategy; scheduling method

1 概述

车间调度问题指的是如何在有限的资源环境里，通过合理安排车间生产任务，进而满足一至多个性能指标的过程。随着经济社会的不断发展，企业之间的竞争也愈发激烈，生产车间的生产规模也越来越大，如何合理安排车间调度也越来越复杂，车间调度业已成为智能制造的基础组成部分。对于车间调度的优化问题研究已经成为工业发展的重点研究问题之一，对车间调度进行优化是提升现代制造技术和企业管理水平的重要内容。开展车间调度研究，寻求良好的生产车间调度问题求解方案具有十分巨大的理论价值和实际应用价值[1]。本文针对两种典型的生产车间调度问题，就基本原理、研究方法等展开探讨与分析。

2 流水车间调度

流水车间调度问题是加工制造业中的一类重要的规划问题，多数情况下研究流水车间调度问题的加工任务中的作业个数都要大于3，这时候的车间调度问题是NP-hard问题。在过去的几十年里国内外学者对这个问题做了大量的研究，相應的提出了许多解决这一问题的方法。这些方法大致可分成精确算法、启发式算法和元启发式算法三种。由于NP-hard问题的复杂性，所以，精确算法无法对规模较大的问题进行求解，只能解决一些规模较小的流水车间调度问题。启发式算法的优点是能够快速构造问题的解，但是通常得到的这些解的质量较差，无法满足要求。元启发式算法能够在较短的时间里面得到较高质量的解，所以，广泛采用这种算法来对流水车间调度问题进行求解。

2.1 流水车间调度的主要特点

流水车间调度问题的主要特点是一个生产任务内包含一些代加工的作业，这些作业在处理机上的加工顺序都相同，因此也被称为同顺序调度问题。流水车间调度问题的基本思路为：将一个加工任务中所有的待加工作业合理的安排到加工企业内的处理机上，使得整个加工过程的某一项或者某几项指标达到最优的目的。其中，每个作业在处理机上的准备时间和加工时间、每个作业的交货期等都是已知的，且要求每台处理机上加工工件的顺序相同。在某一时段内每台处理机只能对一个工件进行操作，操作过程不能中断直到作业的这一个操作完成为止。从对流水车间调度的描述可以看出它是许多实际流水线生产调度问题的简化模型，是目前研究最广泛的一类典型调度问题，受到了许多研究学者的重视，且提出了许多针对该问题的求解方法。但是主要的研究还是集中在单目标的流水车间调度问题上，而在实际生产环境中，流水车间调度问题存在着多个相互冲突的目标需要进行优化，因此开展多目标流水车间调度问题的研究更加符合实际。

2.2 混合流水车间调度

混合流水车间调度是一种相对比较复杂的流水车间调度。它是根据石油工业的背景提出来的。在被提出后的几十年里，许多研究学者对这一类问题进行了研究，得到了许多解决这一问题的方法。混合流水车间调度问题就其本质而言，可以分为两类经典调度问题：标准的流水车间调度问题和并行机调度问题。它的主要特征是：待加工作业的某些操作可以在几台并行处理机上进行加工，因此混合流水车间调度也被称为多机多阶段流水车间调度问题[2]。混合流水车间调度问题经常出现在柔性流水线的流程工业中，所以它也被称为柔性流水车间调度问题，其研究目的即对工序进行有效的排序，使得所选择的某个性能指标达到最优，进而实现企业效益最优[3]。由于其在理论研究领域的代表性和在诸多工业领域的广泛应用背景，近年来得到许多研究者的重视。

混合流水车间调度的特点为多目标性、多约束性、多阶段性以及非线性。其本质是由一系列加工过程组成，加工过程中的某些阶段可能只有一台处理机，但在整个加工过程中至少存在一个阶段有两台或者两台以上的并行处理机可以对其进行加工。待加工的工件可由并行处理机中的任一台进行加工，工件在车间里必须是单向流动的。混合流水车间调度在流程加工制造行业中应用比较广泛，如钢铁企业加工工艺大概可以分为炼钢、连铸和热轧三个阶段，每个阶段都会存在多个并行处理机可以对其进行操作。

3 作业车间调度

作业车间调度问题是计算机集成加工制造领域的一个重要组成部分，是最经典的离散制造系统调度问题，从数学规划的角度来看又是一类困难的组合优化问题[4]。由于作业车间调度是源于制造业生产的实际需要，所以近年来作业车间调度成为一个研究热点。

作业车间调度问题的基本思路为：将一个加工任务中所有的待加工作业合理的安排到加工企业内的处理机上，使得整个加工过程的某一项或者某几项指标达到最优的目的[5]。要求每个作业的操作都需要占用处理机或其它资源才能完成加工过程，在这个过程中必须满足各个作业的工艺路线、工艺次序要求进行加工。在加工过程中每台处理机可以加工作业的若干操作，并且在不同处理机上能加工的操作集可以是不同的，这是作业车间调度与流水车间作业调度最大的不同，因而使作业车间调度更加复杂。简而言之，作业车间调度的本质是确定一个满足各种约束的调度，该调度能在某个特定的时间段将每个工序分配到对应的处理机上，然后找到可以最小化加工成本和时间等某几个性能的调度。

3.1 作业车间调度的策略

基于作业车间调度问题的复杂性，根据具体情况选择相应的解决方案，为了能够得到更好的调度，可以从策略上对作业车间调度进行研究。目前形成的策略主要有以下几种：（1）并行和分布策略：从车间调度的描述就可以看出它是一个比较复杂的问题，所以求解大规模的作业车间调度问题来说是一件是非常困难的事情。基于此许多的研究学者提出用并行或分解的策略来解决车间调度问题。这种策略主要应用在不同车间控制结构和高度问题等复杂性的作业车间调度问题。（2）分解和成组策略：利用分解生产计划的策略，可以降低作业车间调度计算的复杂性和规模，经过分解后的作业调度问题更加容易得到好的解，同时还可以优化系统的一些性能指标。这种方法在制造系统应用的比较广泛。基本思想是根据工件和机器之间的相似性对它们进行分类，然后利用组内的相似性来提高工作效率。（3）多目标权衡调度策略：在实际生产过程中，以多目标的作业车间调度问题为主。如最大化生产效率、最小化生产周期、最小化加工成本等等，其中有些目标还是相互影响、相互冲突的，所以要对多目标进行权衡分析，得到一个均衡的调度。（4）生产计划与调度集成策略：应用这种策略可以对作业车间调度的全局优化和生产系统的柔性进行提升，所以生产计划与调度集成策略符合先进制造模式的思路。（5）人机交互策略：由于作业车间调度问题的多目标性和各种因素的影响，为了能够得到好的调度结果，往往需要与调度决策者的经验知识相结合来寻找最优的调度。人机交互的策略可以减少系统的搜索空间，能够更好更快的找到复杂的作业车间调度问题的最优解。

3.2 作业车间调度的研究方法

作业车间调度是生产调度问题中的典型代表，很多领域中具体的组合优化问题都可以抽象为作业车间调度问题进行求解。所以各领域的研究学者对作业车间调度问题进行了深入而广泛的研究，并应用到各自的领域当中，取得了令人满意的结果。特别是机械、自动化、计算机和数学等不同领域的结合交叉，为解决作业车间调度问题提出了众多新的研究理论和新的研究方法。这些方法主要有三种类型：精确算法、近似算法以及智能搜索算法：（1）精确算法：这类方法虽然从理论上能够寻找到最优解，但由于计算复杂度较高的一些原因，使得精确求解方法只适用于规模不大的问题和性质并不十分复杂的优化问题。而在实际生产环境中存在许多不确定性的因素会对问题的求解带来很大的困难，所以很难应用精确方法去处理实际调度问题。（2）近似算法：由于大多数的作业车间调度问题属于NP-hard问题。精确求解方法无法解决一些计算量大的复杂问题，所以许多研究学者研究这一问题采用各种近似或者启发式的方法来对问题进行求解。近似求解方法能在有限的时间内找到相对满意的次优解，这種方法可以用来解决较大规模的实际调度问题。（3）智能搜索算法：这种方法是根据生物种群特有的一些属性而抽象出来的一类算法。这类方法的特点是通用性强、求解的速度快且无需问题的任何特殊信息等。这种算法虽也是近似方法，但他们可以找到解空间中的最优调度方案。

4 结束语

随着智能制造的不断发展，车间调度问题的研究也越来越深入，车间调度在实现智能制造方面起着举足轻重的作用。本文分别从流水车间调度问题与作业车间调度问题的基本原理、主要特点以及调度策略等方面展开分析，并对混合流水车间调度问题的应用背景与主要特点进行了简要介绍。综述了作业车间调度问题常见的五种调度策略，以及其三种类型的研究方法。通过本文的分析与阐述，为后续车间调度问题的研究拓展提供了良好参考。

参考文献：

[1]包云，姜华，郑丽萍.基于和声搜索的阻塞流水车间调度问题的算法优化[J].计算机工程与科学，2013，35（7）：108-112.

[2]宋存利.求解混合流水车间调度的改进贪婪遗传算法[J].系统工程与电子技术，2019，41（5）：1079-1086.

[3]王建朝，袁逸萍，李晓娟，等.关键链约束理论解决柔性车间调度问题[J].机械设计与制造，2019（2）：30-33.

[4]闫旭，叶春明，姚远远.量子鲸鱼优化算法求解作业车间调度问题[J].计算机应用研究，2019，36（4）：975-979.

[5]杨恒.基于改进粒子群算法的作业车间调度优化[J].机械设计与制造工程，2019，48（2）：73-76.