Minimizing mean completion time in a batch processing system
type: Item
instance of: scholarly article
title: Minimizing mean completion time in a batch processing system
zbMATH Open document ID: 1095.68009
author: Xiaotie Deng
author: Haodi Feng
author: Pixing Zhang
author: Hong Zhu
author: Yuzhong Zhang
published in: Algorithmica
publication date: 2004-09-22T00:00:00Z
review text: We consider batch processing jobs to minimize the mean completion time. A batch processing machine can handle up to \(B\) jobs simultaneously. Each job is represented by an arrival time and a processing time. Jobs processed in a batch have the same completion time, i.e., their common starting time plus the processing time of their longest job. For batch processing, non-preemptive scheduling is usually required and we discuss this case. The batch processing problem reduces to the ordinary uniprocessor system scheduling problem if \(B=1\). We focus on the other extreme case \(B=+\infty\). Even for this seemingly simple extreme case, we are able to show that the problem is NP-hard for the weighted version. In addition, we establish a polynomial time algorithm for a special case when there are only a constant number of job processing times. Finally, we give a polynomial time approximation scheme for the general case.
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 2101910
MaRDI profile type: Publication
full work available at URL: s00453-003-1053-2
OpenAlex ID: W1972778917
DOI: 10.1007/S00453-003-1053-2
description: scientific article; zbMATH DE number 2101910