×

Online scheduling on parallel machines with two goS levels. (English) Zbl 1176.90221

Summary: This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. Hence, each job and machine are labeled with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The goal is to minimize the makespan. We consider the problem with two GoS levels. It is assumed that the GoS levels of the first \(k\) machines and the last \(m - k\) machines are 1 and 2, respectively. Also, every job has alternatively a GoS level of 1 or 2. We first prove that the lower bound of the problem under consideration is at least 2. Then, we discuss the performance of the algorithm AW presented by Y. Azar et al. [J. Algorithms 18, No. 2, 221–237 (1995; Zbl 0818.68026)] for the problem and show it has a tight bound of \(4 - 1/ m\). Finally, we present an approximation algorithm with competitive ratio \(\frac{12+4\sqrt{2}}{7}\approx 2.522\).

MSC:

90B35 Deterministic scheduling theory in operations research

Citations:

Zbl 0818.68026
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Azar Y, Naor J, Rom R (1995) The competitiveness of on-line assignments. J Algorithms 18:221–237 · Zbl 0818.68026 · doi:10.1006/jagm.1995.1008
[2] Bar-Noy A, Freund A, Naor J (2001) On-line load balancing in a hierarchical server topology. SIAM J Comput 31:527–549 · Zbl 0994.68069 · doi:10.1137/S0097539798346135
[3] Crescenzi P, Gambosi G, Penna P (2004) On-line algorithms for the channel assignment problem in cellular networks. Discret Appl Math 137(3):237–266 · Zbl 1047.90007 · doi:10.1016/S0166-218X(03)00341-X
[4] Hwang H, Chang S, Lee K (2004) Parallel machine scheduling under a grade of service provision. Comput Oper Res 31:2055–2061 · Zbl 1074.68529 · doi:10.1016/S0305-0548(03)00164-3
[5] Jiang YW, He Y, Tang CM (2006) Optimal online algorithms for scheduling on two identical machines under a grade of service. J Zhejiang Univ Sci 7(3):309–314 · Zbl 1108.90314
[6] Lenstra JK, Shmoys DB, Tardos NE (1990) Approximation algorithms for scheduling unrelated parallel machines. Math Program 46:259–271 · Zbl 0715.90063 · doi:10.1007/BF01585745
[7] 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(6):692–696 · Zbl 1112.90036 · doi:10.1016/j.orl.2005.11.004
[8] Zhou P, Jiang YW, He Y (2007) Parallel machines scheduling with two GoS levels. Appl Math J Chin Univ Ser A 22(3):275–284 (in Chinese) · Zbl 0985.35046 · doi:10.1142/S0252959901000280
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.