-
Notifications
You must be signed in to change notification settings - Fork 0
/
introduction.lyx
146 lines (129 loc) · 3.8 KB
/
introduction.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
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
#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
The job shop problem (JSP) is a well-known scheduling problem and is one
of the hardest combinatorial optimization problems
\begin_inset CommandInset citation
LatexCommand cite
key "Vaessens-Aarts-Lenstra-1996"
\end_inset
.
In JSP a number of jobs consist of a number of operations that need to
be performed by specific machines.
A machine can only perform one operation at a time and each operation within
a job must be finished before the next operation can be started.
The essence of the JSP is to find a schedule that will finish all jobs
as quickly as possible.
\end_layout
\begin_layout Standard
Combinatorial optimization problems like JSP are problems with discrete
variables that can be combined and ordered in many ways.
Among all combinations there is an optimal solution.
The definition of optimal depends on the problem at hand.
In case of the JSP it would be finding an ordering of operations that leads
to the earliest finishing time.
\end_layout
\begin_layout Standard
The challenging part of solving problems like JSP is that there is no exact
algorithm to solve each instance of this problem within polynomial time.
Exact algorithms guarantee to find the proven optimal answer using a fixed
number of steps.
For JSP, such an algorithm has not yet been found.
\end_layout
\begin_layout Standard
However, exact algorithms for specific variants of JSP have been found.
A specific variant with ten jobs and ten operations, known as the 10x10
benchmark problem, was proposed by Muth and Thompson in 1963 and remained
unsolved for over twenty years
\begin_inset CommandInset citation
LatexCommand cite
key "Fisher63probabilisticlearning"
\end_inset
.
The first proven optimal solution was developed with exact algorithms by
Carlier in 1987
\begin_inset CommandInset citation
LatexCommand cite
key "carlier-pinson"
\end_inset
.
More difficult instances like the 15x15 JSP are still considered to be
unsolvable within polynomial time using exact algorithms
\begin_inset CommandInset citation
LatexCommand cite
key "Goncalves_ahybrid"
\end_inset
.
\end_layout
\begin_layout Standard
In this paper we will inspect non-exact algorithms to the JSP that do run
within polynomial time.
These algorithms will approximate the optimal solution using so-called
heuristics.
We will specifically cover pure genetic algorithms and genetic hybrid algorithm
s.
\end_layout
\begin_layout Standard
In the first section of this paper we will cover the basics of heuristics,
genetic algorithms and genetic hybrid algorithms.
In the second section these specific types of heuristics will be applied
to JSP.
\end_layout
\end_body
\end_document