TY - BOOK

T1 - Scheduling a batching machine

AU - Brucker, P.

AU - Gladky, A.

AU - Hoogeveen, J.A.

AU - Kovalyov, M.Y.

AU - Potts, C.N.

AU - Tautenhahn, T.

AU - Velde, van de, S.L.

PY - 1997

Y1 - 1997

N2 - We address the problem of scheduling n jobs on a batching machine to minimize regular scheduling criteria that are nondecreasing 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 analyze two variants:?? the unbounded model?? where b \geq n;?? and the bounded model?? where b ??<n.??
For the unbounded model??, we give a characterization of a class of optimal schedules??, which leads to a generic dynamic programming algorithm that solves the problem of minimizing an arbitrary regular cost function in pseudopolynomial time??. The characterization leads to more e??cient dynamic programming algorithms for speci??c cost functions??: a polynomial algorithm for minimizing the maximum cost,?? an O(??n^3)???? time algorithm for minimizing the number of tardy jobs,?? an O(??n^2) time algorithm for minimizing the maximum lateness??, and an O(??n log n)?? time algorithm for minimizing the total weighted completion time.?? Furthermore,?? we prove that minimizing the weighted number of tardy jobs and the total weighted tardiness are NP-hard problems??.
For the bounded model,?? we derive an O(??n^{b(??b-1)})???? time dynamic programming algorithm for minimizing total completion time when b > 1; for the case with m di??fferent processing times, we give a dynamic programming algorithm that requires O(b^2 m^2 2^m)?? 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 fi??xed number of batches??.

AB - We address the problem of scheduling n jobs on a batching machine to minimize regular scheduling criteria that are nondecreasing 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 analyze two variants:?? the unbounded model?? where b \geq n;?? and the bounded model?? where b ??<n.??
For the unbounded model??, we give a characterization of a class of optimal schedules??, which leads to a generic dynamic programming algorithm that solves the problem of minimizing an arbitrary regular cost function in pseudopolynomial time??. The characterization leads to more e??cient dynamic programming algorithms for speci??c cost functions??: a polynomial algorithm for minimizing the maximum cost,?? an O(??n^3)???? time algorithm for minimizing the number of tardy jobs,?? an O(??n^2) time algorithm for minimizing the maximum lateness??, and an O(??n log n)?? time algorithm for minimizing the total weighted completion time.?? Furthermore,?? we prove that minimizing the weighted number of tardy jobs and the total weighted tardiness are NP-hard problems??.
For the bounded model,?? we derive an O(??n^{b(??b-1)})???? time dynamic programming algorithm for minimizing total completion time when b > 1; for the case with m di??fferent processing times, we give a dynamic programming algorithm that requires O(b^2 m^2 2^m)?? 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 fi??xed number of batches??.

M3 - Report

T3 - Memorandum COSOR

BT - Scheduling a batching machine

PB - Technische Universiteit Eindhoven

CY - Eindhoven

ER -