Semi-Online Machine Covering under a Grade of Service Provision
Two semi-online scheduling problems on two parallel identical machines under a grade of service (GoS) provision were studied. The goal is to maximize the minimum machine load. For the semi-online version where the largest processing time of all jobs is known in advance, we show that no competitive algorithm exists. For the semi-online version where the optimal offline value is known in advance, we propose an optimal algorithm with competitive ratio 2.
Di Zheng, Yiqiang Wang, Yi-Min Deng, Aibing Yu and Weihua Li
Y. Wu et al., "Semi-Online Machine Covering under a Grade of Service Provision", Applied Mechanics and Materials, Vols. 101-102, pp. 484-487, 2012