带有时间窗口约束的排序及相关问题研究

发布时间：2017-11-10 17:40

  本文关键词：带有时间窗口约束的排序及相关问题研究

  更多相关文章： 排序 时间窗口约束 近似算法 最坏情况分析

【摘要】：排序问题一直以来是经典组合优化问题之一,近几十年来,正被越来越广泛地应用于生产与制造领域。本论文研究了带有时间窗口约束的排序问题,可以被看作是一个新的资源约束模型,其在柔性制造系统和印刷电路板组件等方面具有潜在的应用。论文分为四章,重点研究了近似算法的设计与分析。第一章主要简要介绍了排序问题的一些相关知识和国内外研究的现状,提供了几个经典排序问题的复杂性及其算法,同时也对启发式算法与近似算法进行了一些简单介绍。第二章研究了带单位时间窗口约束的单机排序问题。要求任意单位时间内最多只允许B个工件进行加工,对B=2与B≥3两种情况分别设计了近似算法,并证明当B=2时,算法目标值τ(T)≤τ(S)+(1/2)（其中τ(S)为最优值);当B=3,4时,τ(T)≤(B/(B-1))τ(S)+2,当B≥5时,τ(T)≤(5/4)τ(S)+2。第三章在第二章的基础上,讨论了带单位时间窗口约束的两台平行机排序问题。要求任意单位时间内两台机器上最多允许B个工件进行加工。分析了LPT与LS两个经典算法的近似性能,当B=2时,对LS算法有τ(LS)≤(3/2)τ(OPT)+(1/2)以及τ(LS)≤2τ(OPT);对LPT算法有τ(LPT)≤(1+(1/n))τ(OPT)+(1/n)以及τ(LPT)≤(5/4)τ(OPT);而当B≥3时,对LS算法有τ(LS)≤((5/2)-(2/B))τ(OPT)+(1/2)。第四章研究了一类带外包选择的单机排序问题。假设仅有一台本地机器和一个外包承包商,每个工件既可以在本地机器上加工又可以外包商处加工。本地加工的费用为总误工工件数,外包加工的费用与外包工件有关。对于极小化总加工费用这一NP难问题,给出伪多项式时间动态规划算法。如果外包费用正比于外包工件的加工时间,设计出近似算法并给出最坏情况分析。第五章,我们对本文进行了归纳与总结,并对未来的相关研究工作作了展望。
【学位授予单位】：杭州电子科技大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O223

【参考文献】

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

1 陈荣军;唐国春;;平行机的排序与转包(英文)[J];数学季刊;2012年04期

2 仲维亚;刘晓蕾;霍志明;;工件可转包加工的排序问题研究[J];运筹学学报;2012年01期

3 ;TWO-STAGE PRODUCTION SCHEDULING WITH AN OPTION OF OUTSOURCING FROM A REMOTE SUPPLIER[J];Journal of Systems Science and Systems Engineering;2009年01期

4 王宇平,何文章;m×n排序问题在实际中的应用[J];数学的实践与认识;1990年04期

5 张正铀;;散列排序算法[J];广西科学院学报;1982年01期

6 越民义,韩继业;同顺序m×n排序问题的一个新方法[J];科学通报;1979年18期

7 秦裕瑗;;一个排序UO楲[J];武汉钢铁学院学报;1979年02期

8 常庆龙;以延误时间为指标的一台设备上的排序问题[J];数学的实践与认识;1978年02期

9 越民义,韩继业;排序问题中的一些数学问题[J];数学的实践与认识;1976年03期

10 越民义,韩继业;n个零件在m台机床上的加工顺序问题(Ⅰ)[J];中国科学;1975年05期

，

本文编号：1167688