本文研究机器带中断的排序问题。该问题可以描述为：两台平行机加工一批工件，加工过程中，由于某种原因，其中一台机器发生故障可能在某一个时刻产生中断，这使得安排在该机器上加工的工件无法及时加工，因而这些工件要么等待中断结束后继续在原机器上加工，要么转移到另一台正常运行的机器上加工，当发生故障的机器恢复加工后，安排在正常运行的机器上加工的工件也可以转移到恢复以后的机器上加工。(1)文章研究如何安排新的加工顺序，使得目标函数为误工工件个数∑∪ij最小化；(2)两台平行机加工，n个工件，文章研究如何重新安排工件的加工顺序，并将任意，n个交工期限怎样分配给各个工件，使得目标函数P2|d[I]|Tmax，P2|d[I]|n∑I=1Ti，P2|d[I]|max｛Ei，Ti｝，P2|d[I]max{Ei，Ti}为最小，其中d[I]是分配给工件Ji的交工期限。　　 全文共分为四章。　　 第一章是绪论，主要介绍组合优化、计算复杂性的基本理论，并对排序问题的背景、研究方法等知识进行阐述。　　 第二章讨论问题(1)。当工件转移时间T=0时，证明问题P2|D，T=0|∑∪ij是多项式时间可解问题，本文给出了相应的算法，并证明了算法的最优性；当转移时间T>0时，问题P2|D，T≠0|∑∪ij是NP难问题，对该问题文章提出了一个差界为1的多项式时间的近似算法，并给出了证明，算法的计算复杂度为O(nlogn)。　　 第三章讨论问题(2)。研究交工期限可分配的机器带中断的两台平行机排序问题，并将其推广到m台机的情形，当交工期限为-C1，-G2，…，-Cn分配给先后加工的工件时，，考虑目标函数P2|d[I]|Tmax，P2|d[I]|n∑I=1Ti，P2|d[I]|max{Ei，Ti)，P2|d[I]|n∑I=1{Ei+Ti}，文章给出了一个最优排序。对于上述给定的排序，当交工期限d[1]，d[2]…，d[n]．按EDD序分配给先后加工的工件时，对上述目标函数文章证明是最优的。　　 第四章是对全文的总结概括，并对以后的工作做了展望。