-
Notifications
You must be signed in to change notification settings - Fork 0
/
JSS-GA.drawio
219 lines (219 loc) · 29.4 KB
/
JSS-GA.drawio
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
<mxfile host="app.diagrams.net" modified="2022-08-31T09:51:26.023Z" agent="5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/104.0.5112.102 Safari/537.36 Edg/104.0.1293.70" etag="vWft_d-PNGQ8n4PjOkkv" version="20.2.7" type="github">
<diagram name="Page-1" id="b5b7bab2-c9e2-2cf4-8b2a-24fd1a2a6d21">
<mxGraphModel dx="1085" dy="610" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="3300" pageHeight="4681" background="none" math="0" shadow="0">
<root>
<mxCell id="0" />
<mxCell id="1" parent="0" />
<mxCell id="xL0LI_DuVyFmDKx2Fw36-1" value="Machine
" style="swimlane;fontStyle=1;align=center;verticalAlign=top;childLayout=stackLayout;horizontal=1;startSize=26;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" parent="1" vertex="1">
<mxGeometry x="720" y="1230" width="480" height="210" as="geometry" />
</mxCell>
<mxCell id="xL0LI_DuVyFmDKx2Fw36-2" value="int machine_id_
 int machine_free_time_
 free_slots free_slots_ (free_slots is a boost class)
Free_slot_tree free_slot_tree_;" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="xL0LI_DuVyFmDKx2Fw36-1" vertex="1">
<mxGeometry y="26" width="480" height="74" as="geometry" />
</mxCell>
<mxCell id="xL0LI_DuVyFmDKx2Fw36-3" value="" style="line;strokeWidth=1;fillColor=none;align=left;verticalAlign=middle;spacingTop=-1;spacingLeft=3;spacingRight=3;rotatable=0;labelPosition=right;points=[];portConstraint=eastwest;" parent="xL0LI_DuVyFmDKx2Fw36-1" vertex="1">
<mxGeometry y="100" width="480" height="8" as="geometry" />
</mxCell>
<mxCell id="xL0LI_DuVyFmDKx2Fw36-4" value="Machine(int machine_id, int machine_free_time)
 void OccupyTimeSlot(int start_time, int end_time)
 void ScheduleOperation(Operation& operation, int start_time, int end_time)
 void ScheduleOperationNonMappable(Operation& operation, int start_time, int end_time)
 int GetSuitableTimeSlot(int operation_idx, int prev_op_end_time, int operation_duration)
 static Machine& GetMachineByID(int machine_id, std::map<int, Machine>& machines)" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="xL0LI_DuVyFmDKx2Fw36-1" vertex="1">
<mxGeometry y="108" width="480" height="102" as="geometry" />
</mxCell>
<mxCell id="xL0LI_DuVyFmDKx2Fw36-5" value="Operation" style="swimlane;fontStyle=1;align=center;verticalAlign=top;childLayout=stackLayout;horizontal=1;startSize=26;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" parent="1" vertex="1">
<mxGeometry x="1240" y="890" width="440" height="220" as="geometry" />
</mxCell>
<mxCell id="xL0LI_DuVyFmDKx2Fw36-6" value="const int sequence_;
 const int duration_;
 const Process& process_;
 int start_time_{-1};
 int end_time_{-1};
 int allotted_machine_id_{-1};
 int operation_id_{ -1 };" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="xL0LI_DuVyFmDKx2Fw36-5" vertex="1">
<mxGeometry y="26" width="440" height="114" as="geometry" />
</mxCell>
<mxCell id="xL0LI_DuVyFmDKx2Fw36-7" value="" style="line;strokeWidth=1;fillColor=none;align=left;verticalAlign=middle;spacingTop=-1;spacingLeft=3;spacingRight=3;rotatable=0;labelPosition=right;points=[];portConstraint=eastwest;" parent="xL0LI_DuVyFmDKx2Fw36-5" vertex="1">
<mxGeometry y="140" width="440" height="8" as="geometry" />
</mxCell>
<mxCell id="xL0LI_DuVyFmDKx2Fw36-8" value="Operation(int process_id, int sequence, int duration, const Process& process);
 void SetStartTime(int start_time);
 void SetEndTime(int end_time);
 void SetAllottedMachine(int machine_id_);" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="xL0LI_DuVyFmDKx2Fw36-5" vertex="1">
