Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 22-34 |
Number of pages | 13 |
Journal | Future Generation Computer Systems |
Volume | 67 |
DOIs | |
State | Published - Feb 1 2017 |
All Science Journal Classification (ASJC) codes
- Software
- Hardware and Architecture
- Computer Networks and Communications
Keywords
- Ant colony optimization
- Makespan
- Parallel batch machines with arbitrary capacities
- Release times
- Scheduling