Ben Fulton
Let’s consider a scheduling problem that you might run across in a factory. Basically, you have a widget that has to be processed in several stations, in order. So it goes from the first station, to the second station, and on out until it’s complete. But of course, once the first station is done working on the first widget, it can get started on its second widget. Once the second station is done with the first widget, if the first station is done with the second widget, it can work on that one – and in the meantime the first station is free to start working on its third widget.
We make the assumption that there are an infinite, or at least extremely large, number of widgets ready to come through the factory, so we can always think about when we can start the next widget, and not have to try to time it so the last widget is done efficiently.
This isn’t just a factory floor problem, either – consider a CPU that can compute several instructions in parallel, with each instruction consisting of a 7-stage pipeline. There’s certainly no shortage of instructions coming through the line, so schedulers have to try to determine how to minimize the average time through the pipeline, and certainly there are always more instructions to be processed.
So how will we model this? Let’s start by calling our stations, or stages, jobs, and for now we’ll just assume that the processing time is constant each time the job is run:
public class Job
{
public int processingTime;
}
Our scheduler, fundamentally, is just a list of jobs. For each job, we’ll keep track of the starting time on each iteration.
public class CyclicSchedule
{
List<Job> _jobs;
Dictionary<Job, List<int>> _startingTimes;
public CyclicSchedule(List<Job> jobs)
{
_jobs = jobs;
_startingTimes = _jobs.ToDictionary(j => j, j => new List<int>());
}
}
We’ll use another simplifying assumption to get us started: we’ll assume that all the jobs can bang on our widget at the same time. So for example, if we have three jobs that each take time 3 to process, we’ll see that each iteration completes in time 3. Simple, right?
[Fact]
public void Three_jobs_of_time_three_process_evenly()
{
_jobs = new List<Job> {
new Job { processingTime = 3 },
new Job { processingTime = 3 },
new Job { processingTime = 3 }
};
var sched = new CyclicSchedule(_jobs);
sched.Process(3);
Assert.Equal(3m, sched.IterationCompletionTime(0));
Assert.Equal(3m, sched.IterationCompletionTime(1));
}
Again for now, each of our jobs simply runs flat out – when it finishes the first widget, it immediately starts on the next one – it’s 100% efficient. This makes the task of creating a simulator very simple: for each iteration, the start time for a job is just the previous start time, plus the time it takes to process:
public void Process(int numIterations)
{
// each job starts at 0
_jobs.ForEach(job => _startingTimes[job].Add(0));
for (int i = 1; i < numIterations; ++i)
{
_jobs.ForEach(job => _startingTimes[job].Add(_startingTimes[job].Last() + job.processingTime));
}
}
Now we can measure some interesting things about our schedule. For example, the IterationCompletionTime. This does not refer to the time that the iteration completed, but the total time it took to complete. As we see in the test above, both iteration 0 and iteration 1 took time of 3 to complete, as each of the three jobs takes time of 3.
But note – if our jobs took different amounts of time – say 7, 9, and 2, the iteration completion time is not just the average time for those three jobs. What we’re trying to simulate is the amount of time that our raw materials – say a hunk of steel – take to be processed. The raw materials come in as soon as an iteration starts.
So given this example, job 3 starts processing the second hunk of steel at time 2. But job 2 can’t start looking at the second hunk until time 9, and it won’t be done until time 18. So the IterationCompletionTime for iteration 2 = 18 – 2 = 16. And we can see that iteration 3 will start at 4 and end at 27, and pretty soon you’ve got big piles of half-processed steel sitting around the factory. Formally, the limit of the IterationCompletionTime as k approaches infinity, is infinity. That’s known as an “unstable schedule”, not surprisingly.
Here’s one way to calculate that:
public decimal IterationCompletionTime(int i)
{
var values = _startingTimes.Select(x => new { job = x.Key, starttime = x.Value[i], endtime = x.Value[i] + x.Key.processingTime });
return values.Max(val => val.endtime) - values.Min(val => val.starttime);
}
One more statistic that might be of interest: the Average Cycle Time of a job. The Cycle Time of a job is the time difference between starting one iteration and starting the next, so obviously, the average cycle time is the average of all those across all the iterations. Since for our model so far, every job can start on the next iteraton as soon as it’s done with the current one, the average cycle time is equal to the processing time. But here’s how you would calculate it anyway:
public decimal CycleTime(int jobNum)
{
var starts = _startingTimes[_jobs[jobNum]];
return (decimal)Enumerable.Range(1, starts.Count - 1)
.Select(i => starts[i] - starts[i - 1])
.Average();
}
Next time, we’ll model some more complex scenarios. Code is available on GitHub.