  This paper presents a profound analysis of the robust job scheduling problem
with uncertain release dates on unrelated machines. Our model involves
minimizing the worst-case makespan and interval uncertainty where each release
date belongs to a well-defined interval. Robust optimization requires
scenario-based decision-making. A finite subset of feasible scenarios to
determine the worst-case regret (a deviation from the optimal makespan) for a
particular schedule is indicated. We formulate a mixed-integer nonlinear
programming model to solve the underlying problem via three (constructive)
greedy algorithms. Polynomial-time solvable cases are also discussed in detail.
The algorithms solve the robust combinatorial problem using the makespan
criterion and its non-deterministic counterpart. Computational testing compares
both robust solutions and different decomposition strategies. Finally, the
results confirm that a decomposition strategy applied to the makespan criterion
is enough to create a competitive robust schedule.

Optimization and Control;Discrete Mathematics