Title
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
Recommended Citation
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.
https://huskiecommons.lib.niu.edu/niubib/479
Department
Department of Industrial and Systems Engineering