Hybrid Metaheuristics for the Unrelated Parallel Machine Scheduling to Minimize Makespan and Maximum Just-in-Time Deviations

This paper studies the unrelated parallel machine scheduling problem with three minimization objectives – makespan, maximum earliness, and maximum tardiness (MET-UPMSP). The last two objectives combined are related to just-in-time (JIT) performance of a solution. Three hybrid algorithms are presented to solve the MET-UPMSP: reactive GRASP with path relinking, dual-archived memetic algorithm (DAMA), and SPEA2. In order to improve the solution quality, min-max matching is included in the decoding scheme for each algorithm. An experiment is conducted to evaluate the performance of the three algorithms, using 100 (jobs) x 3 (machines) and 200 x 5 problem instances with three combinations of two due date factors – tight and range. The numerical results indicate that DAMA performs best and GRASP performs second for most problem instances in three performance metrics: HVR, GD, and Spread. The experimental results also show that incorporating min-max matching into decoding scheme significantly improves the solution quality for the two population-based algorithms. It is worth noting that the solutions produced by DAMA with matching decoding can be used as benchmark to evaluate the performance of other algorithms.

@article{Chyu,2012,
  title     = {Hybrid Metaheuristics for the Unrelated Parallel Machine Scheduling to Minimize Makespan and Maximum Just-in-Time Deviations},
  journal   = {International Journal of Advanced Research in Artificial Intelligence},
  volume    = {1},
  number    = {3},
  year      = {2012},
  publisher = {The Science and Information Organization},
  author    = {Chiuh Cheng Chyu, and Wei-Shung Chang},
  doi       = {10.14569/IJARAI.2012.010302},
  url       = {https://doi.org/10.14569/IJARAI.2012.010302}
}