Semi-on-line Scheduling On Parallel Machines With Non-simultaneous Machine Available Times

Scheduling problems are a kind of important problems in the field of combinatorial optimization of operations research. The research of scheduling theory has important theoretical interesting and extensive perspective of application in practice. In recent decades, people have studied the area deeply and proposed enormous problems and excellent algorithms.In most literature on scheduling theroy, problems are classified as off-line and on-line. If full information on jobs to be scheduled is available in advance, we call the scheduling problem off-line. By contrast, if the jobs are not known a priori, but arrive one by one, and we are required to schedule jobs irrevocably on the machines as soon as they are released, without any knowledge about jobs that follow later on, such problem is called on-line.With the development of scheguling theory and application, such classification is not sufficient to include all scheduling problems discussed. Plenty of problems arc neither off-line nor on-line, but somehow in between. Hence, semi-on-line scheduling problems gained much attention due to their increased application in practice. A scheduling problem is called semi-on-line if the information about jobs is somehow between off-line and on-line. In other words, in the semi-on-line scheduling some partial information about jobs is available in advance, and we cannot rearrange any job which has been assigned to machines. People wish to achive improvement of the performance of the optimal semi-on-line algorithm with respect to the on-line version by using additional information.This paper considers the problem of semi-on-line scheduling on two identical parallel machines with non-simultaneous machine available times. The problem can be written, using three-field representation, as following:P2,r_i|sum & decr|C_max.That is to say, there are two identical machines with non-simultaneous machine available times. The sum of the processing times of the jobs is known in advance. The jobs are released on-line in the order of the decreasing processing times of jobs. The goal is to minimize the makespan. In section 1, we mainly introduce some basic knowledge about scheduling theory and some related papers. In section 2, we study the problemP2,r_i|sum & decr|C_max(M) and P2, r_i|sum & decr|C_max(J).For each of the above two problems, we present a semi-on-line algorithm whose competitive ratio is 7/6, and we give a rigor proof.