CN106611382A - Method for solving job shop process bottleneck problem based on cuckoo search algorithm - Google Patents
Method for solving job shop process bottleneck problem based on cuckoo search algorithm Download PDFInfo
- Publication number
- CN106611382A CN106611382A CN201610836555.9A CN201610836555A CN106611382A CN 106611382 A CN106611382 A CN 106611382A CN 201610836555 A CN201610836555 A CN 201610836555A CN 106611382 A CN106611382 A CN 106611382A
- Authority
- CN
- China
- Prior art keywords
- nest
- bird
- optimal
- bottleneck
- algorithm
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 60
- 241000544061 Cuculus canorus Species 0.000 title claims abstract description 36
- 238000010845 search algorithm Methods 0.000 title claims abstract description 22
- 235000005770 birds nest Nutrition 0.000 claims abstract description 47
- 235000005765 wild carrot Nutrition 0.000 claims abstract description 47
- 238000004422 calculation algorithm Methods 0.000 claims abstract description 36
- 238000004364 calculation method Methods 0.000 claims abstract description 6
- 230000001174 ascending effect Effects 0.000 claims description 5
- 210000000349 chromosome Anatomy 0.000 claims description 4
- 238000003754 machining Methods 0.000 claims description 4
- 238000005295 random walk Methods 0.000 claims description 3
- 238000007514 turning Methods 0.000 claims description 3
- 238000009827 uniform distribution Methods 0.000 claims description 2
- 235000013601 eggs Nutrition 0.000 claims 3
- 238000012512 characterization method Methods 0.000 claims 2
- 238000005457 optimization Methods 0.000 abstract description 2
- 238000004519 manufacturing process Methods 0.000 description 10
- 230000003071 parasitic effect Effects 0.000 description 3
- 244000000626 Daucus carota Species 0.000 description 2
- 230000006399 behavior Effects 0.000 description 2
- 238000009395 breeding Methods 0.000 description 2
- 230000001488 breeding effect Effects 0.000 description 2
- 230000012447 hatching Effects 0.000 description 2
- 241000271566 Aves Species 0.000 description 1
- 241000272177 Cuculiformes Species 0.000 description 1
- 238000001069 Raman spectroscopy Methods 0.000 description 1
- 241000255588 Tephritidae Species 0.000 description 1
- 238000004458 analytical method Methods 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 125000004122 cyclic group Chemical group 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 238000012804 iterative process Methods 0.000 description 1
- 238000012946 outsourcing Methods 0.000 description 1
- 230000017448 oviposition Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 230000000717 retained effect Effects 0.000 description 1
- 230000009466 transformation Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/004—Artificial life, i.e. computing arrangements simulating life
- G06N3/006—Artificial life, i.e. computing arrangements simulating life based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q50/00—Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
- G06Q50/04—Manufacturing
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02P—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS
- Y02P90/00—Enabling technologies with a potential contribution to greenhouse gas [GHG] emissions mitigation
- Y02P90/30—Computing systems specially adapted for manufacturing
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- Business, Economics & Management (AREA)
- Health & Medical Sciences (AREA)
- General Physics & Mathematics (AREA)
- General Health & Medical Sciences (AREA)
- Marketing (AREA)
- Biophysics (AREA)
- Strategic Management (AREA)
- Tourism & Hospitality (AREA)
- Human Resources & Organizations (AREA)
- General Business, Economics & Management (AREA)
- Economics (AREA)
- Manufacturing & Machinery (AREA)
- Life Sciences & Earth Sciences (AREA)
- Artificial Intelligence (AREA)
- Biomedical Technology (AREA)
- Primary Health Care (AREA)
- Computational Linguistics (AREA)
- Data Mining & Analysis (AREA)
- Evolutionary Computation (AREA)
- Molecular Biology (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Mathematical Physics (AREA)
- Software Systems (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
The invention provides a method for solving a job shop process bottleneck problem based on a cuckoo search algorithm. Bottleneck resources are judged by using the TOC principle, and the processing scheduling of shop bottleneck process is optimized by using an improved cuckoo search algorithm. According to the method provided by the invention, the work scheduling of the bottleneck process is optimized targetedly, thereby avoiding a lot of unnecessary optimization processes, accelerating the execution speed of the algorithm and meanwhile improving the solution accuracy of the algorithm; bird nest groups are classified by using an improved K_means algorithm, and then optimized scheduling is carried out the clusters by using the improved cuckoo search algorithm, thereby reducing the calculation amount of the algorithm on one hand, and effectively improving the solution accuracy of the algorithm on the other hand; and the difference of bird nests is expressed by safety and flight time consumption, the safety is expressed by random number, and the flight time consumption is expressed by geographic positions, thereby being simple and effective, applicable to the actual conditions and easy to understand.
Description
Technical Field
The invention relates to the field of scheduling, in particular to a method for solving the process bottleneck problem of a job shop by using an algorithm.
Background
In the whole operation process of an enterprise, a certain link always restricts the production and sales rate of the enterprise, and the link is called as a bottleneck. The goal of enterprises is to earn more profits at present or in the future, so that improvements and breakthroughs are continuously made, and the bottleneck is no longer an obstacle to income increase of enterprises. But in the course of the improvement the old bottleneck disappears and a new bottleneck will be created. Therefore, the transformation and the breakthrough of the bottleneck are a cyclic and continuous improvement process for enterprises.
Through the analysis of the above definition, it can be found that when judging whether a certain resource is a bottleneck resource, there are the following six typical situations:
1. the production capacity of part of the production resources is lower than the market demand.
2. The production capacity of all production resources is lower than the market demand.
3. The production capacity of all production resources is higher than the market demand.
4. The impact on the bottleneck resources when new production resources are added or the process is improved.
5. The influence on the bottle neck resources is generated when the production capacity is improved through outsourcing processing.
6. The influence on the bottle neck resources is caused when the market demand is improved through marketing and other measures.
The constraint theory holds that the logistics in the system should be balanced, but not the capacity in the system, and the bottleneck resource occupying a very small amount is the key for controlling the logistics, so that the utilization degree of the non-bottleneck resource occupying the majority is determined, and the effective output of the system is determined. Therefore, theoretical tools and principles become one of the key technologies for bottleneck resource identification. The chapter mainly researches an identification method of bottleneck resources so as to scientifically, reasonably, quickly and effectively identify the bottleneck resources in the system. Bottleneck resources limit the effective throughput of the entire system, and are the weakest places in the system capacity.
Cuckoo Search (CS) algorithm is a new modern heuristic proposed in 2009 by Yang and the raman engineering institute Deb, cambridge university. The algorithm is proposed based on nest parasitic breeding behaviors of certain cuckoo species and Levy flight (Levy flight) behavior characteristics of birds, fruit flies and the like. The cuckoo search algorithm is a nest searching process simulating random walk of cuckoos to search for suitable egg laying nests. During the selection process of the host, the cuckoo searches for a host which has basically the same chick feeding character, egg shape and color and is easy to imitate with the chick breeding and hatching period. In most cases, once the host has identified the parasitic egg, the host throws or discards the parasitic egg and creates a new nest elsewhere. The cuckoo will give up the nest and reselect the next time the host is selected. In order to simulate the nest-searching mode of cuckoo, Yang and Deb propose the following 3 assumptions: (1) the cuckoo only lays one egg at a time, and randomly selects a nest position for hatching; (2) in a randomly selected set of nests, the best nest location will be retained to the next generation; (3) the number n of nests of the host is fixed, and the probability of finding a foreign egg by the host is Pa. Pa can be approximately seen as the probability that n poorly located nests are replaced by several new randomly generated nests, usually given a fixed value. Cuckoo has good global optimal search capability, few algorithm parameters are easy to implement, but the algorithm is not fast enough in search speed, not high enough in calculation accuracy, not large enough in algorithm application range and not enough in search activity.
The K _ means algorithm is widely applied to processing of a large amount of data, and the main idea is to divide a data set into different categories through an iterative process, so that a criterion function for evaluating the clustering performance is optimal, and each generated cluster is compact and independent.
Disclosure of Invention
Aiming at the defects in the prior art, the technical problem to be solved by the invention is to provide a cuckoo search algorithm to solve the process bottleneck problem of a job shop.
The object of the present invention is to overcome the problems of the prior art: the production capacity of the operation workshop is short of supply and demand, and the problem of process bottleneck exists; the cuckoo search algorithm is not fast enough in search speed, not high enough in calculation accuracy, not large enough in application range, and does not have an algorithm capable of intuitively providing a job shop scheduling scheme.
The technical scheme adopted by the invention for realizing the purpose is as follows: a cuckoo search algorithm based problem of process bottleneck of a job shop is solved. The steps of the algorithm are as follows:
step 1: identifying a bottleneck: the identification method of the bottleneck is as follows:
step 1.1: and judging bottleneck resources according to a TOC principle.
Step 1.2: when demand exceeds capacity, the longest queued machines are bottlenecks.
Step 2: optimizing a bottleneck: and optimizing the scheduling of the bottleneck process processing of the workshop by utilizing an improved cuckoo search algorithm. The specific process is as follows:
step 2.1: initializing the bottleneck nest number n.
Step 2.2: the nests are clustered by using an improved K _ means algorithm, and nest groups with different safety and flight time consumption are separated. The specific method comprises the following steps:
1. initializing the data set: a set of bird nests is initialized.
2. An initial solution is selected. A set of central solutions, with k centers, is randomly generated.
3. And (6) clustering. Bird nests with similar safety and time consumption in flight are gathered into a category. The method specifically comprises the following steps:
(1) the safety and time-of-flight consumption for each nest were calculated.
(2) And (5) calculating the bird nest dissimilarity. The dissimilarity is characterized by the safety and flight time consumption of the bird nest, and is used as the execution time of the work shop work procedure.
(3) If ρiAnd (4) if the number is less than or equal to the number, the ith country is gathered into the corresponding class c center.
And 2.3, scheduling in different classes by using an improved cuckoo search algorithm. The method comprises the following specific steps:
(1) basic parameters of an initialization algorithm: the number n of bird nests (the number of workpieces), the probability Pa of finding the foreign bird egg by the host (the operation preemption probability), and the maximum iteration number MaxT or the search precision are set.
(2) Initial bird nest position (workpiece machining completion time): the processing time is in ascending trend arrangement.
(3) Calculating an objective function value: and converting the nest positions (completion time) into process arrangement according to a coding rule, calculating objective function values corresponding to the nest positions, and obtaining the current optimal nest position.
(4) And (3) updating the position of the bird nest: and starting iteration, keeping the position of the previous generation of the optimal nest unchanged, updating the position of the nest (namely global search), so as to randomly generate the next generation of the nest, evaluating the objective function value of each nest after the position is updated, and recording the position of the current optimal nest.
(5) Updating the optimal function value: and comparing the optimal values of the positions of the nests in the current iteration and the last iteration, and if the new optimal value is smaller than the original optimal value, giving the new optimal value to the objective function value of the current optimal nest position.
(6) And (4) when the maximum search times are reached or the search precision is met, switching to the step (7), and otherwise, switching to the step (3) to perform the next search.
(7) The optimal scheduling value and the corresponding scheduling scheme (chromosome sequence) are output.
And step 3: if the obtained solution meets the requirements or the iteration times reach a certain value, turning to the step 4, otherwise, taking the average flight time consumption of each current cluster as the center, and returning to the step 2.2.
And 4, step 4: and (5) finishing the algorithm and outputting an optimal scheduling scheme.
The invention has the beneficial effects that:
1. by identifying the bottleneck, the operation scheduling of the bottleneck process is optimized with the right alignment to the bottleneck, so that a plurality of unnecessary optimization processes are avoided, the execution speed of the algorithm is increased, and meanwhile, the accuracy of the algorithm solution is also improved.
2. The improved K-means algorithm is used for classifying the nest groups, and then optimized scheduling is carried out on each cluster through the improved cuckoo search algorithm, so that the calculated amount of the algorithm is reduced, and the solution accuracy of the algorithm is effectively improved.
3. The dissimilarity degree of the bird nest is described by utilizing safety and flight time consumption, the safety is described by utilizing random numbers, the flight time consumption is described by utilizing a geographical position, and the method is simple, effective, suitable for practical situations and easy to understand.
4. The initial positions of the bird nests are arranged according to the ascending trend, the bird nests are simple and orderly, and the iterative search time of the algorithm is reduced.
5. The jsp problem is solved by adopting a process-based encoding rule, workpiece parameters are attributed, simplicity and clarity are realized, the practicability is high, and the searching capability of the algorithm is also improved.
6. The mean value-based method is used for solving the searching step length of the cuckoo, the algorithm searching time is reduced, and the accuracy of the algorithm for solving the scheduling problem of the job shop is improved.
Drawings
Fig. 1 is a flow chart for solving the process bottleneck problem of a job shop based on a cuckoo search algorithm.
Fig. 2 is a basic flow chart of the improved cuckoo search algorithm.
Detailed Description
In order to make the objects, technical solutions and advantages of the present invention more apparent, the following detailed description is made in conjunction with an algorithm flowchart.
Mathematical description of a bottleneck
X for n resources in the system ═ X1，X2，...，XnC, actual output capacity C ═ C1，C2，...，CnOutside of the systemRequired quantity MR ═ MR1，MR2，...，MRn}. And an incidence relation R for guarding input and output exists between certain resources. Hypothesis and resource XiThe set of labels of the associated resources is S, i.e.
Then, if and only if
Time, resource XiIs a bottleneck resource, output capacity CiExternal demand MRi。
Second, an algorithm for solving the problem of workshop scheduling process bottleneck
Step 1: identifying a bottleneck: the identification method of the bottleneck is as follows:
step 1.1: according to the TOC principle, the following model was established:and isTime, resource XiIs a bottleneck resource.
Step 1.2: when demand exceeds capacity, the longest queued machines are bottlenecks.
Step 2: optimizing a bottleneck: and optimizing the scheduling of the bottleneck process processing of the workshop by utilizing an improved cuckoo search algorithm. The specific process is as follows:
step 2.1: the number of nests n is initialized.
Step 2.2: the nests are clustered by using an improved K _ means algorithm, and nest groups with different safety and flight time consumption are separated. The specific method comprises the following steps:
1. initializing the data set: bird nest set N ═ Ni|i＝1，2，...，n}。
2. An initial solution is selected. A set of central solutions, with k centers, is randomly generated.
3. And (6) clustering. Bird nests with similar safety and time consumption in flight are gathered into a category. The method specifically comprises the following steps:
(1) the safety and time-of-flight consumption for each nest were calculated. The bird's nest safety is represented by a random probability p, piRand (0, 1), the bird's nest flight time consumption dynamics formula is as follows:
wherein, tiTime of flight for the ith bird nest, siIs the distance between the ith bird nest and the cuckoo, and v is the average flight speed of the cuckoo.
(2) And (5) calculating the bird nest dissimilarity. The dissimilarity is characterized by the safety and flight time consumption of the bird nest, and is used as the execution time of the work shop work procedure. Degree of dissimilarity:
ρi＝a.ti+b·pi
wherein a and b are constants, defined herein as a and b ∈ (0, 1)
(3) If ρiAnd (4) if the number is less than or equal to the number, the ith country is gathered into the corresponding class c center.
And 2.3, scheduling in different classes by using an improved cuckoo search algorithm. The method comprises the following specific steps:
(1) basic parameters of an initialization algorithm: the number n of bird nests (the number of workpieces), the probability Pa of finding the foreign bird egg by the host (the operation preemption probability), and the maximum iteration number MaxT or the search precision are set.
(2) Initial bird nest position (workpiece machining completion time): the processing time is in ascending trend arrangement.
(3) Calculating an objective function value: and converting the nest positions (completion time) into process arrangement according to a coding rule, calculating objective function values corresponding to the nest positions, and obtaining the current optimal nest position. The concrete implementation is as follows:
an objective function:
f(C)＝min max1≤o≤w{max1≤k≤m{max1≤i≤nCoik}} (1)
constraint conditions are as follows:
Coik-poik+M(1-aoihk)≥Coih(2)
(o＝1，2，...，w；i＝1，2，...，n；k＝1，2，...，m)
Cojk-Coik+M(1-xoijk)≥poik(3)
(i，j＝1，2，...，n；o＝1，2，...，w；k＝1，2，...，m)
Coik≥0(o＝1，2，...，w；i＝1，2，...，n；k＝1，2，...，m) (4)
xoijk0 or 1(i, j ═ 1, 2,.., n; o ═ 1, 2,.., w; k ═ 1, 2,.., m) (5)
Wherein, formula (1) represents an objective function, namely, completion time (Makespan); formula (2) represents the operational sequence of each workpiece determined by the process constraints; equation (3) represents the sequence of each machine processing each workpiece; equation (4) represents the completion time variable constraint; equation (5) represents the possible values of the variables. The symbols referred to in the above formula define the following meanings: coikAnd poikRespectively the completion time point and the processing time length of the ith workpiece in the ith order on the machine k; m is oneA sufficiently large integer; a isoihkAnd xoijkRespectively, indicating coefficient and indicating variable, and the meaning is as follows:
(4) and (3) updating the position of the bird nest: and starting iteration, keeping the position of the previous generation of the optimal nest unchanged, updating the position of the nest (namely global search), so as to randomly generate the next generation of the nest, evaluating the objective function value of each nest after the position is updated, and recording the position of the current optimal nest. The specific implementation scheme is shown in the following mathematical formula:
wherein,indicating the nest position of the ith cuckoo in the t-th generation (using C in the workshop scheduling problem)oikExpressed), α is the step size parameter, subject to uniform distribution, α -U (0, 1). parameter S is the step size of the random walk, the calculation formula is as follows:
S＝u+α·σ (9)
wherein,
and updating each nest position during local search according to conditions: and (3) taking a random number Ra as the probability of finding the foreign bird egg by the bird nest master and comparing the probability with Pa, randomly changing the position of the bird nest if Ra is greater than Pa, otherwise keeping the original position unchanged, calculating the objective function value of each bird nest after the position is moved, and recording the current optimal position of the bird nest. Expressed by the following 0-1 planning model:
(5) updating the optimal function value: and comparing the optimal values of the positions of the nests in the current iteration and the last iteration, and if the new optimal value is smaller than the original optimal value, giving the new optimal value to the objective function value of the current optimal nest position.
(6) And (4) when the maximum search times are reached or the search precision is met, switching to the step (7), and otherwise, switching to the step (3) to perform the next search.
(7) The optimal scheduling value and the corresponding scheduling scheme (chromosome sequence) are output.
And step 3: if the obtained solution meets the requirements or the iteration times reach a certain value, turning to the step 4, otherwise, taking the average flight time consumption of each current cluster as the center, and returning to the step 2.2.
And 4, step 4: and (5) finishing the algorithm and outputting an optimal scheduling scheme.
Claims (2)
1. The invention relates to the field of scheduling, in particular to a method for solving a process bottleneck problem of a job shop based on a cuckoo search algorithm, which is characterized by comprising the following steps of:
step 1: identifying a bottleneck: the identification method of the bottleneck is as follows:
step 1.1: judging bottleneck resources according to TOC principle
Step 1.2: when demand exceeds capacity, the longest queued machine is the bottleneck
Step 2: optimizing a bottleneck: the scheduling of the bottleneck process processing of the workshop is optimized by utilizing an improved cuckoo search algorithm, and the specific flow is as follows:
step 2.1: initializing the number of bottleneck nests n
Step 2.2: clustering the nests by using an improved K _ means algorithm, and separating nest groups with different safety and flight time consumption, wherein the specific method comprises the following steps:
1. initializing the data set: initializing bird nest set
2. Selecting an initial solution, randomly generating a set of central solutions, having k centers
3. Clustering, namely clustering the bird nests with similar safety and time consumption in flight into one class, specifically comprising the following steps:
(1) calculating the safety and time of flight consumption of each bird nest
(2) Calculating the dissimilarity of bird nests, the dissimilarity being characterized by the safety and flight time consumption of bird nests, and being used as an execution time characterization of work shop work procedures
(3) If it is notThen, the ith country is gathered into the corresponding c-center class
Step 2.3, scheduling in different categories by using an improved cuckoo search algorithm, which is specifically as follows:
(1) basic parameters of an initialization algorithm: setting the number of bird nests (the number of workpieces) n, the probability Pa (operation preemption probability) of finding foreign bird eggs by a host, and the maximum iteration number MaxT or the search precision
(2) Initial bird nest position (workpiece machining completion time): arranged in an ascending trend according to the processing time
(3) Calculating an objective function value: converting the nest position (completion time) into process arrangement according to the coding rule, calculating the objective function value corresponding to each nest position, and obtaining the current optimal nest position
(4) And (3) updating the position of the bird nest: starting iteration, keeping the position of the previous generation of the optimal nest unchanged, updating the position of the nest (namely global search) so as to randomly generate the nest of the next generation, evaluating the objective function value of each nest after the position is updated, and recording the position of the current optimal nest
(5) Updating the optimal function value: comparing the optimal values of the nest positions of the current iteration and the last iteration, and if the new optimal value is smaller than the original optimal value, giving the new optimal value to the objective function value of the current optimal nest position
(6) When the maximum searching times is reached or the searching precision is met, the step (7) is carried out, otherwise, the step (3) is carried out for the next searching
(7) Outputting optimal scheduling values and corresponding scheduling scheme (chromosome sequence)
And step 3: if the obtained solution meets the requirement or the iteration times reach a certain value, turning to the step 4, otherwise, taking the average flight time consumption of each current cluster as the center, and returning to the step 2.2
And 4, step 4: and (5) finishing the algorithm and outputting an optimal scheduling scheme.
2. The method for solving the process bottleneck problem of the job shop based on the cuckoo search algorithm as claimed in claim 1, wherein the specific calculation process in the step 2 is as follows:
step 2: optimizing a bottleneck: the scheduling of the bottleneck process processing of the workshop is optimized by utilizing an improved cuckoo search algorithm, and the specific flow is as follows:
step 2.1: initializing nest number n
Step 2.2: clustering the nests by using an improved K _ means algorithm, and separating nest groups with different safety and flight time consumption, wherein the specific method comprises the following steps:
1. initializing the data set: bird nest set
2. Selecting an initial solution, randomly generating a set of central solutions, having k centers
3. Clustering, namely clustering the bird nests with similar safety and time consumption in flight into one class, specifically comprising the following steps:
(1) calculating the safety and flight time consumption of each nest, wherein the safety of each nest is represented by a random probability p,the dynamic formula for the flight time consumption of the bird nest is as follows:
wherein,for the time spent flying the ith nest,is the distance between the ith nest and the cuckoo, and v is the average flying speed of the cuckoo
(2) Calculating the dissimilarity of the bird nest, wherein the dissimilarity is characterized by the safety and flight time consumption of the bird nest and is used as an execution time characterization of a work shop workpiece procedure, and the dissimilarity is as follows:
in the formula,is a constant, as defined herein
(3) If it is notThen, the ith country is gathered into the corresponding c-center class
Step 2.3, scheduling in different categories by using an improved cuckoo search algorithm, which is specifically as follows:
(1) basic parameters of an initialization algorithm: setting the number of bird nests (the number of workpieces) n, the probability Pa (operation preemption probability) of finding foreign bird eggs by a host, and the maximum iteration number MaxT or the search precision
(2) Initial bird nest position (workpiece machining completion time): arranged in an ascending trend according to the processing time
(3) Calculating an objective function value: converting the nest positions (completion time) into process arrangement according to a coding rule, calculating objective function values corresponding to the nest positions, and obtaining the current optimal nest position, wherein the specific implementation is as follows:
wherein, formula (1) represents an objective function, namely, completion time (Makespan); formula (2) represents the operational sequence of each workpiece determined by the process constraints; equation (3) represents the sequence of each machine processing each workpiece; equation (4) represents the completion time variable constraint; the formula (5) represents the possible values of the variables, and the symbols referred to in the formula have the following definitions:respectively the completion time point and the processing time length of the ith workpiece in the ith order on the machine k; m is a sufficiently large integer;andrespectively indicating coefficient and fingerVariables, the meaning of which is:
(4) and (3) updating the position of the bird nest: starting iteration, keeping the position of the previous generation of the optimal nest unchanged, updating the position of the nest (namely global search), thereby randomly generating the nest of the next generation, evaluating the objective function value of each nest after the position is updated, and recording the position of the current optimal nest, wherein the specific implementation scheme is shown in the following mathematical formula:
wherein,indicating the nest position of the ith cuckoo in the t-th generation (used in the workshop scheduling problem)To indicate that),is a step size parameter, subject to uniform distribution,and the parameter S is a step length of random walk, and the calculation formula is as follows:
wherein,
and updating each nest position during local search according to conditions: using a random number Ra as the probability of finding the foreign bird egg by the bird nest owner and comparing with Pa, if Ra is larger than Pa, randomly changing the bird nest position, otherwise keeping the original position unchanged, calculating the objective function value of each bird nest after the position is moved, recording the current optimal bird nest position, and expressing by using a 0-1 planning model as follows:
(5) updating the optimal function value: comparing the optimal values of the nest positions of the current iteration and the last iteration, and if the new optimal value is smaller than the original optimal value, giving the new optimal value to the objective function value of the current optimal nest position
(6) When the maximum searching times is reached or the searching precision is met, the step (7) is carried out, otherwise, the step (3) is carried out for the next searching
(7) The optimal scheduling value and the corresponding scheduling scheme (chromosome sequence) are output.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2016106219990 | 2016-07-30 | ||
| CN201610621999 | 2016-07-30 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN106611382A true CN106611382A (en) | 2017-05-03 |
Family
ID=58615195
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201610836555.9A Pending CN106611382A (en) | 2016-07-30 | 2016-09-21 | Method for solving job shop process bottleneck problem based on cuckoo search algorithm |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN106611382A (en) |
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108508853A (en) * | 2018-03-13 | 2018-09-07 | 济南大学 | Based on the method for improving extension moving bottleneck algorithm solution product integrated dispatch problem |
| CN108876654A (en) * | 2018-05-29 | 2018-11-23 | 昆明理工大学 | A kind of Optimization Scheduling of multiclass cable processing |
| CN108921338A (en) * | 2018-06-20 | 2018-11-30 | 广东工业大学 | A kind of more vehicle shop logistics transportation dispatching methods |
| CN112101759A (en) * | 2020-09-03 | 2020-12-18 | 交通运输部科学研究院 | Method and device for constructing risk assessment model and assessing risk of expressway tunnel |
| CN113033629A (en) * | 2021-03-09 | 2021-06-25 | 中南大学 | Radar signal sorting method and device based on improved cuckoo algorithm |
| CN118365109A (en) * | 2024-06-19 | 2024-07-19 | 深圳市益普科技有限公司 | Bottleneck process identification method |
-
2016
- 2016-09-21 CN CN201610836555.9A patent/CN106611382A/en active Pending
Cited By (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108508853A (en) * | 2018-03-13 | 2018-09-07 | 济南大学 | Based on the method for improving extension moving bottleneck algorithm solution product integrated dispatch problem |
| CN108876654A (en) * | 2018-05-29 | 2018-11-23 | 昆明理工大学 | A kind of Optimization Scheduling of multiclass cable processing |
| CN108876654B (en) * | 2018-05-29 | 2022-02-08 | 昆明理工大学 | Optimized scheduling method for processing of multiple cables |
| CN108921338A (en) * | 2018-06-20 | 2018-11-30 | 广东工业大学 | A kind of more vehicle shop logistics transportation dispatching methods |
| CN112101759A (en) * | 2020-09-03 | 2020-12-18 | 交通运输部科学研究院 | Method and device for constructing risk assessment model and assessing risk of expressway tunnel |
| CN113033629A (en) * | 2021-03-09 | 2021-06-25 | 中南大学 | Radar signal sorting method and device based on improved cuckoo algorithm |
| CN113033629B (en) * | 2021-03-09 | 2022-08-05 | 中南大学 | Radar signal sorting method and device based on improved cuckoo algorithm |
| CN118365109A (en) * | 2024-06-19 | 2024-07-19 | 深圳市益普科技有限公司 | Bottleneck process identification method |
| CN118365109B (en) * | 2024-06-19 | 2024-08-27 | 深圳市益普科技有限公司 | Bottleneck process identification method |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN106611382A (en) | Method for solving job shop process bottleneck problem based on cuckoo search algorithm | |
| Radiuk | Impact of training set batch size on the performance of convolutional neural networks for diverse datasets | |
| WO2018036282A1 (en) | Task scheduling method, device and computer storage medium | |
| US10776400B2 (en) | Clustering using locality-sensitive hashing with improved cost model | |
| CN108446741B (en) | Method, system and storage medium for evaluating importance of machine learning hyper-parameter | |
| CN106527381B (en) | A kind of fast evaluation method towards parallel batch processing machine dynamic dispatching | |
| CN106874112B (en) | Workflow backfilling method combined with load balancing | |
| CN109445386B (en) | Cloud manufacturing task shortest production time scheduling method based on ONBA | |
| US20210081894A1 (en) | Constrained vehicle routing using clusters | |
| CN112232413A (en) | High-dimensional data feature selection method based on graph neural network and spectral clustering | |
| Bergmann et al. | Approximation of dispatching rules for manufacturing simulation using data mining methods | |
| CN106610656A (en) | Improved cuckoo search algorithm for solving scheduling problem of workshop | |
| JPWO2022044064A5 (en) | Machine learning data generation program, machine learning data generation method and machine learning data generation device | |
| CN102831432A (en) | Redundant data reducing method suitable for training of support vector machine | |
| WO2021079442A1 (en) | Estimation program, estimation method, information processing device, relearning program, and relearning method | |
| Bhatia | New improved technique for initial cluster centers of K means clustering using Genetic Algorithm | |
| CN106611276A (en) | Improved cuckoo search algorithm for solving job-shop scheduling problem | |
| CN106611381A (en) | Algorithm for analyzing influence of material purchase to production scheduling of manufacturing shop based on cloud manufacturing | |
| CN106610655A (en) | Improved particle swarm optimization algorithm for solving job-shop scheduling problem | |
| CN115759552A (en) | Multi-agent architecture-based real-time scheduling method for intelligent factory | |
| CN112035234B (en) | Distributed batch job distribution method and device | |
| CN107423810B (en) | Job shop scheduling method and system based on camel group algorithm | |
| CN106709572B (en) | A kind of data processing method and equipment | |
| CN110047509B (en) | Two-stage subspace partitioning method and device | |
| CN106611215A (en) | Novel cuckoo search algorithm for solving job-shop scheduling problem |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| WD01 | Invention patent application deemed withdrawn after publication |
Application publication date: 20170503 |
|
| WD01 | Invention patent application deemed withdrawn after publication |