本文主要研究的是带有加工机器约束的平行机在线排序问题。在此问题中,每个工件都对应一个到达时间rj,一个加工时间pj和一个加工机器集合Mj,工件只能在时刻rj之后被安排到Mj中的某个机器上加工,加工需要占用pj个单位时间。我们考虑这个问题的在线情形。也就是说,只有在此工件到达之后,我们才能得到这个工件的完整信息,甚至包括它是否存在。而在此工件到达后,我们可以选择立刻安排它,或者将此工件推迟到之后的某个时间再进行安排。我们的目标是最小化时间表长。我们考虑的是此问题的四种特殊情形:嵌套加工机器集合、包含加工机器集合、树型加工机器集合以及区间加工机器集合。在第二章,我们考虑的是嵌套加工机器集合的情形。在我们的问题中,机器数目是任意的且工件都带有相同的加工时间。对于此问题,我们给出算法H1,在此算法中,我们将工件安排在时刻αp+kp(α=(?)/2,k= 0,1,2,...)加工,并且在任意时刻,我们优先安排带有最小|Mj|的工件。算法H1的竞争比为(?)/2并且此算法是该问题的最优在线算法。在第三章,我们考虑的是包含加工机器集合的情形。首先我们考虑的问题是所有工件带有相同的加工时间且机器数是任意的。对于此问题,我们给出算法H2。H2与H1较为类似,不同的是我们不仅将工件安排在αp+kp时刻加工,还将工件安排在2αp + kp时刻加工,其中α =(?)-1,k= 0,1,2,...。我们证明了算法H2的竞争比为(?)并且它是此问题的最优在线算法。之后我们考虑的问题是机器数为2且工件的加工时间是任意的。同样我们给出了此问题的最优在线算法。在第四章,我们考虑的是树型加工机器集合。首先我们考虑的是机器数为3且工件的加工时间为任意的情形。我们证明了此问题的下界为3/2,并给出了此问题的最优在线算法。之后,我们考虑了树型图的一种特殊情形:星型图。我们考虑的是机器数为任意且工件都带有相同加工时间的情形。我们证明了此问题的下界为(?)并给出了此问题的最优在线算法。在第五章,我们考虑的是区间加工集合的情形。在我们考虑的问题中,工件的加工时间都相同且只有两种不同的加工机器集合。我们给出了此问题的下界为3/2,并给出了此问题的最优在线算法。