Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1066.90033
Li, Shuguang; Li, Guojun; Zhang, Shaoqiang
Minimizing makespan with release times on identical parallel batching machines. (English)
[J] Discrete Appl. Math. 148, No. 1, 127-134 (2005). ISSN 0166-218X

Summary: We consider the problem of scheduling $n$ jobs on $m$ identical parallel batching machines. Each job is characterized by a release time and a processing time. Each machine can process up to $B$ $(B<n)$ jobs as a batch simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. The objective is to minimize the maximum completion time (makespan). We present a polynomial time approximation scheme (PTAS) for this problem.

MSC 2000:: *90B35 Scheduling theory
90C05 Linear programming

Keywords: Polynomial time approximation scheme; Identical parallel batching machines; Scheduling; Makespan

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]