Scientific Research

An Academic Publisher

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

**Author(s)**Leave a comment

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.

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.

KEYWORDS

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

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.

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

Copyright © 2018 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.