一类批处理机调度的理论和方法研究

摘要

批处理机在生产过程中可以同时加工多个工件，其调度属于并行批调度。由于批处理机具有批生产模式的优越性，因而广泛存在于工业生产中的加热、退火等工序上。特别是近年来，随着企业面临节能降耗的压力的增长，批处理机调度的研究备受工业界和学术界的共同关注。本文以钢铁企业退火炉和钢锭均热炉两个典型批处理机为背景，对从中提炼的一类批处理机调度问题进行研究。其研究对钢铁企业节能降耗、降低生产成本和提高产能都具有重要的实际意义。主要研究概述如下：
　　1)针对单台批处理机总加权完成时间最小化问题，分别设计了启发式算法和智能优化算法。启发式算法是基于问题的最优解性质分析的构造式算法，而智能优化算法是基于环交换的迭代式算法。通过数值实验表明，启发式算法性能优于该类问题已有的满批启发算法和动态规划启发式算法;而智能优化算法解的质量优于启发式算法，但需要更多的计算时间。
　　2)从罩式退火炉加热板卷的组批过程提炼出工件具有尺寸属性的批处理机调度问题。与一般批处理机以工件数量作为能力单位不同，该问题是以高度（尺寸）作为能力单位，确定每一批的工件（带有尺寸属性）组成及批的顺序，目标是最小化机器空余总量和工件总完成时间。针对该NP-难问题，基于最优解性质分析，提出了基于贪婪策略的构造式启发式算法。对于总完成时间最小化问题，基于问题的性质提出了SPT先排序、动态规划后分批的启发式算法。通过数值实验验证了算法的有效性。
　　3)从板卷退火过程提炼出工件在同一机器上具有三步加工时间的新型批处理机调度问题。板卷在一个罩式炉中退火的过程由加热、保温和降温三段组成，而这三段处理时间由于工艺上的要求不能归结为一个时间，这与传统批处理机调度有明显的差别。对新型批处理机的总加权完成时间最小化问题建立了非线性整数规划模型，开发了基于动态规划的启发式算法。通过理论分析，获得该算法的误差性能比为3。对于三段中的某一段板卷的处理时间相同的情况，证明了启发式算法的误差性能比是2，而且证明是紧界。对于三段中的某二段板卷的处理时间相同的情况，证明了启发式算法是最优算法。最后，将启发式算法扩展到加工时间为任意段的一般情况，并进行了算法性能理论分析。
　　4)从均热炉的均热作业中提炼出工件带有线性恶化加工时间和阈值的批处理机调度问题。热钢锭随着等待时间的增加逐渐降温从而导致均热时间恶化，当钢锭等待时间超过一定限制，均热时间将不再变化。对总完成时间最小化问题，分析了问题的最优解性质，基于此性质，提出了构造式启发式算法，并通过仿真实验与该问题已有的满批算法进行比较，验证算法的有效性。

目录

声明

摘要

第1章 绪论

1．1 问题的研究目的及意义

1．1．1 问题来源及研究目的

1．1．2 问题背景、研究意义及三参数表示形式

1．2 批处理机调度问题研究现状

1．2．1 簇调度

1．2．2 批处理调度

1．2．3 半连续型批处理调度

1．3 本文主要工作

第2章 批处理机工件总加权完成时间的理论分析

2．1 引言

2．2 问题的描述

2．3 数学模型

2．4 最优解的一些性质

2．5 小结

第3章 批处理机工件总加权完成时间的两种算法

3．1 引言

3．2 启发式算法

3．2．1 算法描述

3．2．2 计算示例

3．2．3 计算复杂度

3．3 环交换算法

3．3．1 初始分批

3．3．2 环交换邻域

3．3．3 动态规划搜索环交换邻域

3．3．4 环交换邻域空间的缩减

3．4 仿真实验及结论

3．4．1 启发式算法性能验证

3．4．2 环交换算法性能验证

3．5 小结

第4章 工件具有不同尺寸单台批处理机的调度问题

4．1 引言

4．2 问题的描述

4．3 数学模型

4．4 启发式算法

4．4．1 部分工件的分批

4．4．2 启发式算法—贪婪算法

4．5 基于动态规划启发式算法DP1

4．6 总完成时间的动态规划算法

4．6．1 动态规划算法

4．6．2 计算示例

4．7 启发式算法DP的改进

4．7．1 质分析

4．7．2 启发式算法DPLS的改进

4．7．3 计算示例

4．8 仿真实验及结论

4．8．1 一般情况算法比较

4．8．2 总完成时间问题的算法比较

4．9 小结

第5章 工件具有三步加工时间的批处理机调度问题

5．1 引言

5．2 问题的描述

5．3 数学模型

5．4 基于动态规划启发式算法

5．5 算法最坏情况分析

5．6 若干特殊情况的启发式算法DP性能分析

5．7 小结

第6章 加工时间恶化批处理机调度问题

6．1 引言

6．2 数学模型

6．3 解的性质

6．3．1 给定批的调度性质

6．3．2 工件组批的调度性质

6．4 启发式算法

6．4．1 满批算法

6．4．2 贪婪算法

6．4．3 计算示例

6．5 仿真实验及结论

6．6 小结

第7章 结束语

参考文献

致谢

作者博士期间发表和录用的论文

作者博士期间科研情况

个人简历