User Tools

Site Tools


code:ga_scheduling

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.

The algorithm mention constraints and objectives. Constrains method return number of constraint violations and the algorithm tries to minimize them, providing schedule with zero constraint violations. So far there are not soft and hard constraint, and implementation of them to scheduling can be an interesting topics. The algorithm search for maximal values of the objective functions.

Important is to remember that lower constraint violation value means better schedule, and higher objective function value means better schedule. If you come to objective which naturally produces better schedules when lower value is calculated, you can easily change function by using 1/f(x) instead.

In order to use GA scheduling, you will need to fill in database. You will also find it useful to use pyrts2 to visualise schedule, so you will be able to see how scheduling algorithm behaves.

Database setup

Note: Currently you need to build database from REL_0_8_0 branch. See bellow how to retrieve it.

You need to fill tickets and accounts tables.

Tickets table contains those fields:

Field name Data type Description
schedticket_id integer unique ID of ticket - primary key
tar_id integer ID of target which belongs to the ticket
account_id integer ID of account - can be null if this ticket is out of accounting
obs_num integer Maximal number of observations - scheduler will try to schedule only observations bellow this number
sched_from timestamp without time zone Schedule observation from this time; if null, schedule anytime
sched_to timestamp without time zone Schedule observation to this time; if null, schedule anytime
sched_interval_min interval Minimal interval between observations
sched_interval_max interval Maximal interval between observations

Using pyrts2 to preview schedules

Obtaining and modifying code

The GA scheduler code 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 a 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.

After you are done, you shall add new constraint to constraint which will be used in scheduling. This is done in rts2schedbag.cpp:

Rts2SchedBag::Rts2SchedBag (double _JDstart, double _JDend)
{
        // ommited lines..
 
        constraints.push_back (CONSTR_VISIBILITY);
        constraints.push_back (CONSTR_SCHEDULE_TIME);
        constraints.push_back (CONSTR_UNOBSERVED_TICKETS);
        constraints.push_back (CONSTR_OBS_NUM);
}

Adding new objective function

Process of adding new objective function is similar to adding new constraint. If you understand how constraint functions are added, you will not have any problems understanding how objectives are added.

You will need to add new objective symbolic name to objFunc enumeration. In rts2schedule.cpp you will need to add new objective to getObjectiveName function:

const char* getObjectiveName (objFunc obj)
{
        const static char* objNames[] = { "VISIBILITY", "ALTITUDE", "ACCOUNT", "DISTANCE",
                "DIVERSITY_TARGET", "DIVERSITY_OBSERVATIONS", "SINGLE"};
        return objNames[(int) obj];
}

Then procedure is similar - add objective to case in Rts2Schedule::getObjectiveFunction, add function to calculate it to Rts2SchedObs class.

And finally add it to objectives in rts2schedbag.cpp:

        // fill in parameters for NSGA
        objectives.push_back (ALTITUDE);
        objectives.push_back (ACCOUNT);
        objectives.push_back (DISTANCE);
        objectives.push_back (DIVERSITY_TARGET);
code/ga_scheduling.txt · Last modified: 2009/01/18 00:00 (external edit)