File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/3540456783_33
 Scopus: eid_2s2.027844461510
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Article: Online scheduling a batch processing system to minimize total weighted job completion time
Title  Online scheduling a batch processing system to minimize total weighted job completion time 

Authors  
Issue Date  2001 
Publisher  Springer 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. 380389 How to Cite? 
Abstract  Scheduling 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 online 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 online algorithm for the unrestrictive model (i.e., b ≥ n) and show that the algorithm is 10/3competitive. For the restrictive model (i.e., b < n), we first consider the (offline) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NPhard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + ε)competitive online algorithm for any ε > 0 for the original online scheduling problem. These two online algorithms are the first deterministic algorithms of constant performance guarantees. © 2001 Springer Berlin Heidelberg. 
Persistent Identifier  http://hdl.handle.net/10722/75155 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Chen, B  en_HK 
dc.contributor.author  Deng, X  en_HK 
dc.contributor.author  Zang, W  en_HK 
dc.date.accessioned  20100906T07:08:27Z   
dc.date.available  20100906T07:08:27Z   
dc.date.issued  2001  en_HK 
dc.identifier.citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2001, v. 2223 LNCS, p. 380389  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/75155   
dc.description.abstract  Scheduling 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 online 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 online algorithm for the unrestrictive model (i.e., b ≥ n) and show that the algorithm is 10/3competitive. For the restrictive model (i.e., b < n), we first consider the (offline) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NPhard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + ε)competitive online algorithm for any ε > 0 for the original online scheduling problem. These two online algorithms are the first deterministic algorithms of constant performance guarantees. © 2001 Springer Berlin Heidelberg.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  en_HK 
dc.title  Online scheduling a batch processing system to minimize total weighted job completion time  en_HK 
dc.type  Article  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=13826905&volume=8&spage=85&epage=95&date=2004&atitle=Online+Scheduling+a+Batch+Processing+System+to+Minimize+Total+Weighted+Job+Completion+Time  en_HK 
dc.identifier.email  Zang, W:wzang@maths.hku.hk  en_HK 
dc.identifier.authority  Zang, W=rp00839  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.doi  10.1007/3540456783_33  en_HK 
dc.identifier.scopus  eid_2s2.027844461510  en_HK 
dc.identifier.hkuros  88803  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.027844461510&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  2223 LNCS  en_HK 
dc.identifier.spage  380  en_HK 
dc.identifier.epage  389  en_HK 
dc.publisher.place  Germany  en_HK 
dc.identifier.scopusauthorid  Chen, B=11839699400  en_HK 
dc.identifier.scopusauthorid  Deng, X=7401768881  en_HK 
dc.identifier.scopusauthorid  Zang, W=7005740804  en_HK 