TITLE:
Algorithm for Cost Non-preemptive Scheduling of Partial k-Trees
AUTHORS:
Yiming Li, Zhiqian Ye, Xiao Zhou
KEYWORDS:
Coloring, Non-preemptive scheduling, Partial k-tree
JOURNAL NAME:
Open Journal of Applied Sciences,
Vol.2 No.4B,
January
17,
2013
ABSTRACT: 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.