TimetablingProblem/heuristic.py at master · lotavares/TimetablingProblem · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
class Heuristic:

    def __init__(self, intervals, busyIntervals, tasks, meals):
        self.intervals = intervals
        self.busyIntervals = busyIntervals
        self.tasks = tasks
        self.meals = meals


    def heuristic(self):
        self.assignMeals()
        self.sortTasks()

        for task in self.tasks.keys():
            currentIntervals = self.intervals
            if (self.tasks[task].daysItMustBeDone != []):
                currentIntervals = self.tasks[task].daysItMustBeDone

            while self.tasks[task].workload < self.tasks[task].totalWorkload:
                for day in currentIntervals:
                    consecutiveIntervals = 0
                    itHasConsecutiveMinimumWorkload = False
                    intervals = []

                    for interval in self.intervals[day].keys():
                        if (self.intervals[day][interval] == 0):
                            consecutiveIntervals += 1
                            intervals.append(interval)
                        elif ((consecutiveIntervals > 0) and ((str(self.intervals[day][interval]).split('_')[0] == 'Refeição'))):
                            if ((str(self.intervals[day][self.meals[self.intervals[day][interval]].possibleIntervals[-1]]).split('_')[0] != 'Refeição') and self.moveIntervalsForward(day, interval, self.intervals[day][interval])):
                                consecutiveIntervals += 1
                                intervals.append(interval)
                        else:
                            consecutiveIntervals = 0
                            intervals = []

                        if (consecutiveIntervals == self.tasks[task].consecutiveMinimumWorkload):
                            itHasConsecutiveMinimumWorkload = True
                            break

                    if (self.tasks[task].itMustBeDoneBeforeBusyInterval):
                        if ((self.tasks[task].busyIntervalThatTheTaskMustBeDoneBefore[0] == day) and (self.tasks[task].busyIntervalThatTheTaskMustBeDoneBefore[1] == interval)):
                            break

                    if itHasConsecutiveMinimumWorkload:
                        for interval in intervals:
                            self.intervals[day][interval] = task

                        self.tasks[task].workload += consecutiveIntervals

                    if (self.tasks[task].workload == self.tasks[task].totalWorkload):
                        break

                    if (self.tasks[task].itMustBeDoneBeforeBusyInterval and (self.tasks[task].busyIntervalThatTheTaskMustBeDoneBefore[0] == day)):
                        break


    def assignMeals(self):
        for day in self.intervals.keys():
            for meal in self.meals.keys():
                possibleIntervalPos = 0
                consecutiveIntervals = 0
                while consecutiveIntervals < self.meals[meal].duration:
                    if (self.intervals[day][self.meals[meal].possibleIntervals[possibleIntervalPos]] == 0):
                        consecutiveIntervals += 1
                    else:
                        consecutiveIntervals = 0

                    possibleIntervalPos += 1

                possibleIntervalPos -= 1
                while consecutiveIntervals > 0:
                    self.intervals[day][self.meals[meal].possibleIntervals[possibleIntervalPos]] = meal

                    consecutiveIntervals -= 1
                    possibleIntervalPos -= 1


    def moveIntervalsForward(self, day, interval, meal):
        newIntervals = []
        for i in range(len(self.meals[meal].possibleIntervals)):
            if (str(self.intervals[day][self.meals[meal].possibleIntervals[i]]) == meal):
                newIntervals.append(i + 1)
        try:
            self.intervals[day][self.meals[meal].possibleIntervals[newIntervals[-1]]] = meal
            self.intervals[day][self.meals[meal].possibleIntervals[newIntervals[0] - 1]] = 0
        except IndexError:
            return False


    def sortTasks(self):
        tasks = {}
        for task in self.tasks.keys():
            tasks[(len(self.tasks[task].daysItMustBeDone), task)] = None

        sortedTasks = {}
        while len(tasks) > 0:
            numberMaxTask = [max(tasks)[0], max(tasks)[1]]
            sortedTasks[numberMaxTask[1]] = self.tasks[numberMaxTask[1]]
            del tasks[(numberMaxTask[0], numberMaxTask[1])]

        self.tasks = sortedTasks

    def isNumber(self, n):
        try:
            int(n)
            return True
        except ValueError:
            return False


    def objectiveFunction(self):
        value = 0
        for day in self.intervals.keys():
            for interval in self.intervals[day].keys():
                if (not self.isNumber(self.intervals[day][interval])):
                    value += 1

        return value