_____________________ tedd@xxxxxxxxxxxx http://sperling.com On Jul 14, 2012, at 6:32 PM, Bill Guion <bguion@xxxxxxxxxxx> wrote: > On Jul 14, 2012, at 4:53 PM, php-general-digest-help@xxxxxxxxxxxxx wrote: > >> From: Tedd Sperling <tedd@xxxxxxxxxxxx> >> Does anyone have a resource, or better yet code, to solve the scheduling problem described below? >> -snip- >> The problem is, knowing what appointments (i.e., twice a week for 2 hours, three times a week for one hour, etc.) must be scheduled for the week, what is the most efficient way to schedule these appointments into that week? > > > Tedd, > > There is an old general rule that the most time efficient way to schedule is to put the "big" time requests on the schedule first. In this case, that would mean schedule all five times a week requests first, then the four times a week, then the three times a week. The two hour requests should be scheduled next: three times a week and twice a week can be scheduled at the same time. Then fill in the rest with the one hour requests. > > Hope that makes sense. > > -----===== Bill =====----- Bill: Yes, that makes sense and that has been my first-blush approach to the solution to this problem. It's a bit like filling a paper bag at checkout, or filling a moving van -- you put in the biggest items first and then fill the empty spaces with smaller and smaller items. I was just thinking the problem is not new and perhaps there is an algorithm laying around somewhere. For example, an automated "solution" for the Tetris game might be a good match. People have proposed the Bin Packing Problem and looks interesting. Likewise, the knapsack proposal is interesting, but it leaves stuff behind, which is not possible in the problem I'm trying to solve. If I have too many appointments, then I simply hire more people to solve the overbooking problem. This problem is: 1. Fill all the open times efficiently with bookings. 2. If you run out of open times, then open a new week and fill it similarly. Like I said, this is similar to filling a paper bag at checkout -- when the bag is filled (as efficiently as possible), then get another bag and repeat. I claim if you know the size and number of items before-hand, then you should be able to optimize both: a) the filling of each bag; b) and minimize the number of bags you need. Maybe that's a better way to describe this problem. > A closed mouth gathers no feet. LOL -- I should remember that. Cheers, tedd -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
