Branch-and-bound algorithm to minimize the total completion time on two dedicated processors

In this paper, we propose an exact method for solving the problem of scheduling multiprocessor tasks on two dedicated processors with release dates. In this problem, we have three subsets of tasks, where these tasks need one or two dedicated processors to be performed. The aim is to minimize the total completion time, where each task has a release date. In computational complexity theory, this problem is shown to be NP-hard in the strong sense. The contribution of our work is to construct a mathematical model, to give an improved lower bound and to propose a branch-and-bound algorithm to solve the studied problem.