Category : Files from Magazines
Archive : CGAZV5N2.ZIP
Filename : SCHEDULE.C
Output of file : SCHEDULE.C contained in archive : CGAZV5N2.ZIP
* FILE: schedule.c *
* DESCRIPTION: A general-purpose scheduling function *
* COMPILER(s): Turbo C/C++ *
* AUTHOR: Allen I. Holub *
* DATE: November, 1990. *
* SWITCHES: MAIN - if defined, a test drive is defined *
* (c) C Gazette 1990, Use freely as long as authorship and publication *
* are acknowledged *
***********************************************************************/
#include
#include
#include
static int Nevents; /* Number of events to schedule */
static int Nchoices; /* Number of time-slot choices for each event */
static int *Events; /* Input array of events. Two dimensional array */
/* of Nevents elements, each element being */
/* a Nchoices-element array of int. */
/* In the current example, each row is a class */
/* and the columns are the instructors' choices */
/* for time slot for that class. */
static int Nslots; /* Number of time slots in schedule */
static int *Schedule; /* Nslots array of int. Fill with event numbers.*/
static int *Best_soln; /* Best solution found so far. */
static int Soln_weight; /* Weight of schedule in "Best_soln" */
static int Fail_weight; /* Weight of schedule in "Best_fail" */
static int *Best_fail; /* If no solution is possible, holds the best */
/* attempt at finding a solution. */
static int Best_depth; /* Depth at which the Best_fail was recorded */
#define NO_SOLN (((unsigned)~0) >> 1) /* Largest pos. int == no solution*/
/*----------------------------------------------------------------------*/
static int pick ( int );
int schedule ( int **oschedule, int *events, int nevents,
int nchoices, int nslots);
/*----------------------------------------------------------------------*/
int schedule( int **oschedule, /* output schedule */
int *events, /* input events array */
int nevents, /* # of events */
int nchoices, /* # of time-slot choices per event */
int nslots /* # of time slots */
)
{
/* Manufacture a schedule and modify *oschedule to point at it.
* Return 1 on success, 0 if a schedule couldn't be assembled, in
* which case *oschedule will point at the best guess. The schedule
* is an array of time slots, and is filled with the event number
* for that time slot or -1 if the time slot is empty.
*/
Nevents = nevents;
Nchoices = nchoices;
Nslots = nslots;
Events = events;
Best_depth = -1;
Soln_weight = NO_SOLN;
Fail_weight = NO_SOLN;
if( !(Best_soln = malloc( sizeof(int) * nslots )) ) return -1;
if( !(Schedule = malloc( sizeof(int) * nslots )) ) return -1;
if( !(Best_fail = malloc( sizeof(int) * nslots )) ) return -1;
memset( Best_soln, -1, sizeof(int) * nslots );
memset( Schedule, -1, sizeof(int) * nslots );
memset( Best_fail, -1, sizeof(int) * nslots );
if( pick(0) && Soln_weight != NO_SOLN )
{
*oschedule = Best_soln;
free( Best_fail );
free( Schedule );
return 1;
}
else
{
*oschedule = Best_fail;
free( Schedule );
free( Best_soln );
return 0;
}
}
/*------------------------------------------------------------------*/
static int pick( int weight )
{
/* Recursive backtracking scheduler. Returns 0 if there is no
* solution for the current subtree, the subtrees' weight if
* there was a solution. Assuming that the choices are weighted
* by their indexes, the tree weight is the sum of the choices
* for each branch of the path down to the solution. Lighter
* (smaller) weights are better.
*
* The weight argument is the accumulated weight of the path
* down to the current level.
*/
static int depth = 0; /* The recursion depth, also used */
/* as the event number. */
int choice; /* Choice number == branch weight. */
int *event; /* Choice list for current event. */
int *timeslot; /* Current time slot. */
int subtree_ok;
if( depth >= Nevents ) /* no subtree, return success */
return 1;
event = Events + (depth * Nchoices);
for( choice = 0; choice < Nchoices; ++choice )
{
if( *(timeslot = Schedule + *event++ ) == -1 )
{
*timeslot = depth++ ;
subtree_ok = pick( weight + choice );
--depth;
if( subtree_ok )
{
/* We found a solution. If it's weight is lighter than
* an existing solution, remember the current solution for
* comparison against subsequent solutions. Soln_weight
* is initialized to a very large number so the current
* path is always recorded for the first solution found.
* The test against Nevent-1 assures that a path is
* recorded only once from the leaf.
*/
if( Soln_weight > weight+choice && depth == Nevents-1 )
{
memcpy( Best_soln, Schedule, Nslots * sizeof(int) );
Soln_weight = weight + choice;
}
}
else
if( Soln_weight == NO_SOLN && depth >= Best_depth )
{
/* If no solution has been found yet, and either the
* current path is the longest one traversed so far, or
* if the current path is the same length as the
* previously-found longest one, but the weight is
* better, save the current path.
*/
if((depth > Best_depth) || (Fail_weight > weight+choice))
{
Fail_weight = weight + choice;
memcpy( Best_fail, Schedule, Nslots * sizeof(int) );
Best_depth = depth;
}
}
*timeslot = -1; /* Clear this slot and */
} /* loop back up to try */
} /* another. */
return (Soln_weight != NO_SOLN);
}
/*======================================================================*
* Test Driver *
*======================================================================*/
#ifdef MAIN
void print_sched( int *schedule, int nslots )
{
int slot;
printf( "Slot: Instructor:\n" );
for( slot = nslots; slot > 0 ; --slot )
printf( " %2d %2d\n", nslots - slot, *schedule++ );
}
/*----------------------------------------------------------------------*/
#define NUM_EVENTS 3
#define NUM_CHOICES 2
#define AVAILABLE_SLOTS 3
void main( void )
{
static int instructors[ NUM_EVENTS ][ NUM_CHOICES ] =
{
{ 0, 2 },
{ 1, 0 },
{ 0, 1 }
};
int success;
int *the_schedule;
success = schedule( &the_schedule, (int *)instructors,
NUM_EVENTS, NUM_CHOICES, AVAILABLE_SLOTS );
if( success )
printf("Schedule\n", success );
else
printf("No schedule works, my best attempt is:\n");
print_sched( the_schedule, AVAILABLE_SLOTS );
exit(0);
}
#endif /* #ifdef MAIN */
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/