经典车间调度问题中的工件加工时间通常被认为是固定且离散的量，传统车间调度问题可被看成加工时间可控的车间调度问题的特例［26］，所以加工时间可控的车间调度问题仍然是NP难问题。显然，加工时间可控的车间调度问题也是一类复杂的多目标组合优化问题。目前，较少学者研究加工时间可控的流水车间和柔性作业车间调度问题。如何建立相关数学模型并设计出高效可行的优化方法是当前学者需要研究的一个重要方向。因此，研究加工时间可控的车间调度问题具有十分重要的实际应用价值与理论意义。

本书的主要研究内容包括加工时间可控的单机、并行机、流水车间、作业车间和柔性作业车间多目标调度问题模型的建立及其智能优化算法的设计。下面对这5类车间调度问题进行综述与分析。

1.加工时间可控的单机调度问题

由于加工时间可控的调度问题具有高度复杂性，因此目前大多数加工时间可控条件下的调度问题研究主要集中在单机环境下。Vickson［27］是最早研究加工时间可控调度问题的学者之一，他主要研究了单机环境下的总流程时间和由压缩加工时间引起的总压缩成本的权重和最小的问题，并设计了一种启发式算法来优化该类小规模调度问题。Nowicki和Zdrzałka［28］就加工时间可控排序问题给出了直到1990年的研究综述。随后，Shabtay和Steainer［29］对2007年前的加工时间可控调度问题的研究进行了全面回顾和总结。Panwalkar和Rajagopalan［30］考虑了工件具有共同交货期的静态单机排序的小规模问题，其中工件的加工时间是可控的，即压缩时间量与成本成线性关系，优化目标是最小化提前-延迟成本以及加工成本之和。Zdrzałka［31］研究了小规模的单机调度问题，该问题中的每个工件都有一个释放时间、传输时间以及与成本相关的可控加工时间，并提出了一种近似优化算法来求解该问题使总生产成本目标最小化。Chen等［32］考虑了一个单机调度问题，在这个问题中，工件加工时间和释放时间都是在指定范围内可控变化的，并分别优化了最大完工时间和总权重延迟时间等目标。Biskup和Cheng［33］研究了加工时间可控的单机提前-拖期调度问题，在该模型中，压缩时间是关于成本的线性函数。他们的目标是寻找一组最优的工件排序、交货期和加工时间，使其与提前-拖期、完成时间及压缩成本相关的总成本值最小。Kayan和Aktürk［34］确定了一个单机数控机床双目标调度问题在加工时间可控条件下每个工件加工时间的上下界。Cheng等［35］考虑了加工时间和释放时间均可控的小规模单机调度问题。他们提出了一种O（n2）算法来求解该问题，使目标最大完工时间和总压缩成本之和最小。Atan和Aktürk［36］研究了加工时间可控的单机数控机床调度问题，其目标是最大化总利润。该利润为已完成调度的工件带来的税收减去带权重的总提前-拖期之和、加工工具以及机床成本。除此之外，他们还提出了一系列的调度规则和调度算法并将其引入一种四阶段的启发式算法中，同时对每个工件的加工时间与可行的调度方案进行了求解，以此获得最大化的整体利润。Tseng等［37］研究了加工时间可控的单机调度问题，该问题的目标是最小化总延迟时间和压缩成本加权之和。他们设计出了该问题的两种线性规划数学模型，并提出了一种净压缩收益（net benefit of compression，NBC）算法对该小规模车间调度问题进行求解。Kayvanfar等［38，39］延续了Tseng等人的工作，并设计了一种净压缩和净扩展收益（net benefit compression-net benefit expansion，NBC-NBE）算法来求解该类问题。Yin和Wang［40］采用了启发式算法来求解加工时间可控和带有学习效应的单机调度问题。该问题的目标是最小化与最大完工时间、总完工时间及完工时间的绝对差异等相关的成本函数。Xu等［41］提出一种多项式时间O（n2）算法用来求解这类调度问题，使其总延迟时间最小。Yin等［42］求解了具有共同交货期与加工时间可控的单机批量调度问题。他们提出了一种O（n5）动态规划算法和O（n log n）算法来寻找最优解使得成本最小。Nearchou［43］对加工时间可控单机调度问题进行了研究，并将总加权完工时间与压缩成本之和最小化作为目标函数。很多基于种群的元启发式算法也被应用到了这类问题的处理之中。Giglio［44］考虑了一类具有机器行为不可靠、加工时间可控、考虑序列相关的准备时间以及交货期等特点的单机调度问题。该问题的目标是最小化加权拖期和、加权消耗成本及准备成本。他提出了一种动态编程的方法来对此问题进行求解。Zhou和Peng［45］研究了一类具有非负库存约束和离散可控加工时间的单机调度问题，建立了求解不同尺度问题的精确算法和混合元启发式算法。王杜娟等［46］研究了恶化效应下加工时间可控的新工件到达的单机小规模调度问题。减少加工成本和时间扰动为该问题的两个目标。王磊和张玉忠［47］研究了加工时间可控的单机分批调度问题，提出了相应的多项式时间最优算法来分别求解以最小化最大完工时间、总完工时间与加工时间可控所需费用总和最小为优化目标的问题。但研究的问题依然是小规模调度问题。赵玉芳等［48］研究了带有学习效应、恶化效应和资源分配的单机工期分配问题，针对CON、SLK、DIF三种不同工期分配问题中的每一种，均提出相应的多项式时间内的最优算法，通过将其转换为指派问题，证明这些问题都是多项式时间可解的。

