论文部分内容阅读
排序论是运筹学中最有活力的领域之一，大量不同机器环境下的排序模型已经被学者们广泛研究。本文我们是在继列批机器环境下研究工件的加工和运输之间的集成排序问题。为了节约时间和(或)费用，工件生产和工件运输之间的协调已经在文献中广泛研究。文献中通常有两种传统的方法用来运输工件。第一种方法总是单独地运输工件且在工件加工完成之后立即运输给顾客。此时，通常假设有足够多数量的运输车。第二种方法是把加工完成的工件成批地运输给顾客。显然，第二种方法比第一种方法需要更少的车辆和更低的运输费用。本文我们采用第二种方法来运输所有的工件。此外，在工件的实际加工和运输过程中，加工机器和运输车辆可能会存在容量限制。 Lu等人[26]引入了“劈开”的概念。在“劈开”的假设下，一个工件Jj可以被劈开成两部分Jj和 J"j，且被劈开的两部分Jj和J"j在加工和运输过程中可以被看作是两个独立工件。 本文分两部分研究继列批机器上带有容量限制的工件加工和运输之间的集成排序问题。第一部分研宄只有运输车辆存在容量限制且工件只在运输过程中允许“劈开”的排序问题.第二部分研宄加工和运输过程中均有容量限制的排序问题。 在第二章，我们研宄了只有运输车辆存在容量限制且工件只在运输过程中允许“劈开”的排序问题： 针对运输车辆存在一般容量限制且工件只在运输过程中允许“劈开”的情形，我们给出了一个4/3-近似算法，这改进了 Lu等人[26]的3/2-近似算法。 对工件尺寸一致的特殊情形，我们给出了多项式时间算法。 在第三章，我们研宄了运输批和加工批均有容量限制的排序问题： 研究了容量限制是工件个数时的排序问题.针对最小化最大运输完工时间与最小化运输完工时间和两个不同的目标函数，我们分别给出了相应的动态规划算法。 研究了容量限制是一般容量限制的排序问题。针对工件允许“劈开”的情形，我们给出了一个多项式时间算法，而对工件不允许“劈开”的情形给出了一个2-近似算法。