带有拒绝工件的工期指派的排序问题

摘要

随着现代工业的发展,排序模型被不断突破。在一些排序模型中,如果所有工件都不被拒绝,当一个工件的加工时间或加工费用太大时,将导致完工时间变大或费用太大,因此需要考虑该工件是否被加工。若工件被拒绝则有一个惩罚费用。每个工件需要确定一个工期。本文讨论带有拒绝工件的工期指派的排序问题。具体内容概括如下:
　　1.工件的实际加工时间是其开始加工时间的线性增函数。讨论的工期指派分为 CON(公共工期指派)和 SLK(相同松弛工期指派)两种情况。对于 CON工期指派问题,其目的是确定最优公共工期及工件的加工顺序,使工期、提前、延误和拒绝的加权总费用最小。我们将该问题归结为一系列指派问题,给出了求解此问题的多项式时间的最优算法;对于 SLK工期指派问题,目的是确定最优的松弛量及工件的加工顺序,使松弛、提前、延误和拒绝的加权总费用最小。将其归结为一系列指派问题,从而得到了一个复杂性为O(n4)的算法来求解此问题。
　　2.分析了两种资源分配函数和三种工期指派方法。资源分配分为线性资源分配和凸资源分配。在线性资源分配条件下,讨论了三种工期指派方法,工期指派分为 CON(公共工期指派),SLK(相同松弛工期指派)和 DIF(无限制工期指派),分别给出了多项式时间算法来确定最优的加工顺序,工期和资源分配量,使得工期、提前、延误、资源分配和拒绝的加权总费用最小;在凸资源分配条件下,也讨论了CON,SLK和DIF三种工期,目的是确定最优的加工顺序,工期和资源分配量,使得工期、提前、延误、资源分配和拒绝的加权总费用最小,从而得到复杂性为O(n2 log n)的算法。

目录

封面

中文摘要

英文摘要

目录

第一章 绪 论

1.1 排序问题研究背景

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

1.3 拒绝问题的研究现状

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

1.5 本文的主要研究内容

第二章 带有恶化和拒绝工件的工期指派的单机排序问题

2.1 引言

2.2 问题描述

2.3 CON工期指派问题

2.4 SLK工期指派问题

2.5 小结

第三章 带有拒绝和线性资源分配的工期指派的单机排序问题

3.1 引言

3.2 问题描述

3.3 线性资源分配问题

3.4 小结

第四章 带有拒绝和凸资源分配的工期指派的单机排序问题

4.1 引言

4.2 最优解性质

4.3小结

结论和展望

参考文献

致谢

个人简历及在学期间的研究成果和发表的学术论文