I'm given a problem in which I need to schedule multiple sequences. The goal is to minimize the makespan. I'm allowed to elongate all tasks, but I cannot reduce their width nor disconnect any of the tasks. Each of the tasks is indicated using a color. In the final schedule tasks of the same color cannot overlap.
In the example above 2 sequences S1, S2 are shown with respectively 4 and 3 tasks in 3 different colors. In the example both tasks are scheduled to start at the same time but this results in 3 violations. These violations are indicated by an exclamation mark.
Is this type of problem known and studied in literature? If so, under what name and what kind of algorithms are used to solve them? If not, what kind of algorithm would you suggest to use? I have +- 100 sequences and I am using 16 colors. Each sequence contains typically between 9 and 20 tasks.
I found many problem types where disconnecting the tasks within a sequence is allowed, but not being able to disconnect changes the dynamics quite a bit.