【作者】 李凯；

【导师】 杨善林； 储诚斌；

【作者基本信息】 合肥工业大学 ， 管理科学与工程， 2009， 博士

【摘要】 传统的生产调度问题通常假定作业的准备时间和加工时间等参数在调度的过程中是不变的,然而在冶金、化工等一些高耗能领域,它们的取值可能与作业消耗的能源量有关并影响调度结果。因此,对于这些领域中关键生产环节上的关键机器调度问题,在提高其生产效率的同时也应尽量优化其用能效率,从而达到节能降耗的目的。作为受能耗约束调度问题的研究基础,本文首先研究了无能耗约束的多个关键机器调度问题,然后研究了三类考虑节能降耗的多个关键机器调度问题,包括作业准备时间受能耗约束的多个关键机器调度问题、作业加工时间受能耗约束的多个关键机器调度问题以及作业准备时间与加工时间同时受能耗约束的多个关键机器调度问题。由于这些问题均是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)研究了作业准备时间与加工时间同时受能耗约束的多个关键机器调度问题,调度的目标是在限定最大完工时间的前提下最小化能耗总量,其中假定作业准备时间和加工时间的能耗约束函数均为线性减函数。给出了此问题的形式化描述和最优解特征分析,设计了作业左移、右移、压缩和解压缩四种基本操作,讨论了交换、插入、压缩和解压缩四种邻域生成方式及其对能耗总量影响的计算方法,构建了相应的可变邻域搜索算法和模拟退火算法,设计了用于评价解的精确度的问题下界。大量随机数据实验表明,所构造的模拟退火算法能够有效解决该类问题。更多还原

【Abstract】 Most classical scheduling problems assume that the parameters such as job release dates and processing times are constant. However, in some high-energy-consuming industries, especially in metallurgy or chemical industry, the values of the parameters maybe depend on the amount of energy consumption and at the same time affect the scheduling results. Therefore it is necessary to balance the conflict between the production efficiency and the energy consumption in key-machine scheduling problems of these industries.This dissertation firstly researches on the multi-key-machine scheduling problem without consideration of energy consumption. On this basis it researches on three multi-key-machine scheduling problems with energy consumption constraints, including the multi-key-machine scheduling problem with energy dependent release dates, the multi-key-machine scheduling problem with energy constrained processing times and the multi-key-machine scheduling problem in which the job release dates and processing times are simultaneously dependent on energy consumption. Because these problems are all NP-hard and can not be solved exactly in polynomial time, lower bounds are designed to evaluate the accuracy of the solutions. The meta-heuristic algorithms are presented to obtain near-optimal solutions with high quality in a reasonable time.The main contributions of this dissertation are listed as follows.(1) The dissertation first researches on the multi-key-machine scheduling problem without consideration of energy consumption constraints on both release date and processing time. The purpose of the scheduling problem is to minimize the makespan. It analyses the advantages and disadvantages of the existing LPT-ECT algorithm and the Koulamas & Kyparisis’s algorithm, and proposes a modified MLPT algorithm. Based on the characteristics of the optimal solutions of the problem, it designs a new solution presentation method, which can not only effectively simplify the implement of the insertion and swap neighborhood, but also narrow the solution space. It further improves the accuracy of the solution through variable neighborhood search and simulated annealing algorithm. It constructs a large number of random data experiments, considering 10 different distributions of job release date. Experimental studies show the proposed simulated annealing algorithm can make the average relative error converging to 0.363%. For a special case of this problem, in which jobs have the same release date and machines have the same speed, the accuracy and efficiency of the proposed simulated annealing algorithm are obviously superior to the existing simulated annealing algorithm proposed by Lee et al. (2) It researches on the multi-key-machine scheduling problem with energy consumption constraint on the release dates of jobs. The scheduling purpose is to minimize the energy consumption under a given makespan. It assumes that the energy consumption dependent functions of the release dates are general decreasing functions. It gives a formal description of the problem, analyses the potential characteristics of the optimal solutions of the problem, designs two basic operations of left-move and right-move of the task, discusses how to calculate the total energy consumption influenced by the swap and insert neighborhood, and designs a variable neighborhood search algorithm and simulated annealing algorithm for the problem. To evaluate the accuracy of the solutions, it relaxes the corresponding relationship between the job start time and its energy consumption dependent function, thereby obtaining an assignment problem. It uses the Hungary method to obtain the optimal solution of the relaxation problem, and designs a lower bound for the original problem. It tests the performance of the algorithm by a great deal of experiments, taking the linear energy consumption dependent function as example. Moreover, when solving the single key machine scheduling problems with linear and convex decreasing energy consumption dependent functions respectively, the accuracy of simulated annealing algorithm is superior to the existing algorithms proposed by Janiak and Kaspi & Shabtay.(3) It researches on the multi-key-machine scheduling problem with the energy constrained processing times. The purpose of the scheduling is to minimize the makespan under the constraint of given total energy. It gives the formal description of the problem of general decreasing constraint function of the energy consumption and analyses the potential characteristics of the optimal solutions. To design a fast simulated annealing algorithm, it presents the definitions of determine machine and non-determine machine, and optimizes the local solution consisting of a certain determine machine and the non-determine machine with the minimum maximal complete time. The process of search aims to optimize the local solution, and therefore the search is typically narrow targeted. To solve the problem with linear energy consumption functions, the proposed simulated annealing algorithm can solve the problem consisting of 1000 jobs in 0.875 second and hold the relative error within 0.019946%. To solve the problem of convex decreasing energy consumption constraint function, it uses the theoretical results presented by Shabtay & Kaspi and proposes a simulated annealing algorithm. The proposed simulated annealing algorithm can solve the problem consisting of 1000 jobs in 0.1 second and keep the relative error within 0.01%.(4) It researches on the multi-key-machine scheduling problem in which the job release dates and processing times are simultaneously dependent on energy consumption. The purpose of the scheduling is to minimize the total energy consumption under a given makespan. It assumes that the energy consumption constraint function of the job release dates and processing times are linear decreasing. It gives a formal description of the problem and analyses the potential characteristics of the optimal solution. It designs four basic job operations of job left-move, right-move, compression and decompression, discusses the creation of neighborhood with these four operations and calculates the total energy consumption by a modified variable neighborhood search algorithm and simulated annealing algorithm. It also designs a lower bound for the problem to evaluate the accuracy of the solution. Experimental results show that the simulated annealing algorithm can solve the problem effectively.更多还原