• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Anyone good at LOGIC?

S

SONYFX

Senior member
I need help!

Suppose you are given a set S ={a1, a2 ,.......an} of tasks,
Task ai requires Pi ( pi ={p1, p2,......pn} )units of processing time to complete, once it has started.

You have one computer on which to run these tasks, and the computer can run only one task at a time.

Let ci ( ci ={c1, c2,......cn} )be the completion time of task ai , that is, the time
at which task ai completes processing. Goal is to minimize the average completion time

For example, suppose there are two tasks, a1 and a2 , with p1 = 3 andp2 = 5,
and consider the schedule in which a2 runs first, followed by a1 .

Then c2 = 5, c1 = 8, and the average completion time is (5 + 8)=2 = 6.5

(a) Give an algorithm that schedules the tasks so as to minimize the average completion time. Each
task must run non-preemptively, that is, once task a i is started it must run continuously for p i
units of time.
 
I got to "Suppose you are given a set S ={a1, a2 ,.......an} of tasks,
Task ai requires Pi ( pi ={p1, p2,......"

...and then my head exploded.
 
Originally posted by: Astaroth33
If you want help with logic, you should try asking the women who visit here...

😉
Click to expand...

Yeah, but then you're stuck trying to figure out which of them are actually women. That's a bigger and different problem altogether 😉
 
Originally posted by: Dissipate
This problem is ridiculous. Maybe if we knew exactly what these mysterious "tasks" were.
Click to expand...

why? that's not relevant...

i dunno work through some math and figure it out... do you have a specific question?
 
I would agree that it would just be lowest to highest... but I am sure there is more too it than that... The higher up you go the longer it takes, right?
 
Originally posted by: MacBaine
I would agree that it would just be lowest to highest... but I am sure there is more too it than that... The higher up you go the longer it takes, right?
Click to expand...

yea but you can probably do a proof by induction to show it works... it works in the 2 task case...
 
Originally posted by: gopunk
Originally posted by: Dissipate
This problem is ridiculous. Maybe if we knew exactly what these mysterious "tasks" were.
Click to expand...

why? that's not relevant...

i dunno work through some math and figure it out... do you have a specific question?
Click to expand...

It may not be relevant but I'm clawing for something to grab on to that will help me solve this. The information seems scant. Heh.

 
Originally posted by: Dissipate
This problem is ridiculous. Maybe if we knew exactly what these mysterious "tasks" were.
Click to expand...

task can be any task, like a running program in computer.
 
Originally posted by: dighn
lets say you have n tasks, the goal is to minimize the total sum. the last task will finish at the same time regardless of how you order them, so you want to minimize n-1 and all the previous sums by moving one item to the back, you do that by taking out the largest item and moving it to the back, then repeat for n-1, etc etc. so it's a sort from lowest ot highest

or you can sy something like

t1 = a1
t2 = a1 + a2
t3 = a1 + a2 + a3
tn = a1 + a2 ... + an

so t total = n*a1 + (n-1)*a2 ... + 1*an
the items have increasing weights so you want to minimize from left ot right
Click to expand...

hmm.......but the tasks can be random......



 
ok if you don't want to do a proof by induction, just do a direct or indirect proof and show that if you have the tasks lined up from shortest to longest, that your avg completion time will never get shorter (or always get longer or stay the same) if you mess up that order.
 
Do your own OS hw. The answer is simple, algorithm is SJF. The goal is pretty stupid since in the real world load matters more than average completion time, so then RMS is optimal for non-preemptive (max load = 69%).
 
I don't see what this really has to do with logic. The topic should be "Anyone good at my HOMEWORK?" Just choose an algorithm. Most likely it has been recently discussed in lecture.
 
Originally posted by: SONYFX
I need help!

Suppose you are given a set S ={a1, a2 ,.......an} of tasks,
Task ai requires Pi ( pi ={p1, p2,......pn} )units of processing time to complete, once it has started.

You have one computer on which to run these tasks, and the computer can run only one task at a time.

Let ci ( ci ={c1, c2,......cn} )be the completion time of task ai , that is, the time
at which task ai completes processing. Goal is to minimize the average completion time

For example, suppose there are two tasks, a1 and a2 , with p1 = 3 andp2 = 5,
and consider the schedule in which a2 runs first, followed by a1 .

Then c2 = 5, c1 = 8, and the average completion time is (5 + 8)=2 = 6.5

(a) Give an algorithm that schedules the tasks so as to minimize the average completion time. Each
task must run non-preemptively, that is, once task a i is started it must run continuously for p i
units of time.
Click to expand...

1) You ask us this at 2:00/3:00 in the morning?????
2) I have no clue, and if i did know i dont think id take the time to figure it out....

sorry man.
 
i was hoping for a "if sam, and billy and tim had a boat that could hold 90 lbs, and same weighed 40, and billy weighed 50 and tim weighed 90 how would they get it across the river"

to which i could have confidently answered "they swim because their parents were too damned cheap to buy a boat big enough for all of them" and THAT makes the parents asshats...
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top