具有释放时间的单机半连续型批处理机调度问题

摘要

半连续型批处理机调度问题是从钢铁工业加热炉对管坯加热的过程中提炼的，它的主要特征是工件按批加工，工件必须按周期的进入和离开处理机，只有一批工件全部加工完才可以加工下一批的工件，同一批中工件的加工时间为此批工件中的最大加工时间。由于批中的工件是连续进、连续出的，所以批的容量即批的大小可以是无限的。又因为工件具有释放时间，所以在加工同批工件的过程中，存在有空位和无空位两种情况。本文从这两方面进行了研究，具体内容概括如下：
　　1.当同批工件加工过程中无空位产生，即工件按周期一个紧挨着一个进入和离开处理机时，本文主要从两个方面进行了理论研究：
　　（1）为了提高机器的利用率，即对于目标函数是最大完工时间的调度问题，当工件的释放时间和加工时间同序时，分析其问题的最优解性质，给出一个计算复杂性为On的动态规划算法，证明了算法的最优性，并用数值例子进一步说明此算法。
　　（2）当工件带权时，对于工件的加工时间相等的特殊情况，给出了目标函数是最大完工时间的调度问题的最优解性质；当工件的释放时间和权值逆序时，为了降低在制品的库存量，即目标函数是加权总完工时间的调度问题，分析了此问题的最优解性质，给出一个启发式算法，并用数值例子进一步解释此算法。
　　2.当工件加工过程中有空位产生时，工件有可利用性，机器也有可用性。对于目标函数是最大完工时间的问题，当工件的释放时间和加工时间同序时，讨论了其最优解性质，给出了一个启发式算法，并通过数值例子进一步说明此算法及有效性。

目录

封面

中文摘要

英文摘要

目录

第一章 绪 论

1.1调度问题预备知识

1.2批调度问题及研究现状

1.3 本文主要内容

第二章 具有释放时间的半连续型批处理机调度的时间表长问题

2.1 引 言

2.2 批释放时间定义

2.3 最优解性质

2.4 动态规划算法

2.5 数值例子

2.6 本章小结

第三章 工件带权的单机半连续型批处理机调度问题

3.1引 言

3.2 极小化最大完工时间问题

3.3 极小化加权总完工时间问题

3.4 本章小结

第四章 带空位的半连续型批处理机调度的时间表长问题

4.1 引 言

4.2 最优解性质

4.3 启发式算法

4.4 数值例子

4.5 本章小结

结 论

参考文献

致谢

个人简历及在学期间的研究成果和发表的学术论文