| As a discrete optimization problem without the global information, Onlineand semi-online scheduling problems widespreadly exist in areas such as man-ufacturing, communication network, power system, transportation, and publicservice system. Due to the lack of the global information, an optimization algo-rithm based on the complete formulation about the considered problem cannotbe constructed. In addition, many online scheduling problems are time-critical,where dispatch rules with a reasonable computing time have to be used. How-ever, these kind of heuristic rules often perform unstably even for instances fromthe same problem. It is necessary to analyze the competitive performance ofonline scheduling algorithms.Most competitive analysis methods in past works are severely problem-dependent. They often depend on some delicately constructed auxiliary sched-ules. This work tries to develop a relative general method to analyze the com-petitive performance. A novel method is proposed based on the idea of instancesspace contracting. The proposed method is applied on several online and semi-online problems with bounded time. Summarily, the main works of this disser-tation lies in four aspects as follows.An instances space contracting based method is proposed for the compet-itive analysis of online or semi-online scheduling problems. The methodis used to analyze two existing online algorithms for the single machinescheduling problems with the objective of minimizing total (weighted) com-pletion time. ·The total weighted completion time uniform parallel machine online schedul-ing Pm|rj|∑ωjCj is considered. An online algorithm named by CD-SWPT is constructed by extending the optimal algorithm for the corre-sponding single machine problem. The proposed algorithm is proven to be (2.5-1/2m)-competitive by virtue of the instances space contracting based method.·Under the assumption that the ratio of the longest to the shortest processing time in any instance is not greater than a constant γ, two single machine semi-online scheduling problems are investigated. For an algorithm named by aD-SPT is constructed, and its competitive ratio is proved to be1by virtue of the instances space contracting based method; For another algorithm named by aD-SWPT is constructed, and its competitive ratio is proved to be1+by use of the same method.·Under the assumption that the ratio of the longest to the shortest pro-cessing time in any instance is not greater than a constant γ, the total weighted flow time semi-online scheduling is considered. The competitive performance of SWPT is analyzed by virtue of the instances space contract-ing based method. For the single machine problem SWPT is proved to be optimal with the competitive ratio of γ+1; For the parallel machines problem the competitive ratio of SWPT is shown to lie in [γ+1,γ+1.5-1/2m]. |
