Abstract
This paper considers a production-distribution scheduling problem on parallel batch processing machines (BPMs) with multiple vehicles. In the production stage, the jobs with non-identical sizes and equal processing time are grouped into batches, which are processed on BPMs. In the distribution stage, there are vehicles with identical capacity arriving regularly to transport the batches to the customers. The objective is to minimize the total weighted delivery time of the jobs. A method of computing a lower bound is given to evaluate the proposed algorithms. To tackle this NP-hard problem, a deterministic heuristic (Algorithm H) and two hybrid meta-heuristic algorithms based on ant colony optimization (HACO, MMAS) are proposed, respectively. Through analyzing the property of the investigated problem, the heuristic information and the pheromone trails are defined. Incorporated with a local optimization strategy, the ant colony constructs the schedule first. Then, a heuristic is designed to transport the batches that have been processed. The performance of the proposed algorithms are compared with each other through testing on randomly generated problem instances. It is shown that the proposed MMAS algorithm slightly beats the HACO algorithm, which can find the better solutions than the H algorithm in a reasonable amount of time.
Original language | English (US) |
---|---|
Pages (from-to) | 39-51 |
Number of pages | 13 |
Journal | Computers and Operations Research |
Volume | 102 |
DOIs | |
State | Published - Feb 2019 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Computer Science
- Modeling and Simulation
- Management Science and Operations Research
Keywords
- Ant colony optimization algorithm
- Batch processing machines
- Integrated production and transportation
- Local optimization
- Non-identical job sizes