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

Question

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.

Added for clarification:

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:

Answer 1

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.

Answer 2

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

Answer 3

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