Cargando…

Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations

We consider a single machine scheduling problem with multiple maintenance activities, where the maintenance duration function is of the linear form f(t) = a+bt with a ≥ 0 and b > 1. We propose an approximation algorithm named FFD-LS2I with a worst-case bound of 2 for problem. We also show that th...

Descripción completa

Detalles Bibliográficos
Autores principales: Shi, Xuefei, Xu, Dehua
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Hindawi Publishing Corporation 2014
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3950368/
https://www.ncbi.nlm.nih.gov/pubmed/24701177
http://dx.doi.org/10.1155/2014/547573
_version_ 1782306972378333184
author Shi, Xuefei
Xu, Dehua
author_facet Shi, Xuefei
Xu, Dehua
author_sort Shi, Xuefei
collection PubMed
description We consider a single machine scheduling problem with multiple maintenance activities, where the maintenance duration function is of the linear form f(t) = a+bt with a ≥ 0 and b > 1. We propose an approximation algorithm named FFD-LS2I with a worst-case bound of 2 for problem. We also show that there is no polynomial time approximation algorithm with a worst-case bound less than 2 for the problem with b ≥ 0 unless P = NP, which implies that the FFD-LS2I algorithm is the best possible algorithm for the case b > 1 and that the FFD-LS algorithm, which is proposed in the literature, is the best possible algorithm for the case b ≤ 1 both from the worst-case bound point of view.
format Online
Article
Text
id pubmed-3950368
institution National Center for Biotechnology Information
language English
publishDate 2014
publisher Hindawi Publishing Corporation
record_format MEDLINE/PubMed
spelling pubmed-39503682014-04-03 Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations Shi, Xuefei Xu, Dehua ScientificWorldJournal Research Article We consider a single machine scheduling problem with multiple maintenance activities, where the maintenance duration function is of the linear form f(t) = a+bt with a ≥ 0 and b > 1. We propose an approximation algorithm named FFD-LS2I with a worst-case bound of 2 for problem. We also show that there is no polynomial time approximation algorithm with a worst-case bound less than 2 for the problem with b ≥ 0 unless P = NP, which implies that the FFD-LS2I algorithm is the best possible algorithm for the case b > 1 and that the FFD-LS algorithm, which is proposed in the literature, is the best possible algorithm for the case b ≤ 1 both from the worst-case bound point of view. Hindawi Publishing Corporation 2014-02-13 /pmc/articles/PMC3950368/ /pubmed/24701177 http://dx.doi.org/10.1155/2014/547573 Text en Copyright © 2014 X. Shi and D. 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
Shi, Xuefei
Xu, Dehua
Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations
title Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations
title_full Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations
title_fullStr Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations
title_full_unstemmed Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations
title_short Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations
title_sort best possible approximation algorithms for single machine scheduling with increasing linear maintenance durations
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3950368/
https://www.ncbi.nlm.nih.gov/pubmed/24701177
http://dx.doi.org/10.1155/2014/547573
work_keys_str_mv AT shixuefei bestpossibleapproximationalgorithmsforsinglemachineschedulingwithincreasinglinearmaintenancedurations
AT xudehua bestpossibleapproximationalgorithmsforsinglemachineschedulingwithincreasinglinearmaintenancedurations