Hi,
On Thu, Nov 26, 2009 at 4:01 AM, bingbang <[email protected]>wrote:
> Dear all,
> I am a newbie here, this is my first post. I have looked over a few
> algorithms and have searched this board for my question but have not
> been able to narrow down to a clear answer.
>
> I am looking for any pointers/code/advice to help decide how to solve
> the following problem.
>
> I have to write a program to suggest the starting time of a job. There
> is 1 CPU, and there are n jobs already scheduled on it and we know
their run times. I can assume a run time (maybe a median of the known
> run times or something) for this new job. The constraint being at no
> time should there be more than m jobs running in parallel.
>
Since it seems like it is from the operating systems domain, can these
processes be
preempted?
Regards
Aditya Shankar
>
> I think this problem is relatively simple. For a hammer and tongs
> solution, I have implemented a quick-sort kinds binary cleaving
> program which starts with a random time of the day, say, 13:00, and
> checks if one more process can be started at that time, it accepts the
> "assumed" run time of the new process and finds if the number of jobs
> will become greater than m during the assumed run time of the new
> process. If not, success! else, I cleave the two sides of the time
> chosen 00:00-12:59 and 13:01-23:59 (of course I can add the assumed
> run time to 13:01 to make a better choice of the window/range) to get
> the midway time position and check there and so on.
>
> Can there be a more formal solution to this problem? Like maybe based
> on the Knapsack algorithm or something.. any advice.
>
> Also, what could be a good measure of the "assumed" run time, I'm
> thinking median. I do realize that this question is a bit vague.
>
> Thanks in advance,
> -J
>
> --
>
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
