On minimizing total tardiness in a serial batching problem

DOI10.1051/RO:2001105MaRDI QIDQ2765603zbMATH OpenOpenAlexFDO

Authors Philippe Baptiste, Antoine Jouglet

Publication date 25 August 2002

Published in RAIRO. Operations Research (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=RO_2001__35_1_107_0, http://www.numdam.org/item?id=RO_2001__35_1_107_0/, https://eudml.org/doc/197830

zbMATH Keywords

dynamic programmingpseudopolynomial algorithmscheduling of jobstotal tardiness

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Dynamic programming (90C39)

Review text

The article presents a pseudopolynomial algorithm for a scheduling jobs on a serial batching machine minimizing total tardiness (the problem is NP-hard in the ordinary sense). The method used by the algorithm is dynamic programming.

Recommendations

• Earliness and tardiness scheduling problems on a batch processor
• Scheduling a batching machine
• Batching identical jobs
• Solution of the NP-hard total tardiness minimization problem in scheduling theory

Cites work

• Batch sizing and job sequencing on a single machine
• Batching identical jobs
• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• scientific article; zbMATH DE number 830382 (Why is no real title available?)
• scientific article; zbMATH DE number 866105 (Why is no real title available?)
• Minimizing Total Tardiness on One Machine is NP-Hard
• On the Complexity of Scheduling with Batch Setup Times
• Scheduling a batching machine
• Scheduling Groups of Jobs on a Single Machine
• Scheduling with batching: A review
• The complexity of one-machine batching problems

Cited in

(6)

• On minimizing the sum of k tardinesses
• A survey of scheduling problems with setup times or costs
• scientific article; zbMATH DE number 1420452 (Why is no real title available?)
• A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates
• Customer order scheduling on a serial-batch machine in precast bridge construction
• Optimally competitive list batching

This page was built for publication: On minimizing total tardiness in a serial batching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2765603)