论文部分内容阅读
排序问题是一类经典的组合优化问题,并从上世纪50年代开始,伴随着生产制造领域的规模化与自动化而不断发展和成熟。本文主要研究一类带运输的排序问题,该类问题在供应链管理中具有广泛的应用前景,研究的核心是问题的近似算法设计与分析。全文共分四章。 第一章主要简要介绍了供应链与排序问题的一些相关知识和概念,并且综述了带运输排序问题的国内外研究现状。 第二章研究流水作业环境下机器间带运输的排序问题。在这类问题中,运输的过程存在于两台机器之间,工件需要在第一台机器上加工完后通过一辆运输工具分批运输到第二台机器继续进行加工,每个工件具有不同的尺寸,运输工具具有容量限制,目标是极小化最后一个工件完工的时间。针对该问题,本文设计了最坏情况界为11/5的近似算法。 第三章讨论多个客户环境下的带运输排序问题。该问题中,工件在机器上完成加工后,需要由唯一的一辆运输工具运送到相应的顾客处。不同客户的工件不能在同一批中运输,从机器到不同客户的运输时间也不同,并且运输工具的空间是有限的,每个工件占用运输工具的空间各不相同。目标是极小化最后一个工件到达顾客并返回机器的时间。本文给出了该问题顾客数为2时的一个最坏情况界为5/3的近似算法。 第四章研究同型机和同类机环境下工件具有不同尺寸的带运输排序问题。在该问题中,工件完工后,同样由唯一的一辆运输工具运送到顾客处并且考虑工件的尺寸可以不相同且运输工具具有容量限制的情况。根据机器环境的不同,研究了如下两种情形:1)机器环境为同型机,考虑机器数分别为3台和任意m台的情况;2)机器环境为同类机,考虑机器数目分别为2台和任意m台的情况。目标是极小化最后一个工件到达顾客并返回机器的时间。对于上面讨论问题,我们对同型机的两个问题分别给出最坏情况界为17/10,7/3-1/m的近似算法,同类机两类问题分别给出最坏情况界为5/3+1/6s,20/9十√3/3的近似算法。