A Clique Based Algorithm for Scheduling Coupled Tasks with Exact Delay

In this work we single out a scheduling problem in which tasks are coupled and the time delay between the first and second members of the couple is fixed by technological constraints. We will show that this scheduling problem can be reduced to the question to decide if a tactically constructed 𝑘-partite auxiliary graph contains a 𝑘-clique. We will point out that before submitting the auxiliary graph to a clique solver it is expedient to carry out various inspections in order to delete nodes and edges of the graph and consequently speed up the computations. In the lack of theoretical tools we will carry out numerical experiments to test the practicality of the clique approach.