Search
Search results for: incompatibility graph
-
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines
PublicationIn this paper we consider a problem of job scheduling on parallel machines with a presence of incompatibilities between jobs. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. Our research stems from the works of Bodlaender, Jansen, and Woeginger (1994) and Bodlaender and Jansen (1993). In particular, we pursue the...
-
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines: Complexity and Algorithms
PublicationIn this paper, the problem of scheduling on parallel machines with a presence of incompatibilities between jobs is considered. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. The paper provides several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality:...
-
Scheduling on Uniform and Unrelated Machines with Bipartite Incompatibility Graphs
PublicationThe problem of scheduling jobs on parallel machines under an incompatibility relation is considered in this paper. In this model, a binary relation between jobs is given and no two jobs that are in the relation can be scheduled on the same machine. We consider job scheduling under the incompatibility relation modeled by a bipartite graph, under the makespan optimality criterion, on uniform and unrelated machines. Unrelated machines...
-
Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
PublicationWe consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1, s2, and s3 to minimize the schedule length. We assume that jobs are subject to some kind of mutual exclusion constraints, modeled by a cubic incompatibility graph. We how that if the graph is 2-chromatic then the problem can be solved in O(n^2) time. If the graph is 3-chromatic, the problem becomes NP-hard even if s1>s2=s3.
-
Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments
PublicationWe 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,...
-
Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
PublicationThe problem of scheduling n identical jobs on 4 uniform machines with speeds s1>=s2>=s3>=s4 is considered.The aim is to find a schedule with minimum possible length. We assume that jobs are subject to mutual exclusion constraints modeled by a bipartite incompatibility graph of degree delta. We show that the general problem is NP-hard even if s1=s2=s3. If, however, delta<5 and s1>12s2 s2=s3=s4, then the problem can be solved to...
-
Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines
PublicationThe goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|p j = 1, G = bisubquartic|Cmax . The second one is Algorithm 3 which is 4-approximate for the problem Qm|p...
-
Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
PublicationIn the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP- complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize...
-
Total Completion Time Minimization for Scheduling with Incompatibility Cliques
PublicationThis paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph equivalent to a collection of disjoint cliques. No two jobs in a clique are allowed to be assigned to the same machine. Scheduling with incompatibilities between jobs represents a well-established line of research in scheduling theory and the case of disjoint cliques has received increasing attention in recent...
-
Approximation algorithms for job scheduling with block-type conflict graphs
PublicationThe problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality criterion, is considered in this paper. No two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine in this model. The presented model stems from a well-established line of research combining scheduling theory...
-
Scheduling of compatible jobs on parallel machines
PublicationThe dissertation discusses the problems of scheduling compatible jobs on parallel machines. Some jobs are incompatible, which is modeled as a binary relation on the set of jobs; the relation is often modeled by an incompatibility graph. We consider two models of machines. The first model, more emphasized in the thesis, is a classical model of scheduling, where each machine does one job at time. The second one is a model of p-batching...