本文主要研究了排序理论中比较新型的排序问题——同时加工排序，它属于现代排序论的范畴，在前人研究的基础上和图论内容结合在一起进行讨论，指工件在一台批加工机器上进行加工，且工件不全兼容，只有兼容工件才能放入一批中加工，该兼容关系由图表示(称为兼容图)，批的容量可能有限，也可能无限，一批的加工时问等于批中所有工件加工时间的最大值。把排序理论和图论联系在一起研究是一个比较重要且新颖的内容。　　 本文主要总结了工件有兼容关系的同时加工排序中，目标函数是最大完工时间的排序问题的一些结论，并在前人研究的基础上进行推广，分析讨论了其他目标函数值的同时加工排序问题，主要内容如下：　　 1、完全二部图及完全m部图作为兼容图时，目标函数是总完工时间的同时加工排序问题。　　 2、完全二部图作为兼容图时，目标函数是加权总完工时间和问题及最大延迟问题。　　 3、完全分割图作为兼容图时，目标函数是总完工时间和问题及加权总完工时间和问题。