并行机实时调度问题的列生成算法

摘要

钢铁和化工等流程工业中工序之间物流的连续和高温运作,对其生产管理中的生产调度的实时性要求苛刻,这一类调度问题被称为实时调度问题.因其在计算机系统也经常存在,探讨这类问题的求解策略,成为近年来学术界的研究热点.该文针对并行机实时调度问题进行了研究,该问题的描述如下:有n个带有不同截止日期要求的工件,需要在m台并行机上进行加工.调度的目标是在满足工件的截止日期要求的情况下,最小化总加权完成时间.

目录

文摘

英文文摘

声明

第一章绪论

1.1问题的研究目的及意义

1.1.1问题的来源及研究目的

1.1.2问题的背景、特点与意义

1.2实时调度问题综述

1.2.1实时调度问题的特点

1.2.2实时调度问题的分类

1.2.3实时调度问题的研究概况

1.3并行机实时调度问题的分类

1.3.1按照目标函数分类

1.3.2按照处理过程特性分类

1.3.3基于实时性质分类

1.3.4基于求解方法分类

1.4并行机环境下实时调度问题的研究现状

1.5本文的主要工作和技术研究路线

第二章并行机实时调度问题的数学模型和列生成算法

2.1并行机实时调度问题的数学模型

2.1.1并行机实时调度问题的描述

2.1.2并行机实时调度问题的数学模型

2.2 Dantzig-Wolfe分解法

2.2.1集划分主问题

2.2.2求解LSP1和LSP2的列生成过程

2.2.3单机子问题

2.3分支定界算法

2.4结论

第三章机器一直可用的并行机实时调度问题的列生成算法

3.1问题的数学模型与有关的性质

3.1.1问题的数学模型

3.1.2一个最优调度的性质

3.1.3单机子问题的NP-难证明

3.2单机子问题的动态规划算法

3.2.1 pricing算法的基本思想

3.2.2 pricing算法框图

3.3初始解的产生

3.4分支定界算法

3.4.1特殊分数解的转换

3.4.2一般分数解----分支定界

3.5算法的整体实现

3.6算法性能实验

3.6.1实验数据的产生

3.6.2实验结果

3.7结论

第四章机器带有释放时间的并行机实时调度问题的列生成算法

4.1问题的描述和有关性质

4.1.1机器具有可用时间约束的调度问题的描述

4.1.2机器带有释放时间的并行机实时调度问题

4.2列生成算法

4.2.1机器具有相同释放时间问题的列生成算法

4.2.2机器具有不同释放时间问题的列生成算法

4.3算法性能试验

4.3.1实验数据的产生

4.3.2实验结果

4.5结论

参考文献

致谢