最小化两个新型目标函数的工件可拒绝排序问题

摘要

排序(也叫做调度)是一类重要的组合最优化问题.它广泛地应用于管理科学、计算机科学和工程技术等很多领域，也是运筹学研究中非常活跃的分支之一.目前，已有大量的文献对各种类型的排序问题进行了研究.在经典排序问题中，所有的工件都必须安排在机器上加工.然而，有时我们为了获取最大的利润，需要放弃加工那些耗费成本大且产生利润较少的工件.在2000年，Bartal等人[2]最早开始研究工件可拒绝的排序问题.自此以后，工件可拒绝的排序问题受到人们越来越多的关注和研究.本文我们主要考虑下面两个工件可拒绝排序问题.
　　(1)最小化机器负载量平方和的工件可拒绝平行机排序问题
　　该排序问题可以被描述如下：m台机器M1,M2,…,Mm和n个工件义J1,J2,…,Jn.每个工件Jj有一个加工时间Pj和一个拒绝费用ej.工件Jj或者被接收并被安排在这m台机器中的某一台上进行加工；或者被拒绝并支付一个相应的拒绝费用ej.目标函数是最小化机器上负载量的平方和与拒绝工件的拒绝费用之和.这里每台机器上的负载量是指该台机器上加工的工件的加工时间之和.我们采用Graham等人[9]提出的排序记号，该问题可以被记为此处为公式
　　首先，我们证明了当机器台数m是固定的常数(甚至m=1)时，该问题在一般意义下是 NP-困难的；当机器台数 m是任意的参数时，该问题是强NP-困难的.其次，当机器台数 m为是固定的常数时，我们给出了一个拟多项式时间的最优算法；特别地，当工件加工时间相同的时候，上述动态规划算法可以在多项式时间内得到该问题的一个最优排序.当机器台数 m是任意的参数时，我们给出了一个有效的近似算法.最后，当机器台数 m是固定的常数时，我们给出了一个全多项式时间近似方案.
　　(2)最小化最大加权完工时间的工件可拒绝单机排序问题.
　　该排序问题可以被描述如下：有一台机器和 n个工件J1，J2,…,Jn.每个工件 Jj都有一个加工时间pj,一个拒绝费用ej以及一个权重wj.工件Jj或者被接收并被安排在机器上加工，或者被拒绝并支付一个相应的拒绝费用ej.目标函数是最小化最大加权完工时间与拒绝工件的拒绝费用之和.我们采用Graham等人[9]提出的排序记号，该问题可以被记为此处为公式
　　首先，我们证明了该问题是NP-困难的；其次，我们给出了一个拟多项式时间算法.特别地，当工件加工时间相同的情形下，该问题是多项式时间可解的.最后，我们也给出了一个近似算法.

目录

声明

第一章引言

§1.1 排序问题介绍

§1.2 定义和记号

§ 1.3相关文献综述

§ 1.4本文主要结果

第二章最小化机器负载量平方和的工件可拒绝平行机排序问题

§2.1 引言

§2.2 NP -困难性证明

§ 2.3动态规划算法

§ 2.4近似算法

§ 2.5全多项式时间近似方案

第三章最小化最大加权完工时间工件可拒绝单机排序问题

§ 3.1引言

§3.2 NP -困难性证明

§3.3 动态规划算法

§ 3.4近似算法

后记

参考文献

致谢