Reading papers (51):integration of a holonic organizational control architecture and multiobjective

Inge2022-06-23 18:04:02

0 introduce

0.1 subject

2008IEEE TMSCA: Integration of global organizational control architecture and multi-objective evolutionary algorithm for flexible distributed scheduling (Integration of a holonic organizational control architecture and multiobjective evolutionary algorithm for flexible distributed scheduling)

0.2 Method

be based on Autonomous Cooperation and overall situation (Autonomous cooperating holons) Concept , A global command and control (Command and control) ( C 2 C^2 C2) Of Organizational control structure (Organizational control architecture,OCA), In order to C 2 C^2 C2 Organization modeling is the integration of global multi-level decentralized decision-making networks .OCA There are two levels :
1) Operation level control ;
2) Tactical level control .
In order to complete tasks in real time in a dynamic environment , Different levels of control Decision makers (decision maker,DM) Extensive task coordination is required , And adjust the task as needed at any time .
stay OCA On the basis of , A complete Multiobjective evolutionary algorithm . The algorithm can generate flexible distributed scheduling , To address unexpected changes in the mission environment , For example, equipment failure 、 Emergencies , as well as DM Failure, etc . The advantage of the method lies in maintaining the stability of the organization , Reduced adaptation costs .

0.3 Bib

@article{
Yu:2008:10011017,
author = {
Fei Li Yu and Fang Tu and Krishna R Pattipati},
title = {
Integration of a holonic organizational control architecture and multiobjective evolutionary algorithm for flexible distributed scheduling},
journal = {
IEEE Transactions on Systems, Man, and Cybernetics-Part A: {
S}ystems and Humans},
volume = {
38},
number = {
5},
pages = {
1001--1017},
year = {
2008},
doi = {
10.1109/TSMCA.2008.923082}
}

1 overall situation C 2 C^2 C2OCA Structure

## 1.1 Some preliminary work of organization design
Before about C 2 C^2 C2 In the research of organization design , We study the modeling and synthesis of organizational structure , To achieve a set of command objectives : Maximize command efficiency 、 Minimize coordination times , And smooth DM Load, etc . for example :
1) The developed task modeling and three-phase organization design methods allow people to solve a series of small and well-defined optimization problems , To iterate the solution and integrate the command structure , Thus, the computational complexity is overcome ;
2) C 2 C^2 C2 The organizational structure is conceptualized as a capacitor topology design problem , To explain the average information delay . This is because the hierarchy is affected by link and node overhead , The resulting information delay can degrade its performance ;
3) Design a method of heterogeneous organization structure , This method takes into account information / Command transfer and task processing activities ;
4) Using from group technology and nested genetic algorithm (GA) To synthesize heterogeneous structures ;
5) Define and classify the organization's strategic and structural adaptation processes in response to mission and environmental changes .
Despite these studies , But has not yet developed a robust 、 To adapt to , And flexible organizational structure decentralized model .

1.2 Two stage control architecture

Based on network centric C 2 C^2 C2 Organizational needs , The control architecture should be distributed 、 abstract , And generalized . In a sense , Control is abstract , For internal structure and others DM The assumption of behavior should be low limit . Generalizable control requires replication from certain basic structures DM. Control should also be stress and self-organizing , That is, the control can respond to environmental interference and adapt to changes in the task execution stage . In particular , C 2 C^2 C2 The organizational control structure can be classified into the following two levels , Pictured 2:
1) Operation level control (Operational-level control,OLC) Architecture is used for task decomposition 、 Careful planning 、 command , And coordination within decision makers . This phase focuses on the overall mission objectives , From the commander's point of view , Establish an initial force structure , Arrange subordinate units at the right place and time before the task starts . As the mission progresses ,OLC The task progress will be monitored in real time and the initial plan will be adjusted as required , To ensure the successful completion of the task ;
2) Tactical level control (Tactical-level control,TLC) Architecture for lower level DM encapsulate , these DM Is the executor of the specific subtask assigned . This phase focuses on local task scheduling 、 War pattern recognition 、 Consultation mechanism , And provide the interface for resource allocation .TLC The schema can have multiple TLC example , namely Tactical unit (tactical unit,TU), Its The quantity is based on OLC Determined by the rigorous plan in Of . In practical tasks ,TU You can add or delete as needed .TU It also provides a consultation mechanism , To resolve conflicts as needed .

