Title: Minimising makespan of batch processing machine with unequal ready times

Authors: Leena Ghrayeb; Shanthi Muthuswamy; Purushothaman Damodaran

Addresses: Department of Industrial and Systems Engineering, Northern Illinois University, De Kalb, Il-60115, USA ' Department of Engineering Technology, Northern Illinois University, De Kalb, Il-60115, USA ' Department of Industrial and Systems Engineering, Northern Illinois University, De Kalb, Il-60115, USA

Abstract: This research considers scheduling a single batch processing machine at a contract electronics manufacturer. The processing times, ready times and the sizes of the jobs are given and the total size of the batch should not exceed the machine capacity. The batch ready time is equal to the latest ready time of all the jobs in the batch. The objective is to minimise the makespan. The commercial solver used to solve the mathematical formulation proposed requires long run times. Consequently, several heuristics and lower bounding procedures are proposed. Through an experimental study, it is shown that one of the lower bounds is within 40% of the best known integer solution from CPLEX for the 200-job instances. The heuristics are very effective in finding good quality solutions with short run times. For smaller problem instances, the quality of the heuristic solution is within 10% of the best known solution from CPLEX.

Keywords: batch processing machine; BPM; scheduling; makespan; heuristics; lower bound.

DOI: 10.1504/IJISE.2022.122823

International Journal of Industrial and Systems Engineering, 2022 Vol.40 No.4, pp.496 - 512

Received: 28 Apr 2020
Accepted: 02 Jun 2020

Published online: 13 May 2022 *

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