Cover Image
QR Code

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 there...

Full description

Published in:Scientific World Journal pp. 547573 - 547574
Main Authors: Shi, Xuefei, Xu, Dehua
Format: research Journal Article
Published: Wiley-Blackwell 2014
Online Access:View this record in EBSCOhost
fields @attributes:
  recordID: 1
pdfLink:
plink: https://search.ebscohost.com/login.aspx?direct=true&db=ccm&AN=109665830&site=ehost-live
header:
  @attributes:
    shortDbName: ccm
    uiTerm: 109665830
    longDbName: CINAHL Complete
    uiTag: AN
  controlInfo:
    bkinfo:
    dissinfo:
    jinfo:
      jid:
        1537744X
        1BX5
      jtl: Scientific World Journal
      issn: 1537744X
      maglogo: N
    pubinfo:
      dt: 2014
      pid: 480
      pub: Wiley-Blackwell
      place: Malden, Massachusetts
    artinfo:
      ui:
        109665830
        109665830
        NLM24701177
        2012535257
        10.1155/2014/547573
        NLM24701177
        PMC3950368
        109665830
      ppf: 547573
      ppct: 1
      formats:
      tig:
        atl: Best possible approximation algorithms for single machine scheduling with increasing linear maintenance durations.
      aug:
        au:
          Shi, Xuefei
          Xu, Dehua
      sug:
        subj:
          Equipment and Supplies
          Algorithms
          Comparative Studies
          Multicenter Studies
          Evaluation Research
          Validation Studies
      ab: 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.
      pubtype: Academic Journal
      doctype:
        research
        Journal Article
      ougenre: Article
    language: English
    refInfo:
    holdings:
      @attributes:
        islocal: N