Thursday, 11 June 2020

Microsoft Excel Based Task Scheduler (non-preemptive earliest-deadline-first (EDF))

I do not usually post any work I do on Microsoft Excel on my blog, but recently I was working on a project which forced me to prepare an automated non-preemptive earliest-deadline-first (EDF) scheduler from excel. As I was not able to find any work done on this previously on the web, I decided to share my approach to this problem.

Disclaimer: This is by far not the best approach to a problem of this nature. There are dedicated software that handle complicated functions like this. But, this is a moderately simple method to achieve the same using Microsoft Excel.
Please also note that there may be some errors that can arise as I have not extensively tested this method outside the scope of what I specifically need this for.

Scenario:

There is a list of tasks that needs to be done among 4 people. The tasks are individually assigned and they arrive at different times. Each task takes a fixed 3 working days to complete and has it's own deadline before which it needs to be completed. The work assigned to each person must be scheduled such that the deadline is prioritized as in an non-preemptive earliest-deadline-first (EDF) scheduler.


Solution:

Step 1: Create 3 hidden columns for each person which extracts only information that is relevant to them, and rank the activities assigned to them using the In-date.


Person 1 ID Rank =IF([@[Person 1 ID]]="","",COUNTIF($G$1:G10,[@[Person 1 ID]])+RANK.EQ([@[Person 1 ID]],[Person 1 ID],1))

Person 1 Deadline =IF([@Person]=Deadline!$H$3,[@Deadline],"")

Person 1 ID =IF([@Person]=Deadline!$H$3,[@[In Date]],"")

Step 2: Create a hidden sheet for 3 hidden tables.

Step 3: Table 1 created is named "tblStartDates". This table will tell the next available start date for a task. The header is removed and is replaced with the date 3 days prior to the minimum In Date in the task list.

Column 1 =WORKDAY(AJ3,1,tblHolidays[Holiday])
Column 2 =AK3+1
Column 3 =IF(MOD(tblStartDates[[#All],[Column2]],$R$1)=1,WORKDAY(AL3,$R$1,tblHolidays[Holiday]),AL3)

This creates a reference date for each date where the reference dates are spaced 3 days apart. (R1 = 3)

Step 4: Create the second table, "tblScheduler" where each person is assigned 8 columns.

ID (in Date) =IF(ISERROR(VLOOKUP([@[In Date Rank]],tblActions[[Person 1 ID Rank]:[Person 1 ID]],3,FALSE)),"",VLOOKUP([@[In Date Rank]],tblActions[[Person 1 ID Rank]:[Person 1 ID]],3,FALSE))

Deadline =IF(ISERROR(VLOOKUP([@[In Date Rank]],tblActions[[Person 1 ID Rank]:[Person 1 ID]],2,FALSE)),"",VLOOKUP([@[In Date Rank]],tblActions[[Person 1 ID Rank]:[Person 1 ID]],2,FALSE))

The two columns above simply pull information from the previous table sorted to the rank defined

Earliest Start Date (ESD) Rank =RANK.EQ([@[A ESD]],[A ESD],1)

ESD =IF(ISERROR(VLOOKUP(WORKDAY([@[A ID]],(COUNTIF($C$3:C3,C4)*$R$1),tblHolidays[Holiday]),tblStartDates[#All],3,TRUE)),"",VLOOKUP(WORKDAY([@[A ID]],(COUNTIF($C$3:C3,C4)*$R$1),tblHolidays[Holiday]),tblStartDates[#All],3,TRUE))

Date =IF(ISERROR(VLOOKUP([@[A ESD Rank]],tblNewStartDates,2,FALSE)),"",VLOOKUP([@[A ESD Rank]],tblNewStartDates,2,FALSE))

Duplicate In Date =IF(COUNTIF([A ESD],[@[A ESD]])>1,[@[A Date]],"")

Duplicate Deadline =IF(COUNTIF([A ESD],[@[A ESD]])>1,[@[A Deadline]],"")

New Deadline =IF(IF(IF([@[A Dup Deadline]]="",0,RANK([@[A Dup Deadline]],[A Dup Deadline],1)-RANK.EQ([@[A Dup ID]],[A Dup ID],1))=0,[@[A Date]],VLOOKUP([@[A ESD Rank]]+IF([@[A Dup Deadline]]="",0,RANK([@[A Dup Deadline]],[A Dup Deadline],1)-RANK.EQ([@[A Dup ID]],[A Dup ID],1)),tblNewStartDates,2,FALSE))="","",WORKDAY(IF(IF([@[A Dup Deadline]]="",0,RANK([@[A Dup Deadline]],[A Dup Deadline],1)-RANK.EQ([@[A Dup ID]],[A Dup ID],1))=0,[@[A Date]],VLOOKUP([@[A ESD Rank]]+IF([@[A Dup Deadline]]="",0,RANK([@[A Dup Deadline]],[A Dup Deadline],1)-RANK.EQ([@[A Dup ID]],[A Dup ID],1)),tblNewStartDates,2,FALSE)),$R$1,tblHolidays[Holiday]))


Step 5: Create the table of new start dates for each person, "tblNewStartDates"

A =IF([@0]=1,VLOOKUP([@0],tblScheduler[[A ESD Rank]:[A ESD]],2,FALSE),IF(ISERROR(VLOOKUP([@0],tblScheduler[[A ESD Rank]:[A ESD]],2,FALSE)),WORKDAY(AO3,$R$1,tblHolidays[Holiday]),IF(VLOOKUP([@0],tblScheduler[[A ESD Rank]:[A ESD]],2,FALSE)<=AO3,WORKDAY(AO3,$R$1,tblHolidays[Holiday]),VLOOKUP([@0],tblScheduler[[A ESD Rank]:[A ESD]],2,FALSE))))

There are definitely mistakes that can arise with this method that I have not thought of and there are better ways of doing this with excel. If you have done a similar task do let me know in the comments below.

No comments:

Post a Comment