Scheduling a batching machine

P. Brucker, A. Gladky, J.A. Hoogeveen, M.Y. Kovalyov, C.N. Potts, T. Tautenhahn, S.L. Velde, van de

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

369 Citaten (Scopus)

Samenvatting

We address the problem of scheduling n jobs on a batching machine to minimize regular scheduling criteria that are non-decreasing in the job completion times. A batching machine is a machine that can handle up to b jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is equal to the largest processing time of any job in the batch. We analyse two variants: the unbounded model, where b¿n; and the bounded model, where b1; for the case with m different processing times, we give a dynamic programming algorithm that requires O(b2m22m) time. Moreover, we prove that due date based scheduling criteria give rise to NP-hard problems. Finally, we show that an arbitrary regular cost function can be minimized in polynomial time for a fixed number of batches.
Originele taal-2Engels
Pagina's (van-tot)31-54
Aantal pagina's24
TijdschriftJournal of Scheduling
Volume1
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 1998

Vingerafdruk

Duik in de onderzoeksthema's van 'Scheduling a batching machine'. Samen vormen ze een unieke vingerafdruk.

Citeer dit