带速率修改活动且工件加工时间离散可控下的排序问题研究

摘要

组合优化是运筹学和理论计算机科学的一个重要分支,其中,人们热衷于讨论的一个方向便是排序问题.一般排序模型是在一定的工件特征和机器环境下考虑的.近年来,随着实际生产需求的不断提高和改变,逐渐衍生出一些新的排序问题.针对工件特征,人们研究工件加工时间可控或者不可控的问题.针对机器环境,人们研究机器需要速率修改活动情形下的排序问题.速率修改活动有两个关键的参数,进行活动的开始时间和活动持续的时长.不同要求下的参数对应着不同的排序问题.围绕上述两点进行展开,本文主要讨论了下面两类新型排序问题:带速率修改活动且工件加工时间离散可控下的单机排序问题和带速率修改活动且工件加工时间离散可控下的平行机排序问题.
　　全文共分为四章:
　　第一章的绪论中主要介绍了组合优化问题,排序问题及计算复杂性的基本概念和相关知识,系统的总结了国内外研究现状和发展趋势.
　　第二章研究了带速率修改活动且工件加工时间离散可控下的单机排序问题,其中速率修改活动的时长是其开始时刻的非降函数.将给定的n个独立工件J={J1,J2,···,Jn}安排在一台机器上进行加工,每个工件有多个加工时间可选,当工件的加工时间不同时,其对应的加工成本也不相同.此外,我们对机器是否进行速率修改活动分情况进行讨论,目标是找到所有工件的最优排序,确定每个工件的加工时间,加工成本及速率修改活动的开始时间,使得目标函数的值最小.当极小化目标函数是最大完工时间加总加工成本时,给出多项式时间的精确算法.当极小化目标函数分别是完工时间和加总加工成本,提前延迟与截止时间惩罚和加总加工成本时,也分别设计了计算复杂度均为O(n4m)的多项式时间精确算法.
　　第三章对第二章的内容进行了拓展,考虑的是带速率修改活动且工件加工时间离散可控的平行机排序问题,将给定的有n个独立工件的工件集J={J1,J2,...,Jn}安排在m(m　　第四章对全文进行了总结,并给出了今后仍需继续探索的方向和内容。

目录

第一章 绪 论

2. 排序问题概述

§1.2 算法和计算复杂性

§1.3 文献评述

第二章 带速率修改活动且工件加工时间离散可控下的单机排序问题

§2.2 排序问题1,DRM|dc|Cmax+TPC

§2.3 排序问题1,DRM|dc|∑ni=1Ci+TPC

§2.4 排序问题1,DRM|dc|α∑ni=1Ei+β∑ni=1Ti+γd+TPC

§2.5 本章小结

第三章 带速率修改活动且工件加工时间离散可控下的平行机排序问题

§3.2 排序问题RM|rma,dc|∑Cimax+TPC

§3.3 排序问题RM|rma,dc|∑Cij+TPC

§3.4 排序问题RM|rma,di=d,dc|∑(αEij+βTij)+TPC

§3.5 本章小结

第四章 总结与展望

参考文献

在校研究成果

致谢