![](https://csdnimg.cn/release/download_crawler_static/85068907/bg3.jpg)
3
一作业加工结束后一作业立即开工。TWETV‐shape 特征
具体来看,第二步的步骤如下:
Step1: 初始化参数,各个作业的
j
、
j
d
、
j
、
j
,当前指定的排序集合 S,调度方案
,
调度方案
为二维数组,一行代表一个作业的加工过程,具体包括作业编号、开工时间和完
工时间,单机最后一个作业任务完工时间 F 初始化为 0。
Step2:令 k=1,j 为排序 S 中第 k 个位置的作业编号,生成作业 j 的具体调度方案并进行前
序作业的开工时间优化
Step2.1: 将作业 j 放到调度方案
的最后,其中开工时间
j
st
为 F 和
jj
dp
两者之间的最小
值,完工时间
jjj
ct st p
,如此处理是保证作业 j 的完工时间要不等于其交付时间,实现
最小的提前和拖期成本(如下图 a 所示);要不是因为机器对前 k‐1 个作业加工完工时间比
较拖后,使得当前作业 j 无法准时完工,即该作业将存在延误(如下图 b 所示)。如果是图
(a)的状态,当前作业调度方案不会影响前面的调度方案目标函数值,执行 Step2.3;如果
是图(b)的状态,执行 Step2.2。
(a) 空闲区域足够
(b)空闲区域不足
图 1 新增作业构建调度方案的两种结果形式
Step2.2 判断和优化调度任务块的开工时间。本步骤是在新任务调度方案生成后整体调度方
案出现了图(b)所示状况下的优化操作。在图(b)状态下,由于是迭代操作,可知在作业
4 加入整个调度方案之前,作业 1、2、3 的调度方案是具有最优目标函数的,即三个作业的
最小提前和拖后成本和。作业 4 加入到现有调度方案形成了图(b)的状态,整个目标函数
增加了
jj j
cd
的延误成本,如果作业 4 继续向右移动,即其开工时间继续增加,这个
延误成本将继续增加,因此以降低延误成本为目标的优化方向是将整个 2、3、4 调度块整体
向左移动。一个调度任务块的提前和延误成本和同其开工时间之间的关系呈现 V 型关系,
所以必然能够找到一个使得 ET 成本最低的开工时间。这个开工时间可能大于作业 1 的完工
时间,也可能小于作业 1 的开工时间。如果大于等于作业 1 的完工时间,则该作业块前移一
定时长后将获得最小目标函数值;如果小于作业 1 的完工时间,则将作业 1 同作业 2、3、4