Author(s)

Yiming Li, Zhiqian Ye, Xiao Zhou

Center of Mordern Educational Technology, Wenzhou University, Wenzhou, Zhejiang, 325035, P.R.China.
College of Biomedical Engineering and Science Instrument, Zhejiang University, Hangzhou, Zhejiang, 310027, P.R. China.
Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579, Japan.

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.

Coloring, Non-preemptive scheduling, Partial k-tree

Li, Y. , Ye, Z. and Zhou, X. (2012) Algorithm for Cost Non-preemptive Scheduling of Partial k-Trees. Open Journal of Applied Sciences, 2, 233-236. doi: 10.4236/ojapps.2012.24B053.