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

This article mainly introduces how to use the matlab bird swarm algorithm to solve the job shop scheduling problem, which has a certain reference value. Interested friends can refer to it. I hope you will gain a lot after reading 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).

Introduction of Butterfly Optimization algorithm (MBO) 1

Butterfly optimization algorithm (butterfly optimization algorithm, BOA) is a meta-heuristic intelligent algorithm proposed by Arora et al in 2019. The algorithm is inspired by butterflies' foraging and mating behavior. Butterflies receive / perceive and analyze odors in the air to determine the potential direction of food sources / mating partners.

Butterflies use their senses of smell, sight, taste, touch and hearing to find food and mates, which also help them migrate from one place to another, escape predators and lay eggs in the right places. Of all the senses, smell is the most important, helping butterflies find food (usually nectar). The butterfly's olfactory receptors are scattered in the butterfly's body parts, such as antennae, legs, tentacles and so on. These receptors are actually nerve cells on the surface of butterflies, called chemosensors. It guides butterflies to find the best mate to inherit powerful genes. Male butterflies can identify female butterflies by pheromones, which are odor secretions emitted by female butterflies that cause specific reactions.

Through observation, it is found that butterflies have a very accurate judgment on the location of these sources. In addition, they can identify different fragrances and sense their intensity. Butterflies produce a certain intensity of fragrance related to their fitness, that is, when the butterfly moves from one position to another, its fitness changes accordingly. When the butterfly senses that another butterfly is emitting more fragrance in this area, it approaches. This stage is called global search. In another case, when a butterfly cannot perceive a fragrance larger than its own, it moves randomly, a stage called local search.

2 fragrance

In order to understand how fragrance in BOA is calculated, we first need to understand how modes such as smell, sound, light, temperature, and so on are calculated. To perceive and deal with these modes, we need to know three important terms: sensory mode C, stimulus intensity I and power index a. In sensory mode, feeling means measuring the form of energy and processing it in a similar manner, while mode refers to the original input used by the sensor. Different forms can be smell, sound, light, temperature, in BOA, the mode is fragrance. I is the size of the physical stimulus. In BOA, I is related to the fitness of butterflies / solutions. This means that when a butterfly emits more fragrance, other butterflies around it can feel and be attracted. The power is the index of the increase in strength. Parameter an allows regular expressions, linear responses, and response compression. The response expansion is that when I increases, fragrance (f) grows faster than I. Response compression is that when I increases, f grows more slowly than I. The linear response is that when I increases, f increases proportionally. It has been proved by experiments that sometimes with the enhancement of stimulation, the sensitivity of insects to stimulus changes becomes lower and lower. So in BOA, to estimate the size of I, response compression is used.

The natural phenomenon of butterflies is based on two important problems: the change of I and the representation of f. To put it simply, the I of the butterfly is associated with the encoded objective function. However, f is relative, that is, it should be perceived by other butterflies. In Stevens' power law, in order to distinguish smell from other forms, C is used. Now, when butterflies with less I move to butterflies with more I, f increases faster than I. Therefore, we should allow f to vary with the degree of absorption realized by the power parameter a. In BOA, fragrance is expressed as a function of the physical strength of the stimulus, as follows:

3 specific algorithm

In order to demonstrate the above discussion with a search algorithm, the above characteristics of butterflies are idealized as follows:

(1) all butterflies can smell, which attracts butterflies to each other.

(2) each butterfly moves randomly or toward the best butterfly, giving off more fragrance.

(3) the stimulation intensity of butterflies is affected or determined by the landscape of the objective function.

The algorithm is divided into three stages: (1) initialization phase, (2) iteration phase and (3) end phase.

In each run of BOA, the initialization phase is performed first, then the iterative search is carried out, and finally the algorithm is terminated when the optimal solution is found. The parameter values used in BOA are also assigned, and after setting these values, the algorithm continues to create the initial butterfly population for optimization. Since the total number of butterflies remains constant during the simulation of BOA, a fixed size of memory is allocated to store information. The position of butterflies is randomly generated in the search space, and their fragrance and fitness values are calculated and stored. This completes the initialization phase, and the algorithm begins the iterative phase, which uses the created artificial butterfly to perform the search. The second stage of the algorithm, that is, the iterative phase, is performed by the algorithm for many iterations. In each iteration, all butterflies in the solution space are moved to a new location, and then their adaptability values are re-evaluated. Firstly, the fitness values of all butterflies in different positions in the solution space are calculated. Then these butterflies will use formula 1 to produce fragrance in their place. The algorithm has two key steps, namely the global search phase and the local search phase. In the global search phase, the butterfly takes a step towards the most suitable butterfly / solution g ∗, which can be expressed by formula (2).