chart 2: Two stage overall situation OCA


Finally, the two-level architecture is coupled : come from TLC Subordinate DM To send information to OLC My superior DM, And the top-down monitoring of the overall progress of the task and the adjustment of tactical activities is distributed to the subordinates DM.

1.3 C 2 C^2 C2 overall situation OCA Characteristics of

Koestler There are the following findings :
1) Biological and social systems by creating stable “ middle ” (intermediate) State to develop and grow , To meet increasingly complex and changing needs . These forms are independent , More capable than the original system ;
2) It is often difficult to distinguish “ whole ” and “ part ”: Almost every distinguishable element is both a whole and a part .
The proposed architecture is an intermediate state between hierarchy and heterogeneity :
1) It is a two-level hierarchical structure with rich horizontal connections ;
2) Whole and part coexist , Each part is also a whole , Because each part has a complete internal structure .
The existence of these features makes C 2 C^2 C2 overall situation OCA The following features are further derived :
1) autonomous (Autonomy): Be able to act responsibly and proactively . Permissions and controls are distributed in DM Or between units , Make them recognizable 、 Decision making and task selection ability ;
2) Integrate (Integration): Power and control flow from the top to the bottom . Subordinate units or DM You must obey the orders of your superiors , To ensure unified command ;
3) synergy (Cooperation): The mandatory coordination order and consultation mechanism make the unit and DM Can be flexible with other units or DM Interact , And minimize confusion ;
4) Self organizing (Self-organization): When environmental conditions change or major interference occurs , subordinate DM Or the company can reorganize the operation automatically or through the superior command ;
5) Reconfigurable (Reconfigurability):TU It can be added or deleted as the task plan evolves . Each unit and DM You can reconfigure yourself through different plans and schedules .

2 A multi-objective model for distributed global scheduling

C 2 C^2 C2OCA The applied multi-objective model includes tasks 、 assets 、 Task priority 、 plan , And scheduling parameters ; Multi level objectives of the model 、 Collaboration mechanism , And dynamics .

2.1 The subtasks (Task)

Subtasks derive from task decomposition , Is an activity that requires the use of relevant resources , By one or more DM Execute to accomplish the task objective . Each subtask T i ∈ [ 1.. I ] T_{i\in[1..I]} Ti[1..I] The following features are included :
1) start (Start) Time t s , i t_{s,i} ts,i;
2) perform (Processing) Time t p , i t_{p,i} tp,i;
3) End (Finish) Time t f , i t_{f,i} tf,i;
4) Location (Geographical location) ( x t , i , y t , i ) (x_{t,i},y_{t,i}) (xt,i,yt,i);
5) Resource requirements (Resource requirement) vector R t , i = [ r i , 1 , … , r i , l , … , r i , L ] R_{t,i}=[r_{i,1},\dots,r_{i,l},\dots,r_{i,L}] Rt,i=[ri,1,,ri,l,,ri,L], among r i , l r_{i,l} ri,l It's a subtask T i T_i Ti Resources required for successful execution l l l The number of .

2.2 assets (Asset)

An asset is a given resource capability 、 The physical entity of the operating range and processing speed .
Every asset P j ∈ [ 1.. J ] P_{j\in[1..J]} Pj[1..J] The following features are included :
1) Initial geographic location ( x p , j , y p , j ) (x_{p,j},y_{p,j}) (xp,j,yp,j);
2) Resource capability (Resource capability) vector R p , j = [ r j , 1 , … , r j , l , … , r j , L ] R_{p,j}=[r_{j,1},\dots,r_{j,l},\dots,r_{j,L}] Rp,j=[rj,1,,rj,l,,rj,L], among r j , l r_{j,l} rj,l It's assets P j P_{j} Pj The resources we have l l l The number of ;
3) Maximum asset allocation speed v j v_j vj.

2.3 Subtask priority (Task precedence constraints)

