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

摘要

在传统的经典调度问题中，一般假设机器数量不会变化。随着互联网等信息技术的充分利用，企业获取额外资源更加便利，因此本文突破了传统经典调度问题关于机器数量固定的假设前提，研究机器数量变化的制造模式具体特点对调度理论的冲击和创新。本文主要研究了在同型机调度环境中，当机器数量从m增加到(m)后对调度目标函数最大完工时间的影响。我们用比值I(m，(m))衡量这个影响，定义为初始机器数量的目标函数值与添加额外机器数量后的目标函数值之比。
　　本研究主要内容包括：⑴针对考虑作业释放时间和加工可中断的在线机器调度问题，首先基于改进的McNaughton规则提出了一种多项式时间算法P，接着证明了该算法能求得问题的最优解和最优机器数目，继而分析了机器影响。最后，通过实验算例验证了算法的有效性。⑵针对考虑作业释放时间和加工不可中断的在线机器调度问题，由于此问题是NP-hard的，难以在多项式时间内获得最优解，因此我们提出了一种启发式算法MLPT。最后，通过实验分析了算法的性能，并说明了算法适应的情形。

目录

声明

致谢

摘要

第一章 绪论

1．1 研究背景及意义

1．2 研究现状

1．2．1 考虑机器数量的调度问题

1．2．2 考虑作业释放时间的调度问题

1．3 论文结构安排

第二章 相关理论基础

2．1 在线机器调度概念

2．2 调度问题的符号表示

2．3 常见的求解方法

第三章 作业可中断的在线机器调度

3．1 引言

3．2 问题的描述

3．3 算法设计

3．3．1 算法P

3．3．2 机器影响的界

3．4 实验算例

3．5 小结

第四章 作业不可中断的在线机器调度

4．1 引言

4．2 问题的描述及分析

4．3 算法设计

4．3．1 启发式算法MLPT

4．3．2 实验算例

4．4 小结

第五章 总结与展望

5．1 总结

5．2 展望

参考文献

攻读硕士学位期间的学术活动及成果情况