文献类型：期刊文献

英文题名：Augmentations of consistent partial orders for the one-machine total tardiness problem

作者：Yu, WC

机构：[1] Institute of Applied Mathematics, E. China Univ. of Sci. and Technol., 130 Meiling Road, Shanghai 200237, China

年份：1996

卷号：68

期号：1-2

起止页码：189

外文期刊名：DISCRETE APPLIED MATHEMATICS

收录：;EI(收录号：2004057836185);WOS:【SCI-EXPANDED(收录号:WOS:A1996UT51700012)】；

语种：英文

外文关键词：one-machine scheduling; total tardiness problem; consistent partial order; proper augmentation; dominance condition, dominance theorem

摘要：A partial order on a job set is called consistent, if it has a linear extension which is an optimal solution to the total tardiness problem of the job set. The concept of proper augmentations of consistent partial orders is based on Emmons' well-known dominance theorem. In this paper, we address the question of whether the proper augmentation of a consistent partial order always results in a partial order which is also consistent. By giving an example, we show that this need not be true in general. However, as the main result of this paper, we prove that the answer to this question is affirmative for the normal procedure, i.e., the procedure of proper augmentations beginning from ''null''. Therefore, this paper closes the gap between Emmons' dominance theorem and the normal procedure of augmentations of partial orders.