论文部分内容阅读
传统的生产调度问题通常假定作业的准备时间和加工时间等参数在调度的过程中是不变的,然而在冶金、化工等一些高耗能领域,它们的取值可能与作业消耗的能源量有关并影响调度结果。因此,对于这些领域中关键生产环节上的关键机器调度问题,在提高其生产效率的同时也应尽量优化其用能效率,从而达到节能降耗的目的。作为受能耗约束调度问题的研究基础,本文首先研究了无能耗约束的多个关键机器调度问题,然后研究了三类考虑节能降耗的多个关键机器调度问题,包括作业准备时间受能耗约束的多个关键机器调度问题、作业加工时间受能耗约束的多个关键机器调度问题以及作业准备时间与加工时间同时受能耗约束的多个关键机器调度问题。由于这些问题均是NP-hard的,难以在多项式时间内获得最优解,本文为它们设计了用于评价解的精确度的问题下界,并构建了亚启发式算法,从而在合理的时间范围内为大规模的问题提供高质量的满意解。主要研究工作和创新点如下:(1)研究了作业准备时间和加工时间均不受能耗约束的多个关键机器调度问题,调度的目标是最小化最大完工时间。分析了现有LPT-ECT算法和Koulamas & Kyparisis的算法的优缺点,提出了改进的MLPT算法。针对此问题最优解的特征,设计了一种解的表示方法,不仅能够有效简化插入邻域和交换邻域的实现,也缩小了解空间;进而用可变邻域搜索和模拟退火算法进一步改进了启发式算法解的精确度。考虑作业准备时间分布疏密的十种情形,构造了大量的随机数据实验。实验表明,所构造的模拟退火算法能够将平均相对误差收敛到0.363%。同时,对于此问题的一个特例,当作业具有相同的准备时间且机器速度相同时,该模拟退火算法在解的精确度和计算效率两个方面均明显优于现有Lee et al.给出的模拟退火算法。(2)研究了作业准备时间受能耗约束的多个关键机器调度问题,调度的目标是在限定最大完工时间的前提下最小化能耗总量,并假定作业准备时间的能耗约束函数为一般减函数。给出了此问题的形式化描述,分析了此问题最优解应具有的特征,设计了作业左移和右移两种基本操作,讨论了交换邻域和插入邻域生成对能耗总量影响的计算方法,构建了此问题的可变邻域搜索算法和模拟退火算法。为评价算法解的精确度,松弛了作业开始时间与其能耗约束函数之间的对应关系,从而形成了一个指派问题,进而可以用匈牙利方法获得此松弛问题最优解,并因此设计了一个下界。以线性递减能耗约束函数为例,通过大量实验验证了算法的性能。另外,此模拟退火算法在求解具有线性递减能耗约束函数或凸减能耗约束函数的单个关键机器调度问题时,其解的精确度也分别优于现有Janiak以及Kaspi & Shabtay等人的算法。(3)研究了加工时间受能耗约束的多个关键机器调度问题,调度的目标是在限定可用能源总量的前提下最小化最大完工时间。给出了具有一般递减能耗约束函数的该类问题的形式化描述和最优解特征分析。为啕建快速的模拟退火算法,定义了决定性机器和非决定性机器,并重点对由某一决定性机器和最大完工时间最小的非决定性机器形成的局部解进行优化,从而使得搜索具有很强的针对性。对于具有线性递减能耗约束函数的该类问题,构造的模拟退火算法能够在0.875秒内有效解决1000个作业规模的问题并将相对误差控制在0.019946%以内。对于具有凸减能耗约束函数的此类问题,借鉴了Shabtay & Kaspi的相关结论,将各机器加工的作业对应到串联并联图的等价工作量,建立的模拟退火算法能够在0.1秒内有效求解1000个作业规模的问题,其相对误差也能够控制在0.01%以内。(4)研究了作业准备时间与加工时间同时受能耗约束的多个关键机器调度问题,调度的目标是在限定最大完工时间的前提下最小化能耗总量,其中假定作业准备时间和加工时间的能耗约束函数均为线性减函数。给出了此问题的形式化描述和最优解特征分析,设计了作业左移、右移、压缩和解压缩四种基本操作,讨论了交换、插入、压缩和解压缩四种邻域生成方式及其对能耗总量影响的计算方法,构建了相应的可变邻域搜索算法和模拟退火算法,设计了用于评价解的精确度的问题下界。大量随机数据实验表明,所构造的模拟退火算法能够有效解决该类问题。