Joint Optimization of Unrelated Parallel Machine Scheduling and Multi-Trips Vehicle Routing with Time Windows
摘要
This study examines the difficulties of synchronizing production and distribution scheduling, with a particular focus on the Unrelated Parallel Machine Scheduling Problem (UPMSP) in production and the Multi-Trip Vehicle Routing Problem (VRP) in distribution. The objective is to minimize the makespan, total weighted tardiness, and transportation costs, while ensuring efficient batch deliveries using a fleet of homogeneous-capacity vehicles. To tackle this complex problem, we formulate a Mixed-Integer Nonlinear Programming (MINLP) model and propose a Genetic Algorithm (GA) as a solution approach. Since no established benchmarks exist for this specific problem, we evaluate the performance of our GA by comparing its solutions against IBM CPLEX, a state-of-the-art exact solver. The comparison focuses on small-scale instances generated in this study. Results indicate that the proposed GA is capable of reaching optimal solutions for most small-sized instances, demonstrating its effectiveness in solving this challenging integrated scheduling problem.