foobar
BAN USER- 0of 0 votes
AnswersGiven a set of 21 tasks = {A, B,....Z} except I, O, U, X and Q. Each task requires 4 hours of processing. Except for tasks E, Y, P, R, W that require 8 hours of processing.
- foobar in United States
You have 3 machines to process these tasks = T1, T2, T3. T1 and T2 are available everyday for 8 hours. T3 is available only on Mon, Wed and Fri for 8 hours.
You are given 3 lists that indicate the dependency list among the tasks.
L1 = A->R->K->M (eg A can be completed if R is completed, R can be completed only if K is completed etc.)
L2 = N->G->V->E->Z->H
L3 = C->F->Y->D->J->P->T->S->W->B->C (cycle)
Each task needs one machine for its duration to complete.
Tasks cannot be resumed. Which means the 8 hour tasks cannot be executed over 2 days.
Each machine can process only one task at any time.
T1, T2 and T3 can process different tasks in parallel.
You are starting your schedule on a Wednesday.
Machines can be scheduled only during weekdays.
The first Monday in your schedule is a downtime for all the machines.
Given these constraints, write a program that generates a schedule between the tasks and machines such that all the tasks are completed at the
earliest.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm C++ Coding
L1 and L2 tasks can be scheduled in a straight forward way. But you cant schedule the tasks in L3 directly because there is a cycle.
- foobar May 14, 2014So, you will have to use some strategy (like bankers algo) to break this deadlock and proceed to schedule the tasks in L3 as well.