考虑作业释放时间的在线机器调度问题研究

发布时间：2018-02-28 12:43

本文关键词： 同型机调度最大完工时间释放时间启发式算法　出处：《合肥工业大学》2017年硕士论文　论文类型：学位论文

【摘要】：在传统的经典调度问题中,一般假设机器数量不会变化。随着互联网等信息技术的充分利用,企业获取额外资源更加便利,因此本论文突破了传统经典调度问题关于机器数量固定的假设前提,研究机器数量变化的制造模式具体特点对调度理论的冲击和创新。本文主要研究了在同型机调度环境中,当机器数量从m增加到?m后对调度目标函数最大完工时间的影响。我们用比值I(m,?m)衡量这个影响,定义为初始机器数量的目标函数值与添加额外机器数量后的目标函数值之比。本文讨论了考虑作业释放时间调度问题的可中断和不可中断两种情形:(1)针对考虑作业释放时间和加工可中断的在线机器调度问题,首先基于改进的McNaughton规则提出了一种多项式时间算法P,接着证明了该算法能求得问题的最优解和最优机器数目,继而分析了机器影响。最后,通过实验算例验证了算法的有效性。(2)针对考虑作业释放时间和加工不可中断的在线机器调度问题,由于此问题是NP-hard的,难以在多项式时间内获得最优解,因此我们提出了一种启发式算法MLPT。最后,通过实验分析了算法的性能,并说明了算法适应的情形。实验结果表明,增加机器数量是提升企业生产效率的一种有效的方法,但是我们也应该合理地利用现有的机器资源,以免造成资源的浪费。
[Abstract]:In traditional classical scheduling problems, it is generally assumed that the number of machines will not change. With the full use of information technology such as the Internet, it is more convenient for enterprises to obtain additional resources. Therefore, this paper breaks through the hypothesis of the traditional classical scheduling problem about the fixed number of machines, and studies the impact and innovation of the specific characteristics of the manufacturing mode of the machine quantity change on the scheduling theory. In this paper, we mainly study the scheduling environment of the same machine. When the number of machines increases from m to? The effect of m on the maximum completion time of the scheduling objective function. M) measuring the impact, The ratio of the value of the objective function defined as the number of initial machines to the value of the objective function after adding the number of additional machines is discussed in this paper. In this paper, we discuss the interruptible and non-interruptible cases considering the scheduling problem of job release time. Industry release time and processing interruptible online machine scheduling problems, Based on the improved McNaughton rule, a polynomial time algorithm (P) is proposed, and then it is proved that the algorithm can obtain the optimal solution and the optimal number of machines, and then analyze the influence of the machine. An experimental example is given to verify the effectiveness of the algorithm.) for the on-line machine scheduling problem considering job release time and processing uninterrupted, it is difficult to obtain the optimal solution in polynomial time because the problem is NP-hard. Therefore, we propose a heuristic algorithm MLPT.Finally, the performance of the algorithm is analyzed through experiments, and the adaptive case is illustrated. The experimental results show that increasing the number of machines is an effective method to improve the production efficiency of enterprises. But we should also make rational use of existing machine resources so as not to cause waste of resources.
【学位授予单位】：合肥工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O223

【相似文献】