会议专题

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

国际会议

2012年国际工程应用数学研讨会

北京

英文

233-236

2012-10-26(万方平台首次上网日期,不代表论文的发表时间)