Publication

Preemptive open shop scheduling with multiprocessors: polynomial cases and applications

Related publications (35)

Graph Chatbot

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.

LP-Based Algorithms For Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

Linear programming (LP) has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic me ...

Society for Industrial and Applied Mathematics2017

Passenger Centric Train Timetabling Problem

Michel Bierlaire, Shadi Sharif Azadeh, Mohammad Yousef Maknoon, Tomas Robenek

The aim of this paper is to analyze and to improve the current planning process of the passenger railway service in light of the recent railway market changes. In order to do so, we introduce the Passenger Centric Train Timetabling Problem. The originality ...

Pergamon-Elsevier Science Ltd2016

A two-stage stochastic programming approach to employee scheduling in retail outlets with uncertain demand

Colin Neil Jones

This paper describes an employee scheduling system for retail outlets; it is a constraint-based system that exploits forecasts and stochastic techniques to generate schedules meeting the demand for sales personnel. Uncertain scenarios due to fluctuating de ...

Elsevier2015

Scalable scheduling of energy control systems

Xuan Truong Nghiem

Peak power consumption is a universal problem across energy control systems in electrical grids, buildings, and industrial automation where the uncoordinated operation of multiple controllers result in temporally correlated electricity demand surges (or pe ...

IEEE Press2015

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

Coding Structure and Replication Optimization for Interactive Multiview Video Streaming

Pascal Frossard

Multiview video refers to videos of the same dynamic 3-D scene captured simultaneously by multiple closely spaced cameras from different viewpoints. We study interactive streaming of pre-encoded multiview videos, where, at any time, a client can request an ...

Ieee-Inst Electrical Electronics Engineers Inc2014

LP-Based Algorithms for Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodo ...

IEEE2014

Single machine scheduling with scenarios

Ola Nils Anders Svensson

In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in ...

2013

Tracklet-based Multi-Commodity Network Flow for Tracking Multiple People

Pascal Fua, François Fleuret, Jérôme Berclaz, Horesh Beny Ben Shitrit

(EN)A method for continuously tracking multiple people partitioned into groups while preserving identities under global appearance constraints, wherein people's trajectories may intersect, and wherein only sparse appearance information is available is disc ...

WO2013

Santa Claus Schedules Jobs On Unrelated Machines

Ola Nils Anders Svensson

One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job j requires time p(ij) if processed on machine i. More t ...

Siam Publications2012

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

3

. Then, we draw a connection to Goem ...

EPFL2014