# Problem Clustering and Suggestions for Solving it (Job-Shop?)

I am trying to find the amount that an item may get produced.

To produce this item I need casting-molds. A casting-mold can be used multiple times after it becomes available again.

For the production I have to take into consideration the following parameters:

• The production period
• The duration a casting-mold needs to get prepared before it gets sent to production
• The number of casting-molds
• The time it gets for a casting-mold to be available again.

In this case, the quantity of this item to produce is infinite.

Here is a simple example:

• Production period: 10:00 - 11:00 (60 Minutes)
• Casting-mold preperation time: 5 Minutes
• Number of casting-molds: $$|\{a,b,c,d\}| = 4$$
• Re-use time: 25 Minutes

Production Process:

1. 10:00 casting-mold $$(a)$$ preparation

2. 10:05 casting-mold $$(a)$$ sending for production and start processing the next casting-mold $$(b)$$

3. 10:10 casting-mold $$(b)$$ sending for production and start processing the next casting-mold $$(c)$$

4. 10:15 casting-mold $$(c)$$ sending for production and start processing the next casting-mold $$(d)$$

5. 10:20 casting-mold $$(d)$$ sending for production

6. 10:20 - 10:30 Wait until the first casting-mold $$(a)$$ gets available again

7. 10:30 casting-mold $$(a)$$ preparation (since 10:05 + 00:25 = 10:30)

8. 10:35 casting-mold sending $$(a)$$ for production and start processing the next casting-mold $$(b)$$

9. 10:40 casting-mold $$(b)$$ sending for production and start processing the next casting-mold $$(c)$$

10. 10:45 casting-mold $$(c)$$ sending for production and start processing the next casting-mold $$(d)$$

11. 10:50 casting-mold $$(d)$$ sending for production

12. End (The casting-mold $$(a)$$ can be used at 11:00 again which is out of the production window)

In this case, the item gets produced 8 times.

It is irrelevant which mold gets processed first.

The production happens to one machine.

The products may get finished after the production time frame (10:00 - 11:00), e.g., the items produced at 10:40 $$(b)$$, 10:45 $$(c)$$ and 10:50 $$(d)$$ end respectively at 11:05 $$(b)$$, 11:10 $$(c)$$ and 11:15 $$(d)$$

How would you tackle such a problem?

Thanks to @A.Omidi for the idea of a Gantt-chart: • Why is this question tagged "optimization" and "linear programming"? Are there any decisions to be made? Feb 23 '20 at 18:57
• @prubin because I am not sure where the question really belongs to. Feb 23 '20 at 19:21
• @Georgios, what exactly are you looking for the schedule? have you mentioned parameter, representing Gantt chart like this? Are all molds on one machine or each mold has a specific machine? (I suppose that the compilation time of each product can be extended to the end of the waiting time.) Feb 24 '20 at 12:10
• @A.Omidi I am not looking for a particular schedule, but only the number of times an item gets produced within the time frame. Oh, your table is great, I will add it to the question. What kind of parameters do you mean? All molds are on one machine. I could not understand your last question. Feb 24 '20 at 13:10
• @Georgios, As you don't mention how long time needs to finish a job, I suppose that they can be performed until the end of the waiting time. As per all of the job durations are the same, it doesn't differentiate between the mutation of products. (specifically in your case with one machine and without the sequence-depending setup time.). I think you should use the task Gantt chart (like the above chart) instead of the resource Gantt chart. Also, if you are interested to develop an MP, might resource-constrained project scheduling models be useful. Feb 25 '20 at 9:40

I gather that you are assuming an unlimited demand for castings. Let $$n$$ be the number of molds, $$p$$ be the prep time for each mold (assumed the same for all molds) and $$u$$ the use time for a prepped mold (again assumed to be the same for all molds). Assuming no delays, each mold has a cycle time of $$p+u$$. As long as $$u\ge (n-1)p$$, there will be no delay in preparing molds as they become available (no queue at the preparation station). So every mold will be in continuous use.

Let $$W$$ be the time window. The number of times the first mold is used will be $$\left\lfloor \frac{W}{p+u}\right\rfloor$$, the number of times for the second mold will be $$\left\lfloor \frac{W-p}{p+u}\right\rfloor$$, for the third it's $$\left\lfloor \frac{W-2p}{p+u}\right\rfloor$$, and so on. In your case, that's 2 + 1 + 1 + 1 = 5. (The other three molds in your solution of 8 will be started within the production window but will be completed outside the window.)

If $$u < (n-1)p$$, then you have to factor in a queue at the preparation station. It's not clear to me from the question whether that case is of interest.

• It is eligible for the 3 forms to complete outside the window, so I do want the number of 8. Also, the case of $u < (n-1)p$ would be perfect to my understanding since there would be no waiting for the used forms to become available again. in my example I have to wait: $25 > (4-1)\cdot 5 = 15$ Feb 23 '20 at 19:31
• If forms can complete outside the window, you can just redefine $W$ to be the original window length plus $u$. So, in your example, for the fourth mold we would have $\left\lfloor \frac{60+25-3\cdot 5}{5+25}\right\rfloor=2$, while for the first mold it would be $\left\lfloor \frac{60+25}{5+25}\right\rfloor$ which is still $2$. I'm assuming here that $u<W$, which seems reasonable. Feb 24 '20 at 16:04

So I wrote a simple discrete algorithm, that delivers the solution.

I have not found any bugs yet. I will make a few more tests and post whether the code is eligible.

Caution!: I used $$u = 35$$ and not $$25$$ to see if it truly works.

import datetime

n = 4 # number of molds
p = 5*60 # prep time in seconds
u = 35*60 # use time in seconds
now = datetime.datetime.now()
day = now.day
year = now.year
month = now.month
startTime = datetime.datetime(year,month,day,10,0)
endTime = datetime.datetime(year,month,day,11,0)
count = []
for i in range(n):
newTime = startTime
pNew = p*(i+1) # i starts from 0
count.append(0)
print(newTime + datetime.timedelta(seconds=pNew))
while newTime + datetime.timedelta(seconds=pNew) < endTime:
count[i] += 1
newTime += datetime.timedelta(seconds=u) + datetime.timedelta(seconds=p)
print(newTime + datetime.timedelta(seconds=pNew))

for i in range(n):
print(count[i])


Output:

2020-02-24 10:05:00
2020-02-24 10:45:00
2020-02-24 11:25:00
2020-02-24 10:10:00
2020-02-24 10:50:00
2020-02-24 11:30:00
2020-02-24 10:15:00
2020-02-24 10:55:00
2020-02-24 11:35:00
2020-02-24 10:20:00
2020-02-24 11:00:00
2
2
2
1


You can use the Graph method of Maximum-Flow-Network to get an optimal solution.