带有恶化效应的单机供应链排序问题

摘要

排序论是运筹学中最重要的分支之一。供应链排序是供应链管理与排序理论相结合产生的新领域,它将排序理论应用于供应链管理,集成研究生产调度和分批配送这两个问题。工件带有恶化效应的排序和工件可拒绝的排序是两种新兴起的现代排序模型,它们更接近现实生活,因而具有很好的研究价值。本文将上述三类排序问题相结合,讨论了几个相关的排序问题。论文主要结构安排如下：
　　第一章绪论部分主要介绍了供应链排序问题、带有恶化效应的排序问题、可拒绝排序,算法的复杂性以及本文所需要的基础知识,并对本文的主要工作进行了简要描述。
　　第二章主要研究了带有恶化效应的单机供应链排序问题：一个制造商为一个客户加工工件,每个工件的加工时间是其开工时间的简单线性增函数,工件加工完之后要安排车辆配送给客户,完工时间为工件送达客户的时刻。在同一辆车配送的工件为一批,每一批可同时配送至多n个工件,每配送一批要支付一定的配送费用。我们分析了加工时间为其开工时间的不同函数,目标函数分别为极小化总完工时间与总配送费用之和、极小化最大延误时间与总配送费用之和的情形,并分别给出了多项式时间的最优算法。
　　第三章在第二章的基础上研究了工件可拒绝的情形。一个制造商为一个客户加工工件,每个工件既可以被接受加工,也可以被拒绝加工。若工件被拒绝,则要支付一定的拒绝费用。若工件被接受,则其加工时间是其开工时间的简单线性增函数,且加工完之后要被安排在车辆运送给客户,完工时间为工件送达客户的时间。在同一辆车配送的工件为一批,每配送一批要支付一定的配送费用,每一批可同时配送至多n个工件。目标函数为极小化被接受工件的总完工时间、总配送费用和被拒绝工件的总拒绝费用三者之和,本文对这个问题给出了运行时间为多项式的动态规划算法。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

§1.1 排序问题

§1.1.1 供应链排序

§1.1.2 带有恶化效应的排序

§1.1.3 可拒绝排序

§1.2 算法和时间复杂性

§1.3 本文的主要工作

第二章 带有恶化效应的分批配送问题

§2.1 引言

§2.2 问题描述

§2.3 主要结果

§2.3.2 ? ?? ?? D Dyz n p a bt j jjj | ?,1|

§2.3.3 ? ? ? ?? D Dyz n p a bt jjjj |,1|

§2.3.4 Dy1|z?n, pj?aj?btj|Lmax?

§2.4 总结

第三章 带有恶化效应的可拒绝单机供应链排序问题

§3.1 引言

§3.2 问题描述

§3.3 主要结果

§3.4 总结

参考文献

附录一 攻读硕士期间撰写的论文

附录二 致谢