Minimizing makespan for arbitrary size jobs with release times on P-batch machines with arbitrary capacities

- Scheduling a set of jobs with arbitrary job sizes and release times on a set of P-batch machines with non-identical capacities is considered.
- The objective is to minimize the makespan.
- Two ACO-based meta-heuristics are proposed to solve the problem.
- The heuristics are evaluated against a lower bound and with each other by computational experiments.

We consider the problem of scheduling a set of arbitrary size jobs with dynamic arrival times on a set of parallel batch machines with arbitrary capacities; our goal is to minimize the makespan. We first give a mathematical model of the problem, and provide a lower bound for the objective function value. Based on different rules of batching the jobs and scheduling the batches on the machines, two meta-heuristics based on Ant Colony Optimization (ACO) are proposed to solve the problem. The performance of the proposed algorithms is evaluated and compared with existing heuristics by computational experiments. Our results show that one of the ACO algorithms consistently finds better solutions than all the others in a reasonable amount of time.