从现有的相关研究可知，加工时间可控的单机调度问题主要集中在单目标、小规模调度问题领域，工件加工时间可控环境下的多目标、大规模调度问题尚未见到研究。为此，本书针对这一问题展开了研究。

2.加工时间可控的并行机调度问题

相比单机调度问题，多机环境下的相关调度问题的研究成果目前尚不多，且主要集中在并行机调度问题上。例如，Nowicki和Zdrzałka［49］考虑了一种双目标优化方法来求解m台并行机预调度问题，其中工件加工成本是可变加工时间的线性函数。在不相关并行机环境下，Alidaee和Ahmadian［50］专门研究了该类具有线性压缩成本函数的调度问题，其目标是最小化总压缩成本和总流程时间或者最小化总压缩成本和提前-延迟惩罚权重和。他们将这类问题当作传输问题来求解。Cheng等［51］研究了不相关并行机调度问题，其中加工时间可通过花费额外成本来进行压缩，且成本是压缩量的一个凸函数；此外，他们还假设交货期是无穷大的。Jansen和Mastrolilli［52］研究了在相同并行机环境下的加工时间可控调度问题，工件加工时间可以被压缩但需要额外的压缩成本。Chen［53］研究了带工件加工与资源分配的并行机调度问题，该问题的目标是最小化由指标性能成本和资源分配成本构成的总成本。Grigoriev等［54］考虑了不相关并行机调度问题，其中工件加工时间依赖于离散可再生资源的使用量。他们采用了一种线性规划方法将资源分配到工件上，同时也将工件分配到机器上，使目标最大完工时间最小。Grigoriev和Uetz［55］考虑了这样的一类调度问题，n个工件在一组m台可选机器上进行加工，工件的加工时间依赖离散可再生资源的使用量。此类问题的目标是找到最优资源分配和对应的可行调度方案使最大完工时间最小。Gürel和Aktürk［56］考虑一台相同并行机的可控加工时间的数控机床，就时间和成本之间的权衡问题进行了研究。Gürel等［57］考虑了加工时间可通过一定的压缩成本来控制，并采用一种可预测的方法来产生一个初始调度方案，以便使有限的生产资源可被充分利用。Turkcan等［58］研究了加工时间可控的并行机数控机床问题，其目标是最小化制造成本与总提前-延迟权重之和。他们假设零件具有提前-延迟惩罚量和不同的交货期；此外，他们还考虑了机器所允许的闲置时间大小对加工时间的影响，但却没有考虑由此释放加工时间所导致的成本变化。Aktürk等［59］研究了不相关并行机调度问题，其中工件加工时间只有在付出一定的制造成本时才能进行压缩且制造成本是压缩时间的一个凸函数。他们引入了替换匹配调度问题来找出时间和成本之间的折中解。Leyvand等［60］研究了加工时间可控的并行机调度问题，其优化目标是最大化工件在交货期范围内完工的数量和最小化资源分配总成本。Li等［61］等考虑了加工时间可控的相同并行机调度问题，目标是最小化总完工时间，该问题中的加工时间是消耗资源量的线性递减函数。Kayvanfar等［5］研究了加工时间可控的不相关并行机调度问题，其目标是最小化提前-延迟与压缩成本的总和。Hsieh等［62］考虑了带离散可控加工时间的不相关并行机调度问题，该问题的目标是最小化标准指标成本与总加工成本之和。Guo等［63］考虑了无关并行机调度问题，以总机器负荷和总控制成本的加权和最小为目标，提出了一种求解该问题的优化算法，给出了相应的数值例子来说明这个问题。徐开亮［26］研究了加工时间可控的并行机调度问题，并设计了高效的禁忌搜索算法用于该问题的求解。

从以上文献综述可知，当前加工时间可控的并行机调度问题研究主要集中在单目标、小规模并行机调度问题领域，工件加工时间可控的多目标并行机调度问题尚未见到相关研究。因此，本书针对该类问题展开了深入研究。(www.daowen.com)

3.加工时间可控的流水车间调度问题

加工时间可控的流水车间调度问题的研究目前较少，同时，采用的优化方法依然是基于先验知识的处理机制。例如，Mokhtari等［64］提出了一种离散差分进化（discrete differential evolutionary，DDE）算法与变邻域搜索（variable neighborhood search，VNS）相结合的方法来优化加工时间可控的置换流水车间调度问题。他们将最大完工时间和总资源成本同时作为优化目标，并对这两个目标设置不同的权重值来获取这两个目标的折中解，但是这类处理多目标优化问题的方法本质上是权重和方法。该方法虽然操作简单，但是需要通过多次运算获取非支配解，且获得的非支配解集的质量一般较差。Shabtay等［65］提出了一种适用于准时化（just in time，JIT）流水车间调度系统的伪多项式时间算法，在该算法中，加工时间可以通过资源分配来控制。但是他们只考虑了两台机器环境下的流水车间调度问题，这与很多实际生产中大规模制造环境仍有一定的差距。Behnamian和Fatemi Ghomi［66］提出了一种基于遗传算法（GA）和可变邻域搜索（VNS）算法的混合方法，用于处理时间依赖于资源的混合流水车间调度问题（HFSP）。他们采用了线性加权和的方法使最大完工时间和总资源分配成本之和最小。Jiang等［67］采用了一种双层优化方法来求解混合流水车间调度问题。在该问题中，某些阶段的加工时间是可控的，然而他们采用了线性加权和的方法来处理该多目标调度问题，这些目标包括等待时间、准时化目标和调整目标。Yu等［68］研究了两台机器上具有学习效应和资源分配的无等待流水车间调度问题，在总加权资源消耗（调度准则）小于或等于给定常数的约束下，找到最小化总加权资源消耗的最优资源分配和作业序列，其中调度准则包括加权完工时间、总完成（等待）时间和完成（等待）时间的总绝对差值。针对加工时间可控的混合流水车间调度问题，Mokhtari等［69］提出了混合离散差分进化（HDDE）和可变邻域搜索（VNS）算法，以解决加工时间依赖于资源的多目标流水车间调度问题。Mokhtari等［70］设计了一种两阶段遗传算法（GA），用于求解加工时间可控的无等待流水车间调度问题。Missbauer等［71］只讨论了铸造阶段涉及加工时间可控的炼钢连铸调度问题，提出了一个数学规划模型，没有计算结果。谭圆圆等［72］以炼钢连铸为实际生产背景，研究加工时间可控的两阶段流水车间多目标调度问题。他们采用了加权的方法将多目标问题转化为单目标问题。

从以上文献综述可看出，大多数研究主要采用了线性加权和方法将多目标优化问题转化为单目标问题（single-objective problem，SOP）后再进行求解。但是这类方法不仅需要运行多次才能获得不太理想的非支配解，而且会掩盖目标之间潜在的折中（trade-off）关系。针对这一问题，本书提出了基于Pareto的多目标进化算法并对相关调度问题展开了深入研究。

4.加工时间可控的作业车间调度问题

目前对加工时间可控的作业车间调度问题的研究较少，所采用的方法也都集中于数学模型优化方面。例如，Aktürk和Ilhan［73］提出了一种数控机床切削力控制方法。由于刀具磨损，加工时间取决于切削力。所提出的方法应用于一台铣床中心（只有一台机器），结果表明，该方法对不确定数控机床是有效的。Niu等［74］提出了一种基于搜索的元启发式算法求解考虑了加工时间离散可控的作业车间调度问题，但是在制造系统中进行测试时没有研究异常和动态事件。Aschauer等［75］将加工时间可控的作业车间调度问题分解成时间表和排序两个子问题来求解，提出了新的方法，优化了最大完工时间。Gao等［76］提出了两个数学模型，用来解决具有交货期和分包成本约束的无等待作业车间调度问题，一个是集成的混合整数线性规划（MILP-IS）模型，另一个是滚动时间线的混合整数线性规划（MILP-RTL）模型；同时，根据滚动时间线的思想进行加工时间的控制，提出了一种基于滚动时间线的人工蜂群算法（RTL-ABC）。

5.加工时间可控的柔性作业车间调度问题

针对加工时间可控的柔性作业车间调度问题，目前相关研究较少。少数研究工作还是集中在加工时间可控的作业车间调度问题上。例如，Niu等［77］建立了一个基于析取图的离散加工时间的作业车间调度问题模型。他们采用了一种三阶段的分解式方法来求解这个调度问题，将该问题看成两个子问题，即作业车间调度问题和一系列的离散时间成本权衡问题，并分别进行求解。孟磊磊等［78］研究了考虑关机/重启节能策略和加工时间可控的柔性作业车间调度问题（FJSP），提出了两个考虑关机/重启节能策略的混合整数线性规划（MILP）模型，并使用CPLEX求解器对20组测试实例进行了求解。