On-Line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time

Bo Chen (), Xiaotie Deng () and Wenan Zang ()
Additional contact information
Bo Chen: University of Warwick
Xiaotie Deng: City University of Hong Kong
Wenan Zang: University of Hong Kong

Journal of Combinatorial Optimization, 2004, vol. 8, issue 1, No 6, 85-95

Abstract: 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. 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 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 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees.

Keywords: scheduling; batch processing; on-line; performance guarantee (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1023/B:JOCO.0000021939.01674.1f Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:8:y:2004:i:1:d:10.1023_b:joco.0000021939.01674.1f

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/B:JOCO.0000021939.01674.1f

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().