本文主要讨论在线生产调度问题，并对这类调度问题设计和分析策略。在文献中，确定性调度模型已经被广泛研究。这类研究模型的一个基本假设是所有信息在调度之前全部知道。然而，这个假设又常常是不切实际的。这种现实情况使得在线调度问题备受关注。在在线调度问题里，在线策略通常在没有未来信息的情况下做决策。本文用竞争分析方法来分析在线策略的效果。具体来讲，用竞争比作为度量标准。这个指标分析策略在最坏情况下的效果。相对于在线策略，离线最优策略是在决策之前对需求序列信息完全知道，并做出最优决策。　　论文主要研究两种在线生产调度模式。第一种，订单以列表方式到达或一个一个到达。需求序列里的订单存储在列表里，并当列表头一个订单被安排加工后下一个订单才出现。第二种，订单随时间到达。每个订单都对应一个到达时刻，并在此时刻后，它才能够被加工。基于这两个模式，本文研究了不同的调度模型：单机调度、平行机调度、不同速度平行机器调度、批处理机调度和流水线调度。对于每一个问题都先给出在线问题竞争比下界。然后，设计并分析在线策略。对于某些问题，本文所设计的策略是最优策略。这里最优策略意味着该策略的竞争比与所对应在线调度问题竞争比的下界相等。　　本文贡献主要集中在以下五部分。　　·第一部分研究单机模型不同目标函数的两个问题：最小化一般性总完工时间（或称为完工时间α次幂之和）以及最小化变形的总延迟（或延迟与预期交货时间之和）。对于第一个问题，证明了D-SPT是最优策略。当a-l时，Vestjens提出并证明D-SPT策略是最优策略。这个结果是本文的一个特例，即本文得到的是更一般化的结果。对于第二个问题，证明D-SWPT策略的竞争比是3。此后，进一步分析两个扩展问题，同时设计了M-D-SWPT策略并分析其效果。在在线调度研究中，本文第一次提出并研究以总延迟为目标的在线问题。　　·第二部分本文研究两平行机模型并行订单在线调度问题。并行订单需要一定数目的机器同时加工才能完成。订单加工时间在一定区间范围。目标是最小化加工时间跨度，即系统中最后一个订单的完成时间。本文利用更多的信息，提出了与文献中相比具有更小竞争比的在线策略。　　·第三部分本文研究两不同速度平行机模型调度问题。考虑的约束条件是两机器中一台是周期性不可用。订单加工过程中不允许抢占。目标是最小化加工时间跨度。本文对不同情况给出了不同下界，同时证明LS策略在一些情况下是最优的。在在线调度研究中，本文第一次提出并研究具有周期性可用性约束的在线问题。　　·第四部分本文研究m不同速度平行机在线调度模型。主要讨论两个问题。在第一个问题里，不允许抢占。目标是最小化加权完工时间。本文证明R-LIST策略的竞争比是√4m-√3+3/2。在第二个问题里，允许抢占。目标是最小化总加权完工时间。本文证明了在一定条件下，WSPT-1策略的竞争比是2。当m=2时，LiuandLu证明了R-LIST和WSPT-1分别是2.618和2一竞争的。这个结果是本文的一个特例，即本文获得了更一般化的结果。　　·第五部分讨论两个关于批加工机器模型里在线调度问题。一个批加工机器可以同时加工B个订单。我们研究无界批加工机器模型，即一批可以加工无穷多个订单。一起加工的订单构成一批，并且这些订单同时开始同时结束。批加工机器的加工时间由这一批里最长订单的加工时间决定。第一个问题，两平行批加工机器模型最小化时间跨度。订单按其加工时间非降序到达情况下，我们给出了最优策略。本文利用更多的信息，提出了与文献中相比具有更小竞争比的在线策略。第二个问题，m批加工机器流水车间模型最小化时间跨度。订单在各个机器上的加工时间相同且订单按加工时间非降序排列。我们给出了一个最优策略。在在线调度研究中，本文第一次提出并研究批加工机器流水车间模型。