有运送协调性的最小化最大运送完成时间平行机排序

摘要

本文研究了两个具有运送协调性的平行机排序问题。目标函数都是求最小化最大运送完成时间，即将所有工件加工完毕后运送到顾客，且运送车辆返回到生产车间的时间。由于工件的作业是由加工和运送两个阶段构成，我们称这样的问题为两阶段排序问题。研究了平行机工件可中断两阶段排序问题，其中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)。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 前言

S1.1 排序问题的三参数表示

S1.2 相关文献

S1.3 本文结果

第二章 可中断的带有运送协调性的最小化最大运送完成时间的平行机排序

S2.1 引言

S2.2 准备工作

S2.3 NP-困难证明

S2.4 一个3/2-近似算法

第三章 可分配运送时间的极小化最大运送时间的两阶段平行机排序

S3.1 引言

S3.2 准备工作

S3.3 一个3/2-近似算法

S3.4 一个多项式时间近似方案

第四章 结论与展望

参考文献

在学期间SCI学术论文发表情况

致谢