Identifying problem: Assignment + Job Shop Scheduling

Question

I am new to OR. Hence, I want your advice on the problem I am trying to solve:

Given:

• $O_1 \rightarrow O_2 \rightarrow O_3 \rightarrow ... \rightarrow O_n$: the sequence of operations to produce $1$ product.

• $M$: the set of machines that can perform operations. Any machine can perform any operation.

• $D$: the time matrix, where $D_{ij}$ is the time units required by machine $M_i$ to perform operation $O_j$.

• $C$: the cost matrix, where $C_{ij}$ is the cost for running machine $M_i$ for performing operation $O_j$.

• $P$: the total number of products required to produce.

• $T_p$: the maximum allowed time to produce $P$ products.

Problem: Find the minimum number of machines with minimum cost that can produce $P$ products in time units $T_p$. The cost of adding a new machine from machines set $M$ can be ignored.

Note: Assuming that $T_1 \leq T_p$, the solution always exists. The worst-case solution will be just adding extra machines. For example: if producing $1$ product in $T_1$ time units requires machines $M_1$ and $M_2$, then producing $2$ products in $T_2 = T_1$ will require adding extra $M_1$ and $M_2$ machines in the worst case.

Example:

• $O_1 \rightarrow O_2$
• $M = \{M_1, M_2 \}$
• $D = \begin{pmatrix} 1 & 5000 \\ 5000 & 100 \end{pmatrix}$
• $C = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$
• $P = 2$
• $T_2 = 102$

Solution:

$M_1$:

• works on $(P_1, O_1)$ from $t=0$ to $t=1$
• works on $(P_2, O_1)$ from $t=1$ to $t=2$

$M_2$:

• works on $(P_1, O_2)$ from $t=1$ to $t=101$

$M_2^{extra}$:

• works on $(P_2, O_2)$ from $t=2$ to $t=102$

Two products can be produced using 3 machines (1 $M_1$ and 2 $M_2$) in $T_2=102$ seconds.

So far, I have been trying to model this using Assignment and Job Shop Scheduling problems. From one side, we need to assign machines to operations, but we can assume that we have infinite machine resources. So this problem is not a strict assignment problem. From the other side, it seems like JSSP where there are $P$ identical jobs with the same set of operations. However, it is not JSSP because each machine can perform any operation if idle. Also, we can always add an extra machine.

I would appreciate it if you let me know if there are similar problems in the OR literature or guide about modeling the above problem.

Answer 1

I don't know that this problem falls neatly into any job scheduling category, although I would not be shocked if there are papers in the literature solving something equivalent or very similar. Both constraint programming (CP) and mixed integer linear programming (MILP) models are possible.

Assuming a MILP model is desired, one approach (if supported by the solver) would be to specify a two dimensional objective function (machine count or cost, operating cost) to be minimized lexicographically. CPLEX, for instance, allows this. If lexicographic optimization is not supported, you would need to solve two models: first minimizing machine count/cost; then minimizing production cost with the optimal machine count/cost as a constraint.

There may be multiple ways to approach this. I'll use the term "job" to refer to one unit of production. I would use the following variables:

• binary variables $x_{ijk}$ indicating whether job $i$ uses a machine of type $j$ to perform operation $k$;
• nonnegative integer variables $s_{ik}$ and $e_{ik}$ representing the time job $i$ starts and ends operation $k$ (respectively);
• nonnegative integer variables $z_j$ representing the number of type $j$ machines put into service;
• binary variables $u_{ikt}$ and $v_{ikt}$ representing respectively whether operation $k$ on job $i$ begins on or before time $t$ and ends on or after time $t$; and
• binary variables $w_{ijkt}$ indicating whether operation $k$ on job $i$ occupies a machine of type $j$ at time $t$.

Answer 2

That is something like a Flow Shop Multi Machine, In Cplex CP Optimizer you will find the Job Shop Multi Machines scheduling (jsspmm examples) which is a more general case.