工件带拒绝费用的两个单机排序问题

摘要

在经典排序模型中,往往假定机器必须加工所有的工件,并且它们的加工时间都是给定的。但是在许多现实的应用中,若某个工件的加工时间或者加工费用很大,就会考虑是否要加工该工件,既可以选择付出一定的费用而拒绝加工该工件也可以选择不付费而加工它。这时目标函数不再是传统的最大总完工时间,极小化最大完工时间,最大延迟等,而是要同时考虑费用,把这种排序称为可拒绝排序。
　　论文共分三章。
　　第一章(绪论)主要介绍了排序的产生背景、发展及其相关的一些基本知识。
　　第二章首次研究了工件带拒绝费用的单机分族分批排序问题。对于常见的目标函数为min﹙Cmax+∑j∈sej﹚的多种情况进行了分析并证明其性质,对几个简单问题给出了最优算法,证明了问题1,sfg∣family-job,rej∣Cmax+∑j∈sej和1,sfg∣family-job,rej∣Cmax+(a)j(I)(S)ej是NP-难的,给出了它们的近似算法并讨论其最差性能比。
　　第三章研究了工件带拒绝费用的单机分族串行分批排序问题。对于常见的目标函数为minCmax+(a)j(I)(S)ej的多种情况进行了分析并证明其性质,对几个简单问题给出了多项式时间的最优算法,证明了问题1,sfg∣family-jobs,rej,s-batch,b?n∣Cmax(a)j(I)(S)ej是NP-难的,并给出了它的近似算法。

目录

声明

中文摘要

英文摘要

目录

第一章 绪论

§1.1排序

§1.2计算复杂性

§1.3 P类、NP类和NP完备

§1.4近似算法

§1.5 分批排序

第二章 工件带拒绝费用的单机分族分批排序

§2.1 引 言

§2.2 主要结果

§2.3结 论

第三章 工件带拒绝费用的单机分族串行分批排序

3.1 引 言

3.2 主要结果

3.3结 论

参考文献

致谢