-
Notifications
You must be signed in to change notification settings - Fork 0
/
conclusion.lyx
110 lines (103 loc) · 3.35 KB
/
conclusion.lyx
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
#LyX 2.0 created this file. For more info see http://www.lyx.org/
\lyxformat 413
\begin_document
\begin_header
\textclass article
\use_default_options true
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\use_hyperref false
\papersize default
\use_geometry false
\use_amsmath 1
\use_esint 1
\use_mhchem 1
\use_mathdots 1
\cite_engine basic
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header
\begin_body
\begin_layout Standard
Heuristic algorithms are a great way of approximating a computationally
complex problem like the job shop problem (JSP) for which no exact algorithm
exists.
In this paper we have shown an interesting type of heuristics called genetic
algorithms (GAs).
\end_layout
\begin_layout Standard
GAs are an inter-disciplinary combination of modern computer science and
evolutionary principles.
So if Charles Darwin was a computer scientist, he would likely be a great
enthusiast of GAs.
We have shown that pure GAs perform sub-optimal on JSP.
Better results can be obtained by combining pure GAs with other heuristics,
resulting in so called genetic hybrid algorithms.
Such hybrid algorithms, like the shifting bottleneck genetic algorithm
(SB-GA), show impressive results on a typical suite of JSP test cases.
Genetic hybrid algorithms will in many cases produce a schedule that finishes
earlier than a schedule that is produced using another heuristics.
The downside is that these hybrid algorithms require a relatively long
computation time compared to other heuristics.
\end_layout
\begin_layout Standard
We have strongly noticed that there is an important time vs quality trade-off.
An approximation algorithm to JSP will either produce a schedule with an
optimal finishing time and take longer, or will produce a sub-optimal schedule
very quickly.
Depending on the problem at hand, a precise or quick algorithm may be preferabl
e.
If we inspect this paper on this phenomenon, we see that this trade-off
acts on different levels.
In local search this trade-off manifests itself in deciding between the
first- and best improvement.
In genetic hybrid algorithms the trade-off manifests itself as follows:
the GA searches in a wide search space, while local search narrows down
this space and focuses on the optimal solution within its surrounding search
space.
So when choosing between approximation algorithms one must consider if
it is more important to obtain a schedule quickly with a possibly worse
finishing time, or obtain a schedule slowly with a higher probability of
finding a better finishing time.
It all depends on the users priorities.
\end_layout
\end_body
\end_document