%0 Journal Article
%T Algorithm for Cost Non-preemptive Scheduling of Partial <i>k</i>-Trees
%A Yiming Li
%A Zhiqian Ye
%A Xiao Zhou
%J Open Journal of Applied Sciences
%P 233-236
%@ 2165-3925
%D 2012
%I Scientific Research Publishing
%R 10.4236/ojapps.2012.24B053
%X Let G be a graph, in which each vertex (job) v has a positive integer weight (processing time) p(v) and eachedge (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.
%K Coloring
%K Non-preemptive scheduling
%K Partial k-tree
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=26836