# Optimizing timeline generation

I have a bunch of processes that are being executed on different virtual machines. All of those processes have a StartDate, EndDate and Resource properties. Resource is a specific virtual machine it was ran on. I generated the actual timeline for items and found out that all of those resources have "holes" in timeline that could fit other processes running on other machines at the same time, which means I could live with less machines. So I am now trying to come up with an algorithm that tries to fit all those processes to timeline. It adds a timeline and first item to timeline, for every next item, it checks if the EndDate of the last item in timeline is greater than current items StartDate, if so Add a new timeline, else put to existing timeline. The current implementation:

public List<TimelineDto> GetOptimizedTimeline()
{
var allItems = GetInterestingItems().OrderBy(x => x.StartDate).ToList();
if (!allItems.Any())
{
return null;
}
// Add the first item to first resource
var firstitem = allItems.FirstOrDefault();
var timelineCount = 1;
var timeline = new List<TimelineDto>
{
new TimelineDto
{
itemId = firstitem.Id,
Resource = timelineCount.ToString(),
StartTime = firstitem.StartDate,
EndTime = firstitem.EndDate
}
};
allItems.Remove(firstitem);

foreach (var item in allItems)
{
for (var i = 1; i <= timelineCount; i++)
{
// as items are ordered by date, take the last item in current resource and see if the new items "fits" to that resource
var last = timeline.Last(x => x.Resource.Equals(i.ToString()));
if (item.StartDate > last.EndTime)
{
{
itemId = item.Id,
Resource = i.ToString(),
StartTime = item.StartDate,
EndTime = item.EndDate
});
break;
}
}
// suitable resource already found, cool.
continue;
// Current item did not fit into any existing resource, add a new one.
timelineCount++;
{
itemId = item.Id,
Resource = timelineCount.ToString(),
StartTime = item.StartDate,
EndTime = item.EndDate
});
}
return timeline;
}


Now this does what I need, but for 100k items it takes minutes to complete. I am processing 1M items daily so it's not that I can't wait several minutes, but it would be great to optimize it. Can I parallelize this?

-

Compound words like firstitem should be camelCase.

Why is the Resource property of TimelineDto a string, when you seem to be filling it with ints?

allItems is a bad name, item is even worse. I have no idea what this represents.

I also have to object to TimelineDto, especially when timeline = new List<TimelineDto>.

var firstitem = allItems.FirstOrDefault(); can return a null, yet you never check this.

Why are you even using the OrDefault version, considering that the first line sorts the result of GetInterestingItems() by StartDate, which would throw an exception if one of the items was null.

Is there a point to all of this:

// Add the first item to first resource
var firstitem = allItems.FirstOrDefault();
var timelineCount = 1;
var timeline = new List<TimelineDto>
{
new TimelineDto
{
itemId = firstitem.Id,
Resource = timelineCount.ToString(),
StartTime = firstitem.StartDate,
EndTime = firstitem.EndDate
}
};
allItems.Remove(firstitem);


Except for var timelineCount = 1; I don't see how this isn't handled by the logic inside foreach (var item in allItems). Of course you need to rethink var last = timeline.Last(x => x.Resource.Equals(i.ToString())); and if (item.StartDate > last.EndTime), but that seems a more elegant solution than the 10+ lines required to add a first entry to timeline.

This code is repeated three times, so it should be moved to a method:

new TimelineDto
{
itemId = item.Id,
Resource = timelineCount.ToString(),
StartTime = item.StartDate,
EndTime = item.EndDate
}


WRT your question, I don't see how you can parallelize it without running the risk of duplicate entries.

I do wonder whether it wouldn't be easier (and increase performance) to maintain a Dictionary<int, DateTime> instead of doing var last = timeline.Last(x => x.Resource.Equals(i.ToString())); each time. Key of that dictionary is the Resource, value is the EndTime.

So you'd end up with something like this:

