Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time

This paper investigates semi-online scheduling problems on two parallel machines under a grade of service (GoS) provision subject to minimize the makespan. We consider three different semi-online versions with knowing the total processing time of the jobs with higher GoS level, knowing the total pro...

Descripción completa

Detalles Bibliográficos
Autores principales: Luo, Taibo, Xu, Yinfeng
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Hindawi Publishing Corporation 2014
Materias:
Research Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3942401/
https://www.ncbi.nlm.nih.gov/pubmed/24672335
http://dx.doi.org/10.1155/2014/576234
Descripción
Sumario:This paper investigates semi-online scheduling problems on two parallel machines under a grade of service (GoS) provision subject to minimize the makespan. We consider three different semi-online versions with knowing the total processing time of the jobs with higher GoS level, knowing the total processing time of the jobs with lower GoS level, or knowing both in advance. Respectively, for the three semi-online versions, we develop algorithms with competitive ratios of 3/2, 20/13, and 4/3 which are shown to be optimal.

Ejemplares similares