几类加工时间可变的单机排序问题

发布时间：2017-04-28 04:01

  本文关键词：几类加工时间可变的单机排序问题，由笔耕文化传播整理发布。

【摘要】：本文考虑几类加工时间可变的单机排序问题,详述如下：首先,第一章介绍排序问题的研究背景、研究现状及研究内容。其次,第二章针对带有学习效应、加工时间可控和退化工件在单机环境下进行了研究,目标为确定工件最优排序、最优加工时间和最优资源分配量,将最大完工时间、总完工时间、完工时间差和资源消耗的费用之和进行极小化。考虑了学习因子与工件有关的线性资源函数,学习效应与工件的实际加工时间依赖开始时间结合在一起的凸资源函数两种情况,通过分析最优解的一些重要性质,将这两个问题分别转化为指派问题,给出了两个计算复杂性为O(n3)的最优算法。再次,第三章针对带有配送时间、加工时间与位置相关和多个工期在单机问题下进行研究。假设工件配送时间与工件等待时间成比例,将带有配送时间和加工时间依赖位置的单机排序问题与多个工期的单机排序问题结合成新的模型。首先分析了此类问题相关重要的性质;然后将这个问题转化为一个指派问题,证明出这个问题可以在多项式时间内可以解决的;最后,通过复杂性为O(n3)的算法,确定了最优排序、最优工期和极小化工件的提前、延误和工期的总费用。然后,第四章研究了带有分段线性递减加工时间和拒绝工件的单机排序问题。在这一模型中,工件的实际加工时间是关于开始时间的分段线性递减函数,目标是使被接受工件最大完工时间与被拒绝工件总惩罚达到最优的值,即最小值。该问题为NP难的问题。在对此问题的分析的基础上,设计了一个全多项式近似策略。全多项式近似策略的计算复杂性为O(n4L4/ε3)。最后,对本文的主要结论进行归纳总结。
【关键词】：加工时间可控 加工时间依赖位置 分段线性递减 拒绝 全多项式近似策略
【学位授予单位】：沈阳师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：F224;F273
【目录】：

• 摘要3-4
• Abstract4-7
• 第一章 绪论7-10
• 一、排序问题简介7
• 二、排序问题的三参数表示法7-8
• 三、相关问题研究现状8-9
• 四、本文主要工作9-10
• 第二章 带有学习效应的加工时间可控退化工件单机排序问题10-18
• 一、引言10
• 二、问题描述10-11
• 三、加工时间是线性资源函数11-14
• 四、加工时间是凸资源函数14-17
• 五、小结17-18
• 第三章 带有配送时间和加工时间依赖位置的多个工期的单机排序问题18-25
• 一、引言18
• 二、问题描述18-19
• 三、主要结论19-24
• 四、小结24-25
• 第四章 带有分段线性递减加工时间和拒绝工件的单机排序问题25-34
• 一、引言25
• 二、问题描述25-26
• 三、全多项式近似策略26-33
• 四、小结33-34
• 结论34-35
• 参考文献35-39
• 致谢39-40
• 个人简历40
• 在学期间的研究成果和发表的学术论文40

【参考文献】

中国期刊全文数据库 前5条

1 王吉波;牛玉萍;刘璐;郭倩;;同时具有学习和恶化效应的不同工期指派问题研究[J];沈阳师范大学学报(自然科学版);2014年03期

2 陈东;赵传立;;带有交货期窗口和工件可拒绝的单机排序问题[J];重庆师范大学学报(自然科学版);2013年06期

3 张敏娇;罗成新;;带有退化工件和机器维修区间的单机排序问题[J];沈阳师范大学学报(自然科学版);2013年03期

4 范雁鹏;赵传立;;带有交货期和加工时间可控的单机排序问题[J];重庆师范大学学报(自然科学版);2013年03期

5 刘澈;罗成新;;带到达时间、不可用区间、拒绝工件的单机排序问题[J];重庆师范大学学报(自然科学版);2013年01期

  本文关键词：几类加工时间可变的单机排序问题，由笔耕文化传播整理发布。

，

本文编号：332043