具有时间与位置相关的两种机器排序问题研究

摘要

本文研究在单机和平行机环境下具有时间效应和位置效应以及维修限制的排序问题,其中平行机环境下仅仅考虑恒同机和无关机.主要研究结果如下：
　　单机排序问题
　　1)研究工件的实际加工操作时间同时具有时间和位置效应,且在机器的加工操作中由于机器磨损而不得不进行维修活动的排序问题,其中维修区间的长度跟工件的开始加工作业的时刻相关,目标函数分别为最大完工时间和总完工时间.通过简化目标函数,使用匹配算法最后得到其多项式算法.
　　2)证明当工件的实际加工操作时间只受到本组工件的实际加工操作时间的总和的影响、位置效应仅与工件在生产中的排列顺序有关和维修区间长度为常数的问题满足组平衡规则.当目标函数为最大完工时间时,得到此排序问题有多项式时间解,并得出其复杂度为O(2 logn).
　　平行机排序问题
　　1)研究工件的实际加工操作时间同时受到位置和时间效应的影响,且在工件的加工过程中,由于机器老化而不得不进行维修活动的无关机排序问题.其中问题的目标函数是由最大完工时间的总和、总完工时间的总和与总等待时间的总和所共同组成的,让其转化为指派问题,能求得多项式时间解,时间复杂度为O(nk+2/(k-1)!).
　　2)研究工件的实际加工操作时间同时受到位置和时间效应的影响,且在工件的加工过程中,由于机器老化而不得不进行维修活动的恒同机问题.其中目标函数由最大完工时间的总和、总完工时间的总和与总等待时间的总和一起组成的,通过转化目标函数,使用匹配算法得出排序问题有多项式时间解,时间复杂度为O((2n+k+nlogn)nk-1/(k-1)!).

目录

1 绪论

1.1 排序论发展简述

1.2排序问题的定义及其符号表示

1.3研究现状

1.4结论及创新点

2 单机排序问题

2.1引言

2.2模型描述

2.3计算位置权重

2.4模型求解

2.5组平衡规则

2.6本章小结

3平行机排序问题

3.1引言

3.2模型描述

3.3相关结论

3.4无关机问题

3.5恒同机问题

3.6本章小结

4结论及展望

4.1论文总结

4.2进一步工作

参考文献

附录A：作者攻读硕士学位期间发表论文及科研情况

致谢

声明