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
_version_ 1782479061112586240
author Luo, Taibo
Xu, Yinfeng
author_facet Luo, Taibo
Xu, Yinfeng
author_sort Luo, Taibo
collection PubMed
description 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.
format Online
Article
Text
id pubmed-3942401
institution National Center for Biotechnology Information
language English
publishDate 2014
publisher Hindawi Publishing Corporation
record_format MEDLINE/PubMed
spelling pubmed-39424012014-03-26 Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time Luo, Taibo Xu, Yinfeng ScientificWorldJournal Research Article 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. Hindawi Publishing Corporation 2014-02-11 /pmc/articles/PMC3942401/ /pubmed/24672335 http://dx.doi.org/10.1155/2014/576234 Text en Copyright © 2014 T. Luo and Y. Xu. https://creativecommons.org/licenses/by/3.0/ This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research Article
Luo, Taibo
Xu, Yinfeng
Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time
title Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time
title_full Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time
title_fullStr Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time
title_full_unstemmed Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time
title_short Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time
title_sort semi-online scheduling on two machines with gos levels and partial information of processing time
topic Research Article
url 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
work_keys_str_mv AT luotaibo semionlineschedulingontwomachineswithgoslevelsandpartialinformationofprocessingtime
AT xuyinfeng semionlineschedulingontwomachineswithgoslevelsandpartialinformationofprocessingtime

Ejemplares similares