Jobshop variants

The jobshop problem is an extreme simplification of a manufacturing plant, that has kept only the most core constraints

• precedences $\quad \forall j,r \enspace \mathrm{start}(\mathrm{task}^r_j) \leq \mathrm{end}(\mathrm{task}^{r+1}_j)$
• no overlap $\quad \forall m \enspace \mathrm{noOverlap}(\lbrace \mathrm{task}^r_j \mid \mathrm{machine}(j,r) = m \rbrace)$

To such an extent that a manufacturing professional probably wouldn't recognize the plant he works in.

The jobshop is used as a basis on which more complex constraints are addded

• limited capacity buffer zones
• subsets of machines, complex process graphs and recipes
• minimum / maximum time between tasks
• reentrance
• tasks within each job are processed on the same sequence of machines
• machine maintenance
• workers

Optimization model always contain the minimum amount of details needed, because extra variables and constraints all come with a time penalty. It is therefore useful to understand how the original problems were reduced to their final model

Buffers

Factories have buffer spaces where the Work in Process (WIP) can be I can be stored while waiting for next actions in the workflow to be applied.

Buffers can be dedicated to a machine or a common space. Because buffers create extra complexity in the process, creation and dimensioning of buffers (and inventor) is by itself a complex optimization problem.

A buffer is required whenever $task^r_j$ ends on a machine and is followed by a task on the same machine before $task^{r+1}_j$ starts. For instance job 1 2 ends then job 2 3 is performed on the same machine before job 1 3 starts. As a result job 1 2 needs to go to the buffer space of machine 2.

If there is no constraint on the buffer space, we just ignore it.

Otherwise we need to represent it and add the appropriate constraint

• capacity constraint (cumulative)
• FIFO behavior
• etc.

A simple variant of the jobshop problem that simulates the absence of buffer is the blocking jobshop which forbids the exact case in the example. To model it we use variable tasks (with a minimum length) and we equal the end of the $r$-th task of a job and the start of the $(r+1)$-th

int m = ...
int n = ...

range machines = 0 .. m - 1
range ranks = 0 .. m - 1
range jobs = 1 .. n
int horizon = 10_000

int machine [jobs][ranks] = ...
int duration [jobs][ranks] = ...

dvar interval task [j in jobs][r in ranks] length duration[j][r] .. horizon

minimize max (j in jobs) end task[j][m - 1]

constraints {

    // Precedences between ranks in a job + blocking machine
    forall (j in jobs, r in ranks : r + 1 in ranks)
        end task[j][r] == start task[j][r + 1]

    // No overlap between tasks on each machine
    forall (m in machines)
        noOverlap { task[j][r] | j in jobs, r in ranks : machine[j][r] == m }

}

Complex workflows

When multiple machines can process a given task within a job, the problem is called the flexible jobshop.

int m = ...
int n = ...

range machines = 0 .. m - 1
range ranks = 0 .. m - 1
range jobs = 1 .. n

{<int, int>} machine_duration [jobs][ranks] = ... 
{int} machine [j in jobs][r in ranks] = { m | <m,_> in machine_duration [j,r] }

dvar interval task_on [j in jobs][r in ranks][m in machines[j][r]] optional
dvar interval task [j in jobs][r in ranks] = alternative { task_on[j][r][m] | m in machines[j,r] }

minimize max (j in jobs) end task[j][m - 1]

constraints {

    // Durations per possible machine
    forall (j in jobs, r in ranks, <m,d> in machine_duration[j][r])
        length task_on[j][r][m] == d

    // Precedences between ranks in a job
    forall (j in jobs, r in ranks : r + 1 in ranks)
        end task[j][r] <= start task[j][r + 1]

    // No overlap between tasks on each machine
    forall (m in machines)
        noOverlap { task[j][r] | j in jobs, r in ranks : machine[j][r] == m }

}

Replacing sequential precedences with a general precedence graphs allows representing problems where various tasks in a job can be performed in parallel (like pieces that are manufactured separately and latter assembled). That is the jobshop with (arbitrary) precedence graph

Precedence graph from Flexible Job Shop Scheduling Problems with Arbitrary Precedence Graphs (2021), Kasapidis et al.

If the precendence graph is empty, the problem becomes an open shop

