File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On-line scheduling a batch processing system to minimize total weighted job completion time

TitleOn-line scheduling a batch processing system to minimize total weighted job completion time
Authors
KeywordsBatch Processing
On-Line
Performance Guarantee
Scheduling
Issue Date2004
PublisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905
Citation
Journal Of Combinatorial Optimization, 2004, v. 8 n. 1, p. 85-95 How to Cite?
AbstractScheduling a batch processing system has been extensively studied in the last decade. A batch processing system is modelled as a machine that can process up to b jobs simultaneously as a batch. The scheduling problem involves assigning all n jobs to batches and determining the batch sequence in such a way that certain objective function of job completion times Cj is minimized. In this paper, we address the scheduling problem under the on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job that may arrive later. Our objective is to minimize the total weighted completion time σ w jCj. We provide a linear time on-line algorithm for the unrestrictive model (i.e., b ≥ n) and show that the algorithm is 10/3-competitive. For the restrictive model (i.e., b < n), we first consider the (off-line) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NP-hard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + 6)-competitive on-line algorithm for any 6 > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees.
Persistent Identifierhttp://hdl.handle.net/10722/156197
ISSN
2015 Impact Factor: 1.08
2015 SCImago Journal Rankings: 1.093
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChen, Ben_US
dc.contributor.authorDeng, Xen_US
dc.contributor.authorZang, Wen_US
dc.date.accessioned2012-08-08T08:40:48Z-
dc.date.available2012-08-08T08:40:48Z-
dc.date.issued2004en_US
dc.identifier.citationJournal Of Combinatorial Optimization, 2004, v. 8 n. 1, p. 85-95en_US
dc.identifier.issn1382-6905en_US
dc.identifier.urihttp://hdl.handle.net/10722/156197-
dc.description.abstractScheduling a batch processing system has been extensively studied in the last decade. A batch processing system is modelled as a machine that can process up to b jobs simultaneously as a batch. The scheduling problem involves assigning all n jobs to batches and determining the batch sequence in such a way that certain objective function of job completion times Cj is minimized. In this paper, we address the scheduling problem under the on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job that may arrive later. Our objective is to minimize the total weighted completion time σ w jCj. We provide a linear time on-line algorithm for the unrestrictive model (i.e., b ≥ n) and show that the algorithm is 10/3-competitive. For the restrictive model (i.e., b < n), we first consider the (off-line) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NP-hard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + 6)-competitive on-line algorithm for any 6 > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees.en_US
dc.languageengen_US
dc.publisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905en_US
dc.relation.ispartofJournal of Combinatorial Optimizationen_US
dc.subjectBatch Processingen_US
dc.subjectOn-Lineen_US
dc.subjectPerformance Guaranteeen_US
dc.subjectSchedulingen_US
dc.titleOn-line scheduling a batch processing system to minimize total weighted job completion timeen_US
dc.typeArticleen_US
dc.identifier.emailZang, W:wzang@maths.hku.hken_US
dc.identifier.authorityZang, W=rp00839en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1023/B:JOCO.0000021939.01674.1fen_US
dc.identifier.scopuseid_2-s2.0-3543088593en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-3543088593&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume8en_US
dc.identifier.issue1en_US
dc.identifier.spage85en_US
dc.identifier.epage95en_US
dc.identifier.isiWOS:000220451200006-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridChen, B=11839699400en_US
dc.identifier.scopusauthoridDeng, X=7401768881en_US
dc.identifier.scopusauthoridZang, W=7005740804en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats