The content of the invention
Existing scheduling method is produced for heavy mechanical equipment excessively to idealize, the scheduling time is short, storage capacity raw material is utilizedThe low problem of rate, the present invention provides the complex scene scheduling method and system based on quantum evolutionary algorithm, applied to storage capacityConstraint, wire body obstruction produce scheduling field for the heavy mechanical equipment of the complex scene of representative.
To achieve these goals, the present invention is adopted the following technical scheme that：
Complex scene scheduling method based on quantum evolutionary algorithm, comprises the following steps：
Step (1)：Quantum population is initialized：Including initialization quantum population evolutionary generation, initialization quantum bit codingWith initialization quantum chromosomes quantity；
Step (2)：Quantum scheduling and Fitness analysis：Set up quantum object function, it is considered to the production of heavy mechanical equipmentUnder the constraints of manufacturing environment, quantum object function is solved；The binary system control of quantum population generation object functionVariable, variable is controlled according to the binary system of generation, corresponds to the order of work order task, carries out scheduling, is calculated according to scheduling orderThe fitness value of the deadline, as quantum of whole heavy mechanical equipment work order；
Step (3)：Compare fitness value, optimal solution is determined by minimum fitness value；Preserve optimal solution；Judge whether toUp to termination condition, optimal solution is exported if termination condition is reached；Step (4) is jumped to if not up to termination condition；
Step (4)：Quantum updates：Quantum population is updated using Quantum rotating gate；Return to step (2) is recalculatedThe fitness value of quantum, continues optimizing.
The heavy mechanical equipment, including：Large-scale blade motor, motorbus engine or hoisting machinery etc., it is used to addConstruction equipment typically purchases one or two because expensive, easily occurs wire body choking phenomenon in process of production.
The complex scene refers to the production and manufacturing environment of heavy mechanical equipment：Produce raw material limited space and line side storehouseIt is several levels to hold stored number, raw material conveying arrangement limited amount and be a several levels；Wire body choking phenomenon takes place frequently.
Quantum population is initialized in the step (1), is comprised the following steps：
Step (1-1)：Initialize evolutionary generation t=0；
Step (1-2)：Initialize quantum bit coding：By determining the selected machine of heavy mechanical equipment work order taskAnd the order for processing of reaching the standard grade, to obtain more excellent quantum object function.
Need to define two variables in initialization procedure：
First variable represents whether work order i j-th of process processes on k-th of machine, is designated as variable aijkIf,Select machine k then variable aijkValue is 1, the variable a if non-selected machine kijkValue is 0；
Second variable represents that the processing sequence of work order i j-th of process is l, is designated as variable bijl, when work order i jthIndividual process start to reach the standard grade at l-th of processing sequence processing when, variable bijl1 is designated as, otherwise variable bijlFor 0.
Make A=[a111,a112..., aijk...], whether j-th of process for depositing work order i adds on k-th of machineThe state of work；
Make B=[b111,b112..., bijl...], for whether depositing work order i j-th of process in l-th of processing sequencePlace starts to reach the standard grade the state of processing；
Sequential concatenation is carried out to A and B, the quantum bit coding of multiple heavy mechanical equipment work orders is obtained, is designated as X.
X=A+B=[a111,a112..., aijk,…,b111,b112..., bijl,…] (1)
Wherein, the "+" order of representation splicing in formula (1), aijk、bijl0 is taken respectively or takes 1, X to be binary sequence.
Work order task, process equipment and manufacturing procedure information are contained in binary sequence X by the coded system.
Specifically, a quantum bit position is expressed as：The state representation of quantum bit is：|ψ>=α | 0 ＞+β | 1>,
Wherein | 0 ＞ and | 1 ＞ represents two kinds of basic status of quantum bit；α and β is plural number, represents the general of qubit stateRate width, α2Probability, the β of state 0 are in for quantum bit2The amplitude and angle of the probability of state 1, α and β are in for quantum bitRandom value, but meet | α |2+|β|2=1；
Q is made to represent chromosome, then the quantum chromosomes that m quantum bit position is represented are
Wherein, | αi|2+|βi|2=1, i=1,2 ..., m；M represents individual chromosome quantum bit bit length, m calculatingMethod is as follows：
M=work orders total task number × number of devices+work order total task number2 (3)
Then formula (1) is expressed as with quantum bit：
Step (1-3)：Initialize population：Chromosome population is associated with evolutionary generation t, if the quantum chromosomes kind in t generationsGroup be：
Then formula (2) is converted into：
In formula, j represents chromosome number, j=1,2 ... n, and n is that chromosome population scale is total chromosome number amount.
In single iteration, chromosome quantitative is more, is more readily obtained globally optimal solution, but calculating speed is slow.
Chromosome quantitative is fewer, and calculating speed is faster, but is easily trapped into locally optimal solution.
In general, chromosome quantitative is arranged between 40-100, and the present invention takes n=60.
Then formula (4) is converted into after being associated with evolutionary generation t：
Quantum fitness is quantum object function in the step (2), the scheduling strategy used under limited space sceneFor positive row's strategy, it is expected that the order of processing is delivered goods as early as possible.
Quantum object function：
Minf (X)=Min ∑sAll work orders(heavy mechanical equipment work order planned end time-heavy mechanical equipment work order planTime started) (8)
X is referred to as the binary system control variable of object function, is one group of binary sequence, the quantum target function value is smallerBetter.
Quantum fitness calculate be by according to individual chromosome value obtain work order task each machine reach the standard grade processing whenBetween and downtime, also referred to as work order task order according to given by chromosome carries out the process of scheduling.
Numerical value one work order task of correspondence in individual chromosome in chromosome population per dimension, each chromosome bagThe current order information for needing to be arranged work order task is contained.
Process time is determined by the machine models or warehouse compartment type and the work order product attribute of work order task processed, is processedTime is the Given information of scheduling.
The calculating of quantum object function needs to consider the pact of the production and manufacturing environment of heavy mechanical equipment in the step (2)Beam condition.
The constraints is specially：During selection machine determines work order process time, big machinery is consideredPriority logical relation of the equipment work order task in work order process, work order task is once can not interrupt, i.e., single workSingle task can not in two times be processed across the unavailable time of machine, and two warehouse compartments can not be also assigned in a process gap and are kept in,The single machine same time can only process a work order task, and machine only processes workpiece within the available period.
The constraints is expressed as follows by formula：
In formula (9), aijkRepresent work order i j-th of process whether the state being processed in k-th of machine；bijlTableShow work order i j-th of process whether the state being processed in l processing sequences, machining state takes 0 or takes 1；
Referred to as sequential operator, represents serial number of each element in array,
bijThe institute of work order task processing sequence for depositing i-th of work order, j-th of process is stateful,For array bijTransposition,Expression takes bijMiddle state is the serial number corresponding to 1 element,Dimension and bijIt is identical；
bi(j+1)The institute of work order task processing sequence for depositing+1 process of i-th of work order jth is stateful,ForArray bi(j+1)Transposition,Expression takes bi(j+1)Middle state is the serial number corresponding to 1 element,'sDimension and bi(j+1)It is identical.
First constraint aijk, bijl=0 or 1, all i, j, k and l is set up, it is ensured that chromosome coding it is feasibleProperty；
Second constraintIt ensure that work order task order is appointed according to work orderThe logical order of business processing is processed；
3rd constraintAll work order task orders are set up, it is ensured that all work ordersTask is only processed once；
4th constraintAll i and j are set up, it is ensured that single work order task is only in a machineIt is processed on device.
The Fitness analysis of the step (2) is controlled to become by quantum chromosomes population Q (t) binary systems for generating object functionMeasure X,
Obtained by formula (7) with formula (10),
In formula (11)A binary bit in variable is controlled for binary system,Value：
Wherein γ is random number, takes the arbitrary value in [0,1].
Variable X is controlled according to the binary system of generation, the order of work order task is corresponded to, scheduling is carried out, according to scheduling orderThe deadline for calculating whole heavy mechanical equipment work order is the fitness value of quantum.
The scheduling principle：Scheduling comprising inventory limitation scene uses the plug hole scheduling method with time window.In schedulingDuring, a dimension will be regarded the time as, regard all occupied machine resources, each warehouse compartment and conveying arrangement as appearanceDevice, every machine, warehouse compartment and conveying arrangement are with an available time window in finite time.According to the actual feelings of production lineCondition, increases the storage process in line side storehouse between two-step, regard available machines used as line side Kuku position, line side storehouse storage process instituteAn insignificant time interval, such as 1 second are set to the time.Increase corresponding work order according to the difference of work order simultaneously to appointBusiness.
The time window that original production can be put in storage is started shooting or processed according to the machine of producing line calendar and initialized, warehouse compartmentAccording to pot life initialization time window, time window includes one or more pot lifes section, the machine in each pot life sectionDevice or warehouse compartment are used for processing or depositing a workpiece.
Scheduling step is as follows in the step (2)：
Step (201)：Quantum is decoded：Incoming single quantum is resolved to the scheduling order of work order task；
Step (202)：Scheduling queue L0 is treated in foundation, and the order deposit of decoded workman's task scheduling is treated into scheduling queue L0In；
Step (203)：Judgement treats whether scheduling queue L0 is empty, if so, then scheduling is finished, calculates fitness value, terminates；If it is not, the head work order task for treating scheduling queue L0 is then taken, into step (204)；
Step (204)：Whether judge current work order task is assembling work order；If being put into step (205)；Just enter if notEnter step (206)；
Step (205)：Judge whether workpiece needed for specifying warehouse compartment is complete, if being put into step (206)；It is put into if notStep (207)；
Step (206)：Whether judge possible schedule fragment is empty；Determine that if not it is available and its and start process time, moreNew possible schedule fragment set；Foundation is had been lined up arranging L1, and current drained work order task is put into L1 afterbody, return to step(203)；If so, being put into step (208)；
Step (207)：Judgement treats whether scheduling queue L0 is empty, if so, then scheduling fails, fitness value is set to positive nothingThoroughly, terminate；Just take if not and treat that scheduling queue L0 head work order task, for current work order task, then appoints the work order just handledBusiness is put into the head position for treating scheduling queue L0, return to step (204)；
Step (208)：Whether be empty, if failing with regard to scheduling, fitness value is set to just infinite, terminates if judging L1；If notThe work order task just handled is just put into L0 head positions, it is current work order task to take L1 afterbody work orders task, when updating feasibleBetween section set, return to step (206).
The step (3) compares fitness value, and fitness value reckling is correspondingFor optimal solution, optimal solution is preserved to B(t)；Judge whether to reach termination condition, optimal solution is exported if termination condition is reached；Jumped to if not up to termination conditionStep (4)；
The B (t) is used to preserve population optimal solution, including locally optimal solution.
When step (3) termination condition is the maximum quantum update times set and/or reaches scheduling set in advanceBetween desired threshold.
Step (4) quantum updates, and comprises the following steps：
Step (4-1)：T=t+1 is made, X is generated by Q (t-1), according to X binary sequence amount of calculation specific item scalar functions；
Step (4-2)：With Quantum rotating gate Population Regeneration Q (t).
The Quantum rotating gate selects similar Givens orthogonal matrixes form, formula：
In formulaFor the Quantum rotating gate of i-th of quantum bit position of j-th of chromosome that evolutionary generation is t,It is revolving door parameter,For the anglec of rotation, anglec of rotation angular dimension takes fixationThe π of value 0.02, anglec of rotation direction of rotation is determined according to table 1.
The anglec of rotation inquiry table of table 1
In table 1A binary bit in variable is controlled for binary system,To be stored in the optimal solution in B (t)The binary bit of correspondence position.
The Quantum rotating gate more new formula is：
Quantum bit after renewal needs to meet,
Step (4-3)：Return to step (2) calculates the fitness value of quantum after renewal, by the X corresponding to minimum fitness valuePreserve to B (t).
Complex scene product plan based on quantum evolutionary algorithm, including：Memory, processor and it is stored in memoryComputer program that is upper and running on a processor, following steps are realized described in the computing device during computer program：
Step (1)：Quantum population is initialized：Including initialization quantum population evolutionary generation, initialization quantum bit codingWith initialization quantum chromosomes quantity；
Step (2)：Quantum scheduling and Fitness analysis：Set up quantum object function, it is considered to the production of heavy mechanical equipmentUnder the constraints of manufacturing environment, quantum object function is solved；The binary system control of quantum population generation object functionVariable, variable is controlled according to the binary system of generation, corresponds to the order of work order task, carries out scheduling, is calculated according to scheduling orderThe fitness value of the deadline, as quantum of whole heavy mechanical equipment work order；
Step (3)：Compare fitness value, optimal solution is determined by minimum fitness value；Preserve optimal solution；Judge whether toUp to termination condition, optimal solution is exported if termination condition is reached；Step (4) is jumped to if not up to termination condition；
Step (4)：Quantum updates：Quantum population is updated using Quantum rotating gate；Return to step (2) is recalculatedThe fitness value of quantum, continues optimizing.
Beneficial effects of the present invention：
1st, evolution algorithm is applied to heavy mechanical equipment production scheduling field, meets local optimal searching and is relatively being put down with global optimizingOptimal solution is found in the state of weighing apparatus, realizes that heavy mechanical equipment produces scheduling.
2nd, the scheduling of heavy mechanical equipment uses quantum evolutionary algorithm, and input data is changed into quantum information, the algorithmDeployment process is easy to be transplanted to quantum computer field, on quantum calculation machine platform, and the arithmetic speed of algorithm has noveltyImprove.
3rd, the present invention is not based on perfect condition model, under storage capacity constraints, deployment line side storehouse, conveying arrangement etc.Complicated production scene fitting actual production, has to actual production by the heavy mechanical equipment production scheduling of above-mentioned realization and refers toLead meaning.
4th, the present invention proposes a kind of innovative quantum bit coding method, by work order task, process equipment and processing workSequence is encoded simultaneously；The environment such as storage capacity constraints and transport are taken into account, a kind of scheduling suitable for heavy mechanical equipment producing line is proposedStep.
Embodiment
The invention will be further described with embodiment below in conjunction with the accompanying drawings.
As shown in figure 1, the complex scene scheduling method based on quantum evolutionary algorithm, comprises the following steps：
Step (1) quantum population is initialized；Including initialization quantum population evolutionary generation, initialization quantum bit coding andInitialize quantum chromosomes quantity；
Step (1-1) initialization evolutionary generation t=0.
Step (1-2) initialization quantum bit coding：By determining the selected machine of heavy mechanical equipment work order taskAnd the order for processing of reaching the standard grade, to obtain more excellent quantum object function.
Need to define two variables in initialization procedure：
First variable represents whether work order i j-th of process processes on k-th of machine, is designated as variable aijkIf,Select machine k then variable aijkValue is 1, and variable-value is 0 if non-selected machine k；
Second variable represents that the processing sequence of work order i j-th of process is l, is designated as variable bijl, when work order i jthIndividual process starts the processing variations per hour b that reaches the standard grade at l-th of processing sequenceijl1 is designated as, otherwise variable bijlFor 0.
Make A=[a111,a112..., aijk...], whether j-th of process for depositing work order i adds on k-th of machineThe state of work；
Make B=[b111,b112..., bijl...], for whether depositing work order i j-th of process in l-th of processing sequencePlace starts to reach the standard grade the state of processing；
Sequential concatenation is carried out to A and B, the quantum bit coding of multiple heavy mechanical equipment work orders is obtained, is designated as X.
X=A+B=[a111,a112..., aijk,…,b111,b112..., bijl,…] (1)
Wherein, the "+" order of representation splicing in formula (1), aijk、bijlTake 0 or take 1, then X is binary sequence.
Work order task, process equipment and manufacturing procedure information are contained in binary sequence X by the coded system.
Specifically, a quantum bit position is expressed as：The state representation of quantum bit is：|ψ>=α | 0 ＞+β | 1>,
Wherein | 0 ＞ and | 1 ＞ represents two kinds of basic status of quantum bit；α and β is plural number, represents the general of qubit stateRate width, α2Probability, the β of state 0 are in for quantum bit2The amplitude and angle of the probability of state 1, α and β are in for quantum bitRandom value, but meet | α |2+|β|2=1；
Q is made to represent chromosome, then the quantum chromosomes that m quantum bit position is represented are
Wherein, | αi|2+|βi|2=1, i=1,2 ..., m；M represents individual chromosome quantum bit bit length, m calculatingFormula is as follows：
M=work orders total task number × number of devices+work order total task number2 (3)
Then formula (1) is expressed as with quantum bit：
Step (1-3)：Initialize population：Chromosome population is associated with evolutionary generation t, if the chromosome population in t generations is：
Then formula (2) is converted into：
J represents chromosome number in formula, and m represents single quantum dye body length, and n is that chromosome population scale is dyeColour solid total quantity.
In single iteration, chromosome quantitative is more, is more readily obtained globally optimal solution, but calculating speed is slow.
Chromosome quantitative is fewer, and calculating speed is faster, but is easily trapped into locally optimal solution.
In general, chromosome quantitative is arranged between 40-100, and the present invention takes n=60.
Then formula (4) is converted into after being associated with evolutionary generation t：
Quantum scheduling Fitness analysis；The scheduling strategy used under limited space scene expects processing for positive row's strategyOrder deliver goods as early as possible.
The assessment of the quantum object function needs to consider the constraints of the production and manufacturing environment of heavy mechanical equipment.
The quantum object function is：
Minf (X)=Min ∑sAll work orders(heavy mechanical equipment work order planned end time-heavy mechanical equipment work order planTime started) (8)
In formula, X is referred to as the binary system control variable of object function, is one group of binary sequence, the quantum object functionValue is the smaller the better.
Quantum fitness calculate be by according to individual chromosome value obtain work order task each machine reach the standard grade processing whenBetween and downtime, also referred to as work order task order according to given by chromosome carries out the process of scheduling.
Numerical value one work order task of correspondence in individual chromosome in chromosome population per dimension, each chromosome bagThe current order information for needing to be arranged work order task is contained.
Process time is determined by the machine models or warehouse compartment type and the work order product attribute of work order task processed, is processedTime is the Given information of scheduling.
The calculating of quantum object function needs to consider the pact of the production and manufacturing environment of heavy mechanical equipment in the step (2)Beam condition.
The constraints is specially：During selection machine determines work order process time, big machinery is consideredPriority logical relation of the equipment work order task in work order process, work order task is once can not interrupt, i.e., single workSingle task can not in two times be processed across the unavailable time of machine, and two warehouse compartments can not be also assigned in a process gap and are kept in,The single machine same time can only process a work order task, and machine only processes workpiece within the available period.
The constraints is expressed as follows by formula：
In formula (9), aijkRepresent work order i j-th of process whether the state being processed in k-th of machine；bijlTableShow work order i j-th of process whether the state being processed in l processing sequences, machining state takes 0 or takes 1；
Referred to as sequential operator, represents serial number of each element in array,
bijThe institute of work order task processing sequence for depositing i-th of work order, j-th of process is stateful,For array bijTransposition,Expression takes bijMiddle state is the serial number corresponding to 1 element,Dimension and bijIt is identical；
bi(j+1)The institute of work order task processing sequence for depositing+1 process of i-th of work order jth is stateful,ForArray bi(j+1)Transposition,Expression takes bi(j+1)Middle state is the serial number corresponding to 1 element,'sDimension and bi(j+1)It is identical.
First constraint aijk, bijl=0 or 1, all i, j, k and l is set up, it is ensured that chromosome coding it is feasibleProperty；
Second constraintIt ensure that work order task order is appointed according to work orderThe logical order of business processing is processed；
3rd constraintAll work order task orders are set up, it is ensured that all work ordersTask is only processed once；
4th constraintAll i and j are set up, it is ensured that single work order task is only in a machineIt is processed on device.
The binary system that the Fitness analysis of the step (2) need to be generated object function by quantum chromosomes population Q (t) is controlledVariable X,
Obtained by formula (7) with formula (10),
In formula (11)A binary bit in variable is controlled for binary system,Value：
Wherein γ is random number, takes the arbitrary value in [0,1].
Variable X is controlled according to the binary system of generation, the order of work order task is corresponded to, scheduling is carried out, according to scheduling orderThe deadline for calculating whole heavy mechanical equipment work order is the fitness value of quantum.
Step (2)：Quantum scheduling and Fitness analysis；
As shown in Fig. 2 scheduling step is as follows in the step (2)：
Step (201)：Quantum is decoded：Incoming single quantum is resolved to the scheduling order of work order task；
Step (202)：Scheduling queue L0 is treated in foundation, and the order deposit of decoded workman's task scheduling is treated into scheduling queue L0In；
Step (203)：Judgement treats whether scheduling queue L0 is empty, if so, then scheduling is finished, calculates fitness value, terminates；If it is not, the head work order task for treating scheduling queue L0 is then taken, into step (204)；
Step (204)：Whether judge current work order task is assembling work order；If being put into step (205)；Just enter if notEnter step (206)；
Step (205)：Judge whether workpiece needed for specifying warehouse compartment is complete, if being put into step (206)；It is put into if notStep (207)；
Step (206)：Whether judge possible schedule fragment is empty；Determine that if not it is available and its and start process time, moreNew possible schedule fragment set；Foundation is had been lined up arranging L1, and current drained work order task is put into L1 afterbody, return to step(203)；If so, being put into step (208)；
Step (207)：Judgement treats whether scheduling queue L0 is empty, if so, then scheduling fails, fitness value is set to positive nothingThoroughly, terminate；Just take if not and treat that scheduling queue L0 head work order task, for current work order task, then appoints the work order just handledBusiness is put into the head position for treating scheduling queue L0, return to step (204)；
Step (208)：Whether be empty, if failing with regard to scheduling, fitness value is set to just infinite, terminates if judging L1；If notThe work order task just handled is just put into L0 head positions, it is current work order task to take L1 afterbody work orders task, when updating feasibleBetween section set, return to step (206).
Treatment on special problems：If quantum group is not all arranged in the calculating in a whole generation, it may proceed to initialize a generationQuantum continues optimizing, until reaching termination condition, stops this chromosome population iteration.Scheduling strategy has two classes, and a class is aboutShu Youxian a, class is that result is preferential.Under constraint-prioritized strategy, if not discharging result, pot life is returned to not enough, scheduling is lostLose.Under the preferential strategy of result, can according to order priority order, will be set to successively by the time it is just infinite, at thisChromosome population optimizing is restarted under part, until finding feasible scheduling strategy.
Step (3)：Compare fitness value, fitness value reckling is correspondingFor optimal solution, optimal solution is preserved to B (t)；Judge whether to reach termination condition, optimal solution is exported if termination condition is reached；Step is jumped to if not up to termination condition(4)；
The B (t) is used to preserve population optimal solution, including locally optimal solution.
When step (3) termination condition is the maximum quantum update times set and/or reaches scheduling set in advanceBetween desired threshold.
Step (4)：Quantum updates, and step is as follows：
Step (4-1)：T=t+1 is made, X is generated by Q (t-1), according to X binary sequence amount of calculation specific item scalar functions；
Step (4-2)：With Quantum rotating gate Population Regeneration Q (t).
The Quantum rotating gate selects similar Givens orthogonal matrixes form, and formula is as follows：
In formulaFor the Quantum rotating gate of i-th of quantum bit position of j-th of chromosome that evolutionary generation is t,For revolving door parameter,For the anglec of rotation, anglec of rotation angular dimension takes fixed value0.02 π, anglec of rotation direction of rotation is determined according to table 1.
The anglec of rotation inquiry table of table 1
In table 1A binary bit in variable is controlled for binary system,To be stored in the optimal solution in B (t)The binary bit of correspondence position.
The Quantum rotating gate more new formula is：
Quantum bit after renewal needs to meet,
Step (4-3)：Return to step (2) calculates the fitness value of quantum after renewal, by the X corresponding to minimum fitness valuePreserve to B (t).
Although above-mentioned the embodiment of the present invention is described with reference to accompanying drawing, not to present invention protection modelThe limitation enclosed, one of ordinary skill in the art should be understood that on the basis of technical scheme those skilled in the art are notNeed to pay various modifications or deform still within protection scope of the present invention that creative work can make.