<mxGeometry y="148" width="440" height="72" as="geometry" />
</mxCell>
<mxCell id="xL0LI_DuVyFmDKx2Fw36-10" value="Bucket" style="swimlane;fontStyle=1;align=center;verticalAlign=top;childLayout=stackLayout;horizontal=1;startSize=26;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" parent="1" vertex="1">
<mxGeometry x="630" y="890" width="180" height="130" as="geometry" />
</mxCell>
<mxCell id="xL0LI_DuVyFmDKx2Fw36-11" value="int bucket_id_{-1};
 map<int, Job> jobs_;" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="xL0LI_DuVyFmDKx2Fw36-10" vertex="1">
<mxGeometry y="26" width="180" height="44" as="geometry" />
</mxCell>
<mxCell id="xL0LI_DuVyFmDKx2Fw36-12" value="" style="line;strokeWidth=1;fillColor=none;align=left;verticalAlign=middle;spacingTop=-1;spacingLeft=3;spacingRight=3;rotatable=0;labelPosition=right;points=[];portConstraint=eastwest;" parent="xL0LI_DuVyFmDKx2Fw36-10" vertex="1">
<mxGeometry y="70" width="180" height="8" as="geometry" />
</mxCell>
<mxCell id="xL0LI_DuVyFmDKx2Fw36-13" value="Bucket() = default
 explicit Bucket(int bucket_id)
 void AddJob(Job& job)" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="xL0LI_DuVyFmDKx2Fw36-10" vertex="1">
<mxGeometry y="78" width="180" height="52" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-1" value="Using" style="swimlane;fontStyle=0;childLayout=stackLayout;horizontal=1;startSize=26;fillColor=none;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" parent="1" vertex="1">
<mxGeometry x="860" y="80" width="340" height="220" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-2" value="Random = effolkronium::random_static;
chromosome_t = std::vector<int>;
population_t = std::vector<pair<chromosome_t, int>>;
jobs_t = std::map<int, Job>;
machines_t = std::map<int, Machine>;
time_slot = interval<int>::type;
free_slots = interval_set<int>;
json = nlohmann::json;
processes_t = std::map<int, Process>;
buckets_t = std::vector<Bucket>;
processes = std::map<int, Process>;
machines = std::vector<int>;" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-1" vertex="1">
<mxGeometry y="26" width="340" height="194" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-6" value="Process" style="swimlane;fontStyle=1;align=center;verticalAlign=top;childLayout=stackLayout;horizontal=1;startSize=26;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" parent="1" vertex="1">
<mxGeometry x="1280" y="1230" width="400" height="190" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-7" value="using processes = std::map<int, Process>;
 using machines = std::vector<int>;
int process_id_;
 bool mappable_;
 std::vector<int> associated_machines_;" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-6" vertex="1">
<mxGeometry y="26" width="400" height="84" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-8" value="" style="line;strokeWidth=1;fillColor=none;align=left;verticalAlign=middle;spacingTop=-1;spacingLeft=3;spacingRight=3;rotatable=0;labelPosition=right;points=[];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-6" vertex="1">
<mxGeometry y="110" width="400" height="8" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-9" value="Process(int process_id, bool mappable);
 static Process& GetProcessByID(int process_id, processes &processes);
 void AssociateMachineWithProcess(Machine& machine);
 const machines& GetAssociatedMachines() const;" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-6" vertex="1">
<mxGeometry y="118" width="400" height="72" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-14" value="Job" style="swimlane;fontStyle=1;align=center;verticalAlign=top;childLayout=stackLayout;horizontal=1;startSize=26;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" parent="1" vertex="1">
<mxGeometry x="910" y="890" width="270" height="130" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-15" value="int job_id_;
 std::vector<Operation> operations_;" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-14" vertex="1">
