# Identifying problem: Assignment + Job Shop Scheduling

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.

• It is not clear to me whether the machines are arranged in parallel or sequentially? May 17, 2022 at 15:59
• @fontanf Why the arrangement of machines is necessary? May 17, 2022 at 16:05
• Are you saying that you can have an essentially limitless number of machines of each type at no additional cost?
– prubin
May 17, 2022 at 18:37
• @torayeff, sorry for the delay. Based on the example you mentioned, there is a strange thing about your problem. For which you want to limit the processing time in each stage by a pre-defined upper bound, $T_{p}$, for the products with the processing time near to this UB, you would need, at least as a theoretical, the infinite number of machines in some stages. Are you considering this to account? If so, would you please, elaborate more about that? May 22, 2022 at 8:27
• @torayeff, without the above assumption, your problem is fallen into the hybrid scheduling problem with some extra constraints to capture what you want. May 22, 2022 at 8:30

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$$.
• What is the main difference between CP and MILP ? I understand that CP tries to find a feasible solution but MILP tries to find a feasible and optimal one. My question is mainly concerned with the level of complexity of these two approaches. IS CP much faster than MILP ? Jul 14, 2022 at 10:05
• CP can find optimal solutions by finding feasible solutions with the constraint that each new solution be better in objective terms than its predecessor. Neither CP nor MILP is always faster than the other. Any generalizations are risky, but I think CP relies less on linearity, is sometimes more expressive (meaning you can incorporate model elements directly in CP that would require creative and somewhat obscure use of binary variables in MILP), and can have specialized constraints for some things. MILP, I think, tends to have tighter bounds.
– prubin
Jul 14, 2022 at 14:52

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.