论文摘要
排序问题是一类经典的组合优化问题,从上世纪50年代至今受到了许多行业的从业人员与理论研究者的密切关注。本文主要研究排序问题在供应链管理中的应用。众所周知,供应链是由多个环节构成的,因此我们不能孤立地研究排序问题,而要把排序问题与其它过程综合考虑。全文共分四章。第一章主要介绍了供应链与排序问题的一些知识和概念,并且总结了近些年来在综合考虑排序与运输的问题研究方面取得的一些成果。第二章研究工件占用运输工具空间不同的综合考虑运输和排序的问题。在这类问题中,工件在机器上完成加工后,需要由唯一的一辆运输工具运送到相应的顾客处。运输工具的空间是有限的,每个工件占用运输工具的空间各不相同。目标函数是极小化最后一个到达顾客的工件的到达时间。当机器环境是单台机,所有工件的顾客相同时,我们设计了最坏情况界为3/2+ε（ε是任意正常数）的渐近最优算法。当机器环境是两台平行机,所有工件的顾客相同时,我们给出了了最坏情况界为5/3的近似算法。第三章讨论了允许在两个加工工厂之间运送原材料或成品的排序问题。每个工厂可以加工所有属于本身的工件,也可以把一些工件运送到另一个工厂去加工。这样的运送需要一定的时间。若某个工厂需要另一家工厂加工一些工件,根据工厂和工件的不同要求,有以下三种情形:（1）在工件加工之前,原材料不需要运送,工件完成加工后,需要被运送回有需求的工厂;（2）在工件加工之前,需要先运送原材料,工件完成加工后不需要被送回有需求的工厂;（3）在工件加工之前,需要先运送原材料,工件完成加工后,需要被运送回有需求的工厂。问题的目标函数都是极小化最后一个完工工件的完工时间。对这三个问题,我们分别设计了最坏情况界为4/3,4/3和3/2的线性时间近似算法,并且给出了动态规划算法。第四章研究了带承诺到货时间的排序问题。在该问题中,企业根据顾客的订单来加工产品,并把完成的订单交由第三方物流公司运送给顾客。每个订单包含不同的产品数量,而且必须在顾客要求的时间之前送达。订单产生的运输费用与其中的产品数量以及运输需要的时间有关。我们的目标是安排一个加工订单的排序并为每个订单选择运输时间,使得所有订单都能在承诺的最迟到货时间之前到达其顾客处,并且产生的总运输费用尽量地少。我们给出了此问题的最坏情况界为2的近似算法,并且证明了这个界是紧的。