几类加工时间与位置相关的单机排序问题

摘要

在传统的排序中，工件的加工时间是一个固定不变的参数，工件在机器上依次加工。但根据实际的需要，工件的实际加工时间已不再是固定不变的参数，而是与实际问题相关的函数。本文主要研究工件的加工时间是可变的单机排序问题。其中，工件的实际加工时间是与工件位置和开始加工时间有关的函数。本文具体研究内容概括如下：
　　1)在工件同时带有学习效应和恶化效应的单机排序问题中，工件的学习效应是与工件的实际加工位置相关的函数，工件的恶化效应是与工件的开始加工时间相关的线性函数。讨论单机情况下工件最大完工时间、总完工时间及总完工时间的绝对差之和的问题，证明了这些问题都是多项式时间可解的。进一步，在线性资源分配情况下，讨论了带有学习效应、恶化效应和资源分配的工期指派问题，工件有一个共同的工期。目的为确定最优工期、最优资源分配量及工件加工顺序，使公共工期、提前、延误和资源分配之和为最小。通过将其转化为指派问题，证明了带有学习效应、恶化效应和资源分配的工期指派问题是多项式时间可解的。
　　2)工件的学习效应是与工件的实际加工位置相关的一般函数，工件的恶化效应是与工件的开始加工时间相关的线性函数，分别得到了最大完工时间、总完工时间及总完工时间的绝对差之和问题的多项式时间算法。
　　3)在机器在恶化维修时间的情况下，工件的实际加工时间是与工件基本加工时间和工件实际加工位置相关的一般函数。确定了最优工期、加工顺序及机器维修位置，使提前、延误和工期的之和最小。通过将这个问题转化为指派问题，证明了该问题在多项式时间内是可解的，并给出此问题的一种特殊情况的最优算法。

目录

封面

中文摘要

英文摘要

目录

第一章 绪 论

1.1 排序问题研究背景

1.2 带有学习效应和恶化效应的单机排序问题研究现状

1.3 工期指派问题的研究现状

1.4 资源分配问题的研究现状

1.5维修的排序问题的研究现状

1.6 本文主要研究内容

第二章 带有学习效应和恶化效应的单机排序问题

2.1 引言

2.2 问题描述

2.3 最大完工时间问题

2.4 总完工时间问题和TADC问题

2.5 线性资源分配的工期排序问题

2.6 本章小结

第三章 与位置相关抽象函数的单机排序问题

3.1 引言

3.2 问题描述

3.3 主要结论

3.4 数值例子

3.5 本章小结

第四章 带有恶化效应和维修恶化的单机工期指派问题

4.1 引言

4.2 问题描述

4.3 主要结论

4.4 最优值求解

4.5 特殊情况

4.6 本章小节

结论与展望

参考文献

致谢

个人简历及研究生期间发表的学术论文