带不可用时间段的若干单机供应链排序问题的算法研究

发布时间：2017-10-26 23:28

  本文关键词：带不可用时间段的若干单机供应链排序问题的算法研究

  更多相关文章： 供应链排序 不可用时间段 可恢复 不可恢复 近似算法

【摘要】：本文主要对单台机器环境下有不可用时间段的供应链排序问题进行了研究。这类排序问题同时考虑了工件的加工与运输,目标均为最小化总发送时间与总运输费用之和。我们从机器有一个不可用时间段开始,由单个客户到多个客户,工件的加工时间由确定的到与开工时间有关,运输工具由容量无限制到容量有限制,再到机器有多个不可用时间段的情形,分别进行了深入研究。全文由五章组成。第一章介绍了与本文相关的一些排序问题的基本概念和定义,总结了供应链排序问题的研究现状,以及机器有不可用时间段的排序问题的一些概念及研究进展。第二章研究了运输工具数量充足、容量无限制的单机供应链排序问题。由于机器有一个不可用时间段,工件的加工过程可能被中断。当机器重新可用时,工件的加工有两种情况,一种情况是加工可恢复,即工件可继续完成加工；另一种情况是加工不可恢复,即工件需要重新开始加工。多个完成加工的工件可组成一批由运输工具运输给一个客户。当工件的加工可恢复时,我们给出了最优算法,其时间复杂性为O(n2)；当工件的加工不可恢复时,我们提出了3/2-近似算法,并进一步设计了多项式时间近似方案(PTAS)。第三章主要讨论了运输工具数量充足、但容量受限制的单机供应链排序问题。工件完工后发送给多个客户,目标函数为最小化总发送时间与总运输费用之和。我们分别研究了工件的加工可恢复及不可恢复两种情况,而且运输工具发送工件也有直接发送和选路线发送两种方式。这里直接发送是指某客户的工件完工后直接从生产工厂发送给该客户；而选路线发送是指运输工具发送的一批工件中有多个客户的工件,可以选择一条路线依次将工件发送给客户。当工件的加工可恢复时,我们分别就运输工具直接发送及选路线发送工件两种情形,在得到最优加工序的基础上,分别提出了动态规划算法得到最优发送序；当工件的加工不可恢复、运输工具直接发送工件时,我们提出了耗时短易操作的近似算法,该算法是2μ-近似算法,这里μ-min{c,1+(1-1/c)Σλi/λmin},其中c表示运输工具的容量,入m。n表示运输一批工件的最少费用；当工件的加工是不可恢复、运输工具选路线发送工件时,我们基于工件的加工是可恢复的最优序,提供了2-近似算法。第四章研究的是工件带恶化效应的单机供应链排序问题。工件的加工是不可恢复的,工件的实际加工时间与恶化率、开工时间有关,并且在不可用时间段之前完工的工件必须在不可用时间段之前发送给客户。我们证明问题是NP-难的,并在分析问题最优序性质的基础上,提出了伪多项式时间的动态规划算法。进一步地,我们确定了问题目标函数值的上界及下界,并得到了问题的完全多项式时间近似方案(FPTAS)。第五章主要研究了机器有多个不可用时间段的单机供应链排序问题。这个问题起源于医院仓库的医用耗材的物流管理。医用耗材需要用打包机打包后配送给医院各科室。有的打包过程可中断,而有的打包过程是不可中断的,否则会使某些材料受到污染。配送需要由仓库付费。仓库经理希望高效利用打包机,同时希望降低配送成本。如果我们将实际问题中的打包机视为一台机器,将医用耗材视为工件,那么问题即转化为供应链排序问题。对于机器有周期性不可用时间段,工件的加工不可恢复,完工工件成批地由一个无容量限制的运输工具发送至多个客户,运输工具的运输时间固定在每个可用时间段结束时间的问题,我们证明该问题是强NP-难的,并提出了2-近似算法,以及可求得问题最优解的分支定界算法。通过随机生成实例所做的数值模拟,我们可以看到,近似算法是有效的算法。对于机器的可用时间段不可超过某固定值,运输工具的发送时间不受限制的问题,若工件加工可恢复,我们可在多项式时间内得到最优序；若工件加工不可恢复,我们证明问题是强NP-难的,并提出了一个2-近似算法。
【关键词】：供应链排序 不可用时间段 可恢复 不可恢复 近似算法
【学位授予单位】：华东理工大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O223
【目录】：

• 摘要5-7
• Abstract7-12
• 第1章 绪论12-26
• 1.1 排序问题12-13
• 1.2 算法及计算复杂性13-15
• 1.3 NP问题15-18
• 1.4 供应链排序问题简介18-21
• 1.5 机器有不可用时间段的排序问题21-23
• 1.6 论文概述23-26
• 第2章 运输工具容量无限制的单客户供应链排序问题26-40
• 2.1 引言26
• 2.2 问题描述26-27
• 2.3 工件加工可恢复的情形27-29
• 2.4 工件加工不可恢复的情形29-40
• 2.4.1 问题的一些性质29-30
• 2.4.2 近似算法30-36
• 2.4.3 多项式时间近似方案(PTAS)36-40
• 第3章 运输工具容量有限制的多客户供应链排序问题40-56
• 3.1 引言40-41
• 3.2 问题描述及符号说明41-42
• 3.3 工件加工可恢复的情形42-46
• 3.3.1 运输工具直接发送43-45
• 3.3.2 运输工具选路线发送45-46
• 3.4 工件加工不可恢复的情形46-56
• 3.4.1 运输工具直接发送46-52
• 3.4.2 运输工具选路线发送52-56
• 第4章 工件具有恶化效应的单机供应链排序问题56-64
• 4.1 引言56-57
• 4.2 问题描述及符号说明57
• 4.3 求解问题57-64
• 4.3.1 问题的性质58-59
• 4.3.2 动态规划算法59
• 4.3.3 完全多项式近似方案(FPTAS)59-64
• 第5章 单机带多个不可用时间段的供应链排序问题64-82
• 5.1 引言64-65
• 5.2 不可用时间段具有周期性的供应链排序问题65-73
• 5.2.1 问题描述及符号说明65-66
• 5.2.2 问题的复杂性分析66-67
• 5.2.3 近似算法67-71
• 5.2.4 分支定界算法71-73
• 5.2.5 数值模拟73
• 5.3 可用时间段不超过固定值的供应链排序问题73-82
• 5.3.1 问题描述及符号说明73-76
• 5.3.2 工件加工可恢复的情形76-77
• 5.3.3 工件加工不可恢复的情形77-82
• 第6章 结论与展望82-84
• 参考文献84-94
• 致谢94-96
• 附录：博士在读期间发表的论文96

【相似文献】

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

1 马英;左春荣;杨善林;;带不可用时间段和恶化加工时间的单机调度[J];系统工程学报;2010年03期

2 马英;杨善林;储诚斌;;带不可用时间段的部分可续型单机最大完工时间调度[J];系统工程理论与实践;2009年04期

3 马英;左春荣;杨善林;;带不可用时间段的两台同类机加权完工时间和调度[J];中国科学技术大学学报;2009年06期

4 王海明;刘吉红;王庆磊;;带不可用时间段的不允许等待柔性流水排序问题[J];兰州大学学报(自然科学版);2007年01期

5 ;[J];;年期

中国博士学位论文全文数据库 前1条

1 范静;带不可用时间段的若干单机供应链排序问题的算法研究[D];华东理工大学;2015年

，

本文编号：1100971