7
$\begingroup$

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. Example task illustration with colors

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. Optimal Solution

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.

$\endgroup$
15
  • 1
    $\begingroup$ Welcome to OR.SE. First of all, what do you mean by 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 a route 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$
    – A.Omidi
    Aug 25, 2021 at 11:52
  • $\begingroup$ In the example you can find 2 sequences (as intended), S1 contains out of 4 tasks, S2 contains out of 3 tasks. Due to the color of each of the tasks and the connected sequence constraint a lot of dependencies arise. Within each sequence the order needs to be preserved, so this does create precedence constraints and routing constraints on the task level. $\endgroup$
    – Barry S.
    Aug 25, 2021 at 12:00
  • $\begingroup$ So you already have the two ordered sequences S1 and S2, and all you want to do is add "downtime" inside the sequences to avoid collisions of incompatible tasks? $\endgroup$
    – Stef
    Aug 25, 2021 at 12:19
  • $\begingroup$ @Barry S., are what you looking for is something like this? $\endgroup$
    – A.Omidi
    Aug 25, 2021 at 12:22
  • 1
    $\begingroup$ @BarryS. Based on the conversations happening here in the comments, I suggest you edit your question and add these clarifying points and any other details there. $\endgroup$
    – EhsanK
    Aug 25, 2021 at 12:56

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ would you say please, how this problem might be fallen into the job shop scheduling problem? $\endgroup$
    – A.Omidi
    Aug 28, 2021 at 5:47
  • $\begingroup$ @A.Omidi What do you mean? As I've written in the answer the colors are resources with capacity 1, that is, equivalent to machines. Sequences and tasks are jobs and operations. Elongating an operation (task) is equivalent to saying that while the next operations of that job (sequence) has not started, the machine (color) of the previous operation is still busy. This is the "blocking" property $\endgroup$
    – fontanf
    Aug 29, 2021 at 7:15
  • $\begingroup$ As the questioner does not mention anything about either the specific route for each task or sub-operations that is required and necessary for scheduling the shopping environments, I doubt this problem can be categorized in the JSSP. Maybe an open shop or parallel machine scheduling is more suitable. Do you have any reference to use JSSP in other environments like PMSP/RCPS? $\endgroup$
    – A.Omidi
    Aug 29, 2021 at 7:31
  • $\begingroup$ @A.Omidi the route is the sequence. From what I understand, it is not possible to change the order of the colors in a sequence, therefore it's a JSSP. Otherwise, I agree that it would be an open shop scheduling problem $\endgroup$
    – fontanf
    Aug 29, 2021 at 8:55
  • $\begingroup$ The route is a bit different from the sequence, specifically, for the non-shopping environments. It's a key point in the practical sequencing problem. For example, in the PMSP with two resources, without any limitation based on the Graham notation, a feasible sequence of the four jobs on the resource one would be => [j1, j3] and for the second one would be => [j2, j4] and this is not meaning as a route. :) $\endgroup$
    – A.Omidi
    Aug 29, 2021 at 9:21
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.