Mathematical modeling comparisons for the Coupled-Task Scheduling Problem (CTSP)

The Coupled-Task Scheduling Problem aims to allocate N independent tasks in order to minimize the problem makespan. Each task i is composed of two parts a_i and b_i and, between them, there must be a fixed-size interval l_i. The first objective of the article is to carry out empirical tests with existing mathematical models in the literature and a new Constraint Programming model proposed in this work. The tests involve instances from the literature. Some of them have very specific characteristics. The second objective of this work is to verify the impact that these characteristics have on the execution of the mathematical models. The results show that the proposed model was superior to the others and that there are characteristics that make the optimization process more efficient in some cases and less efficient in others.