Browsing by Subject "polynomial algorithm"

Now showing 1 - 2 of 2

Access status: Open Access ,
Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments
(AGH University of Science and Technology Press, 2017) Duraj, Szymon; Kopeć, Paweł; Kubale, Marek; Pikies, Tytus
In this paper, we consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that our problem can be solved to optimality in polynomial time under some restrictions imposed on the number of machines, their speeds, and the structure of the incompatibility graph. The theoretical considerations are accompanied by computer experiments with a certain model of scheduling.
Access status: Open Access ,
Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesowych w oknach czasowych
(Wydawnictwa AGH, 2005) Giaro, Krzysztof; Kubale, Marek
In the paper sparse systems of dedicated 1- and 2-processor tasks with unit execution times are considered. Polynomial-time algorithms based on dynamic programming are given. These algorithms allow finding optimal solutions with respect to broad range of criterion functions. The sparsity of a system is measured in terms of the number of edges in the corresponding scheduling graph. More precisely, we are focused on graphs whose cyclomatic number is bounded by a constant. Our algorithms invoke procedures for finding maximal matching in graphs.