From: Hans Fugal Date: 2005-08-17T14:16:15+09:00 Subject: Re: Scheduling (#42) Kero wrote: > >> May I assume then, that there are only timeslots of full hours? > > > > I assumed that from reading of quiz. It's probably an over > > simplistic assumption, but I think it will do for this challenge. > > P.S. Hans, feel free to jump in here and save me at any time... :D > > Isn't the problem in general NP hard? Meaning you have to make some > simplifications to keep the input small, or apply some other > restrictions to get the problem to P. Well I'll take your word for it on the NP thing because I don't have the brain cycles to spare at the moment. ;-) It is definitely not trivial. > Of course, it is also possible to generate input for which there is no > solution. Then what? When to loosen bonus targets like regular times for > a person and when to give up? See below... > I think everybody has to figure this out for him/herself. I'm not clear what you mean by that. I think you might mean every McDonalds manager has to figure this out him/herself. That's the interesting thing here - lots and lots of people do this every single day. > Moreover, do not restrict the application to people and time, it can be > anything and time (or even boxes and space if you can restrict the space > to 1D meaningfully :) Yes, it is essentially the knapsack problem with time dependence added. > I can't suppress the feeling that the quiz is meant to pick a "nice" > solution when there's plenty of solutions available. For which you need > (a lot of) example input... Yes and no. I alluded to the fact that people have minimal difficulty doing this (although as you can imagine it is a common sore spot between employees and employers) so that seems to suggest that one approach would be an AI approach. We are looking for one of many solutions. Ideally we find the optimal solution, but we're happy to find a "good" solution. Your response has piqued my interest (I unfortunately don't often find time to do these quizzes, even when I'm the one who comes up with the idea. ;-). Here's how I plan to do it: We want to search the solution space for good answers. First we need to represent things, and my first idea here is a sequence of (day, hour, person) tuples, where day is a weekday name, hour is something like 1300, and person is the name of a person. The sequence for a whole week (with a 12-hour business day) is 72 tuples long, not too bad. Next we need to have a way to know if an answer is good, and how good the answer is. This is called a utility function in AI. Normally you award points for things you like and demerit points for things you don't like. Finding a good utility function is the artistic and most important part of a search like this. Now we can represent whole and partial solutions and measure their utility. Now all we have to do is search. I'm guessing an A* search will do the trick nicely (it usually does). If not A* then one of its variants, probably. Or maybe greedy will do the job sufficiently well for most purposes. All that remains is to choose a good heuristic, this is the other artistic and important part of the algorithm. Assuming we can find a reasonable heuristic and utility function, the computer should be able to find us good solutions. If we can find sufficiently good heuristic and utility functions, we can say the solution is optimal - whatever that means. (In other words, if we knew what optimal was in the real world for this problem, and we could represent it with utility/heuristic functions, we could find an optimal solution). I hope to find the time to code this up, for the proof is in the pudding. The only real question in my (perhaps over-confident) mind is, will it fit in memory and time constraints? When you have a problem where valid solutions abound and you're looking for a "good" solution, the answer is usually that you can find better and better solutions given enough time and memory, and hopefully you can find something good enough given realistic time and memory. Hans