1、本文的研究對象——在線算法，是計算機科學、經(jīng)濟學、操作研究學中的一個基本主題。以下主要針對在線算法中的兩類典型問題分別做了相應研究。 一、移動機器人在線構(gòu)建地圖的最優(yōu)探測法。 對復雜未知環(huán)境構(gòu)建地圖，是移動機器人所面臨的一大問題。通常忽略未知環(huán)境的幾何特征，將其抽象成未知無向連通圖，機器人只沿著圖的邊進行搜索，并將走過每條邊的成本看成是1。機器人對一未知環(huán)境在線構(gòu)建地圖時，所有的邊至少都要走一遍，走過的總邊數(shù)越少越好，整

2、個探測過程中的成本用機器人走過的總邊數(shù)來表示。 對于一個完全未知的環(huán)境，將其抽象成未知無向連通圖G=（E，V），其中E為圖G的邊，V為圖G的頂點。從G中的一點S出發(fā)，限制移動機器人最遠能走r（如安全線或通信線）步（邊數(shù)）的范圍內(nèi)，基于深度受限剪枝生成子樹的方法，結(jié)合廣度優(yōu)先搜索和受限的深度優(yōu)先搜索染色策略，給出了對未知環(huán)境構(gòu)建完整地圖的有效算法，該算法的成本為｜E｜+0｜V｜。 二、單個批處理機器的在線任務安排問題在批容

3、量受限制的單個批處理機器在線任務安排問題中，所有待處理事件都是以在線方式動態(tài)隨機到達的，所有事件的相關(guān)屬性在事件到達之前是未知的。其需要處理的時間也是未知的。問題是如何安排這些未知的、隨機到達的工作，從而使整個任務安排用時最短，效率最高。 一臺批處理機器可以同時處理b個工作事件，一批待處理事件的處理時間用這一批中需要最長處理時間的事件的處理時間來描述。在線任務安排的目標是讓所有任務都被處理后，所用的總的處理時間跨度最小。在這篇文