2
$\begingroup$

I think I have some special kind of Job Shop Problem lying at hand which I'd like to solve, however I am unsure how to correctly define it and therefore cannot search for appropriate references in order to implement adequate algorithms.

Assume two machines of type A and four machines of type B. Machines of type A can process all products, but only one product at a time. Machines of type B can process only a specific type of product but can therefore process two of the same kind at once (it is possible to process only one however as well). A product needs to be processed several times by machines of type A and B in a specific order, depending on its type. Assume I know the processing plan for each product, i.e. I know beforehand how many times and in which order a product will visit A and B.

Include scheduled donwtimes / capacities of the machines. Find an optimal schedule, where optimal may refer to either minimum total completion time or minimum completion time of some prioritized product.

What kind of problem lies at hand? I have heard read about flexible job shop problems with recirculation, but I am not 100% sure this is what i should look further into.

In addition, I am looking for references which give some examples of applied solutions to basic and advanced problems. The ones I have found so far are very theoreitcal and focused on algorithm complexity and less on application to real world problems.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Without knowing more details below is the outline what you can follow/develop further:\

Products: $P_p $: Priority $ Z_p$, Type$ C_c$, Processing time $ T_p$
Machines: Type: $ M_m$: Number $ N_m$: $ Cap_{m,c}$: units at a time; $ D_m$: downtime in hours for machine: Downtime Schedule: $ND_{m,t}$

Time: $T_t$: could be in hours {1,2,3,..T} or minutes. Depends upon cycle time unit/

Derived Sets:
Process time-(Machine,Product): $PT_{m,p}$

Parameters/Constants
Available Time $T= $22x8 hours
Product-Priority-Type $ \tau_{p,c} =1 $ if product is of type $c$, else 0

Machine-Product Type $ \tau_{m,c} = 1$ if machine $m$ handles this type $c$, else 0 $T_{AB} = \{t\in T: t_A \le t_B\} $: Times when a product has to pass through machine type A before machine type B
$T_{BA} = T\setminus T_AB $: Times when a product has to pass through machine type B before machine type A
Order of processing: $O_{p,m} $: {1,2,3..}

Variables:
$ x_{p,m,t}^o \in \{0,1\}$

Obj Min $\sum_p\sum_t\sum_mx_{m,p,t}^o $

st
(1) $T_p \le \sum_t \sum_m \sum_o\tau_{p,c}\tau_{m,c}x_{p,m,t}^o \ \forall p \in P \ \forall c \in C $: Total processing time through machines for each product greater than total processing time needed for that product

(2) $\sum_p \tau_{p,c}x_{p,m,t} \le Cap_{m,c}\tau_{m,c}(N_m - ND_{m,t}) \ \ \forall t \in T \ \forall m\in M \ \forall o \in O$:
Each product through a machine type at a time $t$ is constrained by the capacity of the machine (2 vs 1 at a time $t$, number of machines available and if machine can handle that product type $c$

(3) $\sum_o\sum_t \sum_p \tau_{m,c}x_{m,p,t}^o \le T - \sum_t D_{m,t} \ \ \forall m \in M$

(4) $\tau_{m,c}\tau_{p,c}PT_{p,m} \le \sum_t x_{m,p,t}^o \ \forall \ \in P \ \forall m \in M \ \forall o$: ensure every product is processed on machine as per processing time of that product and machine.

(5) $\sum_{o* \gt o}\sum_t x_{m,p,t}^{o^*} \le \sum_t x_{m,p,t}^o \ \forall O \in O$

Further Readings
SAS ORL Ch 3 & 4: Example Models
Google OR Examples
IEEE Paper: Discussion
Gurobi: Presentation
Academic Paper: Discussion and numerous other ERP/Shopfloor scheduling tools.

Improve this answer
$\endgroup$
2
$\begingroup$

Based on What you mentioned, you could have a look at the parallel machine scheduling problem with precedence, resource capacity, and batch processing constraints. ($ P_{m} \ | \ cap, prec, batch \ | \ \sum (Prio_{j}.C_{j}) \ \text{Or} \ C_{max}$).

Also, the problem is fallen under the flexible job shop problem with the resource capacity and batch processing constraint if, all of jobs/tasks would be processed on all of the types of machines through the pre-defined routes. ($ Fj \ | \ cap, batch \ | \ \sum (Prio_{j}.C_{j}) \ \text{Or} \ C_{max}$).

Otherwise, you have faced an open-shop problem. ($ O_{m} \ | \ cap, batch \ | \ \sum (Prio_{j}.C_{j}) \ \text{Or} \ C_{max}$).

I strongly recommend you to read Applications of optimization with Xpress-MP, (Chapter 7) if you would like to take some examples of applied solutions. Also, the following links would be useful:

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer! This gives me a much better starting point. I feel like depending on the constraints I add or remove, the problem definition changes. What is most important for me right now is to understand how to formulate my constraints. Thanks again! $\endgroup$
    – mxrdck
    Commented Jan 31, 2023 at 13:32
  • $\begingroup$ @mxrdck, your welcome. What you are looking for is so vary as there are lots of papers that offer many kinds of mathematical formulations like LP, MILP, CP, etc. for such problems. I think the first mentioned reference is one of the excellents to start. $\endgroup$
    – A.Omidi
    Commented Jan 31, 2023 at 14:33

Your Answer

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

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