One step further in the modeling of real manufacturing problem is the concept of recipe which captures the fact that there are multiple ways of getting a job executed

• different machines
• various partitions of the job into steps

The concept of Bill of Materials (BoM) is used when inventories of parts are explictly represented, which is rarely the case with jobshop problems, where the inventory is hidden in the concept of job.

Depending on the complexity of the recipe this can lead to an OR/AND graph of tasks representing the job, or a full subset of paths, each one representing one possible workflow.

A simple example of manufacturing where different recipes are possible is the creation of multi-flavor beverage six-packs. Beverage production usually is done in large batches therefore one "task" represents hundreds of bottles of a given product.

Then creating multi-flavors six packs can be done by either

• picking up one batch of each product at the right place (typically an inventory buffer), reorganizing and packaging them as multi-flavor six-packs
• picking up already assembled six-packs of the flavors needed, breaking them up, reorganizing and repackaging them

The second option is more wasteful but allows creating a small number of multi-flavor packs and doesn't disrupt the existing processes and would probably be used for seasonal or promotional products - in the first case there are jobs which didn't complete their normal process into "mono-product" six packs.

We see how two different recipes can result in the same product at the end, with different number of steps, different durations and different resources / machines.

Temporal restrictions created by operational constraints

Workflows capture relationships between the work in progress (WiP) and the final product, creating temporal constraints in the process.

There are also operational constraints that create temporal restrictions on the tasks. For instance if a task consists in heating a product in an oven, the delay with the start of the next task cannot be too long.

$$\forall j,r \quad \mathrm{end}(\mathrm{task}^r_j) \leq \mathrm{start}(\mathrm{task}^{r+1}_j) \leq \mathrm{end}(\mathrm{task}^r_j) + C$$

The semi-conductor and metallurgy industries often require schedules with a maximum time between tasks and reentrancy which is the fact that a product will pass multiple times in an oven. Usually the oven has a capacity > 1 hence multiple tasks can be simultaneoulsy scheduled. The oven may also have a temperature that can be adjusted (in which case there is a compatibility constraint between the tasks and the oven temperature) and ramps (the delay it takes for the oven to get to the right temperature).

The no-wait jobshop is a jobshop variant in which each task within a job needs to end when the next task starts. Notice this is the same constraint that in the blocking jobshop but for completely different reasons (and the tasks are not elastic anymore).

$$\forall j,r \quad \mathrm{end}(\mathrm{task}^r_j) = \mathrm{start}(\mathrm{task}^{r+1}_j)$$

Release dates are typically due to availability of materials

$$\forall j,r \quad \mathrm{release}^r_j \leq \mathrm{start}(\mathrm{task}^r_j)$$

Due dates are typically related to contractual agreements, transportation, etc

$$\forall j,r \quad \mathrm{end}(\mathrm{task}^r_j) \leq \mathrm{due}^r_j$$

Machine availability (also known as calendars) is the fact that a resource may not be available at all times due for instance to maintenance. The maintenance calendar may be already given as a constant, or the problem may require to compute the best maintenance times.

The jobshop with predictive maintenance ...

Transportation

Sometimes the transfer times between the machines is not negligible

When the number of vehicles is considered infinite, explicit representation of vehicles with intervals and the corresponding contraints (departures, synchronzations) are avoided. Instead the transportation between sites is represented as a delay

• If transportation time only depends on the machines then the constraint is simplified into a constant term in the precedence

$$\forall j, r \quad \mathrm{end}(t_j^r) + distance^{\,machine(j,r)}_{\,machine(j,r+1)} \leq \mathrm{start}(t_j^r)$$

• A transportation time that depends on the task could be for instance due to packaging. A transportation time that depends on the machines and the task could be for instance due to special means of transportation (a refrigerated truck)
• Because in the pure jobshop problem the sequence of the tasks in a jobs is known, transportation contraints rarely become setup times. Setup times appear either within a given machine (e.g. cleaning between tasks of different jobs) or in variants of the jobshop that relax the sequential precedences.

When the number of vehicles is finite, explicit constraints need to be added to capture that

• One carrier per job can occur when there is an internal transportation system within the plant like a pneumatic transportation system, autonomous vehicles, rail, etc. In that case the transportation constraint reduces to
  • a cumulative constraint to limit the total number of simultaneous jobs
  • time constraints betweeen machines