OJAppS  Vol.2 No.4 B , December 2012
Algorithm for Cost Non-preemptive Scheduling of Partial k-Trees
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.

Cite this paper
nullLi, 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.
References
[1]   H.L. Bodlaender, polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, J. Algorithms 11, pp. 631-643, 1990.

[2]   R.B. Borie, R.G. Parker and C.A. Tovey, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems of recursively constucted graph families, Algorithmica 7, pp.555-581, 1992.

[3]   E. Balas and J. Xue, Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs, SIAM.J. Comput., 20, pp. 209-221, 1991.

[4]   C.T. Hoang, Efficient algorithms for minimum weighted colouring of some classes of perfact graphs,Discreate Applied Mathemativs, 55, pp.133-143, 1994.

[5]   T. Ito, T. Nishizeki and X. Zhou, Algorithms for multicolorings of partial k-trees, IEICE Trans. Inf&Syst., E86-D, pp 191-200, 2003.

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

[7]   E. Kubicka and A.J. Schwenk, An introduction to chromatic sum, Proc. 17th Annual ACM Computer Science Conf., pp. 39-45, 1989.

[8]   A. Moukrim, K. Sghiouer, C. Lucet and Y. Li, Lower bounds for the minimal sum coloring problem, Electronic Noted in Discrete Mathematics, vol.36, pp.663-670, 2010.

[9]   A. Oproscu and T. Kielmann, Bag-of-tasks scheduling under budget constraints, In Cloud Computing Technology and Science, 2010 IEEE Second International Conference, pp.351-359, 2010.

[10]   A. Sen, H. Deng and S. Guha, On a graph partition problem with an application to VLSI layout, Information Processing Letters, 43, pp. 87-94, 1992.

[11]   W. Shi and B. Hong, Resource allocation with a budget constraint for computing independent task in the cloud. In Cloud Computing Technology and Science, 2010 IEEE Second International Conference, pp. 327-334, 2010.

[12]   S. Isobe, X. Zhou and T. Nishizeki, A polynomial-time algorithm for finding tital colorings of partial k-trees, International Journal of Foundations of Computer Science, 10, pp.171-194, 1999.

[13]   X. Zhou and T Nishizeki, Multicolorings of series-parallel graphs, Algorithmica, 38, pp. 271-297, 2004.

 
 
Top