摘要
This paper considers the online scheduling problem on m(m≥3)parallel machines(the first k machines with grade 1 and the remaining m-k machines with grade 2)with two Go S levels and makespan as the objective function.The jobs arrive over time with grade 1 or 2 and an arrival job can be assigned to a machine only when the grade of the job is no less than the grade of the machine.Three cases are considered:(i)For k=1,the authors present an online algorithm with competitive ratio of9/5.(ii)For 1<k<m-1,an online algorithm with competitive ratio of 2.280 is proposed.(iii)For k=m-1,an online algorithm is presented with competitive ratio of 2.All the three algorithms are based on greedy algorithm with a similar structure.At last,numerical instances are given and the average competitive ratios of the instances show good performance of the proposed algorithms.
This paper considers the online scheduling problem on m(m ≥ 3) parallel machines(the first k machines with grade 1 and the remaining m-k machines with grade 2) with two Go S levels and makespan as the objective function. The jobs arrive over time with grade 1 or 2 and an arrival job can be assigned to a machine only when the grade of the job is no less than the grade of the machine. Three cases are considered:(i) For k = 1, the authors present an online algorithm with competitive ratio of9/5.(ii) For 1 < k < m-1, an online algorithm with competitive ratio of 2.280 is proposed.(iii)For k = m-1, an online algorithm is presented with competitive ratio of 2. All the three algorithms are based on greedy algorithm with a similar structure. At last, numerical instances are given and the average competitive ratios of the instances show good performance of the proposed algorithms.
基金
supported by the National Natural Science Foundation of China under Grant Nos.71390334 and 11271356
