总延误问题的相容偏序

Consistent Partial Orders for the Total Tardiness Problem

给定工件集合上的一个偏序,如果存在符合于该偏序的排列为总延误问题的最优解,则该偏序被称为相容偏序。在有关文献中,相容偏序通常由著名的Emmons优先准则所得出,并用于总延误问题的算法。本文根据Emmons优先准则定义了相容偏序的恰当扩张的概念,研究了这种扩张所得的偏序能否保持为相容偏序的问题。

A partial order on a job set is called a consistent partial order, if there exists it's linear extention as an optimal solution for the total tardiness problem of the job set. Also the concept of proper augmentations of a consistent partial order is defined in relation with Emmons dominance rules. A queston is proposed in this paper that, is a partial order obtained by proper augmentations from a consistent partial order always a consistent partial order? The answer to this question in general is shown to be negative by an example in this paper. Mainly the answer to this question is proved to be affirmative for the normal procedure, i.e. the procedure of proper augmentations from 'null'. Therefore this paper aims at filling up the existing gap between Emmons dominance rules and the normal procedure of augmentations of consistent partial orders.