Algorithm for Cost Non-preemptive Scheduling of Partial k-Trees

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.

DOI: 10.4236/ojapps.2012.24B053                

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.

Keywords

Coloring, Non-preemptive scheduling, Partial k-tree

Conflicts of Interest

The authors declare no conflicts of interest.

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.