论文摘要
排序问题一直受到国际学术界的重视,其中分批排序问题,因其明显的实际意义,更是吸引了国内外许多学者。本文主要考虑了两个单机分批排序问题。用国际上常用的三参数表示法可写为:1|B,sj,rj|Cmax和1|B,rj|Lmax。论文分三章叙述。 第一章是引言,主要介绍了排序的产生背景、发展及其一些相关的知识。 在第二章中,我们主要讨论了工件有到达时间和尺寸的单机分批排序问题1|B,rj,sj|Cmax。对于这一类问题,国内外很多学者做了大量的研究工作。目前最好的成果是李曙光等提出的2近似算法。我们所考虑的问题和李曙光等所研究的略有不同之处,本文严格限制机器的容量B是和问题规模无关的常量。就最差性能比方面来说,我们得出了更好的研究结果。我们分三种情况考虑: （1）对于大工件（工件的尺寸严格大于机器容量的1/2）的加工时间不小于小工件（工件的尺寸小于或等于机器容量的1/2）的加工时间的特定情形,利用动态规划的方法和拆分的技巧,我们提出了最差性能比为3/2+∈的多项式时间近似算法,此处∈为任意小的正数。除非P=NP,否则这个问题在此情形下不存在最差性能比小于3/2+∈的近似算法。 （2）关于这个问题的一般情形,我们在改进了单机分批排序问题1|B,sj|Cmax的7/4近似算法的基础上,提出了最差性能比为7/4+∈的多项式时间近似算法。 （3）最后指出上述结果在m台同型机的情况下仍然成立。 在第三章中,我们主要讨论了工件有到达时间的目标函数是极小化最大延误时间的单机分批排序问题1|B,rj|Lmax。有大量的文献对这个问题的特殊情形展开了讨论和分析。在机器的容量B充分大时,这是个NP-难的问题,已经有人给出了PTAS算法和时间复杂性较好的伪多项式时间算法;但对于机器的容量B
论文目录
相关论文文献
- [1].目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报 2019(04)
- [2].具有时间与位置相关的两类平行机排序问题[J]. 运筹学学报 2019(04)
- [3].基于Flexsim的零件加工排序仿真实现方法研究[J]. 新技术新工艺 2020(02)
- [4].总加权误工损失的两个代理单机排序问题[J]. 湖北民族学院学报(自然科学版) 2019(01)
- [5].机器带周期性维护时段的加工与运输协同排序问题[J]. 浙江理工大学学报(自然科学版) 2016(06)
- [6].带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报 2016(04)
- [7].具有维护活动及公共工期的加工时间依赖资源的单机排序问题[J]. 沈阳航空航天大学学报 2016(06)
- [8].关于工期分配与加权误工数的双指标排序问题（英文）[J]. 工程数学学报 2017(01)
- [9].带有交货期窗口和加工时间可控的排序问题[J]. 沈阳师范大学学报(自然科学版) 2016(04)
- [10].具有学习效应和遗忘效应的单机排序问题研究[J]. 枣庄学院学报 2017(02)
- [11].资源定时投放的单机排序问题[J]. 杭州电子科技大学学报(自然科学版) 2017(02)
- [12].有公共交货期的单机分批排序问题（英文）[J]. 重庆师范大学学报(自然科学版) 2017(02)
- [13].在退化维修活动下具有多窗口及退化效应的单机排序问题[J]. 重庆师范大学学报(自然科学版) 2017(03)
- [14].一类资源费用可变的平行机排序问题[J]. 上海第二工业大学学报 2017(02)
- [15].数学规划与约束规划整合下的多目标分组排序问题研究[J]. 运筹学学报 2016(01)
- [16].具有学习效应的排序问题的某些新进展[J]. 沈阳师范大学学报(自然科学版) 2014(04)
- [17].有界平行批处理机的在线排序问题[J]. 河南师范大学学报(自然科学版) 2015(05)
- [18].集思[J]. 福建教育 2020(25)
- [19].高中数学一道数列典型题解法的探究[J]. 数学学习与研究 2016(23)
- [20].单机排序问题的研究[J]. 数学学习与研究 2017(24)
- [21].一个排序问题的解决[J]. 中等数学 2009(07)
- [22].具有多个制造商和分批配送的同类机排序问题[J]. 系统科学与数学 2019(09)
- [23].工件具有加工位置上限最小化加权总误工量的单机排序问题（英文）[J]. 运筹学学报 2020(02)
- [24].具有恶化效应与可控加工时间的工期指派排序问题研究[J]. 沈阳航空航天大学学报 2019(05)
- [25].优化交货期窗口的两阶段供应链排序问题[J]. 运筹学学报 2016(04)
- [26].具有公共流、退化效应与维护和资源分配的单机窗口排序问题[J]. 沈阳航空航天大学学报 2016(05)
- [27].关于总误工损失的两个代理单机排序问题[J]. 运筹学学报 2017(01)
- [28].具有不同生产时区费用的单机可拒绝排序问题[J]. 数学的实践与认识 2017(04)
- [29].具有柔性维护周期的单机误工排序问题[J]. 杭州电子科技大学学报(自然科学版) 2017(03)
- [30].带有多个工期窗口及退化维护的单机排序问题[J]. 重庆师范大学学报(自然科学版) 2017(03)