若干供应链排序问题的算法研究

发布时间：2017-07-06 11:25

  本文关键词：若干供应链排序问题的算法研究

  更多相关文章： 供应链排序 加工和运输 动态规划算法 算法复杂度 近似比

【摘要】：供应链排序是研究供应链管理中加工、分批和运输集成的排序模型、复杂性及其算法。本文主要研究了单机和平行机上,运输机数量和容量有限制或不受限制的供应链排序问题。 在单机环境下,我们研究了两个供应链排序问题。对单客户、运输机数量和容量不受限制的情形,我们研究了工件有不同到达时间、加工可中断、以最大延迟加运输费用为目标的问题,给出了复杂度为O(n3)的最优算法。对单客户、运输机数量和容量有限制的情形,我们考虑了机器在加工过程需要安排维护区间,使得机器连续加工的时间不超过T。我们以车辆运完最后一批工件返回制造商处的时间为目标,对问题给出了2-近似算法。 在平行机环境下,我们研究了运输机数量和容量不受限制的三个供应链排序问题。首先,我们研究了以最大延迟加运输费用为目标的两个问题。对单客户情形,我们研究了工件有不同到达时间、加工不可中断的问题,设计了渐近最优的近似算法。对多客户情形,我们研究了工件在零时刻就绪、加工不可中断的问题,设计了渐近最优的近似算法。然后,我们研究了在单客户情形下,工件有不同到达时间、以送货时间和加运输费用为目标的供应链排序问题,设计了近似比为3-1的算法。
【关键词】：供应链排序 加工和运输 动态规划算法 算法复杂度 近似比
【学位授予单位】：华东理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223
【目录】：

• 摘要5-6
• Abstract6-9
• 第1章 绪论9-19
• 1.1 排序问题9-10
• 1.2 供应链排序问题10-17
• 1.2.1 供应链排序问题的模型10-12
• 1.2.2 供应链排序问题研究综述12-17
• 1.3 本文的研究内容17-19
• 第2章 单机可中断以L_(max)+TC为目标的问题19-22
• 2.1 问题描述19
• 2.2 算法设计和分析19-22
• 2.2.1 最优性质20-21
• 2.2.2 算法设计21
• 2.2.3 算法复杂性21-22
• 第3章 平行机不可中断以L_(max)+TC为目标的问题22-29
• 3.1 问题描述22-23
• 3.2 问题P_m|r_j|V(∞,∞)|1|L_(max)+TC的近似算法23-25
• 3.2.1 算法设计23
• 3.2.2 算法性能分析23-25
• 3.3 问题P_m||V(∞,∞)|k|L_(max)+TC的近似算法25-29
• 3.3.1 算法设计25-26
• 3.3.2 算法性能分析26-29
• 第4章 平行机不可中断以∑D_j+TC为目标的问题29-34
• 4.1 问题描述29-30
• 4.2 3-1-近似算法30-34
• 4.2.1 算法设计30-31
• 4.2.2 算法性能分析31-34
• 第5章 具有可选维护区间的单机排序问题34-45
• 5.1 单机可选维护区间的加工排序问题34-39
• 5.1.1 算法设计35-36
• 5.1.2 算法性能分析36-39
• 5.2 单机可选维护区间的集成排序问题39-45
• 5.2.1 算法设计40-43
• 5.2.2 算法性能分析43-45
• 第6章 总结与展望45-46
• 参考文献46-49
• 致谢49

【参考文献】

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

1 陈荣军;唐国春;;平行机物流排序的近似算法[J];应用数学学报;2011年06期

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

1 仲维亚;供应链管理中的若干排序问题研究[D];浙江大学;2008年

，

本文编号：526030