1.3 紧凑型生产模式下的调度问题
1.3.1 问题背景与意义
随着精益生产、智能制造等先进生产理念的提出与发展，现代制造业对生产管理水平的要求不断提高，生产流程趋向于紧凑连续化，进而产生了紧凑型生产模式下的调度问题，即紧凑调度问题（Compact Scheduling Problem）。紧凑调度限定了阶段间的工件等待时间，以及阶段内的工件时间间隔，其中，工件等待时间（Waiting Time）是指工件在完成一个阶段的加工后，等待下一个阶段加工开始的时间间隔长度；工件时间间隔（Time Lag）是指在同一阶段要求先后加工的工件，从前一个工件完工到下一个工件开工的时间间隔长度。对工件等待时间的约束存在于具有高温连续生产、中间产品性质不稳定、阶段间存在运输时间等特殊需求的多阶段加工环境，而对工件时间间隔的限制多见于工件间有优先约束或加工机器有空闲时间约束的调度环境，以保障生产的高度连续性。
在调度理论研究中，传统的紧凑调度问题要求阶段间的工件等待时间和同台机器的工件时间间隔均为零（即无等待且无空闲）[53]。这是一类“强NP-难”问题[54]，而且，无等待且无空闲的限定很容易导致问题无解[55]，因此，实际生产中不会同时存在这两种严苛的约束，换言之，传统的紧凑调度的概念并不符合生产实际，但这并不意味着在实际生产中不会同时出现对工件等待时间和工件时间间隔的限制。在生产具有高度连续性的制造业，由于工艺要求及机器限制，经常会同时限定工件等待时间和机器空闲时间的上限，这点在钢铁生产中尤为典型。例如，在钢铁生产的炼钢—连铸工艺中，其高温生产要求限定了等待时间上限，阶段间的钢包运送限定了等待时间下限；最末的连铸阶段为生产瓶颈，要求连铸机必须在一定炉次范围内连浇，切换浇次时，需要一定时间更换结晶器（并行链约束下的工件时间间隔上下限）。在钢铁生产的加热炉—热轧工艺中则要求板坯离开加热炉后直接进入热轧机组（无等待），热轧时必须严格按照轧制计划规定的板坯顺序（轧制单元）连续加工，仅允许短时间的空转待料（时间间隔上限约束）。此外，对工件等待时间和时间间隔的约束要求也普遍存在于食品加工、晶圆加工、化工生产等生产过程。
对于产品性质不稳定、高温连续作业的流程工业而言，特殊的工艺要求会产生较紧的等待时间上限和时间间隔上限，导致生产的高度连续，并造成了生产瓶颈。基于上述生产实际，我们将传统的紧凑调度扩展为工件等待时间受限和时间间隔受限的一类调度问题。在实践上，这一问题更贴近实际生产情况与工艺要求，能够对生产过程中的各类时间间隔进行严格控制，加快生产节奏，满足紧凑连续化生产需求；在理论上，传统的无等待且无空闲的紧凑调度是此扩展问题的一种特例，对于该课题的理论研究可以指导并应用于传统的紧凑调度问题。因此，对扩展的紧凑调度问题的研究相对于传统紧凑调度更具有理论价值和实际意义。
等待时间受限的调度问题是紧凑调度中一类基础且重要的问题，它在生产阶段间存在等待时间上限或下限的约束，产生于多阶段加工的车间生产环境，如流水车间（Flow Shop）、混合流水车间（Hybrid Flowshop）、作业车间（Job Shop）、开放车间（Open Shop）等。其中，等待时间受限的紧凑型流水车间调度（以下简称“等待时间受限的流水车间调度”）是最基本的形式，其研究成果不仅能够推进流水车间调度领域的理论研究，而且可以为其他三种调度问题的研究提供基础，并为解决更具复杂性的实际调度问题提供理论支撑。
虽然等待时间受限的紧凑调度具有广泛的现实基础，但目前研究多是针对具体的应用背景。在食品加工中，Hodson等[56]探讨了调度系统模型，其中，烹饪和冷冻阶段间的时间间隔不允许超过一定的上限，否则食物将会因腐烂而不能食用。在钢铁生产中，炼钢—连铸作为其关键工序而被研究者们关注，现有研究多是将对等待时间的限制要求作为优化目标而非约束条件[57-60]，这样虽然能够减少总的等待时间，但并不能确保每个工件的等待时间均在限定范围。除食品加工和钢铁生产外，还有一类研究广泛的典型应用——晶圆制造。晶圆制造作为半导体制造中最为复杂和重要的环节，具有规模庞大、制造资源众多及反复重入型加工等特性[61]。在晶圆的加工过程中具有严格的等待时间限制，当一片晶圆在一个加工模块中完成加工以后，必须在规定的时间内将其取出，否则就会损坏而成为废品，这也称为晶圆逗留时间约束。由于该约束给调度带来的困难，许多研究不考虑晶圆逗留时间[62，63]。也正是由于考虑晶圆逗留时间约束的调度问题未能很好解决，进而导致某些逗留时间约束严格的工艺过程不能在自动化组合设备（Cluster Tool）上加工，限制了半导体制造的自动化发展[64]。
通过上述文献可以看出，基于生产实际的等待时间受限的紧凑调度研究成果不具有普适性和推广性，无法对存在相似特征的生产调度问题起到指导作用。因此，有必要将具有等待时间上限的生产调度问题从实际生产中抽象出来进行理论研究，建立全面、系统、深入的理论体系。此外，虽然等待时间受限的流水车间调度是在一般流水车间调度问题的基础上提出的，但是等待时间约束使问题的性质出现了一些根本性的变化，Yang和Chern[65]指出，即使是仅有两台机器、等待时间仅受上限约束的情况，流水车间调度问题也具有“NP-难”的复杂性。由于问题的基本性质不同，现有的一些经典算法在等待时间受限的情况下将不再适用。因此，对于等待时间受限的流水车间调度问题，无论是在问题的基本性质还是求解方法上都需要进一步进行系统化研究。
1.3.2 基本概念与分类
工件等待时间和工件时间间隔是影响生产连续性的两类关键因素，紧凑型生产模式对其中至少一种因素的上限或上下限有着严格要求，进而产生紧凑调度问题。紧凑调度根据所考虑的关键因素，可分为等待时间受限的紧凑调度、时间间隔受限的紧凑调度及更为复杂的双重受限紧凑调度。下面对等待时间受限和时间间隔受限的基本概念及分类进行详细阐述。
（1）等待时间受限
等待时间受限（Waiting Time Constraints）是对加工对象的等待时间具有特殊要求的普遍形式，即要求工件在相邻两个加工阶段间的等待时间位于给定的上限或下限范围，在理论上可以抽象为具有等待时间上限和（或）下限的一般性约束。根据等待时间的受限范围，等待时间限制可以进一步细分为等待时间下限约束、等待时间上限约束和等待时间上下限约束。
等待时间下限约束（Minimum Waiting Time Constraints）规定了工件在相邻阶段间所允许的最小等待时间。定义wij为工件Ji在相邻阶段Mj和Mj+1间的等待时间，βij≥0为对应的等待时间下限，则存在等待时间下限约束时，工件Ji在阶段间的等待时间wij被限制为[βij，∞）。当所有工件在各阶段间的等待时间下限均为0时，具有等待时间下限的调度问题转化为一般调度问题。等待时间下限约束多见于阶段间存在工件运输的情况。此外，在对产品的物理属性有特殊要求的生产流程中，工件在开始某阶段的加工之前需要等待一定的时间，使其达到规定的温度或发生凝结或沉淀。
等待时间上限约束（Maximum Waiting Time Constraints）限定了工件在阶段间的最大等待时间。定义αij（αij≥0）为工件Ji在相邻阶段Mj和Mj+1间的等待时间上限，在此约束下，工件Ji所允许的等待时间范围为wij∈[0，αij]。若∀i，j均有αij=0，则等待时间的限制范围为wij=0，即为无等待（No-wait）约束；反之，若∀i，j有αij→∞，具有等待时间上限的调度问题，即为一般调度问题。等待时间上限约束普遍存在于高温连续或中间产品性质不稳定的生产过程。例如，在食品加工中，等待时间不允许超过一定的上限，否则食物将会腐烂而不能食用；在晶圆的加工过程中，当一片晶圆在一个加工模块中完成加工以后，必须在规定的时间内将其取出。
等待时间上下限约束（Minimum and Maximum Waiting Time Constraints）将工件在相邻阶段的等待时间限制在一定的区间范围，即同时具有等待时间上限和下限约束。此时，工件Ji许可的等待时间为wij∈[βij，αij]。等待时间上限约束和等待时间下限约束是这类约束的两种特殊情况，若∀i，j有βij=0，则为等待时间上限约束；反之，若∀i，j有αij→∞，则相当于等待时间下限约束。对等待时间上下限的限制经常存在于一些复杂的生产流程，例如，钢铁生产中钢水在相邻阶段间只允许等待较短时间，且要满足运输时间的要求；抓钩调度问题要求工件在处理槽中的处理时间必须在上下限范围。
（2）时间间隔受限
时间间隔受限（Time Lag Constraints）多存在于工件间具有优先约束或机器有空闲时间约束的调度环境。由于产品特点或工艺要求，两个位于同一生产阶段且要求先后加工的工件，其时间间隔具有硬性要求，即在前一工件开工或完工后的一个上限或下限范围，下一个工件必须开工或完工。时间间隔约束广泛存在于具有资源约束的项目调度（Resource Constrained Project Scheduling）及化工生产。对于存在化学工艺的生产系统，化学反应时间是具有上下限的，而处理时间（如试液移取、实验结果分析等）则为定值。因此，在化工生产调度中，往往将后者视为工件，而化学反应过程则被抽象为具有上下限的时间间隔约束[66]。
机器空闲时间约束（Idle Time Constraint）是一类特殊的时间间隔受限约束。机器空闲时间约束的典型特例是工件组批的批调度约束，即机器在加工不同规格的工件时存在安装时间，因而需要将工件分批连续加工，其位于同批次内的相邻工件间的机器空闲时间为零或有较紧的上限要求，相邻批次的首尾工件间存在机器安装时间，即机器空闲时间存在下限约束。
（3）问题分类总结
等待时间受限多见于具有多工序的车间环境，对应的调度问题为等待时间受限的流水车间、作业车间、混合流水车间调度问题等；时间间隔受限则是针对某一特定生产阶段，由于时间间隔约束的作用，该阶段往往会遇到生产瓶颈，对应的调度问题通常可抽象为时间间隔受限的单机或平行机调度问题，进而扩展到面向整体生产流程的车间调度问题，如图1-2所示。对于中间产品性质不稳定、高温连续作业、生产过程连续性强的流程工业而言，特殊的工艺要求会导致对上限要求颇为严苛的等待时间和（或）时间间隔约束，且会遇到生产瓶颈，例如，钢铁生产的炼钢—连铸工艺、加热炉—热轧工艺等。
图1-2 紧凑调度的分类与分析
1.3.3 问题研究现状
传统的紧凑调度由Werra和Solot于1991年正式提出[67]，要求同时满足无等待（No-wait）和无空闲（No-idle）约束，研究集中在流水车间和开放车间环境，且多采用图论的方法来解决。Werra和Solot[67]将紧凑调度问题映射为边着色模型（Edge Coloring Model），并给出了这一问题的工业应用场景。此后，Giaro及其团队对紧凑调度展开了一系列研究。在问题复杂性方面，Giaro[54]证明了在两阶段的流水车间和开放车间环境下，紧凑调度问题是“强NP-难”的。针对工件在各阶段的加工时间非0即1的特殊情况，Giaro等[53]指出开放车间下的该问题等价于二分图的连续边着色问题，并对一个特殊问题给出了多项式最优算法；Giaro和Kubale[55]考虑了开放车间、流水车间和混合车间，将其映射为二分图的连续边着色问题，证明了其“强NP-难”的复杂性。此外，Wang等[68]考虑了无等待的两阶段混合流水车间调度问题，其中，第二阶段存在无空闲约束，证明了问题是“强NP-难”的，并提出了一种修正的LPT调度规则，分析了该规则的最坏性能比。
紧凑调度在实际生产中出现的情景较少，因此，研究成果不多。我们将紧凑调度的无等待和无空闲约束分别松弛为等待时间受限和时间间隔受限，得到的扩展问题在钢铁生产、食品加工、半导体制造等制造工业普遍存在。但基于生产实际的紧凑调度研究成果不具有普适性和推广性，仅对存在相似特征的生产调度问题起到指导作用。关于紧凑调度的理论研究，可以借鉴等待时间受限或时间间隔受限的调度理论成果。
对于等待时间受限的紧凑调度问题，由于此问题为本课题研究对象，相关研究成果将在1.4节重点分析，这里只对时间间隔受限的紧凑调度问题研究现状进行综述。
具有时间间隔约束的调度问题多存在于工件间具有优先约束关系的调度环境。由于产品特点或工艺要求，对于两个需要先后加工的工件，其间隔时间有硬性的要求，即在前一个工件开工或完工后的一个上下限范围，下一个工件必须开工或完工。根据受限的时间变量类型，可以分为开工时间间隔约束、完工时间间隔约束、完工—开工时间间隔约束、开工—完工时间间隔约束。显然，对于加工时间为定值的调度问题，这四类约束可以相互转化。在下文中若不作特殊说明，则时间间隔约束是指对完工—开工时间间隔的限制。
时间间隔约束往往与工件加工的优先约束或机器空闲时间约束有关，目前的研究集中在项目管理[69，70]，在生产调度领域则集中于单机调度方面。
（1）具有时间间隔下限的单机调度问题
Balas等[71]从求解作业车间调度问题的移动瓶颈法抽象出具有工件间的间隔下限的单机调度问题，提出了一种求解算法并将其嵌入移动瓶颈法。Finta和Liu[72]对于具有工件优先约束和时间间隔下限的单机调度问题，指出加工时间为单位时间且时间间隔下限不等时，该问题是“强NP-难”的；当下限值相同但加工时间不同时，该问题是多项式可解的。Brucker和Knust[73]研究了时间间隔下限相同的单机调度问题的复杂性，提出了流水车间和平行机调度转化为此类单机调度问题的方法，并针对最小化总完工时间的目标函数，给出了几类特殊的单机调度问题的多项式最优算法，对于具有链（Chain）约束且下限相同的情况，证明了问题的“强NP-难”复杂性。
（2）具有时间间隔上下限的单机调度问题
Wikum等[74]针对具有优先约束且设定时间间隔上下限的单机调度问题，分析了问题复杂性；对于一些简单的优先约束，给出了多项式算法；对于具有复杂结构的问题，证明了“NP-难”特性，并针对其中一类问题给出了启发式算法和最坏性能比。Chu和Proth[66]以自动化医学实验室为背景，将其抽象为工件间具有平行链约束且时间间隔具有上下限的单机调度问题，证明了该问题是“NP-难”的，提出了启发式算法和分支定界法。Brucker等[75]研究了开工时间间隔具有上下限约束的单机调度问题，指出如车间调度、具有机器资格限制的平行机调度、多功能机调度，以及具有更换时间（Changeover Time）的调度问题均可以归结为这类单机调度问题，并设计了分支定界法求解；Hurink和Keuchel[76]针对这类问题，提出了利用邻域搜索算法来求得问题的解。
对于工件间不存在优先约束的调度问题，Sheen和Liao[77]研究了每个工件对于其他任一工件的时间间隔上下限为已知定值的情况，在求解过程中引入团（Clique）的概念，设计了分支定界方法。Condotta等[78]针对一类特殊情况，即双操作工件加工环境下要求同工件的两个操作间的间隔时间满足定值的单机调度问题展开研究，在给出两种求解策略的基础上设计了禁忌搜索算法求解。
（3）机器空闲约束的流水车间调度问题
机器空闲约束作为一类特殊的时间间隔受限约束，目前对于无空闲的流水车间调度问题的研究成果较多，Goncharov和Sevastyanov[79]对其研究现状进行了详尽的综述，并提出了多种近优启发式算法。已有研究指出，无空闲的流水车间调度问题，当优化目标为Makespan，且阶段数不少于3时，问题是“强NP-难”的[79]。
由上述成果可以看出，由于时间间隔受限的紧凑调度问题的“NP-难”特性，现有求解算法多集中于分支定界这类精确算法，在近似算法领域，则主要采用构造启发式算法。原因是启发式算法能够有效利用问题的领域知识实现快速求解，在计算时间上具有精确算法和智能搜索算法无法比拟的优势，且结合问题特征的启发式算法能够为智能搜索算法提供良好的初始解，并指导算法的优化搜索方向。对于本课题“等待时间受限的紧凑型流水车间调度”的近似算法研究，同样有必要从启发式算法入手，探讨能够指导算法设计的问题特征并设计高效的多项式近似算法；在对问题特征和启发式算法深入研究的基础上，进一步开展对智能搜索方法的研究。