Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities

We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m parallel batch machines with non-identical capacities; the objective is to minimize the makespan. The problem is known to be NP-hard. A heuristic based on the First-Fit-Decreasing (FFD) rule is presented as well as a meta-heuristic based on Max-Min Ant System (MMAS). The performances of the two heuristics are compared with a previously studied heuristic by computational experiments. The results show that both proposed algorithms outperform the previously studied heuristic. Moreover, the MMAS heuristic obtains better solutions compared with the FFD heuristic.