工件可拒绝的单机重新排序问题

摘要

在本文中，我们考虑了工件可拒绝的单机重新排序问题．假设有一批初始工件已经被排好顺序准备加工，然而，在开始加工之前，又有一批新工件到达，此时，生产商需要对所有工件重新排序，将新工件插入到初始工件中进行加工，但是，这样可能会影响初始工件的加工位置以及开工时间，生产商为了保证初始工件对应顾客的利益，往往会要求初始工件保持相对顺序不变并且尽可能少的推后，即要求满足一定的(位置或者时间)错位约束条件．所以，本文主要研究在满足错位约束条件下最小化某些目标函数的重新排序问题．进一步，我们也假设新工件允许拒绝，若新工件集中的工件被拒绝那么我们要支付一个相应的拒绝费用．我们的目标是使给定的目标函数f与被拒绝工件的总拒绝费用之和达到最小，其中f为所有加工工件的排序目标函数，这里我们要求仅有新工件是允许拒绝的且f∈{Cmax，Lmax，∑Cj}，我们也把错位值γ作为约束的目标，其中γ∈{Dmax，∑Dj，△max，∑△j}．这里DmaX为初始工件的最大位置错位，∑Dj为初始工件总的位置错位，△max为初始工件的最大时间错位，∑△j为初始工件总的时间错位，本篇文章将带有错位约束条件的重新排序问题与工件可拒绝相结合．我们用rej表示新工件允许被拒绝，用γ≤k表示初始工件相应的（位置或者时间）错位不超过k．相应的问题可以表示成为1|γej，γ≤k|f+∑j∈RN ej,这里RN是新工件中被拒绝的工件集合． (1)在第二章中，我们研究了单机排序问题1|γ，rej，γ≤k|Cmax+∑j∈RN ej. 当γj=0时，所有接收的新工件都可以在初始工件之后加工，因此，所有的排序问题1|rej，γ≤k|Cmax+∑j∈RN ej是多项式时间可解的，当γj≠0时，我们证明了该问题是一般NP-困难的并且给出了一个拟多项式时间的动态规划算法．进一步，我们也给出了一个2一近似算法和FPTAS. (2)在第三章中，我们研究了单机排序问题1|rej，γ≤K|∑Cj+∑j∈RN ej. 针对每一个问题1|rej，γ≤K|∑Cj+∑j∈RN ej，当γ∈{△max，∑△j}，我们证明了它们都是一般NP-困难的并且给出了一个拟多项式时间的动态规划算法．当γ∈{Dmax，∑Dj）时，给出了一个多项式时间算法． (3)在第四章中，我们研究了单机排序问题1|rej，γ≤k|Lmax+∑j∈RN ej． 我们系统分析了问题1|rej，γ≤k|Lmax+∑j∈RN ej的计算复杂性，我们证明了，当γ∈{Dmax，△max，∑Dj）时，每一个问题都是一般NP-困难的并且给出了一个动态规划算法，然而，当γ=∑△j时，问题1|rej，∑△j(π*)≤k|Lmax+∑j∈RN ej是强NP-困难的．因此，该问题不存在任何拟多项式时间算法．

目录

声明

第一章 引言

§ 1.1 问题背景

§ 1.2 定义及相关符号

§ 1.3 研究方法

§ 1.4 相关文献综述

§ 1.5 本文的主要结果

第二章 目标为Cmax+∑j∈RN ej且新工件可拒绝的重新排序问题

§ 2.2 动态规划算法

§ 2.3 近似算法

§ 2.4 FPTAS

第三章 目标为∑Cj+∑j∈RN ej且新工件可拒绝的重新排序问题

§ 3.2 问题 1|rej,Dmax(π*)≤k|∑Cj+∑j∈RN ej

§ 3.3 问题 1|rej,Δmax(π*)≤k|∑Cj+∑j∈RN ej

§ 3.4 问题 1|rej,ΣΔj(π*)≤k|∑Cj+∑j∈RN ej

§ 3.5 问题 1|rej,ΣDj(π*)≤k|∑Cj+∑j∈RN ej

第四章 目标为Lmax+∑j∈RN ej且新工件可拒绝的重新排序问题

§ 4.2 问题 1|rej,Dmax(π*)≤k|Lmax+∑j∈RN ej

§ 4.3 问题 1|rej,Δmax(π*)≤k|Lmax+∑j∈RN ej

§ 4.4 问题 1|rej,ΣΔj(π*)≤k|Lmax+∑j∈RN ej

§ 4.5 问题 1|rej,ΣDj(π*)≤k|Lmax+∑j∈RN ej

结论

参考文献

致谢