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

Author ORCID Identifier

Purushothaman Damodaran:https://orcid.org/0000-0002-6925-8486

Christine Nguyen:https://orcid.org/0000-0003-1260-8956

Publication Title

International Journal of Industrial and Systems Engineering

ISSN

17485037

E-ISSN

43941

Document Type

Article

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.

First Page

57

Last Page

79

Publication Date

1-1-2020

DOI

10.1504/IJISE.2020.106852

Keywords

Batch processing machine, BPM, GRASP, Number of tardy jobs, Path relinking, Scheduling

Department

Department of Industrial and Systems Engineering

Link to Full Text

Share

COinS