下载掌阅APP，畅读海量书库
立即打开
1.SMISP描述
在生产调度研究领域，单机调度问题（Single Machine Scheduling Problem）是一个基本问题，并且已有许多研究成果。单机调度是多数调度问题的特例，通过对此问题的研究，可以给其他复杂调度问题提供参考，指导其他调度问题的深入研究。在实际生产中，根据分解特性，将复杂调度问题进行分解。根据排列组合知识可知，系统中 n 个工件加工次序的全排列为 n ！，当 n =20时， n ！≈2.4×10 18 ，很显然，该问题的计算量相当大。由此可见，当 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。
基于以上理论背景，本章研究单机环境下带交货期的车间逆调度问题，通过调整交货期使得原先调度变得最优，并且考虑以最小化最大拖期的问题为研究背景。该问题可以描述如下：
某生产车间有一台机器和 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
1
，
J
2
，…，
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 1 ≤ d 2 ≤…≤ 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
1
下的值。