In some cases , Need to work with others before determining the task decomposition criteria DM negotiation . Make I i s I_i^s Iis It means task T i T_i Ti Direct successor task set for , Then the subtask priority constraints are as follows :
t s , i ′ ≥ t f , i + t timeout (1) \tag{1} t_{s,i'}\geq t_{f,i}+t^\text{timeout} ts,itf,i+ttimeout(1) among T i ′ ∈ I i s T_{i'}\in I_i^s TiIis, as well as t timeout t^\text{timeout} ttimeout yes T i T_i Ti Between them and their successors ” Overtime “.

2.4 Planning and scheduling parameters (Planning and scheduling parameters)

OLC In the architecture planning DM (planning DM) Responsible for solving the following planning problems :
1)TU The number of M M M;
2) Subtask to TU The distribution of :
g i , m = { 1 , Son ren service T i branch with to TU m ; 0 , no be . (2) \tag{2} g_{i,m}=\left\{ \begin{array}{ll} 1,\qquad& The subtasks T_i Assigned to \text{TU}_m;\\ 0,\qquad& otherwise . \end{array}\right. gi,m={ 1,0, Son ren service Ti branch with to TUm; no be .(2) 3) Assets to TU The distribution of :
q j , m = { 1 , information production P j branch with to TU m ; 0 , no be . (3) \tag{3} q_{j,m}=\left\{ \begin{array}{ll} 1,\qquad& assets P_j Assigned to \text{TU}_m;\\ 0,\qquad& otherwise . \end{array}\right. qj,m={ 1,0, information production Pj branch with to TUm; no be .(3) 4) Design parameters : Optimal or near optimal asset to task scheduling variables :
h i , j ( b i , c i ) = { 1 , information production P j stay when between Fan around [ b i , c i ] Inside branch with to Son ren service T i ; 0 , no be , (4) \tag{4} h_{i,j}(b_i,c_i)=\left\{ \begin{array}{ll} 1,\qquad& assets P_j In the time frame [b_i,c_i] Assign to subtasks within T_i;\\ 0,\qquad& otherwise , \end{array}\right. hi,j(bi,ci)={ 1,0, information production Pj stay when between Fan around [bi,ci] Inside branch with to Son ren service Ti; no be ,(4) among [ b i , c i ] [b_i,c_i] [bi,ci] Execution time interval of .

2.5 Multi level objectives of the model 、 coordinating mechanism , And dynamics

The global agent network consists of a group of autonomous agents DM A system of units , They cooperate with each other to achieve common goals , Every DM Each unit has its own independent goal . These goals can be divided into two levels : Tactical level and operational level .

2.5.1 Tactical level

Each of the current levels TU The goal is to maximize Task completion accuracy (Task completion accuracy,TCA). In addition, you need to minimize Task execution time (Task execution cost, TEC).
1) Maximize TCA: When T i T_i Ti When all the required resources are available ,TCA=100%. But in reality , Resources are usually scarce , And the organization may reduce TCA To improve TEC Purpose . To balance time and accuracy , Mission T i T_i Ti By TU m \text{TU}_m TUm The accuracy of execution is defined as :
A i , m = ( 1 L ~ ∑ i = 1 L a i , l ⋅ g i , m ) , (5) \tag{5} A_{i,m}=\left(\frac{1}{\tilde{L}}\sum_{i=1}^La_{i,l}\cdot g_{i,m}\right), Ai,m=(L~1i=1Lai,lgi,m),(5) among L ~ \tilde{L} L~ yes T i T_i Ti The number of non-zero resources consumed , namely L ~ = ∑ l = 1 L δ 1 ( r i , l ) \tilde{L}=\sum_{l=1}^L\delta_1(r_{i,l}) L~=l=1Lδ1(ri,l), among
δ 1 ( r i , l ) = { 1 , Such as fruit Son ren service T i Need to be want information Source l ; 0 , no be . (6) \tag{6} \delta_1(r_{i,l})=\left\{ \begin{array}{ll} 1,\qquad If subtasks T_i Resources required l;\\ 0,\qquad otherwise . \end{array}\right. δ1(ri,l)={ 1, Such as fruit Son ren service Ti Need to be want information Source l;0, no be .(6) a i , l a_{i,l} ai,l It's a subtask T i T_i Ti About resources l l l Task accuracy , It identifies the percentage of resources in the corresponding resource type that meet the requirements , namely a i , l = ( r ~ i , l / r i , l ) a_{i,l}=(\tilde{r}_{i,l}/r_{i,l}) ai,l=(r~i,l/ri,l) yes T i T_i Ti About l l l Actual consumption of :
r ~ i , l = min ⁡ { r i , l , ∑ j = 1 J h i , j ( b i , c i ) ⋅ r j , l ⋅ q j , m } . (7) \tag{7} \tilde{r}_{i,l}=\min\left\{r_{i,l},\sum_{j=1}^Jh_{i,j}(b_i,c_i)\cdot r_{j,l} \cdot q_{j,m}\right\}. r~i,l=min{ ri,l,j=1Jhi,j(bi,ci)rj,lqj,m}.(7) hypothesis T i T_i Ti The duration of is b i b_i bi To c i c_i ci, You can find A i , m A_{i,m} Ai,m It's actually L ~ \tilde{L} L~ Average task accuracy of resource types consumed .
Maximize TCA The problem can be formulated as :
max ⁡ { h i , j ( b i , c i ) } 1 I m ∑ i = 1 I m A i , m , (8) \tag{8} \max_{\{h_{i,j}(b_i,c_i)\}}\frac{1}{I_m}\sum_{i=1}^{I_m}A_{i,m}, { hi,j(bi,ci)}maxIm1i=1ImAi,m,(8) It is governed by the formula 1 Constraints , And I m I_m Im Is assigned to TU m \text{TU}_m TUm Number of subtasks .
2) To minimize the TEC: When scheduling one or more tasks , If a certain TCA standard ,TU More willing to send fewer assets . There are two main reasons :
a) As more assets are used to perform tasks , Travel and coordination costs will be higher ;
b) Too many assets assigned to one task will result in not enough assets to perform other concurrent tasks .
The subtask will be executed T i T_i Ti The travel time of the asset is defined as TEC:
C i , m = ∑ j = 1 J T r i , j ⋅ h i , j ( b i , c i ) ⋅ q j , m , (9) \tag{9} C_{i,m}=\sum_{j=1}^JTr_{i,j}\cdot h_{i,j}(b_i,c_i)\cdot q_{j,m}, Ci,m=j=1JTri,jhi,j(bi,ci)qj,m,(9) among
T r i , j = ( x p , j − x t , i ) 2 + ( y p , j − y t , i ) 2 v j (10) \tag{10} Tr_{i,j}=\frac{\sqrt{(x_{p,j}-x_{t,i})^2+(y_{p,j}-y_{t,i})^2}}{v_j} Tri,j=vj(xp,jxt,i)2+(yp,jyt,i)2(10) Its assets P j P_j Pj Migrate from your own location to a subtask T i T_i Ti Travel time at execution location .TEC optimization problem Can be formulated as :
min ⁡ { h i , j ( b i , c i ) } ∑ i = 1 I m C i , m , \min_{\{h_{i,j}(b_i,c_i)\}}\sum_{i=1}^{I_m}C_{i,m}, { hi,j(bi,ci)}mini=1ImCi,m, It yields to the formula 1.
In this model ,TCA And TEC There is an essential conflict between , because TEC Reduce , Will probably lead to TCA Also reduces . The goal of multi-objective optimization is to find a set of trade-offs between the two optimizations .

2.5.2 coordinating mechanism

Coordination mechanism is used for different tasks during execution TU Communication between . By negotiation , Information and commands can be exchanged . If at present TU Unable to complete the assigned task , Can be used with a specific TCA Local resources of / Professional knowledge , It may find the necessary resources / Others with professional knowledge are willing to TU To coordinate the task . The schedule of certain assets performing common tasks can also be set in different TU Negotiation between . The goal of coordination is usually to find a set of assets that meet the task time constraints .
coordinating mechanism It can be divided into the following three steps :
1) Mission release (Task announcement): Tactical level control TLC After scheduling , Unable to meet TCA Required tactical units TU ~ m \tilde{\text{TU}}_m TU~m The set of is defined as :
T ^ m = { T i ∣ A i , m < α , i ∈ I m } , (12) \tag{12} \hat{T}_m=\{T_i|A_{i,m}<\alpha,i\in I_m\}, T^m={ TiAi,m<α,iIm},(12) among α \alpha α yes TCA threshold . T ^ m \hat{T}_m T^m It contains all the subtasks that need to be coordinated TU m \text{TU}_m TUm.
2) docking (Contracting): Having the following characteristics TU Meet docking requirements :a) Have the necessary resources or skills . For subtasks T i ∈ T ^ m T_i\in\hat{T}_m TiT^m for , The candidate asset set meets the following requirements: :
P ^ = { P j ∣ r j , l ⋅ r i , l > 0 ; l = 1 , … , L ; r j , l ∈ R p , j ; r i , l ∈ R t , i } . (13) \tag{13} \hat{P}=\{P_j|r_{j,l}\cdot r_{i,l} > 0; l=1,\dots,L;r_{j,l}\in R_{p,j};r_{i,l}\in R_{t,i}\}. P^={ Pjrj,lri,l>0;l=1,,L;rj,lRp,j;ri,lRt,i}.(13)b) The owned assets meet the time requirements of the negotiation task :
max ⁡ { h i , j ( b i , c i ) } 1 ∣ T ^ m ∣ ∑ i = 1 ∣ T ^ m ∣ A i , m ′ ∀ i , j , T i ∈ T ^ m , P j ∈ P ^ (14) \tag{14} \max_{\{h_{i,j}(b_i,c_i)\}}\frac{1}{|\hat{T}_m|}\sum_{i=1}^{|\hat{T}_m|}A_{i,m}'\qquad\forall i,j,T_i\in\hat{T}_m,P_j\in\hat{P} { hi,j(bi,ci)}maxT^m1i=1T^mAi,mi,j,TiT^m,PjP^(14) Succumb to
b i = min ⁡ j { t s , i − T r i , j } ∀ P j ∈ P ^ , c i = max ⁡ j { t f , i + T r i , j } ∀ P j ∈ P ^ , (15) \tag{15} \begin{array}{ll} b_i = \min_j\{t_{s,i}-Tr_{i,j}\}&\forall P_j\in\hat{P},\\ c_i=\max_j\{t_{f,i}+Tr_{i,j}\}&\forall P_j\in\hat{P}, \end{array} bi=minj{ ts,iTri,j}ci=maxj{ tf,i+Tri,j}PjP^,PjP^,(15) among A i , m ′ A_{i,m}' Ai,m Is greater than one TU Executive T i T_i Ti Of TCA.
3) negotiation (Coordinated processing): Because some tasks require multiple TU At the same time , T i T_i Ti The task accuracy of is redefined as :
A i = { A i , m , T i ∉ T ^ m ; A i , m ′ , T i ∈ T ^ m . (16) \tag{16} A_i=\left\{ \begin{array}{ll} A_{i,m},&\qquad T_i\notin \hat{T}_m;\\ A_{i,m}',&\qquad T_i\in\hat{T}_m. \end{array} \right. Ai={ Ai,m,Ai,m,Ti/T^m;TiT^m.(16)

2.5.3 Operation level

At the operational level ,DM Need to integrate from every TU Multiple distributed scheduling for S S S, To achieve the following two goals :
1) Finish the task as soon as possible ;
2) Complete the task with maximum degree of completion .
These tasks are modeled through the global TCA Realization , The time interval of the task indicates the life cycle of the task . The corresponding two optimization objectives are as follows :
1) Maximize TCA: Overall operation level TCA It is defined as the mean value of task completion accuracy , What is involved TCA Optimized to yield to the formula 1 Of
max ⁡ S A = max ⁡ S 1 I ∑ i = 1 I A i . (17) \tag{17} \max_{S}A=\max_S\frac{1}{I}\sum_{i=1}^I A_i. SmaxA=SmaxI1i=1IAi.(17) 2) Minimize the lifetime of task execution : Suppose the start time of the task t s t a r t = 0 t_{start}=0 tstart=0, Minimizing the lifecycle is equivalent to minimizing t e n d t_{end} tend. Because subtasks are parallel and distributed across multiple TU, So by combining each TU To calculate the life cycle . However , These distributed schedules may conflict with each other and violate the time priority constraints of tasks . therefore , You need to eliminate global conflicts before calculating the lifecycle . Finally, the problem can be formulated as :
min ⁡ S t end (18) \tag{18} \min_St_\text{end} Smintend(18) Yield to the formula 1.

