CP-SAT in Multiobjective Optimization and Decision Analysis for Scheduling on Parallel Machines

This work studies the unrelated parallel machine scheduling problem from a multi-objective perspective. A Constraint Programming model and the ε-constraint method were employed to extract the Pareto Front. The CP-SAT approach demonstrated better computational performance over Mixed Integer Linear Programming regarding solution quality. In a computational experiment with 33 instances, the CP model achieved an average gap of 51.99% whereas the MILP closed with an average gap of 58.32%, a reduction proven to be statistically significant by the paired Student's t-test. After verifying the strong performance of CP-SAT compared to MILP, the complete resolution of the multi-objective problem was conducted for one of the instances. The resulting frontier revealed three non-dominated solutions, which were evaluated using the Hypervolume indicator. Solution 3 was chosen as the most suitable, reflecting the high priority assigned to tardiness reduction within the evaluated scenario.