Batch machine production with perishability time windows and limited batch size
This article provides a theoretical analysis of the problem of scheduling jobs in batches by family on a batch-processing machine, in the presence of perishability time windows of equal length. The problem arises in the context of production planning in a microbiological laboratory, and has application in wafer-fab production and for wireless broadcasting. The combined features of multiple families and time windows are new to the literature. The study is restricted to unit job processing times. We prove that the problem is NP-hard, thus solving an open problem by Uzsoy [24]. A Dynamic Programme is developed, with running time polynomial in the input variables of maximum batch size, the number of families and the length of the demand time horizon. In addition, we show that an heuristic approach to minimising the perishability time window can provide a 2-approximation to the optimum.
Year of publication: |
2011
|
---|---|
Authors: | Chakhlevitch, Konstantin ; Glass, Celia A. ; Kellerer, Hans |
Published in: |
European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 210.2011, 1, p. 39-47
|
Publisher: |
Elsevier |
Keywords: | Scheduling Batch production Broadcast scheduling Optimisation |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Batch machine production with perishability time windows and limited batch size
Chakhlevitch, Konstantin, (2011)
-
Batch machine production with perishability time windows and limited batch size
Chakhlevitch, Konstantin, (2011)
-
Minimising the number of gap-zeros in binary matrices
Chakhlevitch, Konstantin, (2013)
- More ...