from django.db import models from pyrosapp.models import Schedule, Sequence from operator import attrgetter from decimal import * DEFAULT_PLAN_START = 2457485.250000 # April 6th 2016, 18:00:00.0 UT DEFAULT_PLAN_END = 2457485.916667 # April 7th 2016, 10:00:00.0 UT PRECISION = Decimal(0.0000000001) SIMULATION = False ''' Note : the following functions are necessary due to a too-high precision of Decimal objects ''' def is_nearby_equal(a : Decimal, b : Decimal, precision : Decimal = PRECISION): ''' Compare the two decimal, according to the given precision ''' return (True if abs(b - a) < PRECISION else False) def is_nearby_sup_or_equal(a : Decimal, b : Decimal, precision : Decimal = PRECISION): ''' Compare the two decimal, according to the given precision ''' if (a > b): return True return (True if abs(b - a) < PRECISION else False) def is_nearby_less_or_equal(a : Decimal, b : Decimal, precision : Decimal = PRECISION): ''' Compare the two decimal, according to the given precision ''' if (a < b): return True return (True if abs(b - a) < PRECISION else False) class Interval: """ Simple class that represents an interval of time Julian days should be used """ def __init__(self, start, end): self._start = Decimal(start) self._end = Decimal(end) self.duration = Decimal(end - start) def __str__(self): print("["+str(self.start)+" - "+str(self.end)+"]") def _get_start(self): return self._start def _set_start(self, start): if start > self._end: raise ValueError("Cannot set start (%d): must be lower than end (%d)" % (start, self._end)) self._start = start self.duration = self._end - self._start def _get_end(self): return self._end def _set_end(self, end): if end < self._start: raise ValueError("Cannot set end (%d): must be bigger than start (%d)" % (end, self._start)) self._end = end self.duration = self._end - self._start start = property(fget=_get_start, fset=_set_start) end = property(fget=_get_end, fset=_set_end) class Scheduler(): """ Role : create a planning for the following/current night Read in DB : Sequence, PyrosUser, ScheduleHistory and parents Create in DB : Schedule, ScheduleHistory ? (not sure) Update in DB : Schedule, Sequence Delete in DB : None Entry point(s) : - make_schedule - re_schedule - simulate_schedule """ """ TODO: - définition de plan_start et plan_end - calcul de la priorité - calcul des quotas - définir l'attribut 'flag' de Schedule - gestion du re-scheduling (en cas de nouvelle requete) - remplissage des espaces libres - gestion de l'historique (je sais pas si c'est ce module qui va s'en charger au final mais bon ...) """ def __init__(self): self.schedule = Schedule.objects.create() # TODO: quel est le "flag" dans le schedule ?? self.get_night_limits() # TODO self.intervals = [] def get_night_limits(self): ''' determines and set plan_start and plan_end (beginning & end of the observation night) ''' # TODO: définir comment on calcule plan_start et plan_end (via quels moyens) self.schedule.plan_start = DEFAULT_PLAN_START # default value self.schedule.plan_end = DEFAULT_PLAN_END # default value def make_schedule(self): ''' ENTRY POINT Check all 'OBSERVABLE' sequences to create the most optimized planning for the following/current night It is assumed that all sequences that MUST and CAN be analyse have the OBSERVABLE status (e.g. : there must not be any PLANNED sequence at this point) :side-effect : - modify sequences status and dates in DB ''' global SIMULATION SIMULATION = False self.sequences = list(Sequence.objects.filter(status=Sequence.OBSERVABLE)) self.compute_schedule() self.save_sequences() def re_schedule(self): ''' ENTRY POINT Creates a brand new schedule for the current night. Takes all the PLANNED sequences to make them OBSERVABLE Saves all the EXECUTED sequences of the current planning to put them in the new one, then delete the current Calls make_schedule to create the new one ''' # voir comment on gère la sauvegarde des plannings, si on fait le coup des EXECUTED ui rentrent dans le nouveau, on n'aura # plus la correspondance des dates. Ce serait peut-être bien de garder le même objet schedule au cours de la nuit, # avec le même plan_start et plan_end, mais quand on fait un scheduling on le fait à partir d'un start déterminé en interne # mais ça va être chiant si le plan_start et plan_end peuvent changer au cours de la journée # TODO: cette méthode pass def simulate_schedule(self, sequences): ''' ENTRY POINT - SIMULATION Do the same as make_schedule but do not touch the DB :type sequences : list of Sequence :param sequences : sequences to plan :returns : a tuple (Schedule, list of sequences) ''' global SIMULATION SIMULATION = True self.sequences = sequences self.compute_schedule() return (self.schedule, self.sequences) def compute_schedule(self): self.intervals.append(Interval(self.schedule.plan_start, self.schedule.plan_end)) self.check_sequences_validity() self.determine_priorities() self.remove_not_eligible_sequences() self.sort_by_jd2_and_priorities() self.organize_sequences() def check_sequences_validity(self): ''' Checks come sequence attributes to validate their integrity :side-effect : - remove invalid sequences from self.sequences - set INVALID status for invalid sequences in DB ''' ''' Note(1) ''' for sequence in list(self.sequences): if sequence.jd1 < 0 or sequence.jd2 < 0 or is_nearby_less_or_equal(sequence.duration, 0) or sequence.jd2 - sequence.jd1 < sequence.duration: self.sequences.remove(sequence) sequence.status = Sequence.INVALID if SIMULATION == False: sequence.save() def determine_priorities(self): ''' Computes sequences priority according to the user, the scientific program, ... ''' # TODO: définir comment on calcule la priorité pass def remove_not_eligible_sequences(self): ''' Computes overlap between [jd1; jd2] and [plan_start; plan_end] Removes from self.sequences all the sequences that cannot be observed between plan_start and plan_end Set UNPLANNABLE sequences if jd2 < plan_start :side-effect : - remove unwanted sequences from self.sequences ''' ''' Note (1) ''' for sequence in list(self.sequences): overlap = min(self.schedule.plan_end, sequence.jd2) - max(self.schedule.plan_start, sequence.jd1) if overlap < sequence.duration: if sequence.jd1 < self.schedule.plan_start: """ Note (2) """ sequence.status = Sequence.UNPLANNABLE if SIMULATION == False: sequence.save() self.sequences.remove(sequence) def sort_by_jd2_and_priorities(self): ''' Sort by priority and jd2, priority being the main sorting parameter ''' self.sequences.sort(key=attrgetter('priority', 'jd2')) def organize_sequences(self): ''' Main function of the Scheduler Arrange a maximum of observable sequences in the planning Algorithm (for each sequence) : - check quota (remove sequence from list if quota is too low) - select matching intervals - IF matching intervals => place sequence according to tPrefered - IF NO matching intervals => try to move other sequences to place this one :side-effect : - remove unwanted sequences from self.sequences - change status and dates of sequences in self.sequences (but not in DB yet) ''' ''' Note (1) ''' for sequence in list(self.sequences): quota = self.determine_quota(sequence) if quota < sequence.duration: self.sequences.remove(sequence) continue matching_intervals = self.get_matching_intervals(sequence) if len(matching_intervals) > 0: self.place_sequence(sequence, matching_intervals) sequence_placed = True else: sequence_placed = self.try_shifting_sequences(sequence) if sequence_placed == True: sequence.status = Sequence.PLANNED self.update_quota(sequence) def determine_quota(self, sequence:Sequence) -> float: ''' Determines the quota (in minutes) according to the current planning duration and the quota of the user and scientific program associated :returns : The quota (float) ''' # TODO: définir comment on calcule le quota return sequence.request.pyros_user.quota # default value def get_matching_intervals(self, sequence:Sequence): ''' Find the intervals where the sequence could be inserted :returns : list of matching Intervals ''' matching_intervals = [] for interval in self.intervals: overlap = min(sequence.jd2, interval.end) - max(sequence.jd1, interval.start) if overlap > sequence.duration or is_nearby_equal(overlap, sequence.duration): matching_intervals.append(interval) return matching_intervals def place_sequence(self, sequence:Sequence, matching_intervals) : ''' Place the sequence in the better interval, according to the t_prefered :type matching_intervals: list [Interval] :param matching_intervals: Intervals in which the sequence can be placed :side-effect : - changes self.intervals - change the sequence if it it placed ''' if len(matching_intervals) == 0: raise ValueError("matching_intervals shall not be empty") prefered_interval = self.get_prefered_interval(sequence, matching_intervals) sequence_position_in_interval = self.get_sequence_position_in_interval(sequence, prefered_interval) self.insert_sequence_in_interval(sequence, prefered_interval, sequence_position_in_interval) self.cut_interval(sequence, prefered_interval) self.update_other_deltas(sequence, prefered_interval) def get_prefered_interval(self, sequence:Sequence, matching_intervals) -> Interval: ''' Find the better interval, according to the t_prefered (get the nearest) :type matching_intervals: list [Interval] :param matching_intervals: Intervals in which the sequence can be placed :returns : An Interval that fits sequence.t_prefered at most ''' if len(matching_intervals) == 0: raise ValueError("matching_intervals shall not be empty") if sequence.t_prefered == 0 or len(matching_intervals) == 1: prefered_interval = matching_intervals[0] else: for index, interval in enumerate(matching_intervals): if is_nearby_less_or_equal(interval.start, sequence.t_prefered) and is_nearby_less_or_equal(sequence.t_prefered, interval.end): prefered_interval = interval break elif sequence.t_prefered < interval.start: if index == 0: prefered_interval = interval else: prefered_interval = matching_intervals[index - 1] break return prefered_interval def get_sequence_position_in_interval(self, sequence:Sequence, interval:Interval) -> str: ''' Determines where the sequence will be inserted in the interval, regarding sequence.t_prefered :returns : A string in ["START", "END", "PREFERED"] describing where the sequence will be inserted in the interval ''' if is_nearby_less_or_equal(interval.start, sequence.t_prefered) and is_nearby_less_or_equal(sequence.t_prefered, interval.end): if is_nearby_less_or_equal(sequence.t_prefered - Decimal(0.5) * sequence.duration, interval.start): position_in_interval = "START" elif is_nearby_sup_or_equal(sequence.t_prefered + Decimal(0.5) * sequence.duration, interval.end): position_in_interval = "END" else: position_in_interval = "PREFERED" else: if sequence.t_prefered < interval.start: position_in_interval = "START" else: position_in_interval = "END" return position_in_interval def insert_sequence_in_interval(self, sequence:Sequence, interval:Interval, position:str): ''' Inserts the sequence in the interval: - sets sequence.tsp and sequence.tep - sets sequence.deltaTL and sequence.deltaTR :param interval: Interval in which the sequence will be inserted :param position: String describing where the sequence will be inserted in the interval :side-effect : - modify sequence attributes (tsp, tep, deltaTL, deltaTR) ''' if position not in ["START", "END", "PREFERED"]: raise ValueError("position must be either 'START', 'END' or 'PREFERED'") if position == "START": sequence.tsp = max(interval.start, sequence.jd1) sequence.tep = sequence.tsp + sequence.duration sequence.deltaTL = 0 sequence.deltaTR = min(interval.end, sequence.jd2) - sequence.tep elif position == "END": sequence.tep = min(interval.end, sequence.jd2) sequence.tsp = sequence.tep - sequence.duration sequence.deltaTL = sequence.tsp - max(interval.start, sequence.jd1) sequence.deltaTR = 0 else: sequence.tsp = max(sequence.jd1, sequence.t_prefered - Decimal(0.5) * sequence.duration) sequence.tep = sequence.tsp + sequence.duration sequence.deltaTL = sequence.tsp - max(interval.start, sequence.jd1) sequence.deltaTR = min(interval.end, sequence.jd2) - sequence.tep def cut_interval(self, sequence:Sequence, interval:Interval): ''' Separates the interval in two parts regarding to the sequence position Sorts the interval list in time order :param interval : the interval in which the sequence was added :side-effect : - removes interval from self.intervals - add created intervals to self.intervals - sorts self.intervals ''' interval_before_sequence = Interval(interval.start, sequence.tsp) interval_after_sequence = Interval(sequence.tep, interval.end) self.intervals.remove(interval) if interval_before_sequence.duration > 0: self.intervals.append(interval_before_sequence) if interval_after_sequence.duration > 0: self.intervals.append(interval_after_sequence) self.intervals.sort(key=lambda interval: interval.start, reverse=False) def update_other_deltas(self, sequence:Sequence, interval:Interval): ''' Update deltaTL and deltaTR of sequences planned near this sequence :param interval: Interval in which the sequence was added :side-effect : - modify deltaTL and deltaTR of sequences before and after the interval ''' for sequence_ in self.sequences: if sequence_.status == Sequence.PLANNED: if is_nearby_equal(sequence_.tep, interval.start): sequence_before_interval = sequence_ elif is_nearby_equal(sequence_.tsp, interval.end): sequence_after_interval = sequence_ if 'sequence_before_interval' in locals(): sequence_before_interval.deltaTR = min(sequence.tsp, sequence_before_interval.jd2) - sequence_before_interval.tep if 'sequence_after_interval' in locals(): sequence_after_interval.deltaTL = sequence_after_interval.tsp - max(sequence.tep, sequence_after_interval.jd1) def try_shifting_sequences(self, sequence:Sequence) -> bool: ''' Tries to find a place in the planning for the sequence, moving the other sequences :returns : A boolean -> True if the sequence was placed, False otherwise :side-effect: - might change some sequences' deltaTL and/or deltaTR ''' potential_intervals = self.get_potential_intervals(sequence) potential_intervals.sort(key=attrgetter("duration"), reverse=True) for interval in potential_intervals: ''' we get the adjacent sequences ''' for sequence_ in self.sequences: if sequence_.status == Sequence.PLANNED: if is_nearby_equal(sequence_.tep, interval.start): sequence_before_interval = sequence_ elif is_nearby_equal(sequence_.tsp, interval.end): sequence_after_interval = sequence_ available_duration = min(interval.end, sequence.jd2) - max(interval.start, sequence.jd1) missing_duration = sequence.duration - available_duration if 'sequence_before_interval' in locals(): possible_move_to_left = min(sequence_before_interval.deltaTL, interval.start - sequence.jd1) else: possible_move_to_left = 0 if 'sequence_after_interval' in locals(): possible_move_to_right = min(sequence_after_interval.deltaTR, sequence.jd2 - interval.end) else: possible_move_to_right = 0 if is_nearby_sup_or_equal(possible_move_to_left, missing_duration): self.move_sequence(sequence_before_interval, missing_duration, "LEFT") elif is_nearby_sup_or_equal(possible_move_to_right, missing_duration): self.move_sequence(sequence_after_interval, missing_duration, "RIGHT") elif is_nearby_sup_or_equal(possible_move_to_left + possible_move_to_right, missing_duration): self.move_sequence(sequence_before_interval, possible_move_to_left, "LEFT") self.move_sequence(sequence_after_interval, missing_duration - possible_move_to_left, "RIGHT") else: continue matching_intervals = self.get_matching_intervals(sequence) if len(matching_intervals) != 1: raise ValueError("There should be one and only one matching interval after shifting") self.place_sequence(sequence, matching_intervals) return True return False def get_potential_intervals(self, sequence:Sequence): ''' Find the intervals where a part of the sequence could be inserted :returns : list of partially-matching Intervals ''' potential_intervals = [] for interval in self.intervals: overlap = min(sequence.jd2, interval.end) - max(sequence.jd1, interval.start) if overlap > 0: potential_intervals.append(interval) return potential_intervals def move_sequence(self, sequence:Sequence, time_shift:Decimal, direction:str): ''' Moves the sequence in the wanted direction, decreasing its deltaTL or deltaTR. :param sequence: sequence to be moved :param time_shift: amplitude of the shift :param direction: "LEFT" or "RIGHT" :side-effect : - modify the sequence in self.sequences - changes the interval before and the interval after the sequence ''' if direction not in ["LEFT", "RIGHT"]: raise ValueError("direction must be 'LEFT' or 'RIGHT'") if time_shift > (sequence.deltaTL if direction == "LEFT" else sequence.deltaTR): raise ValueError("Shift value is bigger than deltaT(R/L)") for interval in self.intervals: if is_nearby_equal(interval.end, sequence.tsp): interval_before = interval elif is_nearby_equal(interval.start, sequence.tep): interval_after = interval if direction == "LEFT": interval_before.end -= time_shift if "interval_after" in locals(): interval_after.start -= time_shift sequence.tsp -= time_shift sequence.tep -= time_shift sequence.deltaTL -= time_shift sequence.deltaTR += time_shift else: if "interval_before" in locals(): interval_before.end += time_shift interval_after.start += time_shift sequence.tsp += time_shift sequence.tep += time_shift sequence.deltaTL += time_shift sequence.deltaTR -= time_shift if "interval_before" in locals() and is_nearby_equal(interval_before.duration, 0): self.intervals.remove(interval_before) if "interval_after" in locals() and is_nearby_equal(interval_after.duration, 0): self.intervals.remove(interval_after) def update_quota(self, sequence:Sequence): ''' Update the quota of the user / scientific program / whatever by substracting the sequence duration to the quotas :side-effect: - Modify User quota in DB ''' # TODO: faire les vrais calculs de quota user = sequence.request.pyros_user user.quota -= float(sequence.duration) # action par défaut qui correspond au code de self.determine_quota if SIMULATION == False: user.save() def save_sequences(self): ''' Final function : save in the db all modifications done to sequences, and the schedule :side-effect : - change sequences status and dates in DB - add a schedule in the DB ''' self.schedule.save() for sequence in self.sequences: sequence.schedule = self.schedule sequence.save() def print_schedule(self): ''' ONLY FOR DEBUG Prints the planned sequences ''' sequences = Sequence.objects.filter(status=Sequence.PLANNED).order_by('tsp') print("---- There are %d sequence(s) planned ----" % len(sequences)) for sequence in sequences: print("name: %r\t, start: %d\t, end: %d\t, duration: %d\t, deltaTL: %d\t, deltaTR: %d\t" % (sequence.name, sequence.tsp, sequence.tep, sequence.duration, sequence.deltaTL, sequence.deltaTR)) print("---- There are %d free interval(s) ----" % len(self.intervals)) for interval in self.intervals: print("start: %d\t, end: %d\t" % (interval.start, interval.end)) ''' Notes (1) list(self.sequences) creates a copy in order to modify self.sequences and still iterate on it without unexpected behavior (2) UNPLANNABLE is a definitive status meaning that the sequence will never be able to be scheduled '''