This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s （s 〉 1）,...This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s （s 〉 1）, and on m identical machines, respectively. For the first problem, the authors show that the on-line LPT algorithm has a competitive ratio of （1 ＋ √5）/2 ≈ 1.6180 and the bound is tight. Furthermore, the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s ≥ 1.8020. For the second problem, the authors present a lower bound of （15 - √17）/8 ≈ 1.3596 on the competitive ratio of any deterministic on-line algorithm. This improves a previous result of 1.3473.展开更多
In this paper, the authors consider an on-line scheduling problem of rn （m≥ 3） identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance tim...In this paper, the authors consider an on-line scheduling problem of rn （m≥ 3） identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance time interval is larger than the largest processing time of jobs, the authors prove that any on-line algorithm has not a constant competitive ratio. For the case that the length of maintenance time interval is less than or equal to the largest processing time of jobs, the authors prove a lower bound of 3 on the competitive ratio. The authors give an on-line algorithm with competitive 1 ratio 4 - 1/m. In particular, for the case of m = 3, the authors prove the competitive ratio of the on-line algorithm is 10/3.展开更多
基金supported by the Special Funds of the National Natural Science Foundation of China under Grant No.61340045the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20123705110003Innovation Project of Shangdong Graduate Education under Grant No.SDYC13036
文摘This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s （s 〉 1）, and on m identical machines, respectively. For the first problem, the authors show that the on-line LPT algorithm has a competitive ratio of （1 ＋ √5）/2 ≈ 1.6180 and the bound is tight. Furthermore, the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s ≥ 1.8020. For the second problem, the authors present a lower bound of （15 - √17）/8 ≈ 1.3596 on the competitive ratio of any deterministic on-line algorithm. This improves a previous result of 1.3473.
基金supported by the National Natural Science Foundation of China under Grant Nos.11271338,11171313,61070229,10901144,11001117supported by the Ph.D.Programs Foundation of Ministry ofEducation of China under Grant No.20111401110005the Henan Province Natural Science Foundation under Grant No.112300410047
文摘In this paper, the authors consider an on-line scheduling problem of rn （m≥ 3） identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance time interval is larger than the largest processing time of jobs, the authors prove that any on-line algorithm has not a constant competitive ratio. For the case that the length of maintenance time interval is less than or equal to the largest processing time of jobs, the authors prove a lower bound of 3 on the competitive ratio. The authors give an on-line algorithm with competitive 1 ratio 4 - 1/m. In particular, for the case of m = 3, the authors prove the competitive ratio of the on-line algorithm is 10/3.
