Abstract
We study the problem of semi-online scheduling on 2 machines under a grade of service (GoS). GoS means that some jobs have to be processed by some machines to be guaranteed a high quality. The problem is online in the sense that jobs are presented one by one, and each job shall be assigned to a time slot on its arrival. Assume that the processing time p i of every job J i is bounded by an interval [a,α a], where a>0 and α>1 are two constant numbers. By knowing the bound of jobs’ processing times, we denote it by semi-online problem. We deal with two semi-online problems.
The first one concerns about bounded processing time constraint. First, we show that a lower bound of competitive ratio is: (1) \(\frac{1+\alpha}{2}\) in the case where 1<α<2; (2) \(\frac{3}{2}\) in the case where 2≤α<5; and (3) \(\frac{4+\alpha}{6}\) in the case where 5≤α<6. We further propose an algorithm, called B-ONLINE, and prove that in the case where \(\frac{25}{14}\leq \alpha\) and the optimal makespan C OPT ≥20a, B-ONLINE algorithm is optimal.
For the second problem, we further know the sum of jobs’ processing times Σ in advance. We first show a lower bound \(\frac{1+\alpha}{2}\) in the case where 1<α<2, then we propose an algorithm B-SUM-ONLINE which is optimal in the case where \(\Sigma \geq \frac{2\alpha}{\alpha-1}a\) and 1<α<2.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge
He Y, Zhang G (1999) Semi on-line scheduling on two identical machines. Computing 62:179–187
Hwang H, Chang S, Lee K (2004) Parallel machines scheduling under a grade of service provision. Comput Oper Res 31:2055–2061
Jiang Y (2008) Online scheduling on parallel machines with two GoS levels. J Comb Optim 16:28–38
Jiang Y, He Y, Tang C (2006) Optimal online algorithms for scheduling on two identical machines under a grade of service. J Zhejiang Univ Sci A 7(3):309–314
Park J, Chang SY, Lee K (2006) Online and semi-online scheduling of two machines under a grade of service provision. Oper Res Lett 34:692–696
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Liu, M., Chu, C., Xu, Y. et al. Semi-online scheduling on 2 machines under a grade of service provision with bounded processing times. J Comb Optim 21, 138–149 (2011). https://doi.org/10.1007/s10878-009-9231-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-009-9231-z