Abstract
We consider the problem of scheduling a set of n jobs with arbitrary job sizes, processing times and release times on a set of m parallel batch machines with non-identical capacities; the objective is to minimize the makespan. We first present an algorithm to compute a lower bound for the optimal makespan. Based on different rules of batching the jobs and assigning the batches to the machines, several heuristics are proposed to solve the problem. The performance of the proposed heuristics is evaluated by computational experiments. The proposed heuristics are compared against the lower bound and against each other. Our results show that the one of the proposed algorithms outperforms all the other heuristics.
Original language | English (US) |
---|---|
Pages (from-to) | 977-993 |
Number of pages | 17 |
Journal | Journal of Industrial and Management Optimization |
Volume | 13 |
Issue number | 2 |
DOIs | |
State | Published - Apr 1 2017 |
All Science Journal Classification (ASJC) codes
- Business and International Management
- Strategy and Management
- Control and Optimization
- Applied Mathematics
Keywords
- Heuristics
- Makespan
- Non-identical job sizes
- Non-identical machine capacities
- Parallel batch machines
- Release times