Algorithm for Cost Non-preemptive Scheduling of Partial k-Trees
Let G be a graph,in which each vertex (job) v has a positive integer weight (processing time) p(v) and each edge (u,v) represented that the pair of jobs u and v cannot be processed in the same slot.In this paper we assume that every job is non-preemptive.Let C =1,2,… be a color set.A multicoloring (scheduling) F of G is to assign each job v a set of p(v) consecutive positive integers (processing consecutive time slots) in C so that any pair of adjacent vertices receive disjoint sets.Such a multicoloring is called a non-preemptive scheduling.The cost non-preemptive scheduling problem is to find an optimal multicoloring of G,that is,a multicoloring F such that ∑v∈V w(F(v)) is minimum among all multicolorings of G,where w is a cost function of processing time slots which assigns a real number to a set of consecutive positive integers.In this paper we give a polynomial-time algorithm to find an optimal multicoloring F of a given partial k-tree.The algorithm takes time O(n|C|k+2) if n is the number of vertices and C is the color set.
Coloring Non-preemptive scheduling Partial k-tree
Yiming Li Zhiqian Ye Xiao Zhou
Center of Modem Educational Technology, Wenzhou University, Chashan Educational Area, Wenzhou, Zheji College of Biomedical Engineering and Science Instrument, Zhejiang University, 38 Zheda Road, Hangzh Graduate School of Information Sciences, Tohoku University, Aoba-yama 6-6-05, Sendai, 980-8579, Japa
国际会议
北京
英文
233-236
2012-10-26（万方平台首次上网日期，不代表论文的发表时间）