分批的供应、加工、配送供应链排序问题

发布时间：2017-09-08 13:30

  本文关键词：分批的供应、加工、配送供应链排序问题

  更多相关文章： 排序 分批供应 分批加工 分批配送 多项式时间算法 近似算法 近似比

【摘要】：排序问题是一类重要的组合最优化问题,是在某些约束条件下合理安排工件在机器上的加工顺序从而使目标值达到最优.供应链排序则是将排序的方法应用到供应链管理上使生产、运输等过程得到整体优化.随着时代的发展和竞争的加剧,如何合理安排生产和运输使客户需求得到满足即提高服务水平变得尤为重要.本文研究了综合考虑原材料的供应、工件加工以及成品配送目标函数为极小化最大完工时间的供应链排序问题.文章结构安排如下：第一章,介绍了一些基本概念如：3-划分问题、算法的复杂性等,并对文中符号进行了说明,最后对本文所研究问题的产生背景、研究现状、研究成果进行简要阐述.第二章,研究了极小化最大完工时间分批加工、分批配送的供应链排序问题.制造商与客户都只有一个,制造商为一台容量为B的并行批加工机器;运输工具仅有一台且容量为K;共有n个工件需要加工和配送.可将整个调度过程划分为两个阶段：第一阶段工件在机器上进行加工,第二阶段运输工具将已完成加工的工件配送给客户.首先对K≥n的情况给出复杂性为O(nlog n)的多项式时间最优算法.然后对Kn的情况进行了分析;对K=B的情形给出复杂性为O(nlog n)的多项式时间最优算法;对两种特殊情形KB、KB分别给出复杂性为O(nB3 log n)、O(nB log n),近似比上界为3/2的近似算法.最后对问题的一般情形给出复杂性为O(nB3 log n)、近似比小于3/2的近似算法.第三章,研究了极小化最大完工时间分批的供应、加工、配送供应链排序问题.该问题在第二章所研究问题的基础上增加了一个供应商,可将该问题划分为三个阶段：第一阶段工件由一台容量为K1的运输工具将工件从供应商处运至制造商处,第二阶段工件在容量为B的并行批机器上进行加工,第三阶段容量为K2的运输工具将已完成加工的工件配送给客户.首先证明了该问题是强NP-难的,然后给出复杂性为O(nB3 log n)、近似比上界为5/2的近似算法,并对某些特殊情形给出多项式时间最优算法.
【关键词】：排序 分批供应 分批加工 分批配送 多项式时间算法 近似算法 近似比
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223
【目录】：

• 摘要3-4
• Abstract4-7
• 第1章 绪论7-11
• 1.1 引言7
• 1.2 基本概念7-9
• 1.3 本文所研究问题的应用背景与研究现状9-10
• 1.4 本文的主要工作10-11
• 第2章 极小化最大完工时间分批加工、分批配送的供应链排序问题11-23
• 2.1 问题描述11-12
• 2.2 符号说明12
• 2.3 多项式可解情形12-14
• 2.4 一般情形14-22
• 2.5 本章小结22-23
• 第3章 极小化最大完工时间分批的供应、加工、配送供应链排序问题23-29
• 3.1 符号说明23
• 3.2 问题描述23-24
• 3.3 多项式可解情形24-26
• 3.4 一般情形26-27
• 3.5 本章小结27-29
• 参考文献29-32
• 在读期间发表的学术论文及研究成果32-33
• 致谢33

【相似文献】

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

1 周泓,张惠民;求解多目标作业排序问题的遗传算法[J];系统工程理论与实践;2001年08期

2 周泓,姬彬;求解作业排序问题的通用混合遗传算法研究[J];系统工程理论与实践;2001年12期

3 陈德伍,张 峰;一类新的可控排序问题(英文)[J];运筹学学报;2001年04期

4 张瑞,刘国珍;单机排序问题最优解方法[J];聊城师院学报(自然科学版);2001年02期

5 黎群;单台机器多目标作业排序问题的探讨[J];系统工程理论方法应用;2001年02期

6 方保昒,徐汉忠;用单亲遗传算法解具有窗口式交货期的多机加工排序问题[J];系统工程理论方法应用;2001年04期

7 宋政芳,孙世杰,吴春燕;一个超前有奖迟后受罚的排序问题(英文)[J];运筹学学报;2002年04期

8 赵传立,唐恒永;具有相关调整时间的排序问题[J];沈阳师范学院学报(自然科学版);2002年01期

9 郑自途;关于"三台以上机床作业排序问题"的算法[J];天津理工学院学报;2002年04期

10 张玉忠,苗翠霞;复制法及其在分批排序问题中的应用[J];曲阜师范大学学报(自然科学版);2004年02期

中国重要会议论文全文数据库 前10条

1 柏孟卓;唐国春;;加工时间可控的同时加工排序问题[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

2 张莲珠;;关于六角链的极值和排序问题的一些结果[A];中国运筹学会第六届学术交流会论文集（上卷）[C];2000年

3 周支立;李怀祖;;有重叠区域的两抓钩周期性排序问题的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孙世杰;陈跃;;参数可控的排序问题[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

5 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

6 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

7 谭万达;;二元对比排序中的最少逆序原理[A];中国系统工程学会模糊数学与模糊系统委员会第五届年会论文选集[C];1990年

8 吕绪华;杨汉兴;;求解装配式排序问题的归并算法及其性能比研究[A];中国运筹学会第六届学术交流会论文集（下卷）[C];2000年

9 樊保强;;带仓储约束的准时排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

10 陈荣军;唐国春;;自由作业环境下的供应链排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

中国重要报纸全文数据库 前1条

1 山东 赵玉勇;数组，你的规律机器[N];电脑报;2004年

，

本文编号：814304