In this paper, we consider the on-line scheduling of unit time jobs with rejection on rn identical parallel machines. The objective is to minimize the total completion time of the accepted jobs plus the total penalty ...In this paper, we consider the on-line scheduling of unit time jobs with rejection on rn identical parallel machines. The objective is to minimize the total completion time of the accepted jobs plus the total penalty of the rejected jobs. We give an on-line algorithm for the problem with competitive ratio 1/2 （2 ＋√3） ≈ 1.86602.展开更多
This paper considers the scheduling problem with rejection on m identical parallel machines to minimize the maximum flow time. The authors show that this problem is NP-hard even when there is a single machine and all ...This paper considers the scheduling problem with rejection on m identical parallel machines to minimize the maximum flow time. The authors show that this problem is NP-hard even when there is a single machine and all jobs have two distinct release dates. Furthermore, the authors present a dynamic programming algorithm and two approximation algorithms to solve them.展开更多
基金This work is supported by Natural Science Foundation of China under Grant No. 10171054.
文摘In this paper, we consider the on-line scheduling of unit time jobs with rejection on rn identical parallel machines. The objective is to minimize the total completion time of the accepted jobs plus the total penalty of the rejected jobs. We give an on-line algorithm for the problem with competitive ratio 1/2 （2 ＋√3） ≈ 1.86602.
基金supported by the National Nature Science Foundation of China under Grant Nos.11426094,11271338 and U1504103
文摘This paper considers the scheduling problem with rejection on m identical parallel machines to minimize the maximum flow time. The authors show that this problem is NP-hard even when there is a single machine and all jobs have two distinct release dates. Furthermore, the authors present a dynamic programming algorithm and two approximation algorithms to solve them.
