A Study On On-line Scheduling With Reassignment

This paper investigates online scheduling problems with reassignment ontwo identical machines, where we can reassign some jobs under given conditionsafter all the jobs have been assigned. Four different versions are studied andalgorithms are proposed. The first is that we can reassign the lastκjobs ofthe sequence, whose lower bound remains 3/2, whereκis a finite number. Thesecond is that we can reassign the last job of each machine. Optimal algorithmwith competitive ratio 2^1/2 is given. The third is that we can reassign arbitraryκjobs. Optimal algorithm with competitive ratio 4/3 is given. The fourth is thatwe can reassign any job but with some cost, which is proportion to the size of job,the coefficient isα. We give the lower bound of it and analysis the competitiveratio of some simple algorithms.The paper is organized as follows:The first chapter gives the preliminaries that will be used in the rest of thepaper.The second chapter studies the first three models that reassignment with nocost.The third chapter studies the model that we can reassign any job but withsome cost.