2.5.4 Model dynamics

Two dynamic strategies are added to make the model more meet the actual needs :
1) Dynamic asset volume : Due to equipment loss and other reasons , The volume of assets after returning to the base will be reduced to a certain extent . therefore , resources l l l The updated quantity is
r j , l renewed = r j , l ⋅ ( 1 − p l ⋅ r ~ j , l r j , l ) , (19) \tag{19} r_{j,l}^\text{renewed}=r_{j,l}\cdot\left(1-p_l\cdot\frac{\tilde{r}_{j,l}}{r_{j,l}}\right), rj,lrenewed=rj,l(1plrj,lr~j,l),(19) among p l p_l pl It's assets l l l The loss rate of 、 r j , l r_{j,l} rj,l It's resources l l l Full volume of 、 r ~ j , l \tilde{r}_{j,l} r~j,l Is the resource consumption for the precursor task . for example , If resources l l l Consumed , The updated volume will become r j , l ⋅ ( 1 − p l ) r_{j,l}\cdot(1-p_l) rj,l(1pl).
2) The subtasks T i T_i Ti Of Dynamic processing time
t p , i = 1 n i ρ ⋅ c p , i β ⋅ ( e A i λ − 1 ) , (20) \tag{20} t_{p,i}=\frac{1}{n_i^\rho\cdot c_{p,i}^\beta}\cdot\left(e^{A_i^\lambda - 1}\right), tp,i=niρcp,iβ1(eAiλ1),(20) among n i = ∑ j h i , j ( b , c ) n_i=\sum_jh_{i,j}(b,c) ni=jhi,j(b,c) It's a subtask T i T_i Ti In time [ b , c ] [b,c] [b,c] The number of assets allocated within 、 c p , i c_{p,i} cp,i yes T i T_i Ti Asset volume , as well as ρ , β , λ \rho,\beta,\lambda ρ,β,λ Is a constant . chart 3 and 4 The subtask processing time is shown respectively TCA And asset volume 、 Negotiate the relationship between the number of resources .

