A Dual-Archive Memetic Algorithm for Unrelated Parallel-Machine Scheduling to Minimize Total Weighted Flow Time and Weighted Tardiness

摘要

This paper presents an effective approach to solving unrelated parallel-machine scheduling problems that minimizes two aggregation objectives: total weighted flow time and total weighted tardiness. At each iteration step, the approach partitions the objective space using different weights on each objective, and applies weighted bipartite matching (WBM) to find the best neighborhood solution in each objective subspace. Three algorithms are used to assess this approach: NSGAII, SPEA2, and DAMA (dual-archive memetic algorithm). When using WBM, weighted apparent tardiness cost with setups (W-ATCS) is employed to solve single machine scheduling problems. For DAMA, two dissimilar archives are maintained at each generation: one archive preserves efficient solutions, the other preserves inefficient solutions, and the two archives compete to produce next generation offspring. An experiment was conducted to evaluate the proposed approach based on several performance metrics. The results indicate that decoding scheme using WBM will produce significantly better solutions, regardless of which algorithm is employed. The results also show that using random weights (RW) on objectives for evolution excels using fixed weights (FW). Finally, DAMA_RW outperforms all other algorithms based on the same number of calculated solutions.