Defining real-world optimization problems requires the consideration of a certain level of uncertainty in the specified input parameters. Optimizing in manufacturing environments often involves a complex representation of uncertainty. This paper addresses the non-deterministic job scheduling on unrelated machines with well-defined setup times, uncertain release dates, and uncertain processing times. The parameters of the jobs are machine dependent. In this research, uncertainties are represented in the form of defined intervals, and the minimax regret criterion for the makespan is used to evaluate the quality of schedules. A mathematical programming model is developed for the deterministic version of the scheduling problem (in the non-deterministic version, the criterion value cannot be computed in polynomial time). Although two parameters are uncertain, the set containing feasible scenarios, which maximize a regret value, can be determined in polynomial time. In order to solve the robust scheduling problem, two constructive heuristics are developed.