  This paper considers the problem of scheduling a single batch processing
machine such that the total number of tardy jobs is minimized. The machine can
simultaneously process several jobs as a batch as long as the machine capacity
is not violated. The batch processing time is equal to the largest processing
time among those jobs in the batch. Two decisions are made to schedule jobs on
the batch processing machine, namely grouping jobs to form batches and
sequencing the batches on the machines. Both the decisions are interdependent
as the composition of the batch affects the processing time of the batch. The
problem under study is NP-hard. Consequently, solving a mathematical
formulation to find an optimal solution is computationally intensive. A Greedy
Randomized Adaptive Search Procedure (GRASP) is proposed to solve the problem
under study with the assumption of arbitrary job sizes, arbitrary processing
times and arbitrary due dates. A novel construction phase for the GRASP
approach is proposed to improve the solution quality. In addition, a path
relinking procedure is proposed for solving large-sized problems effectively.
The performance of the proposed GRASP approach is evaluated by comparing its
results to a commercial solver (which was used to solve the mathematical model)
and a construction heuristic. Experimental studies suggest that the solution
obtained from the GRASP approach is superior compared to the commercial solver
and the construction heuristic.
