User Tools

Site Tools


code:ga_scheduling

This is an old revision of the document!


GA Scheduling organization

Algorithm and ideas used for scheduling are described in master thesis. Please read this carefully before you will try to add new code.

If you will add new code, it currently lives only in REL_0_8_0 branch. Merging to trunk is expected in a few weeks. To get the code, issue:

svn co https://rts-2.svn.sf.net/svnroot/rts-2/branches/rts-2/REL_0_8_0

Most of functionality you are interested in is located in src/scheduler directory. Here we will mention two changes you will most probably like to to - add a new merit, or new constraint.

Adding new constraint

To add a new constraint, you should first declare its symbolic name in rts2schedule.h. The constraint shall be added to constraintFunc enumeration:

typedef enum
{
        CONSTR_VISIBILITY,                       // visibility violation - target is not visible
        CONSTR_SCHEDULE_TIME,            // schedule violation - target is scheduled outside its allowed time OR there exists target(s) which was not scheduled while it must be scheduled
        CONSTR_UNOBSERVED_TICKETS,       // number of unobserved tickets - tickets which have time constraint for schedule period, have some numObs left, but were not observed
        CONSTR_OBS_NUM                           // target is observed more times then it should be observed
} constraintFunc;

After you are done, you need to define function which will count constraint violation for you. And you will need to add it to getConstraintFunction method. Here is the example how CONSTR_VISIBILITY is defined. In rts2schedule.h you will find:

                /**
                 * Return constraint function. Constraint is satisfied, if return is = 0. Otherwise
                 * number of constraint violations is returned.
                 *
                 * @param _type Constraint function type.
                 *
                 * @return Number of targets which are infeasible with respect to given constraint.
                 */
                unsigned int getConstraintFunction (constraintFunc _type)
                {
                        switch (_type)
                        {
                                case CONSTR_VISIBILITY:
                                        visibilityRatio ();
                                        return unvisible;
                                case CONSTR_SCHEDULE_TIME:
                                        return violateSchedule ();
                                case CONSTR_UNOBSERVED_TICKETS:
                                        return unobservedSchedules ();
                                case CONSTR_OBS_NUM:
                                        return violatedObsNum ();
                        }
                        return UINT_MAX;
                }

and

                /**
                 * Ratio of observations from schedule which are visible.
                 *
                 * @return Ration of visible targets. Higher means better schedule.
                 */
                double visibilityRatio ();

and then in rts2schedule.cpp you will find that visibility constraint is calculated as:

double
Rts2Schedule::visibilityRatio ()
{
        if (!isnan (visRatio))
                return visRatio;
 
        visible = 0;
        unvisible = 0;
 
        for (Rts2Schedule::iterator iter = begin (); iter != end (); iter++)
        {
                if ((*iter)->isVisible ())
                        visible++;
                else
                        unvisible++;
        }
        visRatio = (double) visible / size ();
        return visRatio;
}

The most important is for you inner loop which calculated how much targets in the schedule are unvisible and visible. The first if is only syntax sugar for lazy initialization of values, which significantly improves scheduling algorithm speed. Important is iterator loop through members of the schedule, which ask every member if it is visible. isVisible is then defined in rts2schedobs.h as:

                /**
                 * Determines schedule target visibility.
                 *
                 * @return True is observation is visible.
                 */
                bool isVisible ()
                {
                        // determine if target is visible during whole period
                        if (getTarget()->isGood (getJDStart ()) == false
                                || getTarget ()->isGood (getJDMid ()) == false
                                || getTarget ()->isGood (getJDEnd ()) == false)
                                return false;
                        double minA, maxA;
                        getTarget ()->getMinMaxAlt (getJDStart (), getJDEnd (), minA, maxA);
                        return minA > 0;
                }

For definition of isGood function, please have a look to src/utilsdb/target.ec.

code/ga_scheduling.1231673236.txt.gz · Last modified: 2009/01/11 00:00 (external edit)