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

论文摘要

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

论文目录

• 摘要
• Abstract
• 第一章 引言
•   §1.1 问题背景
•   §1.2 定义及相关符号
•   §1.3 研究方法
•   §1.4 相关文献综述
•   §1.5 本文的主要结果
• max+∑_j∈RNe_j且新工件可拒绝的重新排序问题'>第二章 目标为C_max+∑_j∈RNe_j且新工件可拒绝的重新排序问题
•   §2.1 引言
•   §2.2 动态规划算法
•   §2.3 近似算法
•   § 2.4 FPTAS
• j+∑_j∈RNe_j且新工件可拒绝的重新排序问题'>第三章 目标为∑C_j+∑_j∈RNe_j且新工件可拒绝的重新排序问题
•   §3.1 引言
• max（π^*）≤k|∑C_j+∑_j∈RNe_j'>  §3.2 问题1|rej,D_max（π^*）≤k|∑C_j+∑_j∈RNe_j
• max（π^*）≤k|∑C_j+∑_j∈RNe_j'>  §3.3 问题1|rej,△_max（π^*）≤k|∑C_j+∑_j∈RNe_j
• j（π^*）≤k|∑C_j+∑_j∈RNe_j'>  §3.4 问题1|rej,∑△_j（π^*）≤k|∑C_j+∑_j∈RNe_j
• j（π^*）≤k|∑C_j+∑_j∈RNe_j'>  §3.5 问题1|rej,∑D_j（π^*）≤k|∑C_j+∑_j∈RNe_j
• max+∑_j∈RNe_j且新工件可拒绝的重新排序问题'>第四章 目标为L_max+∑_j∈RNe_j且新工件可拒绝的重新排序问题
•   §4.1 引言
• max（π^*）≤k|L_max+∑_j∈RNe_j'>  §4.2 问题1|rej,D_max（π^*）≤k|L_max+∑_j∈RNe_j
• max（π^*）≤k|L（max）+∑_j∈RNe_j'>  §4.3 问题1|rej,△_max（π^*）≤k|L（max）+∑_j∈RNe_j
• j（π^*）≤k|L_max+∑_j∈RNe_j'>  §4.4 问题1|rej,∑△_j（π^*）≤k|L_max+∑_j∈RNe_j
• j（π^*）≤k|L_max+∑_j∈RNe_j'>  §4.5 问题1|rej,∑D_j（π^*）≤k|L_max+∑_j∈RNe_j
• 结论
• 参考文献
• 致谢

文章来源

类型: 硕士论文

作者: 丛稳

导师: 录岭法

关键词: 重新排序,位置错位,时间错位,拒绝费用,困难,动态规划

来源: 郑州大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 郑州大学

分类号: O223

总页数: 46

文件大小: 1739K

下载量: 26