A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes

•We consider makespan minimization of a set of jobs on parallel batch machines.•A MMAS-based heuristic is proposed to batch the jobs.•The batches are then scheduled by the Multi-Fit algorithm on the machines.•Experimental results show that our algorithm outperforms other algorithms. We consider the...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2015-02, Vol.240 (3), p.649-665
Main Authors: Jia, Zhao-hong, Leung, Joseph Y.-T.
Format: Article
Language:English
Subjects:
Heuristic
Job shops
Mathematical problems
Max–min ant system
Meta-heuristic
NP-hard
Parallel batch machines
Production scheduling
Scheduling algorithms
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We consider makespan minimization of a set of jobs on parallel batch machines.•A MMAS-based heuristic is proposed to batch the jobs.•The batches are then scheduled by the Multi-Fit algorithm on the machines.•Experimental results show that our algorithm outperforms other algorithms. We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m identical and parallel batch machines so as to minimize the makespan. Motivated by the computational complexity of the problem, we propose a meta-heuristic based on the max–min ant system method. Computational experiments are performed with randomly generated test data. The results show that our algorithm outperforms several of the previously studied algorithms.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2014.07.039