[PHP] Re: Seeking a scheduling algorithm

On Jul 14, 2012, at 4:53 PM, php-general-digest-help@lists.php.net wrote:

> From: Tedd Sperling <[email protected]>
> Subject: Seeking a scheduling algorithm
> Date: July 14, 2012 4:53:15 PM EDT
> To: php-general@lists.php.net
>
>
> Hi gang:
>
> Does anyone have a resource, or better yet code, to solve the scheduling problem described below?
>
> Let's say you have a week calendar that has openings between 8:00am to 5:00pm for Monday through Friday (40 hours).
>
> Then you have an assortment of appointments that must be scheduled into the week calendar. Some of the appointments are simply a one hour per week, while others may be two, three, four, or five times per week and each appointment for an hour or more (up to eight hours).
>
> 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?
>
> The most efficient way is defined as scheduling appointments with little, or no, gaps in between appointments. For example, four one-hour appointments on Monday between 8:00am to 12:00pm is better than four one-hour appointments spread out between 8:00am to 5:00pm.
>
> Anyone have any solutions, ideas, resources, code?
>
> Thanks,
>
> tedd
>
> _____________________
> tedd@sperling.com
> http://sperling.com
>


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 =====-----
--

A closed mouth gathers no feet.

On Jul 14, 2012 5:34 PM, "Bill Guion" <[email protected]> wrote:
>
> On Jul 14, 2012, at 4:53 PM, php-general-digest-help@lists.php.net wrote:
>
> > From: Tedd Sperling <[email protected]>
> > Subject: Seeking a scheduling algorithm
> > Date: July 14, 2012 4:53:15 PM EDT
> > To: php-general@lists.php.net
> >
> >
> > Hi gang:
> >
> > Does anyone have a resource, or better yet code, to solve the
scheduling problem described below?
> >
> > Let's say you have a week calendar that has openings between 8:00am to
5:00pm for Monday through Friday (40 hours).
> >
> > Then you have an assortment of appointments that must be scheduled into
the week calendar. Some of the appointments are simply a one hour per week,
while others may be two, three, four, or five times per week and each
appointment for an hour or more (up to eight hours).
> >
> > 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?
> >
> > The most efficient way is defined as scheduling appointments with
little, or no, gaps in between appointments. For example, four one-hour
appointments on Monday between 8:00am to 12:00pm is better than four
one-hour appointments spread out between 8:00am to 5:00pm.
> >
> > Anyone have any solutions, ideas, resources, code?
> >
> > Thanks,
> >
> > tedd
> >
> > _____________________
> > tedd@sperling.com
> > http://sperling.com
> >
>
>
> 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 =====-----
> --
>
> A closed mouth gathers no feet.
>

What this sounds like, to me, is quite similar to either a memory
allocation scheme or a disc defragmenting scheme. I haven't worked either
of those since I went to Jurassic United, though...

_____________________
tedd@sperling.com
http://sperling.com

On Jul 14, 2012, at 6:32 PM, Bill Guion <[email protected]> wrote:

> On Jul 14, 2012, at 4:53 PM, php-general-digest-help@lists.php.net wrote:
>
>> From: Tedd Sperling <[email protected]>
>> 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