This paper studies a parallel heterogeneous machine batching and scheduling problem in which weighted jobs are first batched, and the batches are then assigned and sequenced on machines of varying capacities. The duration of a batch is the longest time needed to process a job, and the objective is that of minimizing the makespan, or the sum of the batches durations on the machine finishing last. The authors develop polynomial-size mathematical formulations and a variable neighborhood search metaheuristic. Extensive computational results suggest that a flow-based formulation outperforms a compact formulation, despite its larger number of variables. The metaheuristic is capable of producing high-quality solutions within a limited computing time.

Original languageEnglish
Article number106708
JournalComputers and Operations Research
Early online date25 May 2024
Publication statusE-pub ahead of print - 25 May 2024

Data Availability Statement

Data will be made available on request.


Thanks are due to the Associate Editor and to the referees for their valuable comments. The work reported in this paper was undertaken as part of the Made Smarter Innovation: Centre for People-Led Digitalization, at the University of Bath, University of Nottingham, and Loughborough University.


  • Batch processing machines
  • Makespan minimization
  • Parallel machines
  • Variable neighborhood search

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this