chart 3: Subtask processing time TCA Relationship with asset volume

chart 4: Subtask processing time TCA Relationship with negotiated asset quantity

3 Solution of flexible distributed global scheduling

The global scheduling process involves OLC and TLC Two levels DM Coordination and communication between , namely OLC Architecturally Coordinate DM And each TU Medium Dispatch DM. The global contains five steps :
1) Central task decomposition ;
2) Tactical level scheduling ;
3) Cooperative resource negotiation ;
4) Operation level global scheduling ;
5) Interactive scheduling .
Assume a lower level TU The interaction of occurs during resource negotiation . therefore , The upper unit will have the right to build a global schedule based on multiple local schedules .

3.1 Central task decomposition ( step 1)

The central plan is broken down by OLC Coordination in architecture DM perform . Coordinate DM First, decompose the central plan and the subtask priority diagram , Then assign them to TU. Subtask priority diagram Decompose according to task priority :
1) Calculate the priority value of each subtask , Such as chart 5;

chart 5: Calculation of priority value


2) Sort the subtasks according to the priority value , Such as chart 12;

chart 12: Task priority


3) Assign subtasks and transfer the priority information of subtasks to each TU.

3.2 Tactical level scheduling ( step 2)

Tactical level scheduling is a distributed process , among Every TU According to local information 、 Local target , And local constraints to make scheduling decisions . As mentioned earlier , Every TU Our multiple goals are as follows :1) To minimize the TEC and 2) Maximize TCA. A new method based on NSGA-II To solve the scheduling problem , And through the quick sorting scheme and based on Pareto The scale independent fitness function is improved . The specific steps are as follows :
1) Chromosomes indicate : The key issue is at certain intervals [ b i , c i ] [b_i,c_i] [bi,ci] Inside for each TU Find the appropriate asset allocation within the task , among h i , j ( b i , c i ) = 1 h_{i,j}(b_i,c_i)=1 hi,j(bi,ci)=1. This is a Combinatorial optimization problem . Different allocations may lead to different TCA and TEC. After performing pre selection of candidate assets , Each task is assigned a certain number ( It could be zero ) Candidate assets . Based on this , A binary chromosome contains Q t = I m ⋅ J m Q_t=I_m\cdot J_m Qt=ImJm A gene , among I m I_m Im and J m J_m Jm They are the first m m m individual TU m \text{TU}_m TUm Number of tasks and assets held . Each gene represents the allocation status of each asset to each subtask . If it's worth 1, It means that the asset is assigned to the task . For example, for a three subtask three asset problem , Its chromosome is [ ( 1   0   0 ) , ( 1   0   1 ) , ( 0   1   0 ) ] [(1\ 0\ 0),(1\ 0\ 1),(0\ 1 \ 0)] [(1 0 0),(1 0 1),(0 1 0)] Represents an asset P 1 P_1 P1 Assigned to a task 1 1 1、 The subtasks T 2 T_2 T2 Need to use assets at the same time P 1 P_1 P1 and P 3 P_3 P3、 The subtasks T 3 T_3 T3 You only need to use the asset P 2 P_2 P2.
2) Fitness function : For a solution s k s_k sk Define the following :
a) p k p_k pk yes s k s_k sk The number of dominating solutions ;
b) q k q_k qk yes s k s_k sk The number of dominated solutions ;
c) c k c_k ck Is the total number of solutions .
The broad sense is based on Pareto Of Scale independent fitness function (Pareto-based scale-independent fitness function, GPSIFF) as follows :
FITNESS ( s k ) = p k − q k + c k . (21) \tag{21} \text{FITNESS}(s_k)=p_k-q_k+c_k. FITNESS(sk)=pkqk+ck.(21) GPSIFF Take advantage of s k s_k sk Information about the dominant and non dominant solutions of , This information is obtained from all participants in the search space . A double target is shown as chart 1, s k s_k sk Dominate the solution 9 and 10, be p k = 2 p_k=2 pk=2; s k s_k sk Be solved 2、4, as well as 5 control , be q k = 3 q_k=3 qk=3, Final FITNESS ( s k ) = 2 − 3 + 10 \text{FITNESS}(s_k)=2-3+10 FITNESS(sk)=23+10.