<mxGeometry y="26" width="270" height="34" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-16" value="" style="line;strokeWidth=1;fillColor=none;align=left;verticalAlign=middle;spacingTop=-1;spacingLeft=3;spacingRight=3;rotatable=0;labelPosition=right;points=[];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-14" vertex="1">
<mxGeometry y="60" width="270" height="8" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-17" value="Job() = default;
 explicit Job(int job_id);

 void AddOperation(const Operation& operation);" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-14" vertex="1">
<mxGeometry y="68" width="270" height="62" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-18" value="Application" style="swimlane;fontStyle=1;align=center;verticalAlign=top;childLayout=stackLayout;horizontal=1;startSize=26;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" parent="1" vertex="1">
<mxGeometry x="550" y="400" width="300" height="160" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-19" value="machines_t machines_;
 processes_t processes_;
 buckets_t buckets_;
 json json_input_data_;" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-18" vertex="1">
<mxGeometry y="26" width="300" height="64" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-20" value="" style="line;strokeWidth=1;fillColor=none;align=left;verticalAlign=middle;spacingTop=-1;spacingLeft=3;spacingRight=3;rotatable=0;labelPosition=right;points=[];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-18" vertex="1">
<mxGeometry y="90" width="300" height="8" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-21" value="void LoadData();
void Run();
void ParseCommandLineArgs(int argc, char* argv[]);" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-18" vertex="1">
<mxGeometry y="98" width="300" height="62" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-22" value="Config" style="swimlane;fontStyle=1;align=center;verticalAlign=top;childLayout=stackLayout;horizontal=1;startSize=26;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" parent="1" vertex="1">
<mxGeometry x="540" y="90" width="290" height="240" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-23" value="static Config* config_instance_;
 int number_of_gens_;
 int pop_size_;
 std::string input_file_path;

 Config() : number_of_gens_(10000), pop_size_(0) {}" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-22" vertex="1">
<mxGeometry y="26" width="290" height="94" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-24" value="" style="line;strokeWidth=1;fillColor=none;align=left;verticalAlign=middle;spacingTop=-1;spacingLeft=3;spacingRight=3;rotatable=0;labelPosition=right;points=[];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-22" vertex="1">
<mxGeometry y="120" width="290" height="8" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-25" value="static Config* GetInstance();
 void SetNumberOfGens(int number_of_gens);
 void SetPopSize(int pop_size);
 int GetNumberOfGens() const;
 int GetPopSize() const;
 void SetInputFilePath(std::string path);
 std::string GetInputFilePath();" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-22" vertex="1">
<mxGeometry y="128" width="290" height="112" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-26" value="file_processor" style="swimlane;fontStyle=0;childLayout=stackLayout;horizontal=1;startSize=26;fillColor=none;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" parent="1" vertex="1">
<mxGeometry x="890" y="390" width="410" height="180" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-27" value="class Bucket;
using json = nlohmann::json;

json LoadInputFile(const std::string& input_file_path);

string convertMakeSpanToISODateTime(int makespan);

void CreateBryntumInputFile(Bucket& buckets, machines_t& machines);

void CreateJSSOutputFile(buckets_t& buckets, machines_t& machines);" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-26" vertex="1">
<mxGeometry y="26" width="410" height="154" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-30" value="Namespace
Genetic" style="swimlane;fontStyle=1;align=center;verticalAlign=top;childLayout=stackLayout;horizontal=1;startSize=40;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" parent="1" vertex="1">
<mxGeometry x="1380" y="400" width="570" height="424" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-31" value="const double kCrossoverRate = 1;
 const double kMutationRate = 1;

 struct OrderedOperation {
 int job_id;
 int operation_index;
 OrderedOperation(int job, int operation) : job_id(job), operation_index(operation) {}
 };" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-30" vertex="1">
<mxGeometry y="40" width="570" height="120" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-32" value="" style="line;strokeWidth=1;fillColor=none;align=left;verticalAlign=middle;spacingTop=-1;spacingLeft=3;spacingRight=3;rotatable=0;labelPosition=right;points=[];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-30" vertex="1">
<mxGeometry y="160" width="570" height="24" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-33" value="bool CheckProbability(double rate);

 chromosome_t GenerateChromosome(const jobs_t& jobs);
