Title: Minimising makespan of a batch processing machine with unequal job ready times using simulated annealing

Authors: Leena Ghrayeb; Purushothaman Damodaran

Addresses: 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: Batch processing machines can process multiple jobs simultaneously. Given a set of jobs with their processing times, ready times, and sizes, the objective is to minimise the makespan. Two interdependent decisions are required: group jobs to form batches and schedule batches on the machine. The processing and ready times of the batch depends on the composition of the batch. Batch ready time is equal to the largest ready time of all the jobs in a batch. Similarly, batch processing time is equal to the largest processing time of all the jobs in a batch. As the problem under study is NP-hard, a simulated annealing (SA) approach is proposed. The proposed approach is evaluated by comparing its solution quality and run time with a commercial solver used to solve a mathematical formulation. An experimental study shows that the SA approach is fast in finding good solutions as the problem size increases.

Keywords: scheduling; batch processing machine; BPM; makespan; simulated annealing.

DOI: 10.1504/IJISE.2023.128670

International Journal of Industrial and Systems Engineering, 2023 Vol.43 No.2, pp.222 - 237

Received: 03 Aug 2020
Accepted: 10 Mar 2021
Published online: 01 Feb 2023 *

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