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).