population_t GeneratePopulation(jobs_t& jobs);
 chromosome_t Mutate(chromosome_t chromosome);
 chromosome_t Crossover(chromosome_t parent_1, chromosome_t parent_2);
 int ComputeMakespan(chromosome_t& chromosome, jobs_t jobs, machines_t machines);
 void ComputeFitnessOfPopulation(population_t& population, jobs_t& jobs, machines_t& machines);
chromosome_t& TournamentSelection(population_t& population);
 void CrossoverPopulation(population_t& parent_population, population_t& child_population);
 void MutatePopulation(population_t& population);
 void RunGeneticAlgorithm(jobs_t& jobs, machines_t& machines, int number_of_gens);
 void RunGeneticAlgorithmTest(jobs_t& jobs, machines_t& machines, int number_of_gens);
 pair<chromosome_t, int> RunGA(jobs_t& jobs, machines_t& machines, int number_of_gens);
 void MapChromosomeToMachines(chromosome_t& chromosome, jobs_t& jobs, machines_t& machines);
 void ScheduleBucket(Bucket& bucket, machines_t& machines);" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-30" vertex="1">
<mxGeometry y="184" width="570" height="240" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-34" value="Namespace
Parser" style="swimlane;fontStyle=1;align=center;verticalAlign=top;childLayout=stackLayout;horizontal=1;startSize=40;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" parent="1" vertex="1">
<mxGeometry x="1250" y="98" width="640" height="184" as="geometry" />
</mxCell>
<mxCell id="8Wn9Af_72iYiqqPnA7Zo-37" value="void ParseConfig(const json& json_input_data);

 void ParseMachines(const json& json_input_data, machines_t& machines);

 void ParseProcesses(const json& json_input_data, processes_t& processes, machines_t& machines);

 void ParseBuckets(const json& json_input_data, buckets_t& buckets, processes_t& processes);

 void ParseData(const json& json_input_data, processes_t& processes, machines_t& machines, buckets_t& buckets);" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" parent="8Wn9Af_72iYiqqPnA7Zo-34" vertex="1">
