Article citationsMore>>

D. Karger, C. Stein and J. Wein, "Scheduling algorithms," in Algorithms and Theory of Computation, Handbook, ed. M.J. Atallah, CRC Press, 1998.

has been cited by the following article:

• 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.