论文部分内容阅读
平行机排序问题是多处理机排序问题的一种情况,在理论及其应用过程中都有着重要的意义.从理论上来看,平行机排序问题是单机排序问题的推广;而从应用角度来看,它的研究与我们的生活息息相关,有着广泛的应用背景.本文我们主要研究工件可拒绝约束下的平行机排序问题. 第一章主要介绍一些排序问题的背景、近年来的研究现状以及相关的一些基础知识.然后简单介绍了一下本文的主要研究成果. 第二章主要研究同速机可拒绝的排序问题,主要分了三个模型: (1)工件不同时到达、可拒绝的同速机排序问题.在拒绝工件的惩罚费用之和不超过一给定上界 U的约束下,目标为极小化接受工件的最大完工时间.通过动态规划算法可在:此处公式省略时间内得到最优值,其中m是机器台数;n是工件个数;rmax表示工件的最大到达时间;pj是工件J j的加工时间,:此处公式省略表示所有工件的加工时间之和.此外,我们还给出了这一排序问题的一个FPTAS算法; (2)工件可拒绝的同速机排序问题.目标为极小化接受工件的最大延误与拒绝工件的惩罚费用之和.通过动态规划可在:此处公式省略时间内得到最优值,其中:此处公式省略表示工件Jj的惩罚费用; (3)工件可拒绝的同速机排序问题.在拒绝工件的惩罚费用之和不超过一给定上界U的约束下,目标为极小化接受工件的最大延误.通过动态规划算法可在)( mO mnUP时间内得到最优值. 第三章主要研究恒速机可拒绝的排序问题,主要分了四个模型: (1)工件不同时到达、可拒绝的恒速机排序问题.目标为极小化接受工件的最大完工时间与拒绝工件的惩罚费用之和.通过动态规划算法可在:此处公式省略时间内得到最优值,其中bi,(i=1,2,...,m)表示机器Mi的加工速度; (2)工件不同时到达、可拒绝的恒速机排序问题.在拒绝工件的惩罚费用之和不超过一给定上界 U的约束下,目标为极小化接受工件的最大完工时间.通过动态规划算法可在max:此处公式省略时间内得到最优值; (3)工件可拒绝的恒速机排序问题.目标为极小化接受工件的最大延误与拒绝工件的惩罚费用之和.通过动态规划算法可在:此处公式省略时间内得到最优值; (4)工件可拒绝的恒速机排序问题.在拒绝工件的惩罚费用之和不超过一给定上界U的约束下,目标为极小化接受工件的最大延误.通过动态规划算法可在:此处公式省略时间内得到最优值.