<mxGeometry y="40" width="640" height="144" as="geometry" />
</mxCell>
<mxCell id="oIzOhugc7nF5OuY4yiPl-9" value="" style="endArrow=none;html=1;rounded=0;entryX=1;entryY=0;entryDx=0;entryDy=0;exitX=0;exitY=0;exitDx=0;exitDy=0;" parent="1" source="xL0LI_DuVyFmDKx2Fw36-5" target="8Wn9Af_72iYiqqPnA7Zo-14" edge="1">
<mxGeometry relative="1" as="geometry">
<mxPoint x="1170" y="1000" as="sourcePoint" />
<mxPoint x="1330" y="1000" as="targetPoint" />
</mxGeometry>
</mxCell>
<mxCell id="oIzOhugc7nF5OuY4yiPl-10" value="M" style="resizable=0;html=1;align=left;verticalAlign=bottom;" parent="oIzOhugc7nF5OuY4yiPl-9" connectable="0" vertex="1">
<mxGeometry x="-1" relative="1" as="geometry" />
</mxCell>
<mxCell id="oIzOhugc7nF5OuY4yiPl-11" value="N" style="resizable=0;html=1;align=right;verticalAlign=bottom;" parent="oIzOhugc7nF5OuY4yiPl-9" connectable="0" vertex="1">
<mxGeometry x="1" relative="1" as="geometry" />
</mxCell>
<mxCell id="oIzOhugc7nF5OuY4yiPl-12" value="" style="endArrow=none;html=1;rounded=0;exitX=0;exitY=0;exitDx=0;exitDy=0;entryX=1;entryY=0;entryDx=0;entryDy=0;" parent="1" source="8Wn9Af_72iYiqqPnA7Zo-14" target="xL0LI_DuVyFmDKx2Fw36-10" edge="1">
<mxGeometry relative="1" as="geometry">
<mxPoint x="1170" y="1000" as="sourcePoint" />
<mxPoint x="1330" y="1000" as="targetPoint" />
</mxGeometry>
</mxCell>
<mxCell id="oIzOhugc7nF5OuY4yiPl-13" value="M" style="resizable=0;html=1;align=left;verticalAlign=bottom;" parent="oIzOhugc7nF5OuY4yiPl-12" connectable="0" vertex="1">
<mxGeometry x="-1" relative="1" as="geometry" />
</mxCell>
<mxCell id="oIzOhugc7nF5OuY4yiPl-14" value="N" style="resizable=0;html=1;align=right;verticalAlign=bottom;" parent="oIzOhugc7nF5OuY4yiPl-12" connectable="0" vertex="1">
<mxGeometry x="1" relative="1" as="geometry" />
</mxCell>
<mxCell id="oIzOhugc7nF5OuY4yiPl-15" value="" style="endArrow=none;html=1;rounded=0;exitX=1;exitY=0.861;exitDx=0;exitDy=0;exitPerimeter=0;entryX=1;entryY=0;entryDx=0;entryDy=0;" parent="1" source="xL0LI_DuVyFmDKx2Fw36-8" target="8Wn9Af_72iYiqqPnA7Zo-6" edge="1">
<mxGeometry relative="1" as="geometry">
<mxPoint x="1170" y="1230" as="sourcePoint" />
<mxPoint x="1330" y="1230" as="targetPoint" />
</mxGeometry>
</mxCell>
<mxCell id="oIzOhugc7nF5OuY4yiPl-16" value="1" style="resizable=0;html=1;align=right;verticalAlign=bottom;" parent="oIzOhugc7nF5OuY4yiPl-15" connectable="0" vertex="1">
<mxGeometry x="1" relative="1" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-5" value="Node" style="swimlane;fontStyle=0;childLayout=stackLayout;horizontal=1;startSize=26;fillColor=none;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" vertex="1" parent="1">
<mxGeometry x="320" y="1480" width="300" height="170" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-6" value="Node* left{ nullptr }, * right{ nullptr }, * parent{ nullptr };" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" vertex="1" parent="Y9fXGXn2w2aKXmO8mvR8-5">
<mxGeometry y="26" width="300" height="26" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-7" value=" pair<int, int> time;
" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" vertex="1" parent="Y9fXGXn2w2aKXmO8mvR8-5">
<mxGeometry y="52" width="300" height="26" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-8" value="int free_slot_left{ 0 }, free_slot_right{ 0 };

bool free_slot_avalible{ false };

 int balance_factor{NULL};" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" vertex="1" parent="Y9fXGXn2w2aKXmO8mvR8-5">
<mxGeometry y="78" width="300" height="92" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-9" value="Free_slot_tree" style="swimlane;fontStyle=1;align=center;verticalAlign=top;childLayout=stackLayout;horizontal=1;startSize=26;horizontalStack=0;resizeParent=1;resizeParentMax=0;resizeLast=0;collapsible=1;marginBottom=0;" vertex="1" parent="1">
<mxGeometry x="720" y="1480" width="460" height="760" as="geometry">
<mxRectangle x="720" y="1480" width="120" height="30" as="alternateBounds" />
</mxGeometry>
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-10" value="NodePtr root{nullptr};" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" vertex="1" parent="Y9fXGXn2w2aKXmO8mvR8-9">
<mxGeometry y="26" width="460" height="26" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-11" value="" style="line;strokeWidth=1;fillColor=none;align=left;verticalAlign=middle;spacingTop=-1;spacingLeft=3;spacingRight=3;rotatable=0;labelPosition=right;points=[];portConstraint=eastwest;" vertex="1" parent="Y9fXGXn2w2aKXmO8mvR8-9">
<mxGeometry y="52" width="460" height="8" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-12" value="void initializeNode(NodePtr node, pair<int, int> key);

 void preOrderHelper(NodePtr node);

 void inOrderHelper(NodePtr node);

 void postOrderHelper(NodePtr node);

 NodePtr searchTreeHelper(NodePtr node, pair<int, int> key);

 NodePtr deleteNodeHelper(NodePtr node, pair<int, int> key);

void updateBalance(NodePtr node);

void rebalance(NodePtr node);

 void printHelper(NodePtr root, string indent, bool last);

Free_slot_tree();

void preorder();

void inorder();

 void postorder();

NodePtr searchTree(pair<int, int> k);

