Non-identical parallel machines batch processing problem to minimize the makespan: Models and algorithms

Pedram Beldar; Maria Battarra; Gilbert Laporte

doi:10.1016/j.cor.2024.106708

Non-identical parallel machines batch processing problem to minimize the makespan: Models and algorithms

Pedram Beldar, Maria Battarra, Gilbert Laporte

University of Skövde

Research output: Contribution to journal › Article › peer-review

2 Citations (SciVal)

Abstract

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 language	English
Article number	106708
Journal	Computers and Operations Research
Volume	168
Early online date	25 May 2024
DOIs	https://doi.org/10.1016/j.cor.2024.106708
Publication status	Published - 31 Aug 2024

Data Availability Statement

Data will be made available on request.

Acknowledgements

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.

Funding

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. The project is funded by the Engineering and Physical Sciences Research Council (EPSRC), United Kingdom Grant EP/V062042/1. 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. The project is funded by the Engineering and Physical Sciences Research Council (EPSRC) Grant EP/V062042/1 .

Funders	Funder number
University of Nottingham
Loughborough University
Engineering and Physical Sciences Research Council	EP/V062042/1
Engineering and Physical Sciences Research Council

Keywords

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

Access to Document

10.1016/j.cor.2024.106708Licence: CC BY

Cite this

@article{74d1865e39214f53b12eb7b7740b8f1d,

title = "Non-identical parallel machines batch processing problem to minimize the makespan: Models and algorithms",

abstract = "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.",

keywords = "Batch processing machines, Makespan minimization, Parallel machines, Variable neighborhood search",

author = "Pedram Beldar and Maria Battarra and Gilbert Laporte",

year = "2024",

month = aug,

day = "31",

doi = "10.1016/j.cor.2024.106708",

language = "English",

volume = "168",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier",

}

TY - JOUR

T1 - Non-identical parallel machines batch processing problem to minimize the makespan

T2 - Models and algorithms

AU - Beldar, Pedram

AU - Battarra, Maria

AU - Laporte, Gilbert

PY - 2024/8/31

Y1 - 2024/8/31

N2 - 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.

AB - 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.

KW - Batch processing machines

KW - Makespan minimization

KW - Parallel machines

KW - Variable neighborhood search

UR - http://www.scopus.com/inward/record.url?scp=85194702464&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2024.106708

DO - 10.1016/j.cor.2024.106708

M3 - Article

SN - 0305-0548

VL - 168

JO - Computers and Operations Research

JF - Computers and Operations Research

M1 - 106708

ER -

Non-identical parallel machines batch processing problem to minimize the makespan: Models and algorithms

Abstract

Data Availability Statement

Acknowledgements

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this