On-line Scheduling For Unit Jobs With Release Times

This paper mainly studies the following problem: on-line schedulingfor unit jobs with release times on single machine. We present anoptimal algorithm. The paper consists of two chapters.In Chapter 1, we introduce some basic notions: combinationaloptimization, scheduling problems, algorithm and competitiveratio.In Chapter 2, we investigate the on-line scheduling problemfor unit jobs with release times on single machine. The goalis to minimize the maximum machine completion time. In thefirst section, we introduce the problem: 1|online|C_max. Inthe second section, we present that lower bound of the problem is 1.398.In the third section, we design an online algorithm and show that it is anoptimal online algorithm matching the bound of 1.398.