Title: Using GRASP approach and path relinking to minimise total number of tardy jobs on a single batch processing machine

Authors: Panteha Alipour; Purushothaman Damodaran; Christine Nguyen

Addresses: Department of Industrial Engineering, Purdue University, West Lafayette, IN 47907, USA ' Department of Industrial and Systems Engineering, Northern Illinois University, DeKalb, IL 60115, USA ' Department of Industrial and Systems Engineering, Northern Illinois University, DeKalb, IL 60115, USA

Abstract: 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.

Keywords: number of tardy jobs; batch processing machine; BPM; scheduling; GRASP; path relinking.

DOI: 10.1504/IJISE.2020.106852

International Journal of Industrial and Systems Engineering, 2020 Vol.35 No.1, pp.80 - 99

Received: 11 Jun 2018
Accepted: 22 Sep 2018
Published online: 23 Apr 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article