CODEWITHSUNDEEP
algorithmscheduled-tasks
Telenoobies
Telenoobies

Reputation: 936

Task scheduling to minimize waiting time algorithm

I am completely stuck on a task scheduling problem.

Here is the requirement: Implement a scheduling algorithm that adds jobs to the regular queue and pushes them through in such a way that the average wait time for all jobs in the queue is minimized. A new job isn't pushed through unless it minimizes the average waiting time. Assume that your program starts working at 0 seconds. A request for the ith job came at requestTimei, and let's assume that it takes jobProcessi seconds to process it.

def jobScheduling(requestTime, jobProcess, timeFromStart):

    requestTimeAndDuration={}
    for i in range(len(requestTime)):
        job=[]
        job.append(requestTime[i])
        job.append(jobProcess[i])
        requestTimeAndDuration[i]=job

    taskProcessed=[]
    previousEndTime=0
    while (requestTimeAndDuration):
        endTimes={}
        for k,v in requestTimeAndDuration.items():
            if(len(taskProcessed)==0):
                previousEndTime=0
            else:
                previousEndTime=taskProcessed[-1][1]
            #print previousEndTime
            if(v[0]<=previousEndTime):
                endTimes[k]= previousEndTime+v[1]
            else:
                endTimes[k]= v[0]+v[1]

        endTimesSorted = sorted(endTimes.items(), key=lambda endTimes: endTimes[1])
        nextJobId = endTimesSorted[0][0]
        nextJobEndTime = endTimesSorted[0][1]
        nextJob=[]
        nextJob.append(nextJobId)
        previousEndTime=0
        if(len(taskProcessed)>0):
            previousEndTime=taskProcessed[-1][1]
        nextJobStarTime = nextJobEndTime-jobProcess[nextJobId]
        nextJob.append(nextJobEndTime)
        nextJob.append(nextJobStarTime)
        taskProcessed.append(nextJob)
        del requestTimeAndDuration[nextJobId]
print taskProcessed

My algorithm tries to sort the tasks by its end time, which is computed from previousEndTime + currentJobProcess requestTime = [0, 5, 8, 11], jobProcess = [9, 4, 2, 1]

Final Result printed is [0,2,3,1]

My problem is that, my algorithm works for some cases, but not the complicated ones. requestTime: [4, 6, 8, 8, 15, 16, 17, 21, 22, 25] jobProcess: [30, 25, 14, 16, 26, 10, 11, 11, 14, 8]

The answer is [9, 5, 6, 7, 2, 8, 3, 1, 4] But my algoritm produces [5, 9, 6, 7, 8, 3, 1, 4, 0]

So does anyone know how to do this problem? I'm afraid my algorithm may be fundamentally flawed.

Upvotes: 1

Views: 1776

Answers (1)

mcdowella
mcdowella

Reputation: 19601

I don't see a really neat solution like sorting by end time, but if there is such a solution, you should be able to get the same answer by sorting the tasks using as a comparator a function that works out which task should be scheduled first if those are the only two tasks to be considered.

Upvotes: 1

Related Questions