论文部分内容阅读
本文研究了两个具有运送协调性的平行机排序问题。目标函数都是求最小化最大运送完成时间，即将所有工件加工完毕后运送到顾客，且运送车辆返回到生产车间的时间。由于工件的作业是由加工和运送两个阶段构成，我们称这样的问题为两阶段排序问题。研究了平行机工件可中断两阶段排序问题，其中N={1,2,···,n}是n个工件的集合。这n个工件首先在m台平行机上可中断地加工，然后由一辆汽车运送给顾客，每次只能运送一个工件。该问题的一个排序包括n个工件在m台平行机上可中断加工的方案以及n个工件的运送方案。一个工件j可以被运送只有当它加工完毕并且车辆可用。令Dj是工件j的运送完成时间，也即是工件j运送到它对应的顾客并且车辆返回到工厂的时间。我们使用Dmax来表示所有工件的最大运送完成时间。按照Graham等人[23]对排序问题的表示方法，本章研究的问题可以表示为P|pmtn|Dmax。我们证明了该问题是强NP-困难的并给出了一个3/2-近似算法。研究了在ADT(assignable delivery times)假设下平行机工件不可中断两阶段排序问题。在该问题中，n个工件的集合N={1,2,···,n}首先在m台平行机上加工，然后由一辆汽车将它们运送到顾客，一次只能运送一个工件。在ADT假设下，n个运送时间的集合提前给定，但每个运送时间并不附属于某个特定的工件。该问题的一个排序包括n个工件在m台机器上的一个加工方案，n个运送时间与n个工件的一个分配，以及n个工件的一个运送方案，其中一个工件j只有当它加工完毕且车辆可用才能够分配一个运送时间且被汽车运送。令Dj是工件j的运送完成时间，也即是工件j运送到它的顾客且汽车返回工厂的时间。我们用Dmax来表示所有工件的最大的运送完成时间。按照Graham等人[23]对排序问题的经典的表示方法，本章研究的问题可以表示为P|ADT|Dmax。注意到经典的强NP-困难的排序问题P||Cmax是问题P|ADT|Dmax的一个特殊形式。因此，问题P|ADT|Dmax也是强NP-困难的。对问题P|ADT|Dmax，我们给出了一个3/2-近似的算法和一个多项式时间近似方案(PTAS)。