The Research For Two Kinds Of On-line Algorithm Problems

On-line algorithm is the object studied in this paper.It is also a basic theme in computer science,economics and operation research system.The two typical problems of on-line algorithm are researched separately as follows.First,the optimal on-line exploration method for map building with a mobile robot.The problem faced by a mobile robot is to construct a complete map of an unknown environment.The geometric features of the environment are neglected and the environment is modeled as an unknown connected undirected graph.The robot can only move along edges of the graph. Suppose that the cost of each edge traversal is 1.A robot has to visit all nodes and edges of the graph,using as few edge traversals as possible.The cost of building map is measured by the number of edges traversed during the exploration.In this paper,an unknown environment is modeled as an unknown connected undirected graph G=(E,V),E is the edges number of G,V is the vertex number of G.The robot starts at vertex S,and moves no more than the range of r steps.Based on the approach that prunes a tree with a bounded depth,combining with the strategy of BFS and bounded DFS coloring method,an efficient algorithm of building map of unknown environment is presented.The cost of the algorithm is |E|+O|V|.Second,the problem of on-line scheduling on a single batch processing machine.The problem of on-line job scheduling on a single batch processing machine with bounded batch size is attacked.Jobs arrive dynamically over time,the characteristics of jobs are unknown before their arrivals.A batch processing machine can handle up to b jobs simultaneously. The processing time of a batch is given by the longest processing time of some job in the batch.The objective of on-line scheduling problem is to minimize the time makespan.An on-line algorithm with restarts for a bounded batch machine scheduling is presented,and it is shown that the competitive ratio(The competitive ratio is a ratio of the on-line algorithm complexity and the off-line optial algorithm complexity)is 3/2.