带到达时间和不可用区间以及拒绝工件的排序问题

摘要

排序问题是一类重要的组合最优化问题。在经典排序里，研究者通常假定工件加工商必须接受加工买家要求的全部工件，也就是说，不能拒绝加工任意一个工件。但是，这并不符合生产者的利益要求，工件加工商为了使利益最大化，或者更为通俗地说，为了创造更大的生产效益，就不会去加工那些加工时间很长，但是获取利益却很小的工件，同时也会因此而赔款。此种情况放在排序问题里，称为带有拒绝工件。在加工生产时，机器可能因为发生故障或者其他意外，使得机器在一段时间里不能进行工作。此种情况放在排序问题里，称为机器带有不可用区间。由于这些问题很可能在现实生产中发生，所以，越来越多的学者对既有不可用区间又有拒绝工件的排序问题进行了大量的研究。本文对带到达时间和不可用区间以及拒绝工件的排序问题进行了研究，主要内容如下：
　　第一章介绍排序问题的定义及三参数表示法，并介绍带有不可用区间和拒绝工件的排序问题的一些研究现状以及本文工作。
　　第二章我们采用构造输入数据的方法处理带到达时间和不可用区间以及拒绝工件的单机排序问题，我们的目标是最小化加工工件的时间表长和拒绝工件的惩罚的和，设计了一个全多项式时间近似方案。
　　第三章我们通过改变动态规划算法的执行过程来处理带到达时间和不可用区间以及拒绝工件的单机排序问题，最小化的函数是所有放在机器上加工的工件的时间表长与所有被拒绝的工件的惩罚的和，给出了一个全多项式时间近似方案。
　　第四章研究的是带到达时间和不可用区间以及拒绝工件的两台平行机排序问题。

目录

封面

中文摘要

英文摘要

目录

第一章 引言

一、排序问题的定义、三参数表示法

二、应用背景和研究现状

三、本文工作

第二章 用构造输入的方法获得全多项式时间近似方案

一、引言

二、问题描述

三、动态规划算法和3—因子算法

四、全多项式时间近似方案

五、小结

第三章 用削减状态空间的方法获得全多项式时间近似方案

一、引言

二、动态规划算法

三、全多项式时间近似方案

四、小结

第四章 带到达时间和不可用区间以及拒绝工件的两台平行机排序问题

一、引言

二、问题描述

三、4—因子算法

四、小结

结论

参考文献

个人简历

在学期间的研究成果和发表的学术论文

致谢