一种具有模糊交货期的单机调度问题

2024-10-13

一种具有模糊交货期的单机调度问题（共2篇）

一种具有模糊交货期的单机调度问题篇1

一种具有模糊交货期的单机调度问题

研究了一种具有模糊交货期的.最小化全部满意度的单机调度问题.机器能力限制要求在任何时间至多加工一个工件,且在工件加工之间无空闲时间.考虑了一种梯形隶属度函数并推广为非线性情形.该问题清晰化后可利用动态规划状态空间松弛来求解.

作者：吴会江 Wu Huijiang 作者单位：沈阳工程学院基础部,沈阳,110036;东北大学信息科学与工程学院,沈阳,110004刊名：科学技术与工程 ISTIC英文刊名：SCIENCE TECHNOLOGY AND ENGINEERING年，卷(期)：5(9)分类号：O229 TP29关键词：模糊交货期隶属度函数单机调度动态规划状态空间松弛

一种具有模糊交货期的单机调度问题篇2

调度问题是NP难解问题[1], 在工业、管理等领域有着重要的实际应用价值。本文就具有交货时间的单机作业调度问题[2]给出精确算法, 求得问题的最优解。

1问题描述

有n个作业J1, J2, …, Jn, 需要在一台机器上处理, 任何一个作业Jj (1≤j≤n) 一旦获得机器, 便一直占有机器, 直至处理完成, 机器在处理作业Jj期间不能被中断。每个作业Jj在机器上处理后, 还需要qj≥0的时间用于“交货”。“交货”可以理解为在一台没有瓶颈的机器 (能够同时处理任意数量作业的机器) 上附加的处理, 或者是传送时间, 不同作业的“交货”在时间上可以重叠。

分别用sj, pj和qj表示作业Jj的开始时间, 处理时间和交货时间, 定义作业Jj的延迟时间为Lj=sj+pj+qj。显然, s1=0, sj= $\sum_{i = 1}^{j - 1} p_{i}$ , 因此,

$L_{j} = s_{j} + p_{j} + q_{j} = \sum_{i = 1}^{j - 1} p_{i} + p_{j} + q_{j} = \sum_{i = 1}^{j} p_{i} + q_{j} (1)$

定义单机作业调度问题的最大延迟为

$L_{\max} = \max_{1 \leq j \leq n} L_{j} (2)$

最优调度的Lmax记为L*max, 定义为

L*max=minLmax (3)

n个作业的调度方案共有n!种组合, 其解空间树称为排列树。为了寻找最优调度的L*max, 必须系统地搜索排列树的n!个叶结点。

2回溯算法

下面给出的Find_Min () 函数采用回溯算法[3], 系统地搜索排列树, 计算最优解L*max。

Find_Max () 函数计算当前调度方案的最大延迟Lmax。通过观察试验结果, 发现Find_Min () 函数在搜索解空间过程中, 存在约70%的重复计算, 见表1。

通过分析试验结果和Find_Min () 函数代码, 发现for循环语句第一次执行循环体时, 得到的作业调度方案是重复的。给Find_Min () 函数增加一个形式参数is_repeated, 该参数为真表明当前调度方案是重复的;否则, 计算当前方案。改进后的函数代码如下所示。

Find_Min () 函数对排列树进行系统搜索, 因此它的时间复杂性是O (n!) 。

3改进的算法

对于以上具有交货时间的单机作业调度问题, 下面的定理给出另一种解题算法, 能够将时间复杂性降为O (nlgn) 。

定理:将n个作业按其交货时间降序排序, 按照这个顺序调度作业, 其Lmax就是最优解L*max。

证明:设J1, J2, …, Jn是任意给定的作业调度次序∑, 一定存在作业Jj和Jk, 满足:作业Jj在作业Jk之前处理, 且qj≥qj+1≥…≥qk-1, 但是qj<qk。

设作业Jj的开始时间为t0, 则根据公式 (1) 作业Jk的延迟为:

$L_{k} = t_{0} + \sum_{i = j}^{k} p_{i} + q_{k} (4)$

显然, 在Li (i=j, j+1, …, k-1, k) 中, Lk是最大的。

将作业Jj和Jk交换调度次序, 得到一个新的调度次序∑′:J1, J2, …, Jj-1Jk, Jj+1, …Jk-1Jj, Jk+1, , Jn。在∑′中, 作业Jk和Jj的延迟为:

L′k=t0+pk+qk (5)

$L^{'}_{j} = t_{0} + \sum_{i = j}^{k} p_{i} + q_{j} (6)$

显然, 在L′i (i=j, j+1, …, k-1, k) 中, L′j或者L′k是其中的最大者。根据公式 (4) , (5) 和 (6) , 有Lk>L′j, 同时Lk>L′k。对于作业Ji (i=1, …, j-1和i=k+1, …, n) , 根据公式 (1) 可知, 在调度∑和∑′中, 其延迟没有发生变化。这说明在调度∑′中, 没有增加最大延迟。将以上这个交换过程不断地重复下去, 直到作业的调度顺序已经按交货时间降序排序为止。这个调度次序就是最优调度, 其Lmax就是L*max。