Abstract: 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.

Chiuh Cheng Chyu, and Wei-Shung Chang, “Hybrid Metaheuristics for the Unrelated Parallel Machine Scheduling to Minimize Makespan and Maximum Just-in-Time Deviations ” International Journal of Advanced Research in Artificial Intelligence(IJARAI), 1(3), 2012. http://dx.doi.org/10.14569/IJARAI.2012.010302

@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},
doi = {10.14569/IJARAI.2012.010302},
url = {http://dx.doi.org/10.14569/IJARAI.2012.010302},
year = {2012},
publisher = {The Science and Information Organization},
volume = {1},
number = {3},
author = {Chiuh Cheng Chyu, and Wei-Shung Chang}
}