On Nov 25, 5:31 pm, 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. > > 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.
You'd normally manage a problem like this by maintaining a job queue. Every time one of the n current jobs quits, you pull the next one off the queue and start it. There are various strategies for choosing which job to run next. Of course if a new job needs to run and there are less than n currently running (therefore the queue must be empty), you just start it immediately, otherwise add it to the queue. -- 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.