public List<TimelineDto> GetOptimizedTimeline()
{
var items = GetInterestingItems().OrderBy(x => x.StartDate).ToList();
if (!items.Any())
{
return null;
}

var timeline = new List<TimelineDto>();
var endTimeByResource = new Dictionary<int, DateTime>();
var timelineCount = 1;

foreach (var item in items)
{
for (var i = 1; i <= timelineCount; i++)
{
DateTime endTime;
if(endTimeByResource.TryGetValue(i, out endTime)
{
if (item.StartDate > endTime)
{
endTimeByResource[i] = item.EndTime;
break;
}
}
}

continue;

timelineCount++;
endTimeByResource[i] = item.EndTime;
}

return timeline;
}


Beware: I have not tested this code, so there might be some part of the logic missing! I suspect the if(endTimeByResource.TryGetValue(i, out endTime) needs an else where you add a new TimelineDto.

I would even consider getting rid of timelineCount completely and instead do for (var i = 1; i <= endTimeByResource.Keys.Count; i++), that way you might even be able to get rid of added, something like this:

foreach (var item in items)
{
for (var i = 1; i <= endTimeByResource.Keys.Count; i++)
{
DateTime endTime;
if(endTimeByResource.TryGetValue(i, out endTime)
{
if (item.StartDate > endTime)
{
endTimeByResource[i] = item.EndTime;
break;
}
}
}
}


Again: this is untested.

I think it can even be reduced to this:

    for (var i = 1; i <= endTimeByResource.Keys.Count; i++)
{
DateTime endTime;
endTimeByResource.TryGetValue(i, out endTime);

if (item.StartDate > endTime)
{
endTimeByResource[i] = item.EndTime;
break;
}
}

-

Unnecessary List:

Firstly allItems does not need to be a list. By turning it into a concrete List<T> you are wasting time and memory. Memory is allocated for the List<T>'s backing store and the enumerable it enumerated so the items can be copied.

Instead of removing the first item you can then use allItems.Skip(1) to skip past the first item. As you aren't using allItems for anything other than the foreach loop after that point, you can insert the skip straight into the loop rather than assigning it. i.e foreach(var item in allItems.Skip(1).

Naming Issues:

My next complaint is that itemId in TimelineDto appears to be both public and camel-cased. Public properties and fields should always be pascal-cased, so it should be ItemId.

Another notable issue is that TimelineDto contains a StartTime and EndTime property, but the item it's being assigned from (I say 'item' because it's impossible to infer the name of the type from the code because of your heavy use of var) has corresponding StartDate and EndDate. Assigning a 'date' property to a 'time' property is a semantic conflict. StartDate implies that only the date is valid and the time part of the data should be considered potentially invalid or nothing of importance, whereas StartTime implies the value should be correct to the time scale because the time is important. If the time is important, use StartTime rather than StartDate.

Everything else I wanted like to say has already been covered in depth by @BCdotWEB, I'm just covering a few things I felt were missing.

-

Although you already have some excellent answers I thought I'd focus on your key question - performance. Let's take a look at your current implementation. In particular, this bit:

foreach (var item in allItems)
{
for (var i = 1; i <= timelineCount; i++)
{
var last = timeline.Last(x => x.Resource.Equals(i.ToString()));
if (item.StartDate > last.EndTime)
{
break;
}


Let's consider the best case: everything fits into one resource. The code is now effectively:

forearch (var item in allItems)
{
var last = timeline.Last(x => x.Resource.Equals(1.ToString()));
if (item.StartDate > last.EndTime)
{
}


Do you see the problem? For every item you're doing a Last which will iterate over all of the items you've already processed. First iterating 0, then 1, then 2, then 3, then 4... all the way up to N-1 items on the last call. So we know that Last is going to get more expensive on each iteration of the list even when we schedule everything on the same resource.

In the worst case, you need a new resource for every item. You're now doing one call to Last for every resource id that you've already created. However, you never search the last one as it is created on the last iteration. So just on your last iteration, you'll be doing (N-1)*(N-1) operations. Ouch!

I'm sure the average case is creating quite few 'resources' but it is worth considering the absolute worst it could be.

Just while I'm at it - you're also calling i.ToString() loads and loads of times.

You already have one answer that improves this for you, I'll just throw another one at you. All you need to do is keep track of your 'resource id' and the date/time the current item ends. That fits nicely into a list:

public List<TimelineDto> GetOptimizedTimeline()
{
var allItems = GetInterestingItems().OrderBy(x => x.StartDate);
var resources = new List<DateTime>();
var timeline = new List<TimelineDto>();

foreach (var item in allItems)
{
var freeResourceIndex = resources.FindIndex(endDate => item.StartDate > endDate);
if (freeResourceIndex == -1)
{
// No free resource, add a new one and modify index to point at it.
freeResourceIndex = resources.Count - 1;
}
{
itemId = item.Id,
// 0 based so need to add 1 as you seem to be 1 based
Resource = (freeResourceIndex + 1).ToString(),
StartTime = item.StartDate,
EndTime = item.EndDate
});
// track the new end date for this resource.
resources[freeResourceIndex] = item.EndDate;
}
return timeline;
}


Although the code is untested and typed directly into this answer (so it might not be right) you should hopefully be able to see that we've eliminated all of those operations where we keep searching all of the items we've already added to the timeline instead just keep a list of end dates (which is all we need as we are going in order of start date).

Note that I've also not eagerly evaluated the allItems and have structured the code to avoid needing to detect the no items case.

I've intentionally not done any formal big O analysis so please excuse the hand waving.

Update

I decided to see how much of an impact the changes I suggested would have. On 10,000 items that have to be scheduled across a minimum of 5 resources:

My version: 2ms
Original version: 4324ms

I also tried it with 100,000 items that have to be scheduled across a minimum of 5 resources:

My version: 44ms
Original version: 438834ms (~7.3 minutes)

Tests were averaged over 10 runs with a first warm up of each not measured. I also checked that the algorithms were returning identical results (which they were as far as I could tell).

-