chart 1: Double target Pareto Schematic diagram of adaptability field


3) Fast non dominated sorting : And NSGA-II The non dominated ordering in is different , A preorder scheme for the Bi objective problem is applied to speed up the sorting process . The size is K K K The population of is sorted in ascending order relative to one of the values of the two targets , namely O 1 , k O_{1,k} O1,k, among k = 1 , … , K k=1,\dots,K k=1,,K. In this pre ordered set ,Pareto front It is found by scanning individual solutions one by one relative to the second target value , namely O 2 , k O_{2,k} O2,k. This guarantees the solution s k ′ s_k' sk stay s k s_k sk When scanning later , Its being s k s_k sk control . chart 6 Shows how to get a single solution s k s_k sk The dominating solution of p k p_k pk And non dominated solutions q k q_k qk The number of .

chart 6: Non dominated sort


4) Elitism and subgroups (Elitism and Niching): And NSGA-II similar , The way in which new populations are created is 40% From the old population with the highest fitness value , rest 60% From the offspring with the highest fitness value . By doing so , Elitism and diversity can be maintained in the new species . Another way to maintain diversity is to use subgroups , It calculates the congestion distance allocation for each individual solution by averaging the distance to its adjacent individuals . If multiple individual solutions share a fitness value , Then the solution in less crowded areas will be selected as part of the new population .
5) The feasibility of : If every local scheduling is feasible , The feasibility of global scheduling can be guaranteed . Because the assets assigned to subtasks are different , Some of these subtasks are not feasible , That is, the completion time of the previous subtask exceeds the start time of the next subtask . The reason why this is not feasible is that the assets assigned to the previous task cannot achieve a certain TCA. So they take longer than the time interval allocated to them , Or maybe it's because the low-speed asset is assigned to tasks far away from it , And the long transmission time leads to the delay of task execution . For this infeasible solution , A very low fitness value will be assigned ( High penalty ), So they won't be selected as part of the new population .
Multiobjective evolutionary algorithm (Multiobjective evolutionary algorithm, MOEA) stay TU m \text{TU}_m TUm Up operation , Handle N s , m ≥ 1 N_{s,m}\geq1 Ns,m1 Local scheduling . For different TU \text{TU} TU, N s . m N_{s.m} Ns.m It can be different . some TU Less scheduling , Because the task start time is limited , There may not be enough viable solutions . under these circumstances ,OLC The plan for DM You may need to adjust the initial start time of each task ( Relax the time limit ) To generate additional local plans .

