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.
The optimal solution for this example would be to elongate the green task of S1 and align them as seen in the optimal solution below.
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.
schedule multiple sequences
? From the practical overview, scheduling and sequencing are the same concepts. Would you provide more details about your problem? E.g. each task is independent or does have to sub-operations? Are there any precedence constraints or something like aroute
for each one? Without losing generality, your problem can be categorized into the parallel machine scheduling problem. If you could provide more information, it gives more chance to answer your question by the community. :) $\endgroup$