Publications related to Job-shop scheduling

Near-optimal Deployment of Dataflow Applications on Many-core Platforms with Real-time Guarantees

Safe and optimal deployment of data-streaming applications on many-core platforms requires the realistic estimation of task Worst-Case Execution Time (WCET). On the other hand, task WCET depends on the deployment solution, due to the varying number of inte ...

IEEE2017

Model and metaheuristics for a scheduling problem integrating procurement, sale and distribution decisions

Rémy Glardon, Nicolas Zufferey

This paper presents an integrated approach for short-term supply chain management (SCM) at a fast moving consumer goods production plant. The problem is to determine the production quantities, to provide a detailed production schedule, to trigger the relev ...

Springer2017

Dispatching rule-based scheduling algorithms in a single machine with sequence-dependent setup times and energy requirements

Yong Chan Choi

The research focuses on the problem of scheduling jobs in a single machine with sequence-dependent setup times and energy requirements in which jobs of multiple types arrive dynamically over time. A setup operation is required to change over the job types ...

Elsevier Science Bv2016

On the Complexity of Scheduling in Half-Duplex Diamond Networks

Christina Fragouli, Ayfer Özgür Aydin, Siddhartha Brahma

We consider an n-relay Gaussian diamond network where a source communicates to a destination with the help of n half-duplex relays. Achieving rates close to the capacity of this network requires to employ all the n relays under an optimal transmit/receive ...

Ieee-Inst Electrical Electronics Engineers Inc2016

Multiperiod Sequential Synthesis of Heat Exchanger Networks and Utility Systems including storages

François Maréchal, Alberto Mian, Emanuele Martelli

This work proposes a sequential approach for the multi-period synthesis of Heat Exchanger Networks (HEN) and Utility Systems of chemical processes and energy systems, including thermal, electric and material storage. The optimization approach is sequential ...

2016

Strong LP formulations for scheduling splittable jobs on unrelated machines

Ola Nils Anders Svensson

A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this ...

Springer Heidelberg2015

Low Complexity Scheduling and Coding for Wireless Networks

Siddhartha Brahma

The advent of wireless communication technologies has created a paradigm shift in the accessibility of communication. With it has come an increased demand for throughput, a trend that is likely to increase further in the future. A key aspect of these chall ...

EPFL2015

Structure of optimal schedules in diamond networks

Christina Fragouli, Siddhartha Brahma

We consider Gaussian diamond networks with n half-duplex relays. At any point of time, a relay can either be in a listening (L) or transmitting (T) state. The capacity of such networks can be approximated to within a constant gap (independent of channel SN ...

Ieee2014

An effective mathematical formulation for the unidirectional cluster-based quay crane scheduling problem

Jingmin Chen, Jianghang Chen

The quay crane scheduling problem plays an important role in the paradigm of port container terminal management, due to the fact that it closely relates to vessel berthing time. In this paper, we focus on the study of a special strategy for the cluster-bas ...

Elsevier Science Bv2014

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

Approximation Algorithms for Modern Multi-Processor Scheduling Problems

Martin Niemeier

This thesis is devoted to the design and analysis of algorithms for scheduling problems. These problems are ubiquitous in the modern world. Examples include the optimization of local transportation, managing access to concurrent resources like runways at a ...

EPFL2012

Spread Spectrum for Universal Compressive Sampling

Pierre Vandergheynst, Yves Wiaux, Rémi Gribonval, Gilles Puy

We propose a universal and efficient compressive sampling strategy based on the use of a spread spectrum technique. The method essentially consists in a random pre-modulation of the signal of interest followed by projections onto randomly selected vectors ...

2011

A projective algorithm for preemptive open shop scheduling with two multiprocessor groups

Dominique de Werra

We study a multiprocessor extension of the preemptive open shop scheduling problem, where the set of processors is partitioned into processor groups. We show that the makespan minimization problem is polynomially solvable for two multiprocessor groups even ...

2010

A Tighter Analysis of Work Stealing

Nicolas Gabriel Gast, Denis Trystram

Classical list scheduling is a very popular and efficient technique for scheduling jobs in parallel platforms. However, with the increasing number of processors, the cost for managing a single centralized list becomes prohibitive. The objective of this wor ...

Springer Berlin Heidelberg2010

On the computational complexity of periodic scheduling

Thomas Rothvoss

In periodic scheduling jobs arrive regularly and have to be executed on one or several machines or processors. An enormous amount of literature has been published on this topic, e.g. the founding work of Liu & Layland [LL73] is among the top cited computer ...

EPFL2009

Forward Error Correction for Multipath Media Streaming

Pascal Frossard, Dan Jurca, Aleksandar Jovanovic

We address the problem of joint optimal rate allocation and scheduling between media source rate and error protection rate in scalable streaming applications over lossy multipath networks. Starting from a distortion representation of the received media inf ...

Institute of Electrical and Electronics Engineers2009

Preemptive open shop scheduling with multiprocessors: polynomial cases and applications

Dominique de Werra

This paper addresses a multiprocessor generalization of the preemptive open-shop scheduling problem. The set of processors is partitioned into two groups and the operations of the jobs may require either single processors in either group or simultaneously ...

2008

Packet Selection and Scheduling for Multipath Video Streaming

Pascal Frossard, Dan Jurca

This paper addresses the problem of choosing the best streaming policy for distortion optimal multipath video delivery, under delay constraints. The streaming policy consists in a joint selection of the video packets to be transmitted, as well as their sen ...

2007

Decision-aid methodology for the school bus routing and scheduling problem

Michel Bierlaire, Thomas Liebling

We consider the school bus routing and scheduling problem, where transportation demand is known and bus scheduling can be planned in advance. We present a comprehensive methodology designed to support the decision of practitioners. We first propose a model ...

2005