0
$\begingroup$

Say I have a kiln for making castings. There are 3 shapes. I need to produce the following castings:

102 of A

364 of B

70 of C

I can put 50 molds in the kiln at a time. I can have 75 molds made in any combination.

First, what is the optimal combination of molds to make.

Second, what is the schedule to make the castings in as few firings as possible.

I am trying to wrap my head around this problem. I see that the second part resembles task scheduling problems I've read about, but I have no idea how to tackle the first problem.

Any help/insight very much appreciated.

$\endgroup$
  • $\begingroup$ If I were you I would use linear programming, let A+B+C = 75, then xA >=102, yB >=364 and so on. if the constrain for A+B+C = 75 was not there then we have x+y+z>11, similarily x > 2, y > 7, z > 1. $\endgroup$ – amritanshu Jan 9 at 8:58
  • $\begingroup$ Please credit the original source of the problem. $\endgroup$ – Apass.Jack Jan 9 at 13:44
  • 1
    $\begingroup$ @Apass.Jack this is a real life problem! :) $\endgroup$ – greasegum Jan 10 at 1:45
0
$\begingroup$

Either there is an additional constraint, either this problem is far more simpler than task scheduling.

Well you have to identify the limiting criterium of your problem which is 50 molds maximum in the kiln.

Let's call S = A+B+C = 536, the total number of molds. So You cannot do better than 11 firings (11*50=550).

First compute the euclidean division of the required elements to get the quotient and the remainder, that will be the constant molds and the variable molds to use.

- x, a = A/11 = 9, 3
- y, b = B/11 = 33, 1
- z, c = C/11 = 6, 4

So the constant molds are (x, y, z) = (9, 33, 6), that is to say 48 molds.

You now have 11 firings on the 2 (50-48) variables molds to complete the (a, b, c) = (3, 1, 4) remaining elements. Let's say we want to minimize the number of molds to manipulate. Then just take one extra mold of each A, B, C to have a total of 51 molds.

$\endgroup$
  • $\begingroup$ Thank you! This clarifies it a lot. Originally there was an additional constraint which was that there were limited numbers of each mold available. to wit: $\endgroup$ – greasegum Jan 10 at 1:46
  • $\begingroup$ Originally there was an additional constraint which was that there were limited numbers of each mold available. to wit: a=14 b=44 c=9 so I think that does become a schedule optimizing problem does it not? Thanks again! $\endgroup$ – greasegum Jan 10 at 1:52
  • $\begingroup$ You have no sequencing constraint, once you determined your 11 firings, the order does not matter. Thus, this can hardly be called a schedule problem.... The additional constraint is definitly not limiting. The simple solution I gave would work even on very complex input (you may just have an extra firing if remaining elements are too numerous). $\endgroup$ – Vince Jan 10 at 9:34

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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