基于误工损失指标的调度问题与算法研究
发布时间：2023-08-11 16:12
调度问题是组合优化、计算机科学、管理科学等领域的经典问题之一,其研究内容是指在满足一定约束的前提下,将一定时间内的不同任务分配给有限的处理机,以优化一至多个目标。众多优化目标之中,任务的误工损失是一个与其交付期有关的惩罚量,等于其滞后于交付期加工的部分。以最小化任务误工损失为优化目标的调度问题于1984年提出,已被持续研究超过30年。在前人基础上,本文继续研究了该类问题的若干形式,并利用精确算法、近似算法、元启发式算法等主流方法对它们进行求解。主要成果包括:(1)研究了同型机环境下、带公共交付期的最小化误工损失问题。通过理论分析表明当处理机数量作为参数之一的情况下,该问题是强NP难问题;针对两台同型机的特殊情况,提出了一种伪多项式时间动态规划算法,从而证明在该情况下问题的复杂性降为弱NP难;随后,证明最大处理时间优先算法(LPT算法)的近似比为10。(2)将上述问题扩展到非公共交付期的形式。通过定义解的表达方式、上下界计算方法以及支配规则等,提出了一种求解两台同型机问题的分支定界算法;同时,利用任务划分思想,提出了一种求解上述问题的穷举算法;当处理机数量为m(m≥ 2)时,提出了一种遗...
【文章页数】：117 页
【学位级别】：博士
【文章目录】：
摘要
ABSTRACT
主要符号表
1 绪论
1.1 调度问题及其表示方法
1.1.1 问题概述
1.1.2 调度问题三参数表示法
1.1.3 离线、在线、半在线调度
1.2 复杂性理论
1.3 求解复杂问题的算法分类及评估方法
1.3.1 精确算法
1.3.2 基于质量保证的近似算法
1.3.3 基于数值实验的启发式算法
1.4 以误工损失为优化目标的调度问题研究现状
1.4.1 单机调度问题研究情况
1.4.2 平行机调度问题研究情况
1.4.3 串联机调度问题研究情况
1.5 论文主要贡献及组织结构
2 带公共交付期的同型机调度问题
2.1 P|dj=d|Y问题的复杂性研究
2.2 求解P2|dj=d|Y问题的若干算法
2.2.1 伪多项式时间的动态规划算法
2.2.2 指数时间的穷举算法
2.2.3 多项式时间的近似算法
2.3 数值实验
2.3.1 实验数据集及测试平台
2.3.2 结果分析
2.4 本章小结
3 非公共交付期的同型机调度问题
3.1 求解P2||Y问题的分支定界算法
3.1.1 解的编码方式及搜索树结构
3.1.2 全局上界获取及更新方法
3.1.3 局部解下界计算方法
3.1.4 节点间的支配规则
3.1.5 B&B算法整体结构
3.2 求解P2||Y问题的穷举算法
3.3 求解Pm||Y问题的遗传算法
3.3.1 染色体初始化
3.3.2 交叉操作
3.3.3 变异操作
3.3.4 GA算法整体结构
3.4 数值实验
3.4.1 实验数据集及测试平台
3.4.2 小规模实例测试结果分析
3.4.3 大规模实例测试结果分析
3.5 本章小结
4 流水作业调度问题
4.1 F3|dj=d|Y问题的复杂性研究
4.2 求解Fm|LE|Y问题的粒子群算法
4.2.1 考虑学习效应的调度问题
4.2.2 Fm|LE|Y问题描述
4.2.3 PSO算法设计
4.2.4 PSO算法整体结构
4.3 数值实验
4.3.1 实验数据集及测试平台
4.3.2 结果分析
4.4 本章小结
5 半在线调度问题
5.1 竞争比分析方案
5.2 P2|online,SUM&MAX,dj=d|Y问题
5.2.1 问题定义
5.2.2 ALGOSM算法及其竞争比分析
5.2.3 问题下界
5.3 P2|online,MAX,dj=d|Y问题
5.3.1 问题定义
5.3.2 ALGOM算法及其竞争比分析
5.3.3 问题下界
5.4 本章小结
6 结论与展望
6.1 结论
6.2 创新点
6.3 展望
参考文献
攻读博士学位期间科研项目及科研成果
致谢
作者简介
本文编号：3841353
【文章页数】：117 页
【学位级别】：博士
【文章目录】：
摘要
ABSTRACT
主要符号表
1 绪论
1.1 调度问题及其表示方法
1.1.1 问题概述
1.1.2 调度问题三参数表示法
1.1.3 离线、在线、半在线调度
1.2 复杂性理论
1.3 求解复杂问题的算法分类及评估方法
1.3.1 精确算法
1.3.2 基于质量保证的近似算法
1.3.3 基于数值实验的启发式算法
1.4 以误工损失为优化目标的调度问题研究现状
1.4.1 单机调度问题研究情况
1.4.2 平行机调度问题研究情况
1.4.3 串联机调度问题研究情况
1.5 论文主要贡献及组织结构
2 带公共交付期的同型机调度问题
2.1 P|dj=d|Y问题的复杂性研究
2.2 求解P2|dj=d|Y问题的若干算法
2.2.1 伪多项式时间的动态规划算法
2.2.2 指数时间的穷举算法
2.2.3 多项式时间的近似算法
2.3 数值实验
2.3.1 实验数据集及测试平台
2.3.2 结果分析
2.4 本章小结
3 非公共交付期的同型机调度问题
3.1 求解P2||Y问题的分支定界算法
3.1.1 解的编码方式及搜索树结构
3.1.2 全局上界获取及更新方法
3.1.3 局部解下界计算方法
3.1.4 节点间的支配规则
3.1.5 B&B算法整体结构
3.2 求解P2||Y问题的穷举算法
3.3 求解Pm||Y问题的遗传算法
3.3.1 染色体初始化
3.3.2 交叉操作
3.3.3 变异操作
3.3.4 GA算法整体结构
3.4 数值实验
3.4.1 实验数据集及测试平台
3.4.2 小规模实例测试结果分析
3.4.3 大规模实例测试结果分析
3.5 本章小结
4 流水作业调度问题
4.1 F3|dj=d|Y问题的复杂性研究
4.2 求解Fm|LE|Y问题的粒子群算法
4.2.1 考虑学习效应的调度问题
4.2.2 Fm|LE|Y问题描述
4.2.3 PSO算法设计
4.2.4 PSO算法整体结构
4.3 数值实验
4.3.1 实验数据集及测试平台
4.3.2 结果分析
4.4 本章小结
5 半在线调度问题
5.1 竞争比分析方案
5.2 P2|online,SUM&MAX,dj=d|Y问题
5.2.1 问题定义
5.2.2 ALGOSM算法及其竞争比分析
5.2.3 问题下界
5.3 P2|online,MAX,dj=d|Y问题
5.3.1 问题定义
5.3.2 ALGOM算法及其竞争比分析
5.3.3 问题下界
5.4 本章小结
6 结论与展望
6.1 结论
6.2 创新点
6.3 展望
参考文献
攻读博士学位期间科研项目及科研成果
致谢
作者简介
本文编号：3841353
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3841353.html
