A list,
Job Shop Scheduling (JSP) is one of the most classic NP-hard problems. Its application fields are extremely wide, involving aircraft carrier scheduling, airport aircraft scheduling, port and dock cargo ship scheduling, automobile processing assembly line and so on.
A processing system has M machines and requires N jobs to be processed. Among them, job I contains the number of procedures for Li. , then L is the total working number of the task set. Among them, the processing time of each process has been determined, and each operation must be processed in accordance with the sequence of the process. The task of scheduling is to arrange the processing scheduling of all jobs, so that the performance index can be optimized when the constraints are satisfied.
Job shop scheduling needs to consider the following constraints:
Cons1: Each process is processed on the designated machine and can only begin after the completion of its previous process;
Cons2: A machine can process only one job at a time;
Cons3: Each job can only be processed 1 time on 1 machine;
Cons4: The working sequence and processing time of each job are known and will not change with the change of processing sequencing.
Problem instances
The following is an example of the job-shop scheduling problem, where each process is marked with a pair of values (m, P), where M means that the current process must be processed on the MTH machine, and P means the processing time required by the MTH machine to process the current process. (Note: Machine and job numbers start from 0)
Jop0 = [(0, 3), (1, 2), (2)]
Jop1 = [(0, 2), (2, 1), (1, 4)]
Jop2 = [(1, 4), (2, 3)]
In this example, job JOP0 has three processes: its first process is labeled (0,3), which means that the first process must be processed on machine 0 and requires 3 units of processing time; Its second process is marked with (1,2), which means that the second process must be processed on the first machine, and requires 2 units of processing time; Same thing with the rest. In total, there are eight processes in this example.
A feasible solution of the problem is that L= a permutation of 8 process start times, which satisfies the constraints of the problem. Here is an example of a possible solution (note: this solution is not optimal) :
Genetic Algorithm (GA) is a part of evolutionary computing. It is a computational model that simulates Darwin’s Genetic selection and natural selection of biological evolution process. It is a method to search for optimal solution by simulating natural evolution process. The algorithm is simple, universal, robust and suitable for parallel processing.
2 Characteristics and Application of Genetic Algorithm Genetic algorithm is a kind of robust search algorithm which can be used for complex system optimization. Compared with traditional optimization algorithm, it has the following characteristics: (1) The encoding of decision variables is taken as the operation object. Traditional optimization algorithms often directly use the actual value of the decision variable itself to optimize the calculation, but genetic algorithm uses a certain form of the decision variable encoding as the operation object. This method of encoding decision variables makes it possible for us to use the concepts of chromosomes and genes in biology for reference in optimization calculation, to imitate the genetic and evolutionary incentives of organisms in nature, and to easily apply genetic operators. (2) Directly use fitness as search information. The traditional optimization algorithm not only needs to use the value of the objective function, but also needs to satisfy the requirement of “the derivative of the objective function must exist” in order to determine the search direction. Genetic algorithm can only use the fitness function value transformed from the objective function value to determine the further search range, without the derivative value of the objective function and other auxiliary information. The objective function value or individual fitness value can be directly used to concentrate the search scope into the search space with higher fitness, so as to improve the search efficiency. (3) Search information of multiple points is used with implicit parallelism. Traditional optimization algorithms usually start from an initial point in the solution space to search the optimal solution iteratively. The search information provided by a single point is not much, so the search efficiency is not high, and there may be local optimal solution and stagnation. Genetic algorithms start the search process for optimal solutions from an initial population consisting of many individuals rather than from a single individual. The operation of selection, crossover and mutation on the initial population produces a new generation of population, which contains a lot of population information. This information can avoid searching some unnecessary points, so as to avoid falling into the local optimal solution and gradually approach the global optimal solution. (4) Use probabilistic search rather than deterministic rules. Traditional optimization algorithms often use deterministic search methods, the transfer of a search point to another search point has a certain direction and transfer relationship, such deterministic search may not reach the optimal shop, limit the scope of application of the algorithm. Genetic algorithm (GA) is a kind of adaptive search technology. Its selection, crossover, mutation and other operations are carried out in a probabilistic way, which increases the flexibility of the search process, and can converge to the optimal solution with a large probability, and has a good global optimization capability. However, crossover probability, mutation probability and other parameters can also affect the search results and search efficiency of the algorithm, so how to choose the parameters of genetic algorithm is a relatively important problem in its application. To sum up, genetic algorithm provides a general framework for solving complex system problems because the overall search strategy and optimal search mode of genetic algorithm do not depend on gradient information or other auxiliary knowledge in calculation, but only require the solution of objective function that affects the search direction and the corresponding fitness function. It is not dependent on the specific domain of the problem, and has strong robustness to the type of the problem, so it is widely used in a variety of fields, including: function optimization, combinational optimization production scheduling problems, automatic control, robotics, image processing (image recovery, image edge feature extraction…) Artificial life, genetic programming, machine learning.
Simple Genetic Algorithms (SGA) only uses selection operator, crossover operator and mutation operator. It is the basis of other Genetic Algorithms because of its Simple evolution process.
3.1 Basic flow of genetic algorithm
A number of initial populations encoded by a certain length (length is related to the accuracy of the problem to be solved) are generated in a random way.
Each individual was evaluated by fitness function, and the individuals with high fitness were selected to participate in genetic operation, while the individuals with low fitness were eliminated.
The collection of genetically manipulated individuals (replication, crossover, mutation) forms a new generation of population until the stop criterion (evolutionary algebra GEN>=?) is satisfied. ;
The best cashed individual in the offspring is taken as the execution result of the genetic algorithm.
Where GEN is the current algebra; M is population size and I is population size.
3.2 Implementation technology of genetic algorithm
Basic genetic algorithm (SGA) consists of coding, fitness function, genetic operator (selection, crossover, variation) and operation parameters.
3.2.1 coding
(1) Binary coding
The length of the binary-encoded string depends on the precision of the problem being solved. It is necessary to ensure that every individual in the solved space can be coded.
Advantages: coding, decoding simple operation, inheritance, cross easy to achieve
Disadvantages: Large length
(2) Other coding methods
Gray code, floating point coding, symbol coding, multi – parameter coding and so on
3.2.2 Fitness function
The fitness function should effectively reflect the gap between each chromosome and the optimal solution chromosome of the problem.
3.2.3 Selecting the operator
3.2.4 Crossover operator
Crossover operation refers to two mutually paired chromosomes in a way to exchange part of their genes, so as to form two new individuals; Crossover operation is an important feature of genetic algorithm which is different from other evolutionary algorithms and is the main method to generate new individuals. Before crossover, individuals in the group need to be matched, generally adopting the principle of random pairing.
Common crossover methods:
A single point of intersection
Double point crossing (multi-point crossing, the more points of crossing, the more likely the individual’s structure will be damaged, generally, the multi-point crossing is not adopted)
Uniform cross
Arithmetic crossover
3.2.5 Mutation operator
Mutation operation in genetic algorithm refers to the replacement of gene values at some loci in the coding string of individual chromosome with other alleles of that loci, thus forming a new individual.
In terms of the ability to generate new individuals in the process of genetic algorithm, crossover operation is the main method to generate new individuals, which determines the global search ability of genetic algorithm. Mutation operation is only an auxiliary method to generate new individuals, but it is also an essential operation step, which determines the local search ability of genetic algorithm. The combination of crossover operator and mutation operator completes the global search and local search of the search space, so that the genetic algorithm can complete the optimization process with good search performance.
3.2.6 Operating Parameters
4 Basic principles of genetic algorithm
4.1 Pattern Theorem
4.2 Building block hypothesis
Patterns with low order, short definition length, and fitness values higher than the population average are called gene blocks or building blocks.
Building block hypothesis: individual gene blocks can be spliced together to form individual coding strings with higher fitness through selection, crossover, mutation and other genetic operators.
The building block hypothesis illustrates the basic idea of solving all kinds of problems with genetic algorithms, that is, better solutions can be produced by directly joining the building blocks together.
Ii. Source code
function varargout = diaodu(varargin)
% DIAODU MATLAB code for diaodu.fig
% DIAODU, by itself, creates a new DIAODU or raises the existing
% singleton*.
%
% H = DIAODU returns the handle to a new DIAODU or the handle to
% the existing singleton*.
%
% DIAODU('CALLBACK',hObject,eventData,handles,...) calls the local
% function named CALLBACK in DIAODU.M with the given input arguments.
%
% DIAODU('Property'.'Value',...). creates anew DIAODU or raises the
% existing singleton*. Starting from the left, property value pairs are
% applied to the GUI before diaodu_OpeningFcn gets called. An
% unrecognized property name or invalid value makes property application
% stop. All inputs are passed to diaodu_OpeningFcn via varargin.
%
% *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one % instance to run (singleton)".
%
% See also: GUIDE, GUIDATA, GUIHANDLES
% Edit the above text to modify the response to help diaodu
% Last Modified by GUIDE v2. 5 26-May- 2016. 17:18:21
% Begin initialization code - DO NOT EDIT
gui_Singleton = 1;
gui_State = struct('gui_Name', mfilename, ...
'gui_Singleton', gui_Singleton, ...
'gui_OpeningFcn', @diaodu_OpeningFcn, ...
'gui_OutputFcn', @diaodu_OutputFcn, ...
'gui_LayoutFcn', [],...'gui_Callback'[]);if nargin && ischar(varargin{1})
gui_State.gui_Callback = str2func(varargin{1});
end
if nargout
[varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
else
gui_mainfcn(gui_State, varargin{:});
end
% End initialization code - DO NOT EDIT
% --- Executes just before diaodu is made visible.
function diaodu_OpeningFcn(hObject, eventdata, handles, varargin)
% This function has no output args, see OutputFcn.
% hObject handle to figure
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% varargin command line arguments to diaodu (see VARARGIN)
% Choose default command line output for diaodu
handles.output = hObject;
% Update handles structure
guidata(hObject, handles);
% UIWAIT makes diaodu wait for user response (see UIRESUME)
% uiwait(handles.figure1);
% --- Outputs from this function are returned to the command line.
function varargout = diaodu_OutputFcn(hObject, eventdata, handles)
% varargout cell array for returning output args (see VARARGOUT);
% hObject handle to figure
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Get default command line output from handles structure
varargout{1} = handles.output;
function edit1_Callback(hObject, eventdata, handles)
% hObject handle to edit1 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit1 as text
% str2double(get(hObject,'String')) returns contents of edit1 as a double
% --- Executes during object creation, after setting all properties.
function edit1_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit1 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit2_Callback(hObject, eventdata, handles)
% hObject handle to edit9 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit9 as text
% str2double(get(hObject,'String')) returns contents of edit9 as a double
% --- Executes during object creation, after setting all properties.
function edit2_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit9 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit3_Callback(hObject, eventdata, handles)
% hObject handle to edit3 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit3 as text
% str2double(get(hObject,'String')) returns contents of edit3 as a double
% --- Executes during object creation, after setting all properties.
function edit3_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit3 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit4_Callback(hObject, eventdata, handles)
% hObject handle to edit17 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit17 as text
% str2double(get(hObject,'String')) returns contents of edit17 as a double
% --- Executes during object creation, after setting all properties.
function edit4_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit17 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit5_Callback(hObject, eventdata, handles)
% hObject handle to edit2 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit2 as text
% str2double(get(hObject,'String')) returns contents of edit2 as a double
% --- Executes during object creation, after setting all properties.
function edit5_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit2 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit6_Callback(hObject, eventdata, handles)
% hObject handle to edit5 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit5 as text
% str2double(get(hObject,'String')) returns contents of edit5 as a double
% --- Executes during object creation, after setting all properties.
function edit6_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit5 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit7_Callback(hObject, eventdata, handles)
% hObject handle to edit4 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit4 as text
% str2double(get(hObject,'String')) returns contents of edit4 as a double
% --- Executes during object creation, after setting all properties.
function edit7_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit4 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit8_Callback(hObject, eventdata, handles)
% hObject handle to edit7 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit7 as text
% str2double(get(hObject,'String')) returns contents of edit7 as a double
% --- Executes during object creation, after setting all properties.
function edit8_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit7 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit9_Callback(hObject, eventdata, handles)
% hObject handle to edit6 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit6 as text
% str2double(get(hObject,'String')) returns contents of edit6 as a double
% --- Executes during object creation, after setting all properties.
function edit9_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit6 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit10_Callback(hObject, eventdata, handles)
% hObject handle to edit9 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit9 as text
% str2double(get(hObject,'String')) returns contents of edit9 as a double
% --- Executes during object creation, after setting all properties.
function edit10_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit9 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit11_Callback(hObject, eventdata, handles)
% hObject handle to edit5 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit5 as text
% str2double(get(hObject,'String')) returns contents of edit5 as a double
% --- Executes during object creation, after setting all properties.
function edit11_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit5 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit12_Callback(hObject, eventdata, handles)
% hObject handle to edit17 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit17 as text
% str2double(get(hObject,'String')) returns contents of edit17 as a double
% --- Executes during object creation, after setting all properties.
function edit12_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit17 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit13_Callback(hObject, eventdata, handles)
% hObject handle to edit7 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit7 as text
% str2double(get(hObject,'String')) returns contents of edit7 as a double
% --- Executes during object creation, after setting all properties.
function edit13_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit7 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit14_Callback(hObject, eventdata, handles)
% hObject handle to edit17 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit17 as text
% str2double(get(hObject,'String')) returns contents of edit17 as a double
% --- Executes during object creation, after setting all properties.
function edit14_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit17 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit15_Callback(hObject, eventdata, handles)
% hObject handle to edit9 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit9 as text
% str2double(get(hObject,'String')) returns contents of edit9 as a double
% --- Executes during object creation, after setting all properties.
function edit15_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit9 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit16_Callback(hObject, eventdata, handles)
% hObject handle to edit17 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit17 as text
% str2double(get(hObject,'String')) returns contents of edit17 as a double
% --- Executes during object creation, after setting all properties.
function edit16_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit17 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit17_Callback(hObject, eventdata, handles)
% hObject handle to edit8 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit8 as text
% str2double(get(hObject,'String')) returns contents of edit8 as a double
% --- Executes during object creation, after setting all properties.
function edit17_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit8 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit18_Callback(hObject, eventdata, handles)
% hObject handle to edit17 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit17 as text
% str2double(get(hObject,'String')) returns contents of edit17 as a double
% --- Executes during object creation, after setting all properties.
function edit18_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit17 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit19_Callback(hObject, eventdata, handles)
% hObject handle to edit19 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit19 as text
% str2double(get(hObject,'String')) returns contents of edit19 as a double
% --- Executes during object creation, after setting all properties.
function edit19_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit19 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit20_Callback(hObject, eventdata, handles)
% hObject handle to edit20 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit20 as text
% str2double(get(hObject,'String')) returns contents of edit20 as a double
% --- Executes during object creation, after setting all properties.
function edit20_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit20 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit21_Callback(hObject, eventdata, handles)
% hObject handle to edit21 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit21 as text
% str2double(get(hObject,'String')) returns contents of edit21 as a double
% --- Executes during object creation, after setting all properties.
function edit21_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit21 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
% --- Executes on button press in pushbutton1.
function pushbutton1_Callback(hObject, eventdata, handles)
gx11=str2num(get(handles.edit1,'String'));
gx12=str2num(get(handles.edit2,'String'));
gx13=str2num(get(handles.edit3,'String'));
gx21=str2num(get(handles.edit4,'String'));
gx22=str2num(get(handles.edit5,'String'));
gx23=str2num(get(handles.edit6,'String'));
gx31=str2num(get(handles.edit7,'String'));
gx32=str2num(get(handles.edit8,'String'));
gx33=str2num(get(handles.edit9,'String'));
gxt11=str2num(get(handles.edit10,'String'));
gxt12=str2num(get(handles.edit11,'String'));
gxt13=str2num(get(handles.edit12,'String'));
gxt21=str2num(get(handles.edit13,'String'));
gxt22=str2num(get(handles.edit14,'String'));
gxt23=str2num(get(handles.edit15,'String'));
gxt31=str2num(get(handles.edit16,'String'));
gxt32=str2num(get(handles.edit17,'String'));
gxt33=str2num(get(handles.edit18,'String'));
sl1=str2num(get(handles.edit19,'String'));
sl2=str2num(get(handles.edit20,'String'));
sl3=str2num(get(handles.edit21,'String'));
% Instance=[2 10 1 45 0 0
% 2 10 1 45 0 0
% 2 34 1 20 0 10
% 2 34 1 20 0 10
% 2 34 1 20 0 10
% 0 28 1 12 2 10
% 0 28 1 12 2 10
% 0 28 1 12 2 10];
% gx11=str2num(gx11);
% gx12=str2num(gx12);
% gx13=str2num(gx13);
% gx21=str2num(gx21);
% gx22=str2num(gx22);
% gx23=str2num(gx23);
% gx31=str2num(gx31);
% gx32=str2num(gx32);
% gx33=str2num(gx33);
% gxt11=str2num(gxt11);
% gxt12=str2num(gxt12);
% gxt13=str2num(gxt13);
% gxt21=str2num(gxt21);
% gxt22=str2num(gxt22);
% gxt23=str2num(gxt23);
% gxt31=str2num(gxt31);
% gxt32=str2num(gxt32);
% gxt33=str2num(gxt33);
% sl1=str2num(sl1);
% sl2=str2num(sl2);
% sl3=str2num(sl3);
Instance=zeros(sl1+sl2+sl3,6);
% for i=1:sl1
% Instance(i,:)=[3-gx11 gxt13 3-gx12 gxt12 3-gx13 gxt11];
% end
% for i=3:5
% Instance(i,:)=[3-gx21 gxt23 3-gx22 gxt22 3-gx23 gxt21];
% end
% for i=6:9
% Instance(i,:)=[3-gx31 gxt33 3-gx32 gxt32 3-gx33 gxt31];
% end
for i=1:sl1
Instance(i,:)=[3-gx11 gxt13 3-gx12 gxt12 3-gx13 gxt11];
end
for i=sl1+1:sl1+sl2
Instance(i,:)=[3-gx21 gxt23 3-gx22 gxt22 3-gx23 gxt21];
end
for i=sl1+sl2+1:sl1+sl2+sl3
Instance(i,:)=[3-gx31 gxt31 3-gx32 gxt32 3-gx33 gxt33];
end
NumOfPopulation=20; % population=cell(1,NumOfPopulation); MaxGen = % species500; % Maximum number of iterations PCross=0.9; % cross probability PMutation=0.08; % variable probability SchedulingBest=cell(1,MaxGen); % TimeBest=zeros(MaxGen,1); % TimeAvg=zeros(MaxGen,1); % The average time of each generation % to generate the initial populationfor i=1:NumOfPopulation population{i}=InitPopulation(Instance); End % Start population iteration SchedulingBest{1}= population{1};
SchedulingBestSofar=SchedulingBest{1};
for i=1:MaxGen
disp(['The current evolution algebra is' num2str(i)]);
MaxTime=zeros(1,NumOfPopulation); % optimal time for individuals in population % population=Selection(population,Instance); Cross population % = CrossOver (population, PCross, SchedulingBestSofar); % variable population = Mutation (population, PMutation); % Statistics TotalTime=0;
for j=1:NumOfPopulation MaxTime(j)=MaxSpoon(Instance,population{j}); TotalTime=TotalTime+MaxTime(j); end [MinMaxTime,Index]=min(MaxTime); SchedulingBest{i}=population{Index}; % SchedulingBestSofar=SchedulingBest{I}; TimeBest(i)=MinMaxTime; % of each generation of best time TimeAvg (I) = TotalTime/NumOfPopulation; End % Shows the gantt chart [MinTime,Index]=min(TimeBest); MaxMaxTime=max(TimeBest); [MinMaxTime,Pstarts,Pends,PJobName]=MaxSpoon(Instance,SchedulingBest{Index}); starts=Pstarts; ends=Pends; JobName=PJobName; % Maximum completion time isMinMaxTime
disp(['The maximum processing cycle is' num2str(MinMaxTime)]); The following for the graphical display % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % axes (handles. Axes1); [m,n]=size(JobName); axis_size=[0 max(max(ends))+2 0 m];
yla=[1:m];
set(gca,'ytick',yla);
ylabel('the machine'.'FontSize'.12.'color'.'b');
xlabel('Processing Time (min)'.'FontSize'.12.'color'.'b');
title(['Optimal processing time (min) :' num2str(MinMaxTime)],'FontSize'.16.'color'.'r');
ZO=m+1;
for i=1:m
for j=1:n
x=[starts(i,j) ends(i,j)];
y=[ZO-i ZO-i];
line(x,y);
x=[ends(i,j) ends(i,j)];
y=[ZO-i ZO-i0.5];
line(x,y);
x=[starts(i,j) ends(i,j)];
y=[ZO-i0.5 ZO-i0.5];
line(x,y);
st=strcat(int2str(starts(i,j)));
text(x(1),y(1)0.1,st,'FontSize'.8.'color'.'m');
st=strcat(int2str(ends(i,j)));
text(x(2),y(2)0.1,st,'FontSize'.8.'color'.'m');
x=[starts(i,j) starts(i,j)];
y=[ZO-i ZO-i0.5];
line(x,y);
TrueJobName=strcat(int2str(JobName(i,j)));
text((starts(i,j)+ends(i,j))/20.2,ZO-i0.2,TrueJobName); End end % Show the changes of the optimal time and the average time in the iteration process figure(2);
axis_size=[0 MaxGen 0 MaxMaxTime+10];
axis(axis_size);
ylabel('Processing Time'.'FontSize'.12.'color'.'b');
xlabel('Processing Generation'.'FontSize'.12.'color'.'b');
title('The Literator of Best Time and Average Time'.'FontSize'.16.'color'.'r');
Gen=[1:MaxGen];
plot(Gen,TimeBest,'r',Gen,TimeAvg,'b')
h = legend('Optimal time'.'Mean time');
set(h,'Location'.'Best');
function edit22_Callback(hObject, eventdata, handles)
% hObject handle to edit22 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit22 as text
% str2double(get(hObject,'String')) returns contents of edit22 as a double
% --- Executes during object creation, after setting all properties.
function edit22_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit22 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit23_Callback(hObject, eventdata, handles)
% hObject handle to edit20 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit20 as text
% str2double(get(hObject,'String')) returns contents of edit20 as a double
% --- Executes during object creation, after setting all properties.
function edit23_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit20 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
function edit24_Callback(hObject, eventdata, handles)
% hObject handle to edit21 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Hints: get(hObject,'String') returns contents of edit21 as text
% str2double(get(hObject,'String')) returns contents of edit21 as a double
% --- Executes during object creation, after setting all properties.
function edit24_CreateFcn(hObject, eventdata, handles)
% hObject handle to edit21 (see GCBO)
% eventdata reserved - to be defined in a future version of MATLAB
% handles empty - handles not created until after all CreateFcns called
% Hint: edit controls usually have a white background on Windows.
% See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0.'defaultUicontrolBackgroundColor'))
set(hObject,'BackgroundColor'.'white');
end
Copy the code3. Operation results
Fourth, note
Version: 2014 a