Multitasking and Computation

In my younger years as a novice programmer, I can comfortably sit in a corner and program the day away. Life was so focused back then. You arrive at nine and without even noticing it, it’s time to go home with a great sense of achievement, perhaps because you were able to solve a major bug or develop an elegant framework. Alas, those were the days! Multitasking is now the norm and not the exception.

These days, you come at 9 AM doing all sorts of work, handling all sorts of interruption. By six o’clock you feel you haven’t even accomplished anything. What will all those meetings and interruptions every now and then. How do you measure your productivity then, with all these tasks you need to do every day. Some of these tasks are not even done in a day or two as you wait for data or input to proceed with it. Good thing there is already workflow technology to help you and the management keep track of the time you spent on your tasks without even consciously recording the time you started your task and the time you finished with it.

Suppose a certain employee is multitasking between 3 projects A, B, and C. Each project is composed one or more tasks. To represent Task1 of Project A, we symbolize it as A.1. The same goes with other tasks of other projects. When the employee works on a task, the system records the start time and the end time of the task. Most of the time, the employee switches between tasks, especially if one of the tasks is more urgent, and switches back to the previous task. We can represent this scenario using the diagram below:


In this example, you can see that the employee multitasked between tasks 1 and 2 of project A. We observe that the end time of task A.1 is greater than the start time of task A.2, which means that they overlap. The numbers 1, 2, and 1.5 represent the number of hours of the duration of each segment. The question we want to answer is, what is the total time spent by the employee in each task? Since the tasks overlap for a duration of 2 hours, we can assume, for the sake of simplicity , that the employee did half of the work on task A.1 and half of the work on task A.2 (As to the validity of this assumption, that is another story). Therefore, the total time alloted to each task is

A.1 = 1 + 2/2 = 2
A.2 = 2/2 + 1.5 = 2.5

Well that was easy. Now what happens if the employee’s multitasking graph is like the one below, how will you compute for the duration of each task?



The diagram shows 5 overlaps. The challenge is to create a program that will take as input the start and end times of each task and compute the total time of each task on the assumption that for every time interval that overlaps, the duration assigned to each task is divided equally among the overlapping tasks.

The algorithm

Label the start times and end times of each task like in the figure below.




Sort these times from earliest to latest to get t_1 < t_5 < t_3 < t_2 < t_6 < t_4 . Let us define the segment between any two consecutive t_j a TimeSegment. Create two structures named Project and TimeSegment. The Project structure will hold the name of the project and the start and end times. The TimeSegment structure will hold the duration two timestamps and the projects that intersect that time segment. We can then compute for the duration of each task using the algorithm below:

times= [ t1, t5, t3, t2, t6, t4 ]
times=sorted(times)
t = times[0]
for tj in times[1:len(times)]:
     duration = tj - t
     timesegment = TimeSegment(duration)
     addToTimeSegmentList(timesegment)
     # iterate over all projects and determine intersection
     for p in projectList:
           if p.start < tj and p.end >= tj:
                addProjectTo(timesegment,p)
     t=tj

for ts in segmentList:
     for p in ts.projects:
           theduration = ts.duration/float(len(ts.projects))
          p.duration += theduration

for p in projectList:
     print(p.name + " : " + str(p.duration))

I created a python script to implement this algorithm with the following output below:


project P0: start = 0, end = 3
project P1: start = 2, end = 5
project P2: start = 1, end = 4

Duration of Each Project:

P0 : 1.83333333333
P1 : 1.83333333333
P2 : 1.33333333333

In the next article, I’ll change the output of this program to a csv file and create an R script that will automatically plot the output to show clearly the overlaps.

Advertisements

Published by

Bobby Corpus

Is an IT Architect.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s