Friday, August 19, 2016

jobs with priority and sla

Each job has a priority and each priority has an sla. Return finish time if job can be honored or return false.
priority    sla (mins)
1           3
2           5
3           7
Use queue for each priority. Calculate cumulative count of jobs for a priority and its higher priority(s) and compare with slas.
//examples
Assume each job takes 1 min to finish i.e. job.time = 1.

q(sla) times
q1(3)  2: 1-1
q2(5)  2: 
q3(7)  2:
output: job(1,2,3) is accepted

q(sla) times
q1(3)  0: 
q2(5)  4: 2-2-2-2
q3(7)  4:
output: job(1,2,3) is accepted

q(sla) times
q1(3)  0: 
q2(5)  0: 
q3(7)  6: 3-3-3-3-3-3
output: job(1,2,3) is accepted

--

q(sla) times
q1(3)  0: 
q2(5)  0: 
q3(7)  7: 3-3-3-3-3-3-3
output: none is accepted

--

q(sla) times
q1(3)  0: 
q2(5)  5: 2-2-2-2-2
q3(7)  5:
output: job(3) is accepted

q(sla) times
q1(3)  3: 1-1-1
q2(5)  5: 2-2
q3(7)  7: 3-3
output: none is accepted

--

q(sla) times
q1(3)  2: 1-1
q2(5)  4: 2-2
q3(7)  6: 3-3
output: job(1,2,3) is accepted

q(sla) times
q1(3)  3: 1-1-1
q2(5)  4: 2
q3(7)  6: 3-3
output: job(2,3) is accepted

q(sla) times
q1(3)  3: 1-1-1
q2(5)  5: 2-2
q3(7)  6: 3
output: job(3) is accepted
jobQueue:
    // queues for jobs with priority 1, 2, 3
    q1, q2, q3
    // slas for jobs with priority 1, 2, 3
    sla1, sla2, sla3
    
    // O(nm) for n items and m priorities
    insert(job):
        time1 = q1.time()
        time12 = time1 + q2.time()
        time123 = time12 + q3.time()
        if job.priority == 1:
            if time1 +job.time <= sla1
                && time12 +job.time <= sla2
                && time123 +job.time <= sla3:
                q1.enqueue(job)
                return (true, time1 +job.time)
        else if job.priority == 2:
            if time12 +job.time <= sla2
                && time123 +job.time <= sla3:
                q2.enqueue(job)
                return (true, time12 +job.time)
        else if job.priority == 3:
            if time123 +job.time <= sla3:
                q3.enqueue(job)
                return (true, time123 +job.time)
        return (false, null)
    
    // O(m) for m queues
    job next():
        if !q1.empty():
            return q1.dequeue()
        else if !q2.empty():
            return q2.dequeue()
        else if !q3.empty():
            return q3.dequeue()
        return null

queue:
    q
    time
    enqueue():
        q.enqueue(job)
        time += job.time
    job dequeue():
        if !q.empty():
            job = q.dequeue()
            time -= job.time
            return job
        throw
    time():
        return time
[Hat tip to M]

No comments:

Post a Comment