3.3 Cooperative resource negotiation

After the task announcement, it will be recognized that TCA Tasks that do not meet the accuracy requirements , At the same time, select candidate assets that can perform tasks . The goal of this process is to maximize the average TCA, Such single objective optimization also uses GA To find the best task resource allocation :
1) Chromosome coding : A binary chromosome contains Q c = ∣ T ^ m ∣ ⋅ ∣ P ^ ∣ Q_c=|\hat{T}_m|\cdot|\hat{P}| Qc=T^mP^ A gene , among ∣ T ^ m ∣ |\hat{T}_m| T^m and ∣ P ^ ∣ |\hat{P}| P^ Indicates the number of uncompleted tasks and negotiated assets respectively .
2)GA Parameters
a) Fitness function : Use the formula 14 The average of TAC function ;
b) variation : Using multi-point crossover operator and multi non-uniform mutation ;
c) choice : Each iteration keeps the population size the same , The new species are as follows :50% Of the new species come from the best of the previous species 50%;20% Of the new population comes from the cross ;30% The new population comes from mutation ;
d) evolution : The initial population size is set to N = 100 N = 100 N=100, The number of iterations is set to 50 50 50.
The result of the redeployment of cooperative resources is TU Coordination mode between .OLC The coordination of DM May or may not interfere with this process , It depends on whether the global objectives are affected .

