论文部分内容阅读
本文主要研究了一类带批运输的排序问题。经典的排序模型假设工件一旦完工就可以使用,所以只需要考虑工件的加工阶段。然而,在实际的应用中每个工件属于不同的客户,工件在加工阶段完工后,必须要配送到各个对应的客户。由于加工和配送的资源有限,如何安排加工顺序以及如何分批运输成为一个很重要的问题。本文考虑的问题就是加工和配送协调的两阶段问题,它可以描述如下:给定n个工件的集合N={J1,J2,…,Jn},首先在位于中心的加工环境中加工,完工的工件由一辆初始时刻位于中心的容量有限的车配送到指定客户。目标是找到一个时间表使得车把所有工件配送到指定客户且回到中心的时间最小。针对加工阶段不同的机器环境,以及不同的配送方式,分别设计了算法。
第一章介绍了组合优化问题,算法及复杂性理论的基础知识;简单回顾了排序论的发展历程;综述了与本文研究模型相关问题的研究现状。
第二章考虑加工阶段是同速机的问题。这里考虑一个客户(所有客户分布在同一位置)且工件物理大小相同的情况。我们考虑了两种不同配送方式:Type1允许不同机器上加工的工件在同一批配送;Type2只允许同一台机器上加工的工件在同一批配送。我们分析了两种不同配送方式下问题的性质。针对一般m台机器的情况,分别给出了2-m/1-近似算法;针对两台机器的情况,进一步分别给出了性能比为3/4的改进算法。
第三章讨论了加工阶段是两台同速机的情况。这里假设只有一个客户且工件物理大小不同。我们研究了Type1配送方式,并给出了一个性能比为9/14+ε的算法。
第四章考虑了加工阶段是单机的问题。我们考虑了工件对应的客户分布在一个以机器为中心的星型网络中。对于工件物理大小相同的情形,我们给出了一个3/2-近似算法;对于工件物理大小不同的情形,我们给出了一个2-近似算法。
第五章考虑了加工环境是单机,常数个客户分布在不同位置的问题。针对工件物理大小相同的情况,我们给出了多项式时间的动态规划算法;针对工件物理大小不同的情况,我们讨论了一类特殊的三个客户的问题,并给出了一个2-近似算法。
第六章简单讨论了加工阶段是两阶段流水作业的问题。这里假设只有一个客户且工件物理大小不同。我们给出了一个2-近似算法。
第七章给出了本文的结论并提出了需进一步考虑的问题。