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
Issue Date2001
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2001, v. 2223 LNCS, p. 380-389 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.Th e 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 C j 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 j C j . 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 + ε)-competitive on-line algorithm for any ε > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees. © 2001 Springer Berlin Heidelberg.
Persistent Identifierhttp://hdl.handle.net/10722/75155
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorChen, Ben_HK
dc.contributor.authorDeng, Xen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2010-09-06T07:08:27Z-
dc.date.available2010-09-06T07:08:27Z-
dc.date.issued2001en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2001, v. 2223 LNCS, p. 380-389en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/75155-
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.Th e 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 C j 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 j C j . 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 + ε)-competitive on-line algorithm for any ε > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees. © 2001 Springer Berlin Heidelberg.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleOn-line scheduling a batch processing system to minimize total weighted job completion timeen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1382-6905&volume=8&spage=85&epage=95&date=2004&atitle=On-line+Scheduling+a+Batch+Processing+System+to+Minimize+Total+Weighted+Job+Completion+Timeen_HK
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/3-540-45678-3_33en_HK
dc.identifier.scopuseid_2-s2.0-27844461510en_HK
dc.identifier.hkuros88803en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-27844461510&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume2223 LNCSen_HK
dc.identifier.spage380en_HK
dc.identifier.epage389en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChen, B=11839699400en_HK
dc.identifier.scopusauthoridDeng, X=7401768881en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats