工件退化的在线排序问题研究

论文摘要

在传统的排序问题中,工件的加工时间是一个确定的常数.然而,在实际生活中,由于作业的某些特性,工件的加工时间在工件等待加工的过程中可能会发生退化.比如,大火在等待扑灭的过程中,火势会逐渐变大,被扑灭所需的时间就会变长.诸如此类的例子,在医疗、金融管理、钢铁制造、资源分配和国防等中都可以找到.因此,无论是在理论和实际应用中,带退化的排序问题都具有重要的意义和价值.因此,带退化的排序问题逐渐得到国内外研究者的广泛关注和深入研究.本文所研究的是单机上带退化的时间在线排序问题,即工件随着时间的推进依次到达,且在工件到达之前,排序者对将来的信息一无所知.此外,对任意一个工件Jj,它的加工时间pj是其开工时间Sj的简单线性函数,即pj=bjSj,这里b>0是工件Jj的退化率.全文共分为五章,主要对简单线性退化工件在单机上的带拒绝在线排序和DSGR算法进行了研究.第一章首先对排序问题进行了简单的介绍,然后依次对在线排序问题、退化工件的排序问题以及带拒绝的排序问题的发展概况进行了简述.第二章对文章所涉及的一些基础定义,如竞争比、下界、三参数表示法等,以及关于DSGR算法和SRDR算法一些结论进行了详细地阐述.第三章考虑了简单线性退化工件的带拒绝在线排序问题,即每个工件都具有拒绝惩罚ej,且服从AGREEABLE条件,即对任意的两个工件Ji和Jj,如果bi<bj,那么ei≥ej;如果bi=bj且<rj,那么ei ≥ej.排序者在选择工件进行加工时,或者拒绝工件并为此承担一定的惩罚,或者加工工件.问题的目标函数是最小化被加工工件的总完工时间以及被拒绝工件的总拒绝惩罚.对于此问题,我们给出了竞争比是1+bmax的最好可能的在线算法DSGRR,其中bmax亦是所有工件中最大的退化率.第四章给出了 DSGR算法最优性的另外一种证明方法.DSGR算法是由Liu等人给出的关于简单线性退化工件在单机上的在线排序问题的最好可能的在线算法,且算法的竞争比是1+bmax,其中bmax代表所有工件中最大的退化率.最后一章主要对文章的内容及创新点进行了概述,并展望了未来的研究方向.

论文目录

致谢

摘要

Abstract

1 绪论

1.1 排序问题简介

1.2 排序问题的发展概述

1.2.1 在线排序问题

1.2.2 退化工件的排序问题

1.2.3 带拒绝的排序问题

1.3 文章结构及主要研究结果

2 预备知识

2.1 基本定义

2.1.1 竞争比

2.1.2 算法下界

2.1.3 三参数表示法

2.1.4 决策时刻

2.1.5 退化工件

2.1.6 可用工件

2.1.7 最小反例

2.2 引理

3 退化工件在单机上的带拒绝在线排序

3.1 引言

3.2 DSGRR算法

3.3 DSGRR算法的竞争比分析

4 关于DSGR算法的另一种证明

4.1 引言

4.2 DSGR算法的竞争比分析

5 总结与展望

5.1 总结

5.2 创新与特色

5.3 展望

参考文献

作者简历

学位论文数据集

文章来源

类型: 硕士论文

作者: 刘辉冉

导师: 马冉

关键词: 排序,在线算法,退化,拒绝,竞争比

来源: 河南理工大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 河南理工大学

基金: 国家自然科学基金(11501171)

分类号: O223

DOI: 10.27116/d.cnki.gjzgc.2019.000283

总页数: 52

文件大小: 1717K

下载量: 10

工件退化的在线排序问题研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