This is a very long post, but only the first half is really relevant. The second half describes only what I have tried to solve it, but what seemed to me too inefficient (it can perhaps help to get the idea of what I want). The relevant part ends with the line after the bolded question.
I am trying to simulate multiple productions in an imaginary factory to calculate what amount of goods of each type known will be available at the end. There are several different goods types, and they have all a specific maximum production capacity that can only be reached if enough ingredients are available. An example of how the production lines could look is here:
The goods at the bottom all have a known rate at which they are delivered to the factory, so for those, there is nothing to calculate, though this rate can change over time (also, the maximum production capacity can also change at any point in time, e.g., the capacity can be increased by adding workers or more machines).
As shown in the picture, for the other goods there are three things to look at:
- Some lines produce a good out of a single other one.
- Some lines produce a good out of two others.
- Some lines have a good used for creation of more than one new good (see, for example, "R8" in the middle of the illustration).
I have the following information:
- Maximum production rate of each good (5 produced per hour, for example)
- for the bottom goods we have the amount delivered to the factory (5 delivered per hour, for example)
- how much of each is in stock now (so in case there is not enough delivered, if we still have some in stock, we don't need to reduce production)
- At what times the delivery of a good will change (can happen to any good at the bottom)
- At what times the maximum production rate of a good will change (can happen to any good not at the bottom)
With this information, I want to calculate the amount of each good at a given time in the future. I would like this to be as efficient as possible, since I need these calculations quite often.
I tried to make an implementation for this in Java, but I have some problems. Instead of fixing them I looked at my algorithm again and figured out it did not look as if it was very efficient anyway, so I wanted to know if someone has already seen or solved this kind of problem?
The way I tried to solve this is following:
- I create maximum production (and delivery) intervals for each good using the known information when a production (or delivery) amount changes.
- I put all resources at the bottom in a
remainingSet and acheckedSet (bottom goods are immediately checked ones). - I calculate the actual amount of goods produced for each good: therefore, I take each good in remaining and I check what goods can be produced, if all that can be produced only are made of checked goods I calculate the actual amount produced depending of the maximum rate and the available goods (depending on the production of the things it is made of and the amount in stock if this is less). Additionally, in this step I add production intervals if due to lesser production of a source good (but some in stock at the beginning) the production needs to be reduced. When finished the goods the new ones are made of get removed from the remaining Set and the new ones are added, as well as being added to the checked Set.
- Now we have all the actual good productions for each good and we can calculate it. For this we loop over each good and take the actual production and add it up using the interval borders for time. We have now the amount of goods at the wanted time in the future.
Additional info: we cannot do the point 4. without 3. since the actual amount we calculate for a good, can be consumed again for the production of the next one, so we need need this Step in between.
If it helps to understand what I have done (or wanted to do) I add my code (not working). The class is already initialized with the maximum production rate intervals of each produced good currently in production. Since other goods can be in stock, for all goods that are not included we initialize them to with a production of zero and one interval.
public class FactoryGoods {
private long future;
private long now;
private Map<String, Integer> availableGoods;
private Map<String, ArrayList<ProductionInterval>> hourlyGoodIncrease;
/**
*
* @param future long current time
* @param now long last time the factory's resources got updates
* @param availableGoods Map<String,Integer> of the goods in the factory
* @param hourlyGoodIncrease Map<String,ArrayList<ProductionInterval>> of the intervals of production quantities for the goods
*/
public factoryGoods(long future, long now, Map<String,Integer> availableGoods, Map<String,ArrayList<ProductionInterval>> hourlyGoodIncrease) {
this.future = future;
this.now = now;
this.availableGoods = availableGoods;
this.hourlyGoodIncrease = hourlyGoodIncrease;
}
/**
* Calculates the resources present in a factory's storage
* @return a Map of quantities mapped on the String name of the good
*/
public Map<String,Integer> getResources() {
// Make sure all goods to have all goods inside the loop, to work on goods,
// that are produced, but also those which are only in store
HashMap<String, Boolean> goodChecked = new HashMap<String,Boolean>();
Set<String> remaining = new HashSet<String>();
for (Goods good: Goods.values()) {
String g = good.get();
if (hourlyGoodIncrease.get(g) == null) {
ArrayList<ProductionInterval> prods = new ArrayList<ProductionInterval>();
ProductionInterval start = new ProductionInterval(now, 0);
prods.add(start);
hourlyGoodIncrease.put(g, prods);
}
if (availableGoods.get(g) == null) {
availableGoods.put(g, 0);
}
if (good.isPrimary()) {
goodChecked.put(g, true);
} else {
goodChecked.put(g, false);
}
remaining.add(g);
}
// As long as goods are remaining to be checked loops over the goods, and
// recalculates hourly good increases for goods, that have all its sources
// already calculated
while (remaining.size() > 0) {
Set<String> removes = new HashSet<String>();
for (String good: remaining) {
if (goodChecked.get(good)) {
Good g = GoodFactory.get(good);
Set<String> to = new HashSet<String>();
Map<String,Float> from = new HashMap<String,Float>();
setUpFromAndToGoods(g, to, from, availableGoods);
if (areGoodsAlreadyCalculated(to, goodChecked)) {
//remaining.remove(good);
removes.add(good);
} else {
if (areGoodsReadyForCalculation(to, goodChecked)) {
// Get all resources we are working on now
Map<String,Float> fromDecrease = new HashMap<String,Float>();
for (String t: to) {
for (String f: GoodFactory.get(t).isMadeFrom().keySet()) {
from.put(f, (float) availableGoods.get(f));
}
}
// Get all interval borders
ArrayList<Long> intervalBorders = new ArrayList<Long>();
for (String wGood: from.keySet()) {
ArrayList<ProductionInterval> intervals = hourlyGoodIncrease.get(wGood);
for (ProductionInterval interval: intervals) {
long intervalStart = interval.getStartTime();
if (!intervalBorders.contains(intervalStart)) {
intervalBorders.add(intervalStart);
}
}
}
Collections.sort(intervalBorders);
intervalBorders.add(future);
for (String f: from.keySet()) {
hourlyGoodIncrease.put(f, createNewProductionIntervalls(intervalBorders, hourlyGoodIncrease.get(f)));
}
// For all intervals
int iLast = intervalBorders.size() - 1;
for (int i = 0; i < iLast; i++) {
long elapsedTime = intervalBorders.get(i + 1) - intervalBorders.get(i);
for (String t: to) {
Map<String, Float> source = GoodFactory.get(t).isMadeFrom();
for (String s: source.keySet()) {
Float decrease = fromDecrease.get(s);
fromDecrease.put(s, (decrease != null ? decrease : 0) + source.get(s));
}
}
// Calculate amount after normal maximum production
Set<String> negatives = new HashSet<String>();
Map<String,Float> nextFrom = new HashMap<String,Float>();
for (String f: from.keySet()) {
float delta = from.get(f) + (hourlyGoodIncrease.get(f).get(i).getHourlyIncrease() - fromDecrease.get(f)) * elapsedTime / (1000 * 60 * 60);
nextFrom.put(f, delta);
if (delta < 0) {
negatives.add(f);
}
}
// Check if got under zero
if (negatives.size() == 0) {
for (String f: from.keySet()) {
float newIncrease = hourlyGoodIncrease.get(f).get(i).getHourlyIncrease() - fromDecrease.get(f);
hourlyGoodIncrease.get(f).get(i).setHourlyIncrease(newIncrease);
from.put(f, nextFrom.get(f));
}
} else {
// TODO: handle case when more is used than exists
}
// Else calculate point where at least one from is zero and add an interval
// before its maximum, after needs to be adjusted
}
// Break to remove all calculated goods from the remaining set and rerun the loop
removes = to;
break;
}
}
}
}
for (String remove: removes) {
remaining.remove(remove);
}
}
// Final calculation of the goods amounts that are available in the factory
for (String good: goodChecked.keySet()) {
ArrayList<ProductionInterval> intervals = hourlyGoodIncrease.get(good);
intervals.add(new ProductionInterval(future, 0));
float after = availableGoods.get(good);
for (int i = 0; i < (intervals.size() - 1); i++) {
after += intervals.get(i).getHourlyIncrease() * (intervals.get(i + 1).getStartTime() - intervals.get(i).getStartTime()) / (1000 * 60 * 60);
}
availableGoods.put(good, (int) after);
}
return availableGoods;
}
private static ArrayList<ProductionInterval> createNewProductionIntervalls(ArrayList<Long> intervalBorders, ArrayList<ProductionInterval> hourlyIncreases) {
System.out.print("intervalBorders\n");
System.out.print(intervalBorders + "\n");
System.out.print("hourlyIncreases\n");
System.out.print(hourlyIncreases + "\n");
ArrayList<ProductionInterval> intervalls = new ArrayList<ProductionInterval>();
int i = 0;
long iTime = 0;
long nextTime = 0;
for (long l: intervalBorders) {
float increase = 0;
iTime = hourlyIncreases.get(i).getStartTime();
if (i + 1 < hourlyIncreases.size()) {
nextTime = hourlyIncreases.get(i + 1).getStartTime();
}
if (l == iTime) {
increase = hourlyIncreases.get(i).getHourlyIncrease();
} else if (iTime < l && l < nextTime) {
increase = hourlyIncreases.get(i).getHourlyIncrease();
} else if (l == nextTime) {
increase = hourlyIncreases.get(++i).getHourlyIncrease();
}
intervalls.add(new ProductionInterval(l, increase));
}
return intervalls;
}
private static void setUpFromAndToGoods(Good g, Set<String> to, Map<String,Float> from, Map<String,Integer> availableGoods) {
Set<String> unchecked = g.isUsedToCreate();
while (unchecked.size() > 0) {
String good = unchecked.iterator().next();
unchecked.remove(good);
to.add(good);
Set<String> madeFrom = GoodFactory.get(good).isMadeFrom().keySet();
for (String fromGood: madeFrom) {
if (!from.containsKey(fromGood)) {
from.put(fromGood, (float) availableGoods.get(fromGood));
Set<String> additions = GoodFactory.get(fromGood).isUsedToCreate();
for (String addition: additions) {
if (!to.contains(addition) && !unchecked.contains(addition)) {
unchecked.add(addition);
}
}
}
}
}
}
private static boolean areGoodsReadyForCalculation(Set<String> toGoods, Map<String,Boolean> goodChecked) {
for (String t: toGoods) {
Good toGood = GoodFactory.get(t);
for (String from: toGood.isMadeFrom().keySet()) {
if (!goodChecked.get(from)) {
return false;
}
}
}
return true;
}
private static boolean areGoodsAlreadyCalculated(Set<String> toGoods, Map<String,Boolean> goodChecked) {
for (String t: toGoods) {
if (!goodChecked.get(t)) {
return false;
}
}
return true;
}
}
public class ProductionInterval {
private long startTime;
private float hourlyIncrease;
public ProductionInterval(long startTime, float hourlyIncrease) {
this.setStartTime(startTime);
this.setHourlyIncrease(hourlyIncrease);
}
public float getHourlyIncrease() {
return hourlyIncrease;
}
public void setHourlyIncrease(float hourlyIncrease) {
this.hourlyIncrease = hourlyIncrease;
}
public long getStartTime() {
return startTime;
}
public void setStartTime(long startTime) {
this.startTime = startTime;
}
public String toString() {
return "<starttime=" + this.startTime + ", hourlyIncrease=" + this.hourlyIncrease + ">";
}
}
Does someone know an algorithm that can solve my problem, or have some ideas how I can change my algorithm so that it gets more efficient? (I know it does not work at all, but with all these loops, I don't think it will be efficient and I would like to know if someone sees something I could make better before I put the work into finishing it).