This talk will summarize the main characteristics of the scheduling problems and introduce the non-availability constraints' context. More precisely, we will focus on the description of two scenarios: the offline and the semi-online contexts. The first part of this talk will be devoted to the presentation of the considered optimization problems and their applications. In the second part, we will show that the performance evaluation of some heuristics can be analytically done in the context of the polynomial approximation theory. The differential and absolute approximation measures will be described. As an illustration, we will show analytically some guaranteed performance ratios of approximation algorithms and schemes for solving scheduling problems under non-availability constraints. The studied criterion is the maximum lateness in offline and semi-online contexts.