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

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1引言

1.2基本概念

1.3 本文所研究问题的应用背景与研究现状

1.4 本文的主要工作

第2章 极小化最大完工时间分批加工、分批配送的供应链排序问题

2.1 问题描述

2.2 符号说明

2.3 多项式可解情形

2.4 一般情形

2.5 本章小结

第3章 极小化最大完工时间分批的供应、加工、配送供应链排序问题

3.1符号说明

3.2 问题描述

3.3 多项式可解情形

3.4 一般情形

3.5 本章小结

参考文献

在读期间发表的学术论文及研究成果

致谢