具有错位限制的重新排序问题研究

论文摘要

重新排序起源于机器的生产行业,并迅速在生产管理、交通运输、计算机领域开枝散叶。在实际的加工生产中,生产者通常在加工之前会按照某种最优的目标制定计划,但在还没有开始加工之前可能会到达新的订单,或者取消订单,工期推迟,机器故障等原因而扰乱先前的计划。此时,决策者必须重新制定计划尽可能使得目标函数最优。本文的内容分两部分。研究了加权序列错位以及加权时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化总延误时间问题。研究了工件性质为退化工件,约束条件为工件的位置错位或者工件的时间错位,目标为总完工时间最小化和最大延迟最小化的重新排序问题。当工件的实际加工时间是启动时间的非递减函数时,称工件具有退化效应。对于以上两类问题,当权重系数或者错位限制满足某种特殊情况时,最优排序是原始工件集和新工件集中的工件按照退化率非减的序列排列。在动态规划方法的基础上,给出了以上几个模型的多项式时间算法或者拟多项时间算法,并给出了算法时间复杂度。第二部分中,研究了最小化最大加权误工的重新排序问题。研究了在时间错位和的限制条件下以及工件的时间错位的限制条件下,最大加权误工的最小化问题。对于以上两类问题,利用三划分的思路,给出了强NP-困难性的证明。另外给出了单机情况下无约束条件的加权误工问题的最优算法,并利用列举法证明了该问题的最优性,在该算法的基础上设计了对于时间错位限制条件下,最小化最大加权误工的启发式算法,并给出实例验证其可行性,最后利用不可近似性的思维方法对启发式算法进行证明。

论文目录

• 中文摘要
• 英文摘要
• 1 引言
•   1.1 重新排序问题产生的背景
•     1.1.1 重新排序问题中的符号介绍
•     1.1.2 本文用到的主要已知结果和相关概念
•   1.2 相关文献综述
•   1.3 本文的创新点
•   1.4 本文的主要结果
• 2 具有错位限制且工件可退化的单机重新排序问题
•   2.1 错位限制下含有退化工件的最小化完工时间
•   2.2 最小化总延误时间问题
•   2.3 工件错位限制以及时间错位限制下的重新排序
•   2.4 本小节主要内容
• 3 最小化最大加权误工的重新排序问题
•   3.1 时间错位和限制条件下加权误工重新排序问题
•   3.2 工件的时间错位限制条件下加权误工重新排序问题
•   3.3 本小节主要内容
• 4 结论与展望
• 参考文献
• 附录A
• 致谢

文章来源

类型: 硕士论文

作者: 康宇红

导师: 张新功

关键词: 重新排序,时间错位,序列错位,退化工件,困难

来源: 重庆师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 重庆师范大学

分类号: O223

总页数: 45

文件大小: 1656K

下载量: 12