3.4 Operation level global scheduling

And TLC The scheduling process is different ,OLC Three related issues need to be considered in the creation of scheduling
1) To minimize the ( Or maximize )OLC The goal is ;
2) Assemble local schedules into global schedules ;
3) Resolve conflicts between local schedules , Ensure the feasibility of global scheduling .
OLC The coordination of DM Responsible for passing from each TU Select a schedule in the to build a global schedule to achieve global goals :1) Minimize build time and 2) Maximize the overall situation TCA. The algorithm finds a set of sorted L-Neighboring Dispatch . Flexibility is achieved by moving from one schedule to another that is best suited to the current situation . because L-Neighboring Scheduling is adjacent to each other , So the cost of adaptability is very small .MOEA Proposed to solve the global scheduling problem , And TLC The difference between scheduling and global scheduling lies in the construction process :
1) Chromosomes indicate : Every TU The index of a local schedule in is encoded with M M M In the chromosomes of genes , among M M M yes TU The number of . For example, chromosome sequence [ 1325 ] [1 3 2 5] [1325] Express TU 1 \text{TU}_1 TU1 TU 2 \text{TU}_2 TU2 TU 3 \text{TU}_3 TU3, as well as TU 4 \text{TU}_4 TU4 The scheduling sequence of is 1、3、2, as well as 5.MOEA The combination of these indices will be enumerated , Until you find a group L-Neighboring calendar .
2) Global scheduling build : Building a global scheduling involves two problems :1) Maintain the feasibility of global scheduling ;2) It converges to a stable scheduling state in terms of the start time of each task . Use shift right to build a global schedule and keep it viable , That is to recombine the local according to the task map TLC Schedule . The start time of the task with priority constraint will be transferred to the time when all previous tasks have been completed . This introduces the second problem : How to achieve scheduling stability ? Adopt the following iterative scheme :
Once the right shift is complete , You'll get a new set of start times . Start the whole process with this new set of start times . Repeat this iteration , Until the task starts at the same time . At this stage , The global scheduling has reached a stable state .

chart 7: Global scheduling

3.5 Interactive scheduling

Global scheduling can interact with the environment in the following ways , Such as chart 8: Every L-Neighboring Scheduling is divided into several stages . At the beginning of each phase ,OLC The plan for DM According to the information DM Collect reports and data about the progress of the task to evaluate the feasibility of the current plan . Once infeasible is detected , plan DM Search in alternative adjacent schedules at the same stage , Until a feasible schedule is found . then , plan DM Indicate coordination DM To a lower level TU Issue the scheduling change command .

chart 8: Interactive scheduling

thank
Similar articles