On-line Scheduling Of Parallel Jobs On Uniform Machines With Two Different Speeds

In this paper, we deal with some scheduling problems of parallel jobs. There are 2m uniform machines with m machines of speed s(s > 1) and m machines of speed 1. Every parallel job J_j may require m_j(m≥m_j≥1) machines simultaneously, and every job is only able to choose machines with the same speed. We assume r_j=0 for all jobs, but their processing time is unknown until the job has finished. This tipy of on-line models is Called nonclairvoyant, denoted by ncv in short. The objective is makespan minimization (C_max). Using the 3-field notation, our problem is denoted as Q2m|r_j = 0, m_j, on—line—ncv|C_max.We present algorithms for the scheduling problem and adopt the standard performance measure compititive ratio to analyze it. We alse provide lower bounds by the specific instances. At the same time, we consider special cases of the problem, and give better compititive algorithms.The main results of this paper are as follows.(1) For the scheduling model Q2m|r_j = 0, m_j, on—line—ncv|C_max, we give the lower bound(2) For the scheduling model Q2m|r_j—0,m_j,on—line—ncv|C_max , we give an algorithm with competitive ratioWhere (3) For the scheduling model Q2m|r_j = 0,m_j, on—line—ncv|C_max, when P≥m(s + l)p_max, we give an algorithm with competitive ratioand(4) For the scheduling model Q2m\rj = 0, m_j, on—line—ncv|C_max with P≥m(s + 1) max m_jp_j and using virtualization, we give an algorithm with competitive ratio...