在线排序作为一种信息匮缺情况下的组合优化问题，广泛存在于生产制造、并行计算及公共服务等领域。本项目针对多个 minsum 目标的平行机时间在线排序模型，分析这类问题对应的在线算法由于缺乏完整信息而所面临的困境，挖掘相应算法所对应最差实例的特点与共性，展开以最差实例为中心的算法设计与分析。在分析问题竞争比下界时，用对手策略构造一系列特殊实例以导出较紧的下界；在设计算法时，构造基于工件优先级的在线等待策略,以保证其能兼顾到各类最差实例；在竞争分析时，通过调整任意实例的某些参数使其向最差实例可能的结构靠近，逐步将最差实例的搜索空间从整个实例空间压缩到更小的子集，以导出期望的竞争比。本项目不仅旨在为最小化总加权完工时间的各类平行机在线排序,以及加工时间有界的相应半在线问题,提出具有更好竞争性能的在线或半在线算法，还意在发展一种更具一般性与系统性的基于实例空间压缩的竞争分析方法。

As a discrete optimization problem without the global information, online and semi-online scheduling problems exist in areas such as manufacturing, parallel computing, communication network, and public service system. Due to the lack of the global information, an optimization algorithm based on the complete formulation about the considered problem cannot be constructed. In addition, many online scheduling problems are time-critical, where dispatch rules with a reasonable computing time have to be used. However, these kind of heuristic rules often perform unstably even for instances from the same problem. It is necessary to analyze the competitive performance of online scheduling algorithms...The project considers several parallel machine scheduling problems with minsum criteria in the online setting where jobs arrive over time. First, the common dilemma which online algorithms have to face is investigated. Then the algorithm design and competitive analysis is developed based on the observation on the corresponding worst case instances. For the lower bound on the competitive ratio of any online algorithm for a problem, the so-called adversary method is used. For algorithm design, priority rules based waiting strategies are utilized in order to take account of all kinds of worst case instances. For competitive analysis, the instances space contracting based method is developed, which transforms the instance towards the possible structure of the worst-case instance with respect to the given online algorithm by increasing or reducing some parameters of some jobs, such that the modified instance shows a more special structure of which we can take advantage to analyze the performance ratio. The project aims to not only propose better online or semi-online algorithms for several parallel machine online scheduling problems with minsum criteria, but also to develop a relative general method based on the idea of instances space contracting to analyze the competitive performance.