The Task Assignment Problem With K-arborescence Structure

In this thesis,we address the task assignment problem with K-arborescence struc-ture,which is defined as follows.Given a K-arborescence D=（V,A;t,α）and a set P of m processors,the vertex-set V denotes the set of n tasks and the arc-set A denotes the set of communication relationship between tasks,where（u,v）∈A means that the task v needs to be executed before the task u.The vector function t:V→R₊^mrepre-sents the processing times of tasks in V are assigned to m processors,where a compo-nent t（v）_p represents the processing time of task v∈V that is executed on processor p∈P.The vector functionα:A→R^m+^×mon the arcs of D represents the commu-nication times,where an elementα（u,v）_pqq denotes the communication time between the tasks u and v when u is assigned to processor p and v is assigned to processor q.It is asked to find an allocation scheme to allocate all tasks to the corresponding pro-cessors to be executed,two kinds of the objective are considered as follows,（1）the objective is to minimize the sum of all processing times and communication times,i.e.,min{∑v∈Vt（v）_f（v）+∑（u,v）∈Aα（u,v）_{f（u）f（v）}},where f:V→P is the assignment function of tasks which assigned to the m heterogeneous processors;（2）the objective is to minimize the makespan between the beginning of the first task and the comple-tion of the last task,i.e.,min maxl∈L{∑v∈V（l）t（v）_f（v）+∑（u,v）∈A（l）α（u,v）_{f（u）f（v）}},where f:V→P represents the assignment function of tasks which assigned to the m hetero-geneous multicore processors,L is the set of all directed paths from the root to the leaves of the K-arborescence D,V（l）is the vertex-set of all vertices on the path l,and A（l）is the arc-set of all arcs on the path l.For convenience,we call（1）as the minimum task assignment problem with K-arborescence structure,and（2）as the minimum makespan task assignment problem with K-arborescence structure,respectively.Combining the dynamic programming algorithms and the local enumeration meth-ods,we obtain the following two results.（1）We design an exact algorithm to solve the minimum task assignment problem with K-arborescence structure,and it runs in time O(（n+K）m^K+2).（2）We present an exact algorithm to solve the minimum makespan task assignment problem with K-arborescence structure,and it runs in time O(（n+K）m^K+2).