Here, g ∗ denotes the current best solution found in all the solutions of the current iteration; fi denotes the scent of the first butterfly, and r is a random number in [0Power1]. The local search phase can be expressed as

Among them, xjt and xkt are the j and k butterflies in the solution space.

Butterflies looking for food and mating partners can occur locally and globally. Taking into account geographical proximity and various other factors, such as rain and wind, searching for food may account for a large proportion of the whole foraging activities of mating partners or butterflies. Therefore, the handover probability p is used in BOA to switch between a normal global search and a dense local search.

Iterate until the stop criteria are met. There can be multiple criteria for the end of an iteration, such as the maximum CPU time used, the maximum number of iterations reached, the maximum number of iterations without improvement, the specific value of the error rate reached, or any other appropriate criteria. At the end of the iterative phase, the algorithm outputs the optimal solution with the best fitness.

Part of the source code clc;clear%% download data% processing data including processing time, processing machines, number of machines, weight of each machine, number of workpieces, corresponding process load data operation_time operation_machine num_machine machine_weight num_job num_op%% basic parameters MAXGEN=200;% maximum number of iterations sizepop=201;% population size 0.5 % goal weight Nambisizeolite 30;% number of neighborhood solutions 15;% number of shared solutions Grou5;% number of tours G1: 20;% competitive mechanism 1 parameter G2: 10;% competitive mechanism 2 parameter trace=zeros (2MAXGEN); chrom_best= [] % = = population initialization = = total_op_num=sum (num_op); chroms=initialization (num_op,num_job,total_op_num,sizepop,operation_machine,operation_time); [ZMagol ~] = fitness (chroms,num_machine,e,num_job,num_op);% divides the best solution into min (Z); leader=chroms (ind,:) % remove the leading birds from the chroms, and then divide the left and right populations of the following birds: chroms (ind,:) = []; Z (ind) = []; sp= (sizepop-1) / 2 sp+1:end,: birds chroms (1); Z_left=Z (1:sp); rights=chroms (sp+1:end,:); Z_right=Z (sp+1:end) The crossover function in%% migratory bird algorithm is different from that in genetic algorithm.%% migratory bird algorithm inputs two chromosome populations. Respectively from the left and right queue%-function [lefts,Z_left,rights,Z_right] = crossover (lefts,rights,Z_left,Z_right,total_op_num,num_machine,e,num_job Num_op) chroms1=lefts Chroms2=rights;for i=1:size (chroms1,1)%% crossover operation for work code% parent chromosome parent1=lefts (iMagazine:); parent2=rights (irect:); Job=randperm (num_job);% randomly divide the artifact into two sets J1=Job (1:round (num_job/2)); J2=Job (length (J1) + 1:end); op_p1= []; op_p2= [] For j=1:length (J2)% find the corresponding position of J2 fragment in the parent op_p1= [op _ p1 1:total_op_num find (parent1 (1:total_op_num) = = J2 (j)]; op_p2= [op _ p2 find (parent2 (1:total_op_num) = = J2 (j))]; end op_s1=sort (op_p1); op_s2=sort (op_p2) % progeny 1 exchanged the gene of J2 fragment, the gene corresponding to machine code, the gene corresponding to the working time code chroms1 (iReceiving opposs1) = parent2 (op_s2); chroms1 (ittaltaltalophosphamnum opposites1) = parent2 (total_op_num+op_s2); chroms1 (icenttotaltalophosphamnum _ numpurophosphams1) = parent2 (total_op_num*2+op_s2) % progeny 2 isomorph chroms2 (iGrammar options2) = parent1 (op_s1); chroms2 (irect totaltalophosphapnumtransiopress2) = parent1 (total_op_num+op_s1); chroms2 (irect totalaccounophernum _ nummopharms2) = parent1 (total_op_num*2+op_s1);%% crossover operation for machine code parent1=chroms1 (iEng:); parent2=chroms2 (iEng:) % randomly generate 0Power1 sequence rand0_1=randi ([0L1], 1LEC1); for n=1:num_job ind_0=find (rand0_1 (num_op (n) * (nmae 1) + 1:num_op (n) * n) = 0); if ~ isempty (ind_0) ind1=find (parent1 (1:total_op_num) = = n) Ind2=find (parent2 (1:total_op_num) = = n); chroms1 (ind_0) = parent2 (total_op_num+ind2 (ind_0)); chroms1 (ind_0) = parent2 (total_op_num*2+ind2 (ind_0)); chroms2 (ind_0) = parent1 (total_op_num+ind1 (ind_0)) Chroms2 (ind_0) = parent1 (total_op_num*2+ind1 (ind_0)); end endend%% determines whether an individual can update [Z1 ~] = fitness (chroms1,num_machine,e,num_job,num_op); [Z2 ~] = fitness (chroms2,num_machine,e,num_job,num_op); lefts (Z1)

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.