What strategies to use for Scheduling of Connected Sequences?

Question

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.

Answer 1

This is a blocking job shop scheduling problem.

The description from "An iterated greedy metaheuristic for the blocking job shop scheduling problem" (Pranzo et Pacciarelli, 2016) DOI

In the job shop scheduling problem a set of jobs $J$ must be processed on a set of machines $M$, each processing at most one job at a time. The processing of a job on a machine is called an operation and cannot be interrupted. We let $\{o_1, \dots , o_n \}$ be the set of all operations. The sequence of operations for each job is prescribed, while the sequence of operations for each machine has to be determined in such a way that the time needed to complete all operations, called the makespan, is minimum. More formally, the scheduling problem consists in assigning a starting time $t_i$ to operation $o_i$ , $i = 1, \dots, n$, such that: (i) precedence constraints between consecutive operations of the same job are satisfied; (ii) each machine hosts at most one job at a time; and (iii) the makespan is minimized.

In the blocking job shop scheduling problem no intermediate storage is allowed between two consecutive machines. Hence, once a job completes processing on machine $M_h$ it either moves to the subsequent machine $M_k$ (if it is available) or it remains on $M_h$, thus blocking it (if $M_k$ is not available).

From your examples, "sequences" become "jobs", "tasks" become "operations", and "colors" become "machines".

The simplest and easiest way to get solutions is certainly to use a Constraint Programming solver.

Answer 2

Your problem is reminiscent of the makespan minimization version of the Blocking Job Shop (BJS) problem. For a definition of the BJS problem, refer to [1]. If you consider each sequence as a job, and each color as a machine, then, it looks like the problem sizes that you are interested in are pretty large, and so local-search may be your best bet to compute good quality solutions. For local-search algorithms to solve the BJS problem efficiently, see the recent paper [2].

[1] "Job-shop scheduling with blocking and no-wait constraints", Alessandro Mascisa & Dario Pacciarelli, EJOR, 2002.

[2] "Efficient primal heuristic updates for the blocking job shop problem", JK Mogali, L Barbulescu, SF Smith, EJOR, 2021.