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.
>From the description, I'd keep a list of intervals based on the number of tasks running sorted by the start time of the intervals. Adding known tasks involves breaking into breaking the overlapping intervals at the task's start-end time and incrementing the number of tasks. Then it's a matter of finding a consecutive series of intervals that are not full that sum to the estimated running time. As for estimating run time, it really depends on the distribution of the tasks, one really long or short program can skew results. There are lots of ways of making an estimate. -- Geoff -- 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.
