Unrelated parallel machine scheduling under constraints: stability number of an associated graph

This paper outlines a new formulation for the decision problem defined by Rm|r_j, d_j, s_ijk, M_j |-. This problem deals with scheduling tasks on parallel unrelated machines. Time windows constraints, dependencies on sequences, machine eligibility constraints as well as capacity restrictions are taken into account. We present the main known results for this class of problems. On the basis of state variables and binary exclusion relations, we define two particular graphs representing the problem constraints, namely spatial and temporal exclusions. In addition to suggesting a new formulation of the problem, we point out that the search for a solution to the decision problem under consideration is related to the stability number of a graph called incompatibility graph