Using GRASP approach and path relinking to minimise total number of tardy jobs on a single batch processing machine
Author ORCID Identifier
International Journal of Industrial and Systems Engineering
This paper considers scheduling a single batch processing machine such that the total number of tardy jobs is minimised. 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. As the problem under study is NP-hard solving a mathematical formulation optimality is computationally intensive. A greedy randomised adaptive search procedure (GRASP) is proposed 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 and a construction heuristic. Experimental studies suggest that GRASP is superior compared to the commercial solver and the construction heuristic.
Batch processing machine, BPM, GRASP, Number of tardy jobs, Path relinking, Scheduling
Alipour, Panteha; Damodaran, Purushothaman; and Nguyen, Christine, "Using GRASP approach and path relinking to minimise total number of tardy jobs on a single batch processing machine" (2020). NIU Bibliography. 479.
Department of Industrial and Systems Engineering