NodePtr minimum(NodePtr node);

NodePtr maximum(NodePtr node);

NodePtr successor(NodePtr node);

NodePtr predecessor(NodePtr node);

void leftRotate(NodePtr x);

void rightRotate(NodePtr x);

void insert(pair<int, int> key);

 NodePtr getRoot();

NodePtr deleteNode(pair<int, int> time);

void prettyPrint();
 
 int searchBestStartTime(int operation_idx, int prev_op_end_time, int operation_duration);" style="text;strokeColor=none;fillColor=none;align=left;verticalAlign=top;spacingLeft=4;spacingRight=4;overflow=hidden;rotatable=0;points=[[0,0.5],[1,0.5]];portConstraint=eastwest;" vertex="1" parent="Y9fXGXn2w2aKXmO8mvR8-9">
<mxGeometry y="60" width="460" height="700" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-13" value="" style="endArrow=none;html=1;rounded=0;entryX=0;entryY=0;entryDx=0;entryDy=0;exitX=1;exitY=0;exitDx=0;exitDy=0;" edge="1" parent="1" source="Y9fXGXn2w2aKXmO8mvR8-5" target="Y9fXGXn2w2aKXmO8mvR8-9">
<mxGeometry relative="1" as="geometry">
<mxPoint x="1870" y="1010" as="sourcePoint" />
<mxPoint x="2030" y="1010" as="targetPoint" />
</mxGeometry>
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-14" value="M" style="resizable=0;html=1;align=left;verticalAlign=bottom;" connectable="0" vertex="1" parent="Y9fXGXn2w2aKXmO8mvR8-13">
<mxGeometry x="-1" relative="1" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-15" value="N" style="resizable=0;html=1;align=right;verticalAlign=bottom;" connectable="0" vertex="1" parent="Y9fXGXn2w2aKXmO8mvR8-13">
<mxGeometry x="1" relative="1" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-17" value="" style="endArrow=none;html=1;rounded=0;entryX=1;entryY=0;entryDx=0;entryDy=0;exitX=1.003;exitY=1.007;exitDx=0;exitDy=0;exitPerimeter=0;" edge="1" parent="1">
<mxGeometry relative="1" as="geometry">
<mxPoint x="1199.44" y="1440.714" as="sourcePoint" />
<mxPoint x="1178.0000000000002" y="1480.0000000000005" as="targetPoint" />
</mxGeometry>
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-18" value="M" style="resizable=0;html=1;align=left;verticalAlign=bottom;" connectable="0" vertex="1" parent="Y9fXGXn2w2aKXmO8mvR8-17">
<mxGeometry x="-1" relative="1" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-19" value="N" style="resizable=0;html=1;align=right;verticalAlign=bottom;" connectable="0" vertex="1" parent="Y9fXGXn2w2aKXmO8mvR8-17">
<mxGeometry x="1" relative="1" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-21" value="" style="endArrow=none;html=1;rounded=0;entryX=0;entryY=0;entryDx=0;entryDy=0;exitX=1;exitY=0;exitDx=0;exitDy=0;" edge="1" parent="1" source="xL0LI_DuVyFmDKx2Fw36-1" target="8Wn9Af_72iYiqqPnA7Zo-6">
<mxGeometry relative="1" as="geometry">
<mxPoint x="1209.44" y="1450.714" as="sourcePoint" />
<mxPoint x="1188" y="1490.0000000000005" as="targetPoint" />
</mxGeometry>
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-22" value="M" style="resizable=0;html=1;align=left;verticalAlign=bottom;" connectable="0" vertex="1" parent="Y9fXGXn2w2aKXmO8mvR8-21">
<mxGeometry x="-1" relative="1" as="geometry" />
</mxCell>
<mxCell id="Y9fXGXn2w2aKXmO8mvR8-23" value="N" style="resizable=0;html=1;align=right;verticalAlign=bottom;" connectable="0" vertex="1" parent="Y9fXGXn2w2aKXmO8mvR8-21">
<mxGeometry x="1" relative="1" as="geometry" />
</mxCell>
</root>
</mxGraphModel>
</diagram>
</mxfile>