Semi-online Scheduling With Available Time On Machine

Scheduling is an importmant problem in combinatorial optimization in which we assign some tasks to time and resouces under some constraints, such that one- or multi-criteria attain to the optimum. Recently, on-line and semi-online scheduling are two branches developed faster. On-line scheduling means that all job information is unknown befor their release time, and once a job is scheduled it cannot be changed. Off-line scheduling means that all job information is known in advance. In practice, problems are not only really online or off-line, but somehow in between. Such a case is defined as semi-online scheduling. This means that partial information about jobs is available in advance. Algorithms for a semi-online scheduling are called semi-online Algorithms.Uniform and parallel machine scheduling is an important scheduling problem. Generally, the problem can be discrebed as follows: There are a set J = { J₁, J₂,…, J_n} of independent jobs, where J_i has proessing time P_i. The jobs must be scheduled on m(m > 1) paralle and uniform machines. We are given a set of machines M—{M₁, M₂,…, M_n}, and S_j is the speed of machine M_j, j = 1,2,…, m. Each job has the same proportion relation of processing time on different machines. In classicl scheduling problems, we often assume machines process jobs at time zero. But in practice situations are often not so, such as each machine has an available time. Machines can start to process jobs after the available time. We say such problem as machine with available time.In this paper, we consider semi-online scheduling problems about two machines with available time. We assume sum represents the total processing time of all jobs, and P_maxrepresents the largest processing time of all jobs. The main results in this paper are as follows:(1) For the scheduling model Q2,r_j|sum|C_min, we give a semi-online algorithm with competitive ratio at least (s+1)/(2s+1)(2) For the scheduling model P2, r_j|sum, P_max|C_min, we give a semi-online algorithm with competitive ratio 4/5 and it is the best. (3) For the scheduling model Q2,r_j|sum, P_max|C_min, we give a semi-online algorithm with competitive ratio at least(2s+2)/(3s+2)...