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