本文主要研究将多组工件安排在多组加工速度相同和不同的机器上的排序问题．对于将n个独立工件安排在m台机器上，使得所有机器的总的最后完工时间最小的排序问题被称为经典的平行机排序问题，该问题一直受到人们的广泛关注和研究．由于该类问题是NP-Hard问题，因此无论这类问题的描述多么简单，该类问题都是不易解决的．从而人们在解决该类问题时，通常都寻找其近似算法，分析算法的概率特征，并研究其最坏情况的性能指标． 在对该类问题的研究中，许多学者提出了各种各样的启发式算法，其中比较经典的算法是LPT(LongestProcessingTime)算法和LS(ListScheduling)算法，另外还有最近提出的MSS(Multi-startSubsetSum)算法．在经典的LPT算法中，首先构造一个具有优先顺序的工件列表，所有工件按照加工时间不增的次序排列，一旦有机器空闲，总是把等待加工的加工时间最长的工件安排给这个首先空闲的机器加工；经典的LS算法则按照工件的自然顺序将工件安排在首先空闲的机器上进行加工；MSS算法是一个多开始的局部搜索算法，它通过迭代来不断解决两台机器的排序问题，从而找到一个基于优化的启发解． 本文在经典LPT算法的基础上研究了两种改进的LPT算法，针对机器加工速度相同和不同的情形进行了详细的分析，并得到了不同条件下问题的最差性能指标界．解决了用经典的LPT算法所没有解决的更复杂的新问题，所得的新结果推广和涵盖了用经典的LPT算法所获得的结果．在利用上述两种改进的LPT算法所得的近似解的基础上，提出了一种改进的MSS算法，利用已有的0-1规划理论对近似解做了进一步优化．在经典LS算法的基础上，分别提出了针对机器加工速度相同和不同的改进LS算法，同时还分别分析了工件具有准备时间的复杂情形，并各自得到了不同情形下问题的严格界．这种改进的LS算法解决了用经典的LS算法所没有解决的更复杂的新问题，所得的新结果推广和涵盖了用经典的LS算法所得的结果． 论文的主要内容安排如下： 第一章主要介绍了排序问题的研究背景和实际意义，目前已有的研究成果和所用的研究方法以及与所研究问题相关的一些定义和概念． 第二章在经典的平行机排序问题的基础上，主要讨论了具有多台通用机的同速度的多组工件的排序问题．在经典LPT算法的基础上分析了两种针对实际问题的改进LPT算法．一种算法只在每个工件组内对工件排序，优先安排总任务较多的工件组中的加工时间最长的工件；另一种算法则对所有工件组中的工件混合排序，首先安排加工时间最长的工件．两种算法在机器的选择上都采用”首先空闲”准则，即总是把加工时间最长的工件安排给最先完工的机器．在这一章中分别重点详细地分析了两种改进的LPT算法的性质、步骤和最坏情况下的界．在两种改进的LPT算法所得近似解的基础上，提出了一种改进的MSS算法，利用成熟的0-1规划理论对近似解做了进一步优化．所得的新结果推广和涵盖了已有的结果． 第三章在经典的平行机排序问题的基础上，对不同速度的具有多台通用机的多组工件的排序问题进行了研究，利用第二章提出的两种改进的LPT算法，对机器速度不同的情形重点详细地分析了两种改进LPT算法的性质、步骤和最坏情况下的界．在两种改进的LPT算法所得近似解的基础上，提出了一种针对机器速度不同的改进MSS算法，利用成熟的0-1规划理论对近似解做了进一步优化．所得的新结果推广和涵盖了已有的结果． 第四章针对在经典的平行机调度问题中所提出的经典LS算法，提出了一种改进的LS算法，该算法在机器的选择上仍然利用”首先空闲”准则，在工件组的选择上采用”优先到达”准则，即总是安排各个工件组中最先到达的工件进行加工．本章对多组工件，多台专用机，多台通用机，机器速度相同，并且工件具有准备时间的情形进行了细致的分析，得到并证明了改进的LS算法的严格界．所得的新结果推广和涵盖了已有的结果． 第五章分析机器加工速度不同的情形，在经典LS算法的基础上提出了改进的LS算法，分析了多组工件，多台专用机，多台通用机，特别针对工件具有准备时间，并且在机器加工速度不同的条件下，得到并证明了改进的LS算法的严格界．所得的新结果推广和涵盖了已有的结果． 第六章对本论文的工作做了简要的总结，并对以后的进一步研究进行了展望．