经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题[14],它是排序论中最基本的问题之一,具有重要的理论意义和实用价值。本文研究误工排序问题最优性Pinedo证明的完善及其推广。本文第一章,综述了排序论的学术意义和排序问题的研究概况。本文第二章,介绍了排序问题的一些基础知识。本文第三章,首先研究经典的误工问题1‖∑Uj,著名的Moore-Hodgson算法可以在时间O (n log n)内得到误工问题的最优解。然而关于Moore-Hodgson算法的证明是非常繁杂的。所以,后来BRUCKER在文献[18],PINEDO在文献[19],孙叶平,唐万梅,唐国春在文献[20]研究了Moore-Hodgson算法的最优性新证明。其中文献[20]被认为是关于Moore-Hodgson算法最优性最新最简便的证明。Pinedo[19]对于Moore-Hodgson算法的最优性也有一个证明。虽然这个证明不够严格,许多关键的地方交待不清,但是Pinedo证明的过程表明Moore-Hodgson算法得到的解是所有最优解中不误工工件的总加工时间最短的。这是关于Moore-Hodgson算法的一个很本质的性质,是其他所有证明中没有提及的。因此,本文将补充和完善Pinedo的证明。在Moore-Hodgson算法最优性证明的基础上,本文又分析和研究了求解几种推广的误工排序问题的算法,并且也给出相应的新的证明。比如研究求解在保证工件的一个子集T中的工件必须不误工的前提下,使误工工件的个数为最少的误工排序问题1│T│∑Uj的Sidney算法,并且给出Sidney算法最优性新的证明,同时证明Sidney算法得到的解是所有最优解中不误工工件集合的总加工时间是最小的;研究求解工件的加工时间与权具有“反向一致性”的前提下,使得带权误工工件个数为最少的误工排序问题1│(pi≤pj ) ? (wi≥wj)│∑wjUj。由于使带权的误工工件个数为最少的问题1‖∑wjUj是NP难题,所以,1976年Lawler在增加“一致性权”条件:“(pi