[go: up one dir, main page]

CN114066065A - A multi-objective hybrid zero-idle replacement flow shop scheduling method and system - Google Patents

A multi-objective hybrid zero-idle replacement flow shop scheduling method and system Download PDF

Info

Publication number
CN114066065A
CN114066065A CN202111367979.2A CN202111367979A CN114066065A CN 114066065 A CN114066065 A CN 114066065A CN 202111367979 A CN202111367979 A CN 202111367979A CN 114066065 A CN114066065 A CN 114066065A
Authority
CN
China
Prior art keywords
individual
objective function
value
population
distance
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.)
Granted
Application number
CN202111367979.2A
Other languages
Chinese (zh)
Other versions
CN114066065B (en
Inventor
朱光宇
伍金桥
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fuzhou University
Original Assignee
Fuzhou University
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Fuzhou University filed Critical Fuzhou University
Priority to CN202111367979.2A priority Critical patent/CN114066065B/en
Publication of CN114066065A publication Critical patent/CN114066065A/en
Application granted granted Critical
Publication of CN114066065B publication Critical patent/CN114066065B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • 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
    • G06Q10/00—Administration; Management
    • G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
    • G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem
    • 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
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/12—Computing arrangements based on biological models using genetic models
    • G06N3/126—Evolutionary algorithms, e.g. genetic algorithms or genetic programming
    • 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)
  • Physics & Mathematics (AREA)
  • Business, Economics & Management (AREA)
  • Theoretical Computer Science (AREA)
  • Health & Medical Sciences (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Biophysics (AREA)
  • Human Resources & Organizations (AREA)
  • General Physics & Mathematics (AREA)
  • General Health & Medical Sciences (AREA)
  • Strategic Management (AREA)
  • Economics (AREA)
  • Marketing (AREA)
  • General Business, Economics & Management (AREA)
  • Evolutionary Computation (AREA)
  • Computational Linguistics (AREA)
  • Molecular Biology (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Biomedical Technology (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Artificial Intelligence (AREA)
  • Data Mining & Analysis (AREA)
  • Tourism & Hospitality (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Evolutionary Biology (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Primary Health Care (AREA)
  • Physiology (AREA)
  • Genetics & Genomics (AREA)
  • Manufacturing & Machinery (AREA)
  • Development Economics (AREA)
  • Game Theory and Decision Science (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Operations Research (AREA)
  • Quality & Reliability (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

The invention relates to a scheduling method and a system for a multi-target mixed zero-idle replacement flow shop, wherein the method comprises the following steps: step S1: describing the scheduling problem of the multi-target mixed zero-space idle current conversion water workshop; step S2: establishing a constraint condition meeting the problem; step S3: establishing an expected objective function in the actual production process; step S4: constructing a group intelligent algorithm based on dynamic time warping distance; step S5: and (4) finishing iterative optimization according to the dynamic time warping distance, finding out the set of the optimal solution, and obtaining the final scheduling scheme. The method and the system are favorable for optimizing the mixed zero-air idle current conversion water shop scheduling, so that an effective scheduling scheme is provided for a factory to reasonably arrange the work piece procedures.

Description

Multi-target mixed zero-idle replacement flow shop scheduling method and system
Technical Field
The invention belongs to the field of flow shop scheduling, and particularly relates to a multi-target mixed zero-idle replacement flow shop scheduling method and system based on a dynamic time warping distance.
Background
The Problem of zero-idle Flow water Scheduling (NPFSP) is a Problem of modern industrial combination which is distributed in the electronic circuit production industry, the casting field and the like, the NPFSP is further restricted on the basis of the Scheduling of a replacement Flow Shop, and the NPFSP requires continuous processing of a machine so as to reduce the abrasion and maintenance of a valuable machine.
Since not all machines belong to high-energy-consumption and expensive machines, a mixed zero-idle PermutionLow sheet Scheduling Problim (MNPFSP) is introduced, and the mixed zero-idle PermutionLow Shop Scheduling Problem requires that a designated machine is in a zero-idle constraint state, and other machines are in a normal operation state. Due to the complexity of the problems, such as containing a plurality of targets, a plurality of constraints and having NP-Hard characteristics, the research problems have larger research value as the scale of the research problems is enlarged. At present, methods for solving the problems mainly comprise an accurate algorithm, a heuristic algorithm and an intelligent optimization algorithm, but the realization effect is poor mostly. Therefore, there is a need to develop a new method to optimize the hybrid zero-idle permutation flow shop scheduling.
Disclosure of Invention
The invention aims to provide a multi-target mixed zero-idle replacement flow shop scheduling method and system, which are beneficial to optimizing mixed zero-idle replacement flow shop scheduling, so that an effective scheduling scheme is provided for a factory to reasonably arrange work procedures.
In order to achieve the purpose, the invention adopts the technical scheme that: a multi-target mixed zero-idle replacement flow shop scheduling method comprises the following steps:
step S1: describing the scheduling problem of the multi-target mixed zero-space idle current conversion water workshop;
step S2: establishing a constraint condition meeting the problem;
step S3: establishing an expected objective function in the actual production process;
step S4: constructing a group intelligent algorithm based on dynamic time warping distance;
step S5: and (4) finishing iterative optimization according to the dynamic time warping distance, finding out the set of the optimal solution, and obtaining the final scheduling scheme.
In step S1, n is the total number of components, m is the total number of machines, and U ═ U { (U) }1，U2，…Ui，…UnU denotes the machining sequence of the workpiece, UiFor workpieces positioned at i in the sequence, fHIs the H objective function value, yjFor workpieces U subject to zero idle constraintiThe total time of push-up post-processing in machine j, the set of machines belonging to the zero idle state is
Figure BDA0003361318140000021
Further, in step S2, the constraint condition satisfying the problem is established as follows:
the finishing time constraint conditions for starting the processing are as follows: c1，1＝t1，1；
Constraints of the machine 1 processing: ci，1≥Ci-1，1+ti，1，(i＝2，…n)；
Workpiece U1Constraint conditions of processing: c1，j≥C1，j-1+t1，j+yj-1，(j＝2，…m)；
The constraint conditions to be met by the rest of the workpieces and the machine are as follows:
Ci，j≥max{Ci，j-1，Ci-1，j+yj-1}+ti，j，(i＝2，…n；j＝2，…m)；
zero idle constraint: when j is equal to N, Ci-1，j＝Si，j，(i＝2，…n)；
Each machine delay time constraint: y is1＝0，
Figure BDA0003361318140000022
Wherein S isi，jIs a workpiece UiStarting time of machining on machine j, Ci，jTo workPart UiTime of completion on machine j, ti，jIs a workpiece UiMachining time on machine j, n being total number of workpieces, m being total number of machines, yjFor workpieces U subject to zero idle constraintiThe total time of push-up post-processing in machine j, the set of machines belonging to the zero idle state is
Figure BDA0003361318140000023
Further, in the step S3, an objective function f of the maximum completion time is set1Objective function f of maximum delay time2Total inventory cost objective function f3Objective function f of total holdover cost4：
f1＝Cn，m；
f2＝max{max(0，Ci，m-di)}，i＝1，2…n；
Figure BDA0003361318140000024
Figure BDA0003361318140000025
In the formula, Cn，mIs a workpiece UnThe completion time on machine m, i.e. the maximum completion time; ci，mIs a workpiece UiTime of completion on machine m, diIs a workpiece UiRequired delivery time of alphaiIs a workpiece UiStorage cost per unit time, |iIs a workpiece UiActual delivery time ofiIs a workpiece UiThe delay cost per unit time.
Further, the step S4 includes the following steps:
step S41: defining a parameter of the problem under study;
step S42: encoding individuals in a group intelligent algorithm;
step S43: constructing distance expression based on dynamic time warping;
step S44: and taking the reciprocal of the dynamic time warping distance as the fitness value of the individual in the group intelligent algorithm, and selecting the strategy to carry out the selection operation of the individual in the algorithm according to the fitness value.
Further, in step S41, gen is defined as the number of iterations at this time, maxgen is the total number of iterations, popsize is the population size, pcross is the cross probability, pmutation is the variation probability, ω, ε, and δ are all the intervals [0, 1]Random number in (b) the v-th gene of the r individualrv，bmaxIs gene brvThe upper bound of (1) is the total number n of workpieces; bminIs gene brvA lower bound of 1;
in step S42, the individual codes are integer codes, specifically, an array with a length of workpiece number is randomly generated, and then the array is sorted according to size to obtain a sorted array which meets the research problem, where the total number of individuals is the population number.
Further, the step S43 includes the following steps:
step S431: calculating the objective function value of different individuals of the ith iteration of the population as
Figure BDA0003361318140000031
The maximum value of each objective function in all individuals is selected and recorded as
Figure BDA0003361318140000032
Selecting the minimum value of each objective function in all individuals and marking as
Figure BDA0003361318140000033
Step S432: the objective function values of different dimensions fall in the [0, 1] interval by min-max normalization, which is as follows:
Figure BDA0003361318140000034
wherein i represents a population overlapThe generation is carried out for the ith time,
Figure BDA0003361318140000035
normalizing the value for the H-th objective function after the individual normalization,
Figure BDA0003361318140000036
represents the H-th objective function value of the individual,
Figure BDA0003361318140000037
the minimum function value of the H-th objective function in the population is represented,
Figure BDA0003361318140000038
representing the maximum function value of the H-th objective function in the population;
step S433: calculating the dynamic time warping distance, taking the reciprocal of the dynamic time warping distance as the fitness value of each individual in the group intelligent algorithm, establishing an individual selection strategy according to the fitness value, sequencing the reciprocals of the dynamic time warping distances of all the individuals in the group according to the size, wherein the maximum value is the optimal solution with the highest similarity to the objective function value of the ideal solution in the group, and the objective function value of the ideal solution is the minimum value of all objective functions during single-target optimization.
Further, in step S433, the calculating the dynamic time warping distance specifically includes the following steps:
step S4331: assuming that the function target value min-max normalized sequence of any individual and the minimum value min-max normalized sequence of each target function in the population individuals are respectively
Figure BDA0003361318140000041
Figure BDA0003361318140000042
It is formed into an H pattern matrix MHD, i.e. the distance matrix:
Figure BDA0003361318140000043
elements in a matrix
Figure BDA0003361318140000044
Represents
Figure BDA0003361318140000045
And
Figure BDA0003361318140000046
manhattan distance between;
wherein i represents the ith iteration of the population,
Figure BDA0003361318140000047
the H-th objective function value normalized for the individual,
Figure BDA0003361318140000048
the value normalized by the minimum value of the H-th objective function in the population individuals, M represents the Manhattan distance, and the calculation formula is as follows:
Figure BDA0003361318140000049
step S4332: in the matrix MHD, the continuum of elements forms a plurality of paths, which are normalized paths and denoted by W: w ═ W1，w2…，wK)，H≤K≤2H-1；
The canonical path W satisfies the following constraint:
(1) boundary conditions: the regular paths being from the lower left corner of the matrix MHD
Figure BDA00033613181400000410
At the beginning, corresponding coordinate point w1To the upper right corner of (1, 1)
Figure BDA00033613181400000411
Ending, corresponding to the coordinate point wK＝(H，H)；
(2) Continuity: if the coordinate is (p, q), the conditions that the coordinate is moved to the next coordinate point (p ', q') need to satisfy are that p '-p is less than or equal to 1, and q' -q is less than or equal to 1, which means that a certain point cannot be skipped and only the coordinate is moved to the next point;
(3) monotonicity: the requirement that p '-p is more than or equal to 0 and q' -q is more than or equal to 0 is met, namely W is required to be monotonous;
step S4333: there are many regular paths that satisfy the condition, wherein the path with the minimum regular cost is:
Figure BDA00033613181400000412
wherein K is the number of passing points, wk' is a coordinate point wkSelecting a path to minimize the final total distance according to the corresponding value in the matrix MHD, wherein the total distance measures the similarity of the two sequences, and the smaller the value is, the higher the similarity is;
and calculating the accumulated distance D in a manner of accumulating from the lower left corner to the upper right corner of the distance matrix MHD, and accumulating the distances of the passing points to obtain the accumulated distance D, wherein the calculation formula is as follows:
Figure BDA00033613181400000413
wherein D (p-1, q) represents the accumulated distance when the vehicle travels to the point (p-1, q), D (p, q-1) represents the accumulated distance when the vehicle travels to the point (p, q-1), and D (p-1, q-1) represents the accumulated distance when the vehicle travels to the point (p-1, q-1); initial conditions
Figure BDA0003361318140000051
And finally, calculating the cumulative distance D (H, H) through iteration, wherein the distance is the total distance, the cumulative distance D (H, H) is the dynamic time warping distance DTW (P, Q), and the passed path is the path with the minimum warping cost.
Further, the step S44 includes the following steps:
step S441: initializing a population, randomly generating the population with the size of popsize, setting the iteration number i as 1, and starting iteration;
step S442: solving each objective function value of the population;
step S443: calculating a fitness value, wherein a dynamic time warping distance is used as an individual selection strategy, and the reciprocal of the dynamic time warping distance is the size of the fitness value;
step S444: updating external files, when two or more objective function values are superior to the objective function values of the parent population, saving the values, and finally removing the same individuals;
step S445: selecting by adopting a binary tournament method, randomly selecting two individuals from a parent population each time, wherein the probability of selecting the individuals is the same, determining the selected individuals according to the fitness value of each individual, selecting the individuals with large fitness values to enter a child population, and repeating for multiple times until the child population reaches the size of the parent population;
step S446: performing cross operation, randomly selecting two individuals from a population, and inheriting good aspects of old individuals to new individuals through exchange combination of the individuals so as to generate new excellent individuals; firstly, a real number crossing method is adopted for crossing, and then the crossed individual genes are sequenced from small to large; wherein the x-th individual and the y-th individual are inzThe crossing mode on the position is as follows:
bxz＝bxz(1-ω)+byzω；
byz＝byz(1-ω)+bxzω；
in the formula, bxzIs the z-th gene of the x-th individual, byzIs the z-th gene of the y-th individual, and omega is the interval [0, 1%]A random number within;
step S447: carrying out mutation operation, randomly selecting an individual from the population, firstly selecting any point in the individual for mutation, and then sequencing the mutated genes according to the sequence from small to large; wherein the variation pattern of the r-th individual at the v position is:
Figure BDA0003361318140000061
in the formula, brvIs the v-th gene of the r individual, bmaxIs gene brvThe upper bound of (1) is the total number n of workpieces; bminIs gene brvA lower bound of 1; f (g) δ (1-gen/maxgen)2Both epsilon and delta are the interval [0, 1]]The internal random number gen is the iteration number at the moment, and maxgen is the total iteration number;
step S448: and when i is less than maxgen, i is i +1, jumping to the step S443, otherwise, jumping out of the loop, and stopping the algorithm.
The invention also provides a multi-target mixed zero-idle replacement flow shop scheduling system, which comprises a memory, a processor and computer program instructions stored on the memory and capable of being executed by the processor, wherein when the processor executes the computer program instructions, the steps of the method can be realized.
Compared with the prior art, the invention has the following beneficial effects: the invention provides a multi-target mixed zero-idle replacement flow shop scheduling method based on dynamic time warping distance, which can quickly and accurately find a target value and improve the searching performance by combining constraint conditions possibly encountered by factory production and taking the maximum completion time, the maximum delay time, the total inventory cost and the total deadline cost which are highly concerned by a factory as optimization targets.
Drawings
FIG. 1 is a flow chart of an implementation of an embodiment of the present invention.
Detailed Description
The invention is further explained below with reference to the drawings and the embodiments.
It should be noted that the following detailed description is exemplary and is intended to provide further explanation of the disclosure. Unless defined otherwise, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this application belongs.
It is noted that the terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of example embodiments according to the present application. As used herein, the singular forms "a", "an" and "the" are intended to include the plural forms as well, and it should be understood that when the terms "comprises" and/or "comprising" are used in this specification, they specify the presence of stated features, steps, operations, devices, components, and/or combinations thereof, unless the context clearly indicates otherwise.
As shown in fig. 1, this embodiment provides a method for scheduling a multi-target hybrid zero-idle replacement flow shop, including the following steps:
step S1: and describing the scheduling problem of the multi-target mixed zero-idle replacement flow shop.
In step S1, n is the total number of components, m is the total number of machines, and U ═ U { (U) }1，U2，…Ui，…UnU represents the machining sequence of the workpiece, UiFor workpieces positioned at i in the sequence, Ci，jIndicating the work UiFinish machining time on machine j, Si，j(i 1, 2, …, n, j 1, 2, …, m) represents a workpiece UiStarting time of machining on machine j, fHIs the H objective function value, F ═ F1，f2，…fH)TRepresenting the target vector, ti，jIs a workpiece UiMachining time on machine j, diIs a workpiece UiRequired delivery time of liIs a workpiece UiActual delivery time of alphaiIs a workpiece UiStorage cost per unit time, epsiloniIs a workpiece UiDelay cost per unit time, WpIs the actual delivery volume of the p-th batch, h is the maximum delivery volume of a single batch, b is the number of deliveries, yjFor workpieces U subject to zero idle constraintiThe total time of push-up post-processing in machine j, the set of machines belonging to the zero idle state is
Figure BDA0003361318140000071
Step S2: and establishing constraint conditions meeting the problems.
In step S2, the constraint conditions satisfying the problem are established as follows:
the finishing time constraint conditions for starting the processing are as follows: c1，1＝t1，1；
Constraints of the machine 1 processing: ci，1≥Ci-1，1+ti，1，(i＝2，…n)；
Workpiece U1Constraint conditions of processing: c1，j≥C1，j-1+t1，j+yj-1，(j＝2，…m)；
The constraint conditions to be met by the rest of the workpieces and the machine are as follows:
Ci，j≥max{Ci，j-1，Ci-1，j+yj-1}+ti，j，(i＝2，…n；j＝2，…m)；
zero idle constraint: when j is equal to N, Ci-1，j＝Si，j，(i＝2，…n)；
Each machine delay time constraint: y is1＝0，
Figure BDA0003361318140000072
Conveying amount constraint conditions: wp≤h，p＝1，2，…b；
Wherein S isi，jIs a workpiece UiStarting time of machining on machine j, Ci，jIs a workpiece UiTime of completion on machine j, ti，jIs a workpiece UiMachining time on machine j, n being total number of workpieces, m being total number of machines, yjFor workpieces U subject to zero idle constraintiThe total time of push-up post-processing in machine j, the set of machines belonging to the zero idle state is
Figure BDA0003361318140000073
Step S3: and establishing an objective function expected in the actual production process.
In step S3, the objective function f of the maximum completion time is set1Objective function f of maximum delay time2Total inventory cost objective function f3Objective function f of total holdover cost4：
f1＝Cn，m；
f2＝max{max(0，Ci，m-di)}，i＝1，2…n；
Figure BDA0003361318140000081
Figure BDA0003361318140000082
In the formula, Cn，mIs a workpiece UnThe completion time on machine m, i.e. the maximum completion time; ci，mIs a workpiece UiTime of completion on machine m, diIs a workpiece UiRequired delivery time of alphaiIs a workpiece UiStorage cost per unit time, |iIs a workpiece UiActual delivery time ofiIs a workpiece UiThe delay cost per unit time.
Step S4: and constructing a group intelligent algorithm based on the dynamic time warping distance.
The step S4 includes the steps of:
step S41: the parameters of the problem under study are defined.
In step S41, gen is defined as the number of iterations at this time, maxgen is the total number of iterations, popsize is the population size, pcross is the cross probability, pmutation is the variation probability, ω, ε, and δ are all the intervals [0, 1]Random number in (b) the v-th gene of the r individualrv，bmaxIs gene brvThe upper bound of (1) is the total number n of workpieces; bminIs gene brvA lower bound of 1.
Step S42: and encoding the individuals in the group intelligent algorithm.
In step S42, the individual codes are integer codes, specifically, an array with a length of workpiece number is randomly generated, and then the array is sorted according to size to obtain a sorted array which meets the research problem, where the total number of individuals is the population number.
Step S43: and constructing distance expression based on dynamic time warping.
The step S43 includes the steps of:
step S431: calculating the objective function value of different individuals of the ith iteration of the population as
Figure BDA0003361318140000083
The maximum value of each objective function in all individuals is selected and recorded as
Figure BDA0003361318140000084
Selecting the minimum value of each objective function in all individuals and marking as
Figure BDA0003361318140000085
Step S432: the objective function values of different dimensions fall in the [0, 1] interval by min-max normalization, which is as follows:
Figure BDA0003361318140000086
wherein i represents the ith iteration of the population,
Figure BDA0003361318140000087
normalizing the value for the H-th objective function after the individual normalization,
Figure BDA0003361318140000088
represents the H-th objective function value of the individual,
Figure BDA0003361318140000089
the minimum function value of the H-th objective function in the population is represented,
Figure BDA00033613181400000810
the maximum function value of the H-th objective function in the population is represented.
Step S433: calculating the dynamic time warping distance, taking the reciprocal of the dynamic time warping distance as the fitness value of each individual in the group intelligent algorithm, establishing an individual selection strategy according to the fitness value, sequencing the reciprocals of the dynamic time warping distances of all the individuals in the group according to the size, wherein the maximum value is the optimal solution with the highest similarity to the objective function value of the ideal solution in the group, and the objective function value of the ideal solution is the minimum value of all objective functions during single-target optimization.
In step S433, the calculating the dynamic time warping distance specifically includes the following steps:
step S4331: assuming that the function target value min-max normalized sequence of any individual and the minimum value min-max normalized sequence of each target function in the population individuals are respectively
Figure BDA0003361318140000091
Figure BDA0003361318140000092
It is formed into an H pattern matrix MHD, i.e. the distance matrix:
Figure BDA0003361318140000093
elements in a matrix
Figure BDA0003361318140000094
Represents
Figure BDA0003361318140000095
And
Figure BDA0003361318140000096
manhattan distance between;
wherein i represents the ith iteration of the population,
Figure BDA0003361318140000097
h th after standardization for individualsThe value of each of the objective function values,
Figure BDA0003361318140000098
the value normalized by the minimum value of the H-th objective function in the population individuals, M represents the Manhattan distance, and the calculation formula is as follows:
Figure BDA0003361318140000099
step S4332: in the matrix MHD, the continuum of elements may form a plurality of paths, which are normalized paths, and are generally denoted by W: w ═ W1，w2…，wK) H is not more than K is not more than 2H-1, example: path W { (1, 1), (2, 2), (2, 3), (3, 3), (4, 4) }.
The canonical path W needs to meet the following constraint:
(1) boundary conditions: the regular paths being from the lower left corner of the matrix MHD
Figure BDA00033613181400000910
At the beginning, corresponding coordinate point w1To the upper right corner of (1, 1)
Figure BDA00033613181400000911
Ending, corresponding to the coordinate point wK＝(H，H)；
(2) Continuity: if the coordinate is (p, q), the conditions that the coordinate is moved to the next coordinate point (p ', q') need to satisfy are that p '-p is less than or equal to 1, and q' -q is less than or equal to 1, which means that a certain point cannot be skipped and only the coordinate is moved to the next point;
(3) monotonicity: in addition to satisfying the requirement for continuity, it is also necessary to satisfy p '-p.gtoreq.0 and q' -q.gtoreq.0, i.e., W is required to be monotonous.
Step S4333: there are many regular paths that satisfy the condition, wherein the path with the minimum regular cost is:
Figure BDA00033613181400000912
wherein K is the number of passing points, wk' is a coordinate point wkSelecting a path to minimize the final total distance according to the corresponding value in the matrix MHD, wherein the total distance is used for measuring the similarity of the two sequences, and the smaller the value is, the higher the similarity is.
And calculating the accumulated distance D in a manner of accumulating from the lower left corner to the upper right corner of the distance matrix MHD, and accumulating the distances of the passing points to obtain the accumulated distance D, wherein the calculation formula is as follows:
Figure BDA0003361318140000101
wherein D (p-1, q) represents the accumulated distance when the vehicle travels to the point (p-1, q), D (p, q-1) represents the accumulated distance when the vehicle travels to the point (p, q-1), and D (p-1, q-1) represents the accumulated distance when the vehicle travels to the point (p-1, q-1); initial conditions
Figure BDA0003361318140000102
Through iteration, the cumulative distance D (H, H), i.e. the total distance mentioned above, can be finally obtained, and the cumulative distance D (H, H) is the dynamic time warping distance DTW (P, Q), and the path that is passed is also the path with the minimum warping cost.
Step S44: and taking the reciprocal of the dynamic time warping distance as the fitness value of the individual in the group intelligent algorithm, and selecting the strategy to carry out the selection operation of the individual in the algorithm according to the fitness value.
The step S44 includes the steps of:
step S441: and (5) initializing a population, randomly generating the population with the size of popsize, and starting iteration when the iteration number i is 1.
Step S442: and solving each objective function value of the population.
Step S443: and calculating the fitness value, wherein the dynamic time warping distance is used as an individual selection strategy, and the reciprocal of the dynamic time warping distance is the size of the fitness value.
Step S444: and updating the external file, when two or more objective function values are superior to the objective function value of the parent population, saving the two or more objective function values, and finally removing the same individual.
Step S445: selecting by adopting a binary tournament method, randomly selecting two individuals from a parent population each time, wherein the probability of the individuals being selected is the same, determining the selected individuals according to the fitness value of each individual, selecting the individuals with large fitness values to enter a child population, and repeating for multiple times until the child population reaches the size of the parent population.
Step S446: performing cross operation, randomly selecting two individuals from a population, and inheriting good aspects of old individuals to new individuals through exchange combination of the individuals so as to generate new excellent individuals; firstly, a real number crossing method is adopted for crossing, and then the crossed individual genes are sequenced from small to large; wherein the crossing mode of the x-th individual and the y-th individual at the z position is as follows:
bxz＝bxz(1-ω)+byzω；
byz＝byz(1-ω)+bxzω；
in the formula, bxzIs the z-th gene of the x-th individual, byzIs the z-th gene of the y-th individual, and omega is the interval [0, 1%]The random number in (c).
Step S447: carrying out mutation operation, randomly selecting an individual from the population, firstly selecting any point in the individual for mutation, and then sequencing the mutated genes according to the sequence from small to large; wherein the variation pattern of the r-th individual at the v position is:
Figure BDA0003361318140000111
in the formula, brvIs the v-th gene of the r individual, bmaxIs gene brvThe upper bound of (1) is the total number n of workpieces; bminIs gene brvA lower bound of 1; f (g) δ (1-gen/maxgen)2Both epsilon and delta are the interval [0, 1]]The random number in the table, gen is the number of iterations at this time, and maxgen is the total number of iterations.
Step S448: and when i is less than maxgen, i is i +1, jumping to the step S443, otherwise, jumping out of the loop, and stopping the algorithm.
Step S5: and (4) finishing iterative optimization according to the dynamic time warping distance, finding out the set of the optimal solution, and obtaining the final scheduling scheme.
The embodiment also provides a multi-target mixed zero-idle replacement flow shop scheduling system, which comprises a memory, a processor and computer program instructions stored on the memory and capable of being executed by the processor, wherein when the computer program instructions are executed by the processor, the method steps can be implemented.
As will be appreciated by one skilled in the art, embodiments of the present application may be provided as a method, system, or computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.
The present application is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the application. It will be understood that each flow and/or block of the flow diagrams and/or block diagrams, and combinations of flows and/or blocks in the flow diagrams and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
The foregoing is directed to preferred embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow. However, any simple modification, equivalent change and modification of the above embodiments according to the technical essence of the present invention are within the protection scope of the technical solution of the present invention.

Claims (10)

1.一种多目标混合零空闲置换流水车间调度方法，其特征在于，包括以下步骤：1. a multi-objective mixed zero idle replacement flow shop scheduling method, is characterized in that, comprises the following steps: 步骤S1：对多目标混合零空闲置换流水车间调度问题进行描述；Step S1: describe the multi-objective hybrid zero-idle replacement flow shop scheduling problem; 步骤S2：建立满足所述问题的约束条件；Step S2: establish constraints that satisfy the problem; 步骤S3：建立实际生产过程中所期望的目标函数；Step S3: establishing the desired objective function in the actual production process; 步骤S4：构建基于动态时间规整距离的群体智能算法；Step S4: constructing a swarm intelligence algorithm based on dynamic time warping distance; 步骤S5：依据动态时间规整距离完成迭代寻优，找出最优解的集合，得到最终的调度方案。Step S5: Complete iterative optimization according to the dynamic time warping distance, find the set of optimal solutions, and obtain the final scheduling scheme. 2.根据权利要求1所述的一种多目标混合零空闲置换流水车间调度方法，其特征在于，所述步骤S1中，设n为总工件数量，m为总机器数量，U＝{U1，U2，…Ui，…Un}，U表示工件的加工序列，Ui为序列中位置位于i的工件，fH是第H个目标函数值，yj为受零空闲约束条件时工件Ui在机器j上推后加工的总时间，属于零空闲状态的机器集合为
Figure FDA0003361318130000011
2. A multi-objective hybrid zero-idle replacement flow shop scheduling method according to claim 1, characterized in that, in the step S1, let n be the total number of workpieces, m be the total number of machines, U={U 1 , U 2 ,...U i ,...U n }, U represents the machining sequence of the workpiece, U i is the workpiece at position i in the sequence, f H is the H-th objective function value, y j is subject to the zero idle constraint When the workpiece U i is pushed back and processed on machine j, the set of machines belonging to the zero idle state is
Figure FDA0003361318130000011
 3.根据权利要求2所述的一种多目标混合零空闲置换流水车间调度方法，其特征在于，所述步骤S2中，建立满足所述问题的约束条件如下：3. a kind of multi-objective hybrid zero-idle replacement flow shop scheduling method according to claim 2, is characterized in that, in described step S2, establish the constraint condition that satisfies described problem as follows: 开始加工的完工时间约束条件为：C1，1＝t1，1；The completion time constraint condition for starting processing is: C 1,1 =t 1,1 ; 机器1加工的约束条件：Ci，1≥Ci-1，1+ti，1，(i＝2，…n)；Constraints of processing by machine 1: C i,1 ≥C i-1,1 +t i,1 , (i=2,...n); 工件U1加工的约束条件：C1，j≥C1，j-1+t1，j+yj-1，(j＝2，…m)；Constraints for the machining of workpiece U 1 : C 1, j ≥ C 1 , j-1 +t 1, j +y j-1 , (j=2,...m); 其余工件和机器需满足的约束条件：Constraints to be met by the remaining workpieces and machines: Ci，j≥max{Ci，j-1，Ci-1，j+yj-1}+ti，j，(i＝2，…n；j＝2，…m)；C i,j ≥max{C i,j-1 ,C i-1,j +y j-1 }+t i,j ,(i=2,...n; j=2,...m); 零空闲约束：当j∈M时，Ci-1，j＝Si，j，(i＝2，…n)；Zero idle constraint: when j∈M, C i-1, j =S i,j , (i=2,...n); 各机器延迟时间约束：y1＝0，Each machine delay time constraint: y 1 =0,
Figure FDA0003361318130000012
Figure FDA0003361318130000012
 其中，Si，j为工件Ui在机器j上的开始加工时间，Ci，j为工件Ui在机器j上的完工时间，ti，j为工件Ui在机器j上的加工时间，n为总工件数量，m为总机器数量，yj为受零空闲约束条件时工件Ui在机器j上推后加工的总时间，属于零空闲状态的机器集合为
Figure FDA0003361318130000013
Among them, S i,j is the start processing time of workpiece U i on machine j, C i,j is the completion time of workpiece U i on machine j, t i,j is the processing time of workpiece U i on machine j , n is the total number of workpieces, m is the total number of machines, y j is the total time that the workpiece U i is pushed back on the machine j under the zero-idle constraint, and the set of machines belonging to the zero-idle state is
Figure FDA0003361318130000013
 4.根据权利要求3所述的一种多目标混合零空闲置换流水车间调度方法，其特征在于，所述步骤S3中，设最大完工时间的目标函数f1，最大延期时间的目标函数f2，总库存成本的目标函数f3，总托期成本的目标函数f4：4. a kind of multi-objective hybrid zero-idle replacement flow shop scheduling method according to claim 3, is characterized in that, in described step S3, set the objective function f 1 of maximum completion time, the objective function f 2 of maximum delay time , the objective function f 3 of total inventory cost, the objective function f 4 of total consignment cost: f1＝Cn，m；f 1 =C n,m ; f2＝max{max(0，Ci，m-di)}，i＝1，2…n；f 2 =max{max(0, C i, m -d i )}, i=1, 2...n;
Figure FDA0003361318130000021
Figure FDA0003361318130000021
Figure FDA0003361318130000022
Figure FDA0003361318130000022
 式中，Cn，m为工件Un在机器m上的完工时间，即最大完工时间；Ci，m为工件Ui在机器m上的完工时间，di为工件Ui的要求交货时间，αi为工件Ui单位时间内的存放费用，li为工件Ui的实际交货时间，εi为工件Ui单位时间内的延时费用。In the formula, C n,m is the completion time of the workpiece U n on the machine m, that is, the maximum completion time; C i,m is the completion time of the workpiece U i on the machine m, and d i is the required delivery of the workpiece U i . time, α i is the storage cost of the workpiece U i per unit time, l i is the actual delivery time of the workpiece U i , and ε i is the delay cost of the workpiece U i per unit time. 5.根据权利要求4所述的一种多目标混合零空闲置换流水车间调度方法，其特征在于，所述步骤S4包括以下步骤：5. a kind of multi-objective hybrid zero-idle replacement flow shop scheduling method according to claim 4, is characterized in that, described step S4 comprises the following steps: 步骤S41：定义所研究问题参数；Step S41: define the parameters of the research problem; 步骤S42：对群体智能算法中个体进行编码；Step S42: coding the individuals in the swarm intelligence algorithm; 步骤S43：构建基于动态时间规整的距离表达；Step S43: constructing a distance expression based on dynamic time warping; 步骤S44：以动态时间规整距离的倒数作为群体智能算法中个体的适应度值，依据适应度值选择策略开展算法中个体的选择操作。Step S44: Use the inverse of the dynamic time warping distance as the fitness value of the individual in the swarm intelligence algorithm, and carry out the selection operation of the individual in the algorithm according to the fitness value selection strategy. 6.根据权利要求5所述的一种多目标混合零空闲置换流水车间调度方法，其特征在于，所述步骤S41中，定义gen为此时的迭代数，maxgen为总的迭代次数，popsize为种群大小，pcross为交叉概率，pmutation为变异概率，ω、ε、δ都为区间[0，1]内的随机数，第r个个体的第v位基因为brv，bmax为基因brv的上界，即为工件总数n；bmin为基因brv的下界，其值为1；6. a kind of multi-objective hybrid zero-idle replacement flow shop scheduling method according to claim 5, is characterized in that, in described step S41, define gen as the iteration number at this moment, maxgen is the total iteration number, and popsize is Population size, pcross is the probability of crossover, pmutation is the probability of mutation, ω, ε, δ are random numbers in the interval [0, 1], the vth gene of the rth individual is b rv , and b max is the gene b rv The upper bound of , is the total number of workpieces n; b min is the lower bound of gene b rv , and its value is 1; 所述步骤S42中，个体编码采用整数编码，具体为先随机产生一个长度为工件数的数组，再将其按照大小排序得出一个符合研究问题的排列数组，个体总数为种群数目。In the step S42, the individual coding adopts integer coding, specifically, first randomly generating an array whose length is the number of workpieces, and then sorting it according to the size to obtain an arrangement array that conforms to the research problem, and the total number of individuals is the population number. 7.根据权利要求6所述的一种多目标混合零空闲置换流水车间调度方法，其特征在于，所述步骤S43包括以下步骤：7. a kind of multi-objective hybrid zero-idle replacement flow shop scheduling method according to claim 6, is characterized in that, described step S43 comprises the following steps: 步骤S431：计算种群迭代第i次的不同个体的目标函数值为
Figure FDA0003361318130000023
选出所有个体中各个目标函数的最大值，记为
Figure FDA0003361318130000024
选出所有个体中各个目标函数的最小值，记为
Figure FDA0003361318130000025
Step S431: Calculate the objective function value of different individuals in the ith iteration of the population as
Figure FDA0003361318130000023
Select the maximum value of each objective function in all individuals, denoted as
Figure FDA0003361318130000024
Select the minimum value of each objective function in all individuals, denoted as
Figure FDA0003361318130000025
 步骤S432：通过min-max标准化将不同量纲的目标函数值落在[0，1]区间，标准化方法如下：Step S432: The objective function values of different dimensions are placed in the [0, 1] interval through min-max standardization, and the standardization method is as follows:
Figure FDA0003361318130000031
Figure FDA0003361318130000031
 其中，i表示种群迭代第i次，
Figure FDA0003361318130000032
为个体标准化后的第H个目标函数标准化值，
Figure FDA0003361318130000033
表示个体的第H个目标函数值，
Figure FDA0003361318130000034
表示种群中第H个目标函数的最小函数值，
Figure FDA0003361318130000035
表示种群中第H个目标函数的最大函数值；Among them, i represents the ith iteration of the population,
Figure FDA0003361318130000032
is the standardized value of the H-th objective function after individual standardization,
Figure FDA0003361318130000033
represents the H-th objective function value of the individual,
Figure FDA0003361318130000034
represents the minimum function value of the Hth objective function in the population,
Figure FDA0003361318130000035
Represents the maximum function value of the Hth objective function in the population; 步骤S433：计算动态时间规整距离，将其倒数作为群体智能算法中个体的适应度值，建立依据适应度值的个体选择策略，把种群中各个体的动态时间规整距离的倒数按照大小排序，最大的值即为种群中与理想解目标函数值相似度最高的最优解，此处理想解目标函数值为单目标优化时各目标函数的最小值。Step S433: Calculate the dynamic time warping distance, use its reciprocal as the fitness value of the individual in the swarm intelligence algorithm, establish an individual selection strategy based on the fitness value, and sort the inverse of the dynamic time warping distance of each individual in the population according to size, the largest The value of is the optimal solution with the highest similarity to the ideal solution objective function value in the population, where the ideal solution objective function value is the minimum value of each objective function in single-objective optimization. 8.根据权利要求7所述的一种多目标混合零空闲置换流水车间调度方法，其特征在于，所述步骤S433中，计算动态时间规整距离具体包括以下步骤：8. a kind of multi-objective hybrid zero-idle replacement flow shop scheduling method according to claim 7, is characterized in that, in described step S433, calculating dynamic time regularization distance specifically comprises the following steps: 步骤S4331：假设任意一个个体的函数目标值min-max标准化后序列和种群个体中各个目标函数的最小值min-max标准化后序列分别为
Figure FDA0003361318130000036
Figure FDA0003361318130000037
将其构成一个H×H型式矩阵MHD，即距离矩阵：Step S4331: Suppose that the normalized sequence of the function target value min-max of any individual and the normalized sequence of the minimum value min-max of each objective function in the individual population are respectively:
Figure FDA0003361318130000036
Figure FDA0003361318130000037
It is formed into an H×H type matrix MHD, that is, the distance matrix:
Figure FDA0003361318130000038
Figure FDA0003361318130000038
 矩阵中的元素
Figure FDA0003361318130000039
代表
Figure FDA00033613181300000310
和
Figure FDA00033613181300000311
之间的曼哈顿距离；elements in a matrix
Figure FDA0003361318130000039
represent
Figure FDA00033613181300000310
and
Figure FDA00033613181300000311
Manhattan distance between; 其中，i代表种群迭代第i次，
Figure FDA00033613181300000312
为个体标准化后的第H个目标函数值，
Figure FDA00033613181300000313
为种群个体中第H个目标函数的最小值标准化后的值，M表示曼哈顿距离，其计算公式为：Among them, i represents the ith iteration of the population,
Figure FDA00033613181300000312
is the H-th objective function value after individual standardization,
Figure FDA00033613181300000313
is the normalized value of the minimum value of the Hth objective function in the population individuals, M represents the Manhattan distance, and its calculation formula is:
Figure FDA00033613181300000314
Figure FDA00033613181300000314
 步骤S4332：所述矩阵MHD中，各元素的连续集形成多条路径，该路径为规整后的路径，用W表示：W＝(w1，w2…，wK)，H≤K≤2H-1；Step S4332: In the matrix MHD, the continuous set of each element forms a plurality of paths, and the path is a regularized path, which is represented by W: W=(w 1 , w 2 . . . , w K ), H≤K≤2H -1; 规整路径W符合如下约束条件：The regularized path W meets the following constraints: (1)边界条件：规整路径从矩阵MHD左下角的
Figure FDA00033613181300000315
开始，对应坐标点w1＝(1，1)，到右上角的
Figure FDA0003361318130000041
结束，对应坐标点wK＝(H，H)；(1) Boundary conditions: The regular path starts from the lower left corner of the matrix MHD
Figure FDA00033613181300000315
Start, corresponding to the coordinate point w 1 = (1, 1), to the upper right corner
Figure FDA0003361318130000041
End, the corresponding coordinate point w K = (H, H); (2)连续性：若此时坐标为(p，q)，则行至下一个坐标点(p′，q′)需要满足的条件为p′-p≤1，q′-q≤1，相当于不能跳过某个点，只能行至紧临的点；(2) Continuity: If the coordinates are (p, q) at this time, then the conditions that need to be satisfied to go to the next coordinate point (p', q') are p'-p≤1, q'-q≤1, It is equivalent to not skipping a certain point, and can only go to the next point; (3)单调性：满足p′-p≥0，q′-q≥0，即要求W是单调的；(3) Monotonicity: satisfying p'-p≥0, q'-q≥0, that is, requiring W to be monotonic; 步骤S4333：满足条件的规整路径有很多条，其中规整代价最小的路径为：Step S4333: There are many regularized paths that satisfy the condition, and the path with the smallest regularization cost is:
Figure FDA0003361318130000042
Figure FDA0003361318130000042
 式中，K为经过点的个数，wk′为坐标点wk在矩阵MHD中所对应的值，选择一条路径使得最后得到的总距离最小，该总距离衡量着两序列的相似度，其值越小相似度越高；In the formula, K is the number of passing points, w k ′ is the value corresponding to the coordinate point w k in the matrix MHD, and a path is selected to minimize the final total distance, which measures the similarity of the two sequences, The smaller the value, the higher the similarity; 计算累计距离D，累计距离计算方式为从距离矩阵MHD的左下角累加至右上角，将其经过点的距离累加起来得到累计距离D，计算公式为：Calculate the cumulative distance D. The calculation method of the cumulative distance is to accumulate from the lower left corner of the distance matrix MHD to the upper right corner, and add up the distances of the points it passes through to obtain the cumulative distance D. The calculation formula is:
Figure FDA0003361318130000043
Figure FDA0003361318130000043
 其中，D(p-1，q)代表行驶至(p-1，q)点时的累计距离，D(p，q-1)代表行驶至(p，q-1)点时的累计距离，D(p-1，q-1)代表行驶至(p-1，q-1)点时的累计距离；初始条件
Figure FDA0003361318130000044
通过迭代最终求出累计距离D(H，H)，此距离即上述所说的总距离，累计距离D(H，H)即为动态时间规整距离DTW(P，Q)，所经过的路径也是规整代价最小的路径。Among them, D(p-1, q) represents the cumulative distance when driving to (p-1, q) point, D(p, q-1) represents the cumulative distance when driving to (p, q-1) point, D(p-1, q-1) represents the cumulative distance when traveling to point (p-1, q-1); initial condition
Figure FDA0003361318130000044
The cumulative distance D(H, H) is finally obtained through iteration, which is the total distance mentioned above, and the cumulative distance D(H, H) is the dynamic time warping distance DTW(P, Q), and the traversed path is also Regularize the path with the least cost. 9.根据权利要求8所述的一种多目标混合零空闲置换流水车间调度方法，其特征在于，所述步骤S44包括以下步骤：9. The multi-objective hybrid zero-idle replacement flow shop scheduling method according to claim 8, wherein the step S44 comprises the following steps: 步骤S441：种群初始化，随机产生大小为popsize的种群，迭代次数i＝1，开始迭代；Step S441: population initialization, randomly generating a population with a size of popsize, the number of iterations i=1, and starting the iteration; 步骤S442：求解出种群的各个目标函数值；Step S442: solve each objective function value of the population; 步骤S443：计算适应度值，采用动态时间规整距离作为个体选择策略，动态时间规整距离的倒数即为适应度值大小；Step S443: Calculate the fitness value, adopt the dynamic time warping distance as the individual selection strategy, and the inverse of the dynamic time warping distance is the fitness value; 步骤S444：更新外部档案，当有两个及以上目标函数值优于父代种群目标函数值时，则保存下来，最后再将相同个体去掉；Step S444: update the external file, when there are two or more objective function values that are better than the parent population objective function value, save them, and finally remove the same individuals; 步骤S445：采用二元锦标赛法进行选择操作，从父代种群中每次随机选择两个个体，个体被选择的概率是相同的，根据每个个体的适应度值来确定选择的个体，适应度值大的被选择下来进入到子代种群，重复多次，直到子代种群规模达到父代种群规模的大小；Step S445: The binary tournament method is used for the selection operation, and two individuals are randomly selected from the parent population at a time. The probability of individuals being selected is the same, and the selected individual is determined according to the fitness value of each individual. The larger value is selected and entered into the descendant population, and repeated many times until the size of the descendant population reaches the size of the parent population; 步骤S446：进行交叉操作，从种群中随机选择两个个体，通过个体的交换组合，将旧的个体好的方面遗传给新的个体，从而产生新的优异个体；先采用实数交叉法进行交叉，再将交叉后的个体基因按从小到大的顺序排序；其中第x个个体和第y个个体在z位置上的交叉方式为：Step S446: Perform a crossover operation, randomly select two individuals from the population, and inherit the good aspects of the old individuals to the new individuals through the exchange and combination of individuals, thereby generating new excellent individuals; firstly, the real number crossover method is used to cross over, Then, the individual genes after the crossover are sorted in ascending order; the crossover method of the xth individual and the yth individual at the z position is: bxz＝bxz(1-ω)+byzω；b xz =b xz (1-ω)+b yz ω; byz＝byz(1-ω)+bxzω；b yz = b yz (1-ω)+b xz ω; 式中，bxz为第x个个体的第z位基因，byz为第y个个体的第z位基因，ω为区间[0，1]内的随机数；In the formula, b xz is the zth gene of the xth individual, byz is the zth gene of the yth individual, and ω is a random number in the interval [0, 1]; 步骤S447：进行变异操作，从种群中随机选择一个个体，先选择个体中的任意一点进行变异，再将变异后的基因按照从小到大的顺序排序；其中第r个个体在v位置上的变异方式为：Step S447: Perform mutation operation, randomly select an individual from the population, first select any point in the individual to mutate, and then sort the mutated genes in ascending order; the mutation of the r-th individual at position v The way is:
Figure FDA0003361318130000051
Figure FDA0003361318130000051
 式中，brv为第r个个体的第v位基因，bmax为基因brv的上界，即为工件总数n；bmin为基因brv的下界，其值为1；f(g)＝δ(1-gen/maxgen)2，ε、δ都为区间[0，1]内的随机数，gen为此时的迭代数，maxgen为总的迭代次数；In the formula, b rv is the v-th gene of the r-th individual, b max is the upper bound of gene b rv , which is the total number of workpieces n; b min is the lower bound of gene b rv , and its value is 1; f(g) =δ(1-gen/maxgen) 2 , both ε and δ are random numbers in the interval [0, 1], gen is the number of iterations at this time, and maxgen is the total number of iterations; 步骤S448：当i＜maxgen时，i＝i+1，跳到S443步骤，否则跳出循环，算法停止。Step S448: when i<maxgen, i=i+1, skip to step S443, otherwise, jump out of the loop, and the algorithm stops. 10.一种多目标混合零空闲置换流水车间调度系统，其特征在于，包括存储器、处理器以及存储于存储器上并能够被处理器运行的计算机程序指令，当处理器运行该计算机程序指令时，能够实现如权利要求1-9所述的方法步骤。10. A multi-objective hybrid zero-idle replacement flow shop scheduling system is characterized in that, comprising a memory, a processor and a computer program instruction stored on the memory and can be run by the processor, when the processor runs the computer program instruction, The method steps of claims 1-9 can be implemented.
CN202111367979.2A 2021-11-18 2021-11-18 Multi-target mixed zero-idle replacement flow shop scheduling method and system Active CN114066065B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202111367979.2A CN114066065B (en) 2021-11-18 2021-11-18 Multi-target mixed zero-idle replacement flow shop scheduling method and system

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202111367979.2A CN114066065B (en) 2021-11-18 2021-11-18 Multi-target mixed zero-idle replacement flow shop scheduling method and system

Publications (2)

Publication Number Publication Date
CN114066065A true CN114066065A (en) 2022-02-18
CN114066065B CN114066065B (en) 2024-07-12

Family

ID=80277742

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202111367979.2A Active CN114066065B (en) 2021-11-18 2021-11-18 Multi-target mixed zero-idle replacement flow shop scheduling method and system

Country Status (1)

Country Link
CN (1) CN114066065B (en)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114859832A (en) * 2022-04-24 2022-08-05 合肥工业大学 A T beam production control method and system

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105809344A (en) * 2016-03-07 2016-07-27 浙江财经大学 Hyper-heuristic algorithm based ZDT flow shop job scheduling method
CN109669423A (en) * 2019-01-07 2019-04-23 福州大学 The method that part processes optimal scheduling scheme is obtained based on multiple target grey wolf algorithm is improved
CN110221585A (en) * 2019-06-14 2019-09-10 同济大学 A kind of energy-saving distribution control method considering plant maintenance for hybrid flowshop
WO2021103891A1 (en) * 2019-11-26 2021-06-03 北京工业大学 Method for scheduling hybrid flow shop comprising variable parameter continuous processing and intermittent processing

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105809344A (en) * 2016-03-07 2016-07-27 浙江财经大学 Hyper-heuristic algorithm based ZDT flow shop job scheduling method
CN109669423A (en) * 2019-01-07 2019-04-23 福州大学 The method that part processes optimal scheduling scheme is obtained based on multiple target grey wolf algorithm is improved
CN110221585A (en) * 2019-06-14 2019-09-10 同济大学 A kind of energy-saving distribution control method considering plant maintenance for hybrid flowshop
WO2021103891A1 (en) * 2019-11-26 2021-06-03 北京工业大学 Method for scheduling hybrid flow shop comprising variable parameter continuous processing and intermittent processing

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
杜士卿: "最佳觅食算法求解多目标混合流水车间调度问题", 福州大学学报(自然科学版)., vol. 48, no. 3, 8 May 2020 (2020-05-08), pages 326 - 332 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114859832A (en) * 2022-04-24 2022-08-05 合肥工业大学 A T beam production control method and system

Also Published As

Publication number Publication date
CN114066065B (en) 2024-07-12

Similar Documents

Publication Publication Date Title
CN108053119B (en) An improved particle swarm optimization method for solving the zero-waiting flow shop scheduling problem
CN110221585A (en) A kind of energy-saving distribution control method considering plant maintenance for hybrid flowshop
CN112286152B (en) Distributed flow shop scheduling method and system with batch delivery constraint
CN110458326B (en) Mixed group intelligent optimization method for distributed blocking type pipeline scheduling
US7890205B2 (en) Technique for determining processing sequence of steel plates
CN113792494B (en) Multi-objective flexible job shop scheduling method based on migratory bird flock algorithm and cross fusion
CN113902173B (en) Flexible job shop scheduling method based on improved wolf&#39;s swarm algorithm
CN112668789A (en) Self-adaptive batch scheduling method for flexible operation workshop preparation process
CN112147960A (en) Method and device for optimal scheduling of flexible manufacturing system
CN111290283A (en) A single machine scheduling method for additive manufacturing for selective laser melting process
CN114066065A (en) A multi-objective hybrid zero-idle replacement flow shop scheduling method and system
CN110750079A (en) Hybrid flow shop scheduling optimization method allowing process jump
Zhang et al. A matrix-cube-based estimation of distribution algorithm for blocking flow-shop scheduling problem with sequence-dependent setup times
Hertzberg et al. Finding motifs in promoter regions
CN115935616A (en) Multi-objective optimization method for scheduling of sequence-dependent flow shop groups of consistent batches
Gabriel et al. Tiberius: end-to-end deep learning with an HMM for gene prediction
CN114819728A (en) Flexible workshop production scheduling method capable of self-adaptive local search
CN118863501A (en) Workshop scheduling method, device, storage medium and equipment based on adaptive genetic algorithm
CN113741369B (en) A hybrid flow shop scheduling optimization method
CN104021425A (en) Meme evolutionary algorithm for solving advancing-delay scheduling problem
CN117555305A (en) NSGAII-based multi-target variable sub-batch flexible workshop job scheduling method
CN111160711A (en) A Batch Scheduling Method for Parallel Machines Based on Ant Colony Algorithm
CN117077975A (en) Distributed heterogeneous flow shop scheduling method based on hybrid initialization memetic algorithm
CN114859832A (en) A T beam production control method and system
CN114254721B (en) Flexible job shop scheduling method and equipment with interval gray processing time

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
GR01 Patent grant
GR01 Patent grant