Shulou(Shulou.com)06/01 Report--

This article mainly shows you "how to use matlab simulated annealing algorithm single constraint workshop assembly line scheduling", the content is easy to understand, clear, hope to help you solve doubts, the following let the editor lead you to study and learn "how to use matlab simulated annealing algorithm single constraint workshop assembly line scheduling" this article.

A brief introduction to Job Shop scheduling 1 definition of Job Shop scheduling

Job shop scheduling refers to allocating the sequence of processing workshops according to the reasonable needs of product manufacturing, so as to achieve the purpose of making rational use of product manufacturing resources and improving the economic benefits of enterprises. The job shop scheduling problem can be described mathematically as there are n parts to be processed on m machines. The conditions that the problem needs to meet include that each process of each part is used no more than once per machine, and each part is processed in a certain order.

2 traditional job shop scheduling

Traditional job shop with scheduling example

There are several workpieces, each workpiece has several processes, there are multiple processing machines, but each process can only be processed on one machine. Corresponding to the example in the table above, there are two workpieces, workpiece J1 has three processes, process Q11 can only be processed on M3, and the processing time is 5 hours.

Constraint is that for an artifact, the relative order of processes cannot be changed. O11-> O12-> O13. Each workpiece can only be processed on one machine at a time; there can be only one workpiece on each machine.

The task of scheduling is to arrange the processing order of the process, which is determined, because there is only one machine available for each process, and the processing machine is determined.

The purpose of scheduling is to minimize the total completion time (which can also be other goals). For example, after determining the processing order of O21-> O22-> O11-> O23-> O12-> O13, we can calculate the total processing time according to the constraints of the processing machine.

M2 processing O21 takes 6 hours, and the current processing time of workpiece J2 is 6 hours.

M1 processing O22 takes 9 hours, and the current processing time of workpiece J2 is 6: 9: 15 hours.

M3 processing O11 takes 5 hours, and the current processing time of workpiece J1 is 5 hours.

The processing time of M4 O23 is 7 hours, and the processing time of workpiece J2 is 15-7-22 hours.

M1 processing O12 takes 11 hours, but the processing of O12 does not start until M1 has finished processing O22, so the current processing time of workpiece J1 is max (5mem9) + 1120 hours.

The processing time of M5 O13 is 8 hours, and the processing time of workpiece J2 is 28 hours.

The total completion time is max (22 minutes 28) = 28 hours.

3 flexible job shop scheduling

Flexible Job Shop with scheduling example (refer to teacher's thesis from highlight)

"improved genetic algorithm for flexible Job Shop scheduling problem"-- Journal of Mechanical Engineering)

Compared with traditional job shop scheduling, flexible job shop scheduling relaxes the constraints on processing machines, which is more in line with the actual production situation. Each process has become multiple optional processing machines, which can be processed by one of multiple processing machines. For example, in the example in the table above, the O12 process of J1 can choose M2 and M4 processing, and the processing time is 8 hours and 4 hours respectively, but M4 processing is not necessarily selected, so the total completion time is even shorter. Scheduling algorithm is needed to solve the optimization.

Compared with the traditional job shop, the scheduling task of flexible job shop scheduling needs to determine not only the processing sequence of the process, but also the machine allocation of each process. For example, the processing sequence of O21-> O22-> O11-> O23-> O12-> O13 is determined, so we should also determine the corresponding machine combinations of [M1, M3, M5]-> [M1, M2, M3, M4, M5]-> [M2, M3, M4, M5]-> [M2, M4]-> [M1, M3, M4, M5]. The purpose of scheduling is to have the shortest total completion time (or other goals, such as the shortest maximum machine load and the shortest total machine load).

2. Brief introduction of simulated annealing algorithm

5 parameters of simulated annealing algorithm

Simulated annealing is a kind of optimization algorithm, which can not exist independently, so it needs an application, in which temperature is the parameter to be optimized. If it is applied to cluster analysis, then there are some or several parameters in cluster analysis that need to be optimized, and this parameter, or parameter set, is represented by temperature. It can be an index, a correlation, a distance, and so on.

3. Partial source code clc;clear;close all;%% Problem Definitionmodel=CreateModel ();% CreateModel of the ProblemCostFunction=@ (Q) MyCost (QMagneMod);% Cost FunctionnVar=model.nVar;% Number of Decision VariablesVarSize= [1 nVar];% Size of Decision Variables Matrix%% SA ParametersMaxIt=100;% Maximum Number of IterationsMaxIt2=25;% Maximum Number of Inner IterationsT0=10;% Initial Temperaturealpha=0.97;% Temperature Damping Rate%% Initialization% Create Initial Solutionx.Position=CreateRandomSolution (model) [x.Cost, x.Sol] = CostFunction (x.Position);% Update Best Solution Ever FoundBestSol=x;% Array to Hold BestCost ValuesBestCost=zeros (MaxIt,1);% Set Initial TemperatureT=T0;%% SA Main Loopfor it=1:MaxIt for it2=1:MaxIt2% CreateNeighbor xnew.Position=CreateNeighbor (x.Position); [xnew.Cost, xnew.Sol] = CostFunction (xnew.Position); if xnew.Cost

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.