Publication

Scheduling with Multiprocessors: A rounding network algorithm with a constant error

2005
Student Projects

Abstract

The candidate will study some special cases of preemptive open shop problems with multiprocessors. He will in particular concentrate on the situation when the processor set is partitioned into 2 multiprocessors. The two cases of preemptions (at integral times only or at arbitrary times) will be considered and the formulation as a linear programming problem will be exploited to get bounds on the minumum completion time. Interpretations in terms of graph colouring (generaling the edge colouring formulation of the open shop model) will be studied as well. Solvable cases wil be described (obtained by restricting for instance the various types of jobs characterized by their individual operations (on single processors) and their group operations (on multiprocessors)).

Official source

https://infoscience.epfl.ch/entities/publication/31509d76-620d-446d-bd3f-f284f1e77400

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2005
Student Projects

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/31509d76-620d-446d-bd3f-f284f1e77400

About this result

Related concepts (32)

Vector processor

In computing, a vector processor or array processor is a central processing unit (CPU) that implements an instruction set where its instructions are designed to operate efficiently and effectively on large one-dimensional arrays of data called vectors. This is in contrast to scalar processors, whose instructions operate on single data items only, and in contrast to some of those same scalar processors having additional single instruction, multiple data (SIMD) or SWAR Arithmetic Units.

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Degeneracy (graph theory)

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

Related publications (13)

Scheduling with Multiprocessors: A rounding network algorithm with a constant error

Chat with Graph Search

Exact algorithms for continuous pricing with advanced discrete choice demand models

A Spatial Branch and Bound Algorithm for Continuous Pricing with Advanced Discrete Choice Demand Modeling

Optimum Frame Design with Reused Stock Elements