该文首先介绍了当今在编制作业计划,企业管理、交通运输、航空航天及医药卫生等各个领域都被广泛应用的排序理论的有关概念;简要介绍了目前国内外对排序问题研究的进展,进而说明了:并行多机提前/拖期惩罚排序问题在实际中有极广泛而且重要的应用,同时还有许多问题尚待解决.该文研究了公共交货期的准时制并行多机调度问题,它是对著名的提前、拖期惩罚排序问题的扩展,包括最小化三个目标函数1)提前惩罚;2)拖期惩罚;3)等待时间惩罚.每个工件都有一个非零的非标开始时间.通过证明一些性质,提出一些寻找最优排序的方法.该文针对并行多机提前/拖期惩罚这一大题目,根据其中一些具体环节,条件及要求的不同情况,提出了与之相应的一系列启发式算法,用Turbo c语言在IBM/PC上作了大量仿真实验.将实验结果与目前一些公认的其它较好的启发式算法作了比较,结果证明该文中的算法都是比较有效的.如前所述,排序问题尤其是并行多机排序问题不存在大范围的一致算法,然而许多研究人员还是在不断寻找一种比较普遍的算法,这就出现了TABU SEARCH算法,该文也尝试将TS用于其中一例,并将它与启发式算法的结果作了比较,说明了各自的优缺点.