Article ID Journal Published Year Pages File Type
1142314 Operations Research Letters 2013 4 Pages PDF
Abstract

We consider the online scheduling of incompatible job families on an unbounded parallel-batch machine to minimize the makespan, where jobs arrive over time and the number of job families, ff, is known in advance. We provide an optimal online algorithm for the problem with a competitive ratio of 1+4f2+1−12f.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan
Authors
, , , ,