3.1 单机逆调度问题

3.1.1 加权完成时间和最小的单机逆调度问题描述

1.SMISP描述

在生产调度研究领域，单机调度问题（Single Machine Scheduling Problem）是一个基本问题，并且已有许多研究成果。单机调度是多数调度问题的特例，通过对此问题的研究，可以给其他复杂调度问题提供参考，指导其他调度问题的深入研究。在实际生产中，根据分解特性，将复杂调度问题进行分解。根据排列组合知识可知，系统中 n 个工件加工次序的全排列为 n ！，当 n =20时， n ！≈2.4×10 ¹⁸ ，很显然，该问题的计算量相当大。由此可见，当 n 大到某一程度时，此问题可以看作NP-hard问题，用传统的精确算法已无法解决，需要寻求更加高效的方法。

以往关于单机调度问题研究较多的是静态调度情形，其对实际生产情况做了较多简化，通常假设工件的加工信息在调度之前已知且确定。对于这样的单机调度问题，其最大完工时间指标其实是一个定值，等于所有工件的加工时间之和；针对加权完工时间和的单机调度问题，依据WSPT（Weighted Shortest Processing Time）规则可进行求解，但如果要考虑实际生产情况下的车间调度，常常根据已知的加工信息预先生成一个调度方案，该调度方案往往由于车间状态的变化而失去最优性，有时甚至变为不可行。以往的解决思路是利用重调度或其他调度方法，但是调度功能往往受到工艺加工计划和制造资源的双重制约，在此情况下，调度顺序一旦生成不能轻易调整，即使调整也只能微调。因此如何调整相关参数既能保证方案满足期望，又使得相关成本最低或方案改变最小成为亟须解决的问题，这也是单机逆调度（Single Machine Inverse Scheduling Problem，SMISP）研究的本质。

2.SMISP问题的数学模型

基于以上理论背景，本章主要研究单机环境下带有可控加工参数的车间逆调度问题，通过调整加工时间使得原调度变得最优，并且考虑以加权完工时间和最小为目标。该问题可以描述如下：

某生产车间有一台机器和 n 个待加工工件，每个工件随机到达该机器进行依次加工。工件具有多个性能参数，如加工时间、工件权重、交货期等。加工前可以预先估计各参数，根据当前已知的加工信息预先生成一个调度方案，并且加工参数可以在合理范围内调整，该调度方案往往由于车间状态的变化而失去最优性，通过调整相关参数既保证方案满足期望，又使得相关成本最低或方案改变最小。目前依据性能指标可将其分为两类：基于调度性能和基于调度成本指标。本章进行加权完工时间和最小的单机逆调度问题研究。为了更好地描述该问题的数学模型，条件假设如下：

（1）工件在该台机器上加工时不能被其他工件抢占；

（2）该机器同一时刻至多加工一个工件；

（3）该台机器一直可用，并且在0时刻机器处于空闲状态；

（4）该台机器前有无限缓存区；

（5）工件之间没有加工次序约束；

（6）工件完工后立即被运走；

（7）工件准备时间已作为其加工时间的一部分；

（8）工件的加工参数在一定范围内可控。

根据以上假设，在建立模型之前还需对一些参数进行说明。首先本章以最小化加权完成时间和为目标，建立单机逆调度问题模型，在该问题中，相关参数被分成两个部分，分别是初始加工时间 p _j 、工件权重 w _j 、工件完工时间 c _j ，以及调整后加工时间 、工件权重 、工件完工时间 。固定 w _j ，调整 p _j ，使得原始工件排序 π 在工件加工时间 下最优。对于这种情况，每个工件的加工时间 p _j 都有一个变化区间 ，且 调整后的加工时间为 ，要求最小地调整 p _j ，使得给定的排序 π 最优， Z 为最小化参数改变量。

下面针对这第一种情况给出相应的数学模型：

目标：

约束：

约束条件（3.2）保证预先生成的调度方案 π 在调整后的加工时间 下最优；约束条件（3.3）保证调整后的目标值（加权完成时间和）小于原目标值，本章介绍以最小化加权完成时间和为目标的单机逆调度问题，因此希望该目标值通过逆调度调整之后不比原目标值大；约束条件（3.4）表示所有工件的加工时间应该大于或等于0。

3.1.2 带交货期的单机逆调度问题描述

基于以上理论背景，本章研究单机环境下带交货期的车间逆调度问题，通过调整交货期使得原先调度变得最优，并且考虑以最小化最大拖期的问题为研究背景。该问题可以描述如下：

某生产车间有一台机器和 n 个待加工工件。每个工件随机到达该机器进行顺序加工。工件具有多个性能参数，如加工时间、工件权重、交货期等。加工前交货期可以与客户沟通预先得到，根据此参数信息预先生成一个调度方案，并且可以在合理范围内调整，该调度方案往往由于车间状态的变化而失去最优性，通过调整相关参数既可以保证方案满足期望，又使得相关成本最低或方案改变最小。为了更清晰地描述该问题的数学模型，条件假设如下：

（1）从0时刻起，所有工件都是可行的；

（2）机器在同一时刻只能加工一个工件；

（3）从0时刻开始，机器就是可用的，并且是连续使用的；

（4）不同工件之间不存在优先约束；

（5）每个工件的交货期和加工时间都是已知的；

（6）工件的加工时间是不变的，交货期在给定的随机均匀区间取值；

（7）工件的加工顺序是不变的，且此加工顺序非最优。

基于上面的假设，建立数学模型之前需要对一些符号做以下定义和说明：

n ：工件的数量。

J _i ：第 i 个工件。

p _i ：第 i 个工件的加工时间。

d _i ：第 i 个工件的交货期。

σ ：一个可行排序，而非最优排序。

C _i ：工件 i 的完工时间。

：工件 i 调整后的交货期。

L _max ：最大拖期时间。

：改变 d _i 后的最大拖期时间。

1|| L _max ：以最大拖期最小为目标的单机调度问题。

最大拖期最小的单机逆调度问题的一般描述如下：

给定一台机器， n 个工件分别为 J ₁ ， J ₂ ，…， J _n ，工件相应的加工时间为 p _i （ i =1，2，…， n ），交货期为 d _i （ i =1，2，…， n ），并给定可行排序 σ =（1，2，…， n ），调整交货期 d _i 为 ，使得可行排序 σ 在新的交货期下成为最优排序，同时使交货期的调整量 最小。

在调度问题中，对于1|| L _max 问题，最优解满足EDD（Earliest Due Date，最早交货期）规则：将所有已经到达并等待加工的工件按照交货期的升序排序加工。该规则基于交货期的调度规则，经常作为最小化拖期调度问题的比较基准。数学表达式为 d ₁ ≤ d ₂ ≤…≤ d _n 。在具体的模型中会使用该规则。

通过上述问题描述，可得出带交货期的单机逆调度问题数学模型如下：

目标：

约束：

其中：

目标（3.5）表示交货期 d _i 的调整总量最小；约束（3.6）保证了调整后的交货期 满足EDD规则；约束（3.7）保证了目标值 L _max 调整后优于调整前；约束（3.8）、（3.9）、（3.10）保证了该问题的参数 d _i 、 p _i 、 均大于0；式（3.13）表示在距离 L ₁ 下的值。 xC1SDVuMxDEoiZvZ1oaYIjrPw6GYiRxYdkLlQGYWdOY/FpHc3deig610W8B1YB1/