Scheduling a single batch processing machine with non-identical job sizes

1 July 1994

journal article
research article
Published by Taylor & Francis in International Journal of Production Research

Vol. 32 (7) , 1615-1635
https://doi.org/10.1080/00207549408957026

Abstract

The problem of scheduling jobs with non-identical capacity requirements or sizes on a single batch processing machine to minimize total completion time and makespan is studied. These problems are proven to be NP-hard and heuristics are developed for both, as well as a branch and bound algorithm for the total completion time problem. Computational experiments show that the heuristics are capable of rapidly obtaining near-optimal solutions.

Keywords

This publication has 11 references indexed in Scilit:

Minimizing total completion time on batch processing machines
International Journal of Production Research, 1993
Minimizing total completion time on a batch processing machine with job families
Operations Research Letters, 1993
CONTROL OF MULTIPRODUCT BULK SERVICE DIFFUSION/OXIDATION PROCESSES
IIE Transactions, 1992
Efficient Algorithms for Scheduling Semiconductor Burn-In Operations
Operations Research, 1992
Batching and Scheduling Jobs on Batch and Discrete Processors
Operations Research, 1992
Dynamic batching heuristic for simultaneous processing
IEEE Transactions on Semiconductor Manufacturing, 1991
Efficient scheduling algorithms for a single batch processing machine
Operations Research Letters, 1986
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
SIAM Journal on Computing, 1974
Scheduling independent tasks to reduce mean finishing time
Communications of the ACM, 1974
Bounds for the Optimal Scheduling of n Jobs on m Processors
Management Science, 1964