具有凸资源消耗函数的最小化Makespan的平行机调度问题

摘要

研究了一类资源受限的平行机调度问题,其中假定作业的处理时间是其消耗资源量的凸减函数,调度的目标是在限定资源总量的情况下最小化Makespan(最大完工时间).给出了此类NP-hard问题的形式化描述.定义了关键机器与非关键机器,给出了非最优解必定存在非关键机器的论断.尽快缩短非关键机器与关键机器之间工作量的差距能够有效逼近最优解,从而构造了快速的模拟退火算法.设计了一个下界用于衡量解的精度,并用于构造模拟退火算法迭代结束条件.算法性能通过20000组随机数值算例进行了测试,实验结果表明所构造的模拟退火算法能够在0.1秒之内有效求解1000个作业的问题并将相对误差控制在0.01％以内.该算法体现出很高的精度和计算效率.%In most production environments, such as the steel industry, the job processing times may be shortened by using additional resources, e. g. energy, manpower, money and catalyzer. Different from the supposition that processing times are fixed in the traditional scheduling papers, this paper asserts that scheduling problems with changeable processing times can improve not only the production efficiency but also maximize resource consumption. Factories must find a balance between production efficiency and resource consumption.rnThis paper asserts that the parallel machine scheduling problem has changeable job processing times, which has a convex decreasing function of resource consumption. Monma et al. think that the convex decreasing function has practical implications because it can reflect the diminishing marginal return of the production process. This paper supposes that the total resource is limited, and an optimization method ( e. g. minimizing the makespan) is important to improve the production efficiency. The formal description of this NP-hard problem is given. The characteristics of the optimal and non-optimal solutions are analyzed. Two kinds of machines, including key machine and non-key machine, are defined. There is at least one non-key machine in a non-optimal solution. To minimize the makespan, the algorithm must aim at the sub-schedule with a key-machine and a non-key machine. Minimizing workflow differences between key machine and non-key machine can help obtain the optimal solutions effectively. A lower bound is also designed to evaluate the accuracy of solutions and build the condition to stop the algorithm. Based on the above analysis, this paper designs a simulated annealing algorithm. To improve the efficiency of the simulated annealing algorithm, the optimization process aims at the sub-scheduling with a key machine and a non-key machine. In addition, the sub-scheduling changes during the iteration. The simulated annealing algorithm performance is tested on 20, 000 random instances. The computational results indicate that the proposed simulated annealing algorithm can solve problems with 1000 jobs within 0. 1 seconds, and the relative error is controlled within 0.01%. Therefore, the proposed simulated annealing algorithm has high accuracy and efficiency.rnIn summary, this paper solves the parallel machine scheduling problem with changeable job processing times. The proposed optimization algorithm can provide reference values for practical scheduling problems such as preheating furnace scheduling in the steel industry and scheduling active manufacturers in the pull supply chain.