基于时间D-子集任务排序与调度问题研究
Study on Task Sequencing and Scheduling Problems with Time D-subsets
摘要本文以车间调度问题为背景,以Dioid代数理论为基础,研究了单机任务排序与调度问题及多机任务排序与调度问题.两者都是车间调度问题的特例,同时也是复杂车间调度问题的基础.首先通过引入单机与多机任务排序函数及任务开工与完工时间D子集,从机理上建立了单机与多机任务调度的极大代数模型.模型描述了任务的开工时间和完工时间与任务的到达时间和加工时间之间的复杂关系.多机任务排序函数表征了任务在机器上的分配与排序双重问题.在此基础上,给出极大代数意义下的单机与多机任务最优排序与调度问题规划模型.然后,论文分别研究了单机和多机任务最优排序与调度问题的启发式求解算法.在单机任务排序与调度问题中,给出了求解单机任务排序与调度问题的k均加工时间启发式动态规划算法与多规则混合启发式算法.算法从整体机理考虑调度问题,兼顾了常规启发式算法的优点,可以得到单机问题比较满意的调度方案.在多机任务排序与调度问题中,分别给出了在同速并行机与异速并行机下的动态规划启发式算法.最后,通过实例对比分析,证明了论文所提出启发式算法的有效性,同时指出了相应算法的优缺点.
- 作者：
- 杨新玲
- 学位授予单位：
- 沈阳大学
- 专业名称：
- 管理科学与工程
- 授予学位：
- 硕士
- 学位年度：
- 2010年
- 导师姓名：
- 李彦平
- 中图分类号：
- F273；F224
- 关键词：
- 极大代数；时间D-子集；任务排序函数；最优排序与调度；启发式动态规划算法
- Max-algebra；Time D-subset；Task sequence function；Optimal sequencing and scheduling；Heuristic dynamic programming algorithm