New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Truthful randomized algorithms for scheduling selfish tasks

SpeakerEvripides Bampis

No abstract yet

Scheduling DAGs on Asynchronous Processors

SpeakerMichael Bender

Co-authorCynthia Phillips

This paper addresses the problem of scheduling a DAG of unit-length tasks on asynchronous processors, that is, processors having different and changing speeds. The objective is to minimize the makespan, that is, the time to execute the entire DAG. Asynchrony is modeled by an oblivious adversary, which is assumed to determine the processor speeds at each point in time. The oblivious adversary may change processor speeds arbitrarily and arbitrarily often, but makes speed decisions independently of any random choices of the scheduling algorithm.This paper gives bounds on the makespan of two randomized online firing-squad scheduling algorithms.

Performance and energy optimization of concurrent pipelined applications

SpeakerAnne Benoit

Co-authorPaul Renaud-Goud and Yves Robert

In this talk, we study the problem of finding optimal mappings for several independent but concurrent linear chain workflow applications, in order to optimize performance-related criteria together with energy consumption. The goal is to select an execution speed for each processor, and then to assign application stages to processors, with the aim of optimizing several concurrent optimization criteria. There is a clear trade-off to reach, since running faster and/or more processors leads to better performance, but the energy consumption is then very high. Energy savings can be achieved at the price of a lower performance, by reducing processor speeds or enrolling fewer resources. We establish the complexity of several multi-criteria optimization problems, whose objective functions combine period, latency and energy criteria. We demonstrate the difficulty of performance/energy trade-offs by proving that the tri-criteria problem is NP-hard, even with a single application on a fully homogeneous platform. On the experimental side, we design polynomial-time heuristics, and assess their absolute performance thanks to a linear program. One main goal is to evaluate the impact of processor sharing on the quality of the solution

Distributed load balancing in networks with selfish agents

SpeakerPetra Berenbrink

Co-authorMartin Hoefer and Thomas Sauerwald

In the simplest model considered here, there are n identical machines represented by nodes in a network and m selfish agents that unilaterally decide to move from one node to another if this improves their experienced load. We present several protocols for concurrent migration that satisfy desirable properties such as being based only on local information and computation and the absence of global coordination or cooperation of agents. Our main contribution is to show rapid convergence of the resulting migration process to states that satisfy different stability or balance criteria. In particular, the convergence time to a Nash equilibrium is only logarithmic in m and polynomial in n, where the polynomial depends on the graph structure. Using a slight modification with neutral moves, a perfectly balanced state can be reached after additional time polynomial in n. In addition, we show reduced convergence times to approximate Nash equilibria. Finally, we extend our results to networks of machines with different speeds or to agents that have different weights and show similar results for convergence to approximate and exact Nash equilibria.

A general framework for multiagent scheduling

SpeakerJean-Charles Billaut

Co-authorAlessandro Agnetis, Dario Pacciarelli, Ameur Soukhal, Nguyen Huynh Tuong

We give a modeling framework that generalizes multiagent scheduling problems. Links with classical multicriteria scheduling, multiagent scheduling or interfering jobs scheduling problems are presented and some simple reductions will be given. We will focus on some single machine problems which present some interesting particularities (different complexity status depending on the hypotheses).

SpeakerJacek Blazewicz

No abstract yet

High-multiplicity scheduling on one machine with forbidden start and completion times

SpeakerNadia Brauner

Co-authorChristophe Rapine

For an industrial application in the chemical industry, we were confronted with the planning of experiments, where human intervention of a chemist is required to handle the starting and termination of each of the experiments. This gives rise to a new type of scheduling problems, namely problems of finding schedules with instants when the tasks can neither start nor finish. We show that a schedule without idle time always exists if the number of forbidden instants is less than the number of distinct processing times appearing in the instance. We derive a quite fast algorithm to find such a schedule, based on an hybridization between list algorithm and local exchange. We then improve our approach to propose a polynomial time algorithm under a High Multiplicity encoding. As a corollary minimizing the makespan for a constant number of forbidden instants is polynomial.

The aircraft landing problem with aircraft classes

SpeakerDirk Briskorn

We consider the problem to sequence aircraft landings. Each aircraft belongs to a certain class and has a designated target time. Deviation of target time and actual landing time incurs a penalty according to a piece-wise linear convex penalty function. Landings must be separated by a minimum timespan. We focus on the setting where aircraft of the same classes differ only by their target time. We provide basic ideas of polynomial time algorithms for problems with a fixed number of classes and a fixed number of runways and corresponding special cases.

SpeakerEdmund Burke

No abstract yet

Bargaining and Scheduling of a Set of Jobs between Two Manufacturers

SpeakerXiaoqiang Cai

Co-authorQuanle Chen*, and Yongjian Li**
*Department of Systems Engineering & Engineering Management. The Chinese University of Hong Kong Shatin, N.T., Hong Kong **School of Business, Nankai University Tianjin, P.R. ChinaAlessandro Agnetis, Dario Pacciarelli, Ameur Soukhal, Nguyen Huynh Tuong

We consider a class of scheduling problems where two manufacturers have jointly secured a set of jobs. Each job may bring a certain profit to the party who processes it, subject to a number of constraints including due date and resource constraints. The two parties are facing the problem of how to split the jobs into two subsets, to be undertaken by each of them respectively. The job partition must be fair and mutually beneficial, based on the requirements of the job processing, the resource availability of the two parties, and the level of efforts of the two parties in securing the jobs. We establish a model to address the problem, based on the Nash Bargaining theory. Algorithms to determine the job partition and scheduling solutions are developed.

On the complexity of task graph scheduling with transient and fail-stop failures

SpeakerLouis-Claude Canon

Co-authorAnne Benoit, Emmanuel Jeannot, Yves Robert

This paper deals with the complexity of task graph scheduling with transient and fail-stop failures. While computing the reliability of a given schedule is easy in the absence of task replication, the problem becomes much more difficult when task replication is used. We fill an important complexity gap of the scheduling literature: our main result is that this reliability problem is #P'-Complete (hence at least as hard as NP-Complete problems), both for transient and for fail-stop processor failures. We also study the evaluation of a restricted class of schedules, where a task cannot be scheduled before all replicas of all its predecessors have completed their execution. Although the complexity in this case with fail-stop failures remains open, we provide a method to estimate the reliability while limiting evaluation costs, and we validate it empirically.

Speculative data prefetching for branching structures in dataflow programs

SpeakerJacques Carlier

Co-authorsSergiu Carpov, Renaud Sirdey, Dritan Nace

This paper deals , to some extent, with the problem of speculative data prefetching for dataflow programming models. We focus on finding optimum prefetch strategiesfor a simple n-way dataflow branching structure with respect to several objective functions and exhibit polynomial algorithms for doing so.
Keywords: Knapsack, Shortest path, Parallel Computing, OR in Compilation.

Resource Allocation Games of Utilitarian Social Objectives

SpeakerBo Chen

Co-authorSinan Gurel

In this paper, we study two models of resource allocation games: the classical load balancing game and its new variant involving resource activation costs. The resources we consider are identical and the social costs of the games are utilitarian, which are the average of all individual players' costs. Using the social costs we assess the quality of pure Nash equilibria in terms of the price of anarchy (PoA) and the price of stability (PoS). For each game problem, we identify a problem parameter and provide a parametric bound on the PoA and the PoS. In the case of the load balancing game, the parametric bounds we provide are sharp and asymptotically tight, filling a gap in the literature on the well-studied load balancing game.

Some advances in solving non-idling m-machine scheduling problems

SpeakerPhilippe Chretienne

The basic principles and main motivations of non-idling scheduling are first presented. We first briefly recall the main single-machine results and then consider the m-machine case. Some general properties are proposed that give some insights on the difficulty to handle precedence constraints and to get efficient heuristics. Polynomial algorithms are proposed for some specific problems. However it happens that the complexity of the very basic problem Pm,NI/r(i),d(i),p(i)=1/- remains open while its more restricted variant, when the union of the busy intervals of any subset of machines must make an interval, is shown to be polynomial

Divide and conquer: A polynomial algorithm for linear programming

SpeakerSergei Chubanov

We present a polynomial algorithm for solving systems of linear inequalities. The algorithm uses a divide-and-conquer procedure based on projections onto half-spaces generated by valid inequalities which are obtained in the course of the procedure. If used appropriately, the procedure either finds a feasible solution or proves that one of the inequalities in the system holds as an equation for every integer feasible solution. This fact is used to develop a polynomial algorithm which either finds a feasible solution or decides that the system is infeasible. The algorithm can find a feasible solution or decide that there are no 0,1-solutions in strongly polynomial time.

Selfish scheduling with multiple tasks agents

SpeakerJohanne Cohen

Co-authorFanny Pascual

We study coordination mechanisms for selfish scheduling. Whereas previous work consider that each agent owns only one task, we consider in this paper the setting where two agents, each one having a set of tasks, share a set of parallel identical machines. Each agent chooses the machine on which she assigns each of her tasks, and her aim is to minimize the average completion times of her tasks. A coordination mechanism consists in giving each machine a scheduling policy. We study conditions needed to obtain good coordination mechanisms, and we study the stability of the schedules obtained with three standard coordination mechanisms. Our results show that standard coordination mechanisms are not robust with agents owning several tasks, as pure Nash equilibria do not exist. Furthermore some of these policy may induce schedules as unstable as wanted, whatever the number of machines is.

Blocking and hitting problems in chromatic scheduling

SpeakerDominique De Werra

Co-author M.C.Costa (ENSTA. Paris) and Ch.Picouleau (CNAM, Paris).

By definition chromatic scheduling problems are quite often variations and extensions of classical graph coloring instances. Here we shall consider the case which may occur in conflicting situations where an opponent tries to reduce the performance of a scheduler . In particular we will examine the concept of a d-transversal of special sets of vertices or edges like maximum matchings or maximum stable sets in graphs. The d-transversals are subsets (of vertices or of edges) having at least d elements in common with every special set. In a similar way we will define d-blockers as subsets whose deletion reduces the maximum size of special sets by at least d. Connections between these concepts will be exhibited. Classical examples of such concepts will be given (involving cuts, optimal paths, matroids,etc) and we will concentrate on the case of maximum stable sets since these are the basic components of colorings arising in chromatic scheduling instances. Some complexity issues will be discussed and polynomially solvable cases will be outlined.

Combinatorial design of a minimum cost machining line

SpeakerAlexandre Dolgui

Co-authorXavier Delorme (Ecole des Mines de Saint-Etienne, France) and Mikhail Y. Kovalyov (National Academy of Sciences of Belarus)

We study a problem related to the optimal design of a machining line. This type of line is used for a mass production of a single type of product. To produce an item of this product a given set of operations has to be performed. The line is a sequence of workstations, whose number has to be decided, and each workstation has to be assigned a number of processing modules (blocks). Each block performs a set of operations. A set of available blocks is given. There are the same basic cost associated with each workstation and different additional costs associated with the blocks. The problem is to design a minimum cost machining line of this type. The specicity of the problem is that all operations of the blocks assigned to the same workstation are performed in parallel. Furthermore, there are inclusion, exclusion and precedence relations that restrict the assignment of blocks and operations to the same workstation and the processing order of operations on the line. We suggest two combinatorial approaches for solving this problem, which are theoretically efficient if the number of blocks assigned to the same workstation and the number of workstations are upper bounded by given constants. The first approach is to combinatorially enumerate all feasible solutions, and the second consists in reducing the problem to the well studied maximum weight clique problem. A boolean linear program based on a set packing formulation of the latter problem is presented, and computer experiments with benchmark data are described.

SpeakerMoshe Dror

No abstract yet

Energy Considerations for Divisible Load Processing

SpeakerMaciej Drozdowski

In this presentation energy consumption in divisible computations will be analyzed. Divisible load theory applies to data-parallel computations with communication delays. A simple model of energy consumption will be proposed. We will analyze the interaction of system parameters determining energy consumption. It is demonstrated that energy can be saved by parallel processing.

Bounded Multi Port Model: Motivations, Feasability & Application to Broadcast

SpeakerLionel Eyraud-Dubois

Co-authorOlivier Beaumont, Shailesh Agrawal Kumar, and Hejer Rejeb

The bounded multi-port model is a model for communications in distributed computing platforms, in which each node may be involved in several simultaneous communications, provided bandwidth constraints are respected. In highly heterogeneous environment, this model allows to make better use of the available bandwidth of large server nodes. In this talk, we discuss its feasability by showing that simple optimal algorithms exist for basic problems, and we will show that their implementation require to use QoS mechanisms to enforce the prescribed bandwidth sharing. We also study steady-state application-level broadcast, with an additional degree constraint to ensure the realism of the obtained solution. For this particular problem, we provide a polynomial algorithm based on a minimal resource augmentation.

SpeakerJeremy Fineman

No abstract yet

On the identical coupled task scheduling problem

SpeakerGerd Finke

Co-authorNadia Brauner, Vassilissa Lehoux-Lebacque, G-SCOP, University Joseph Fourier, Grenoble, France

In the identical coupled task scheduling problem, multiple copies of a two-operation task, where the two operations are separated by a fixed distance, are to be processed on a single machine. The objective is to minimize the makespan in the finite case or the throughput rate in the cyclic case. We have recently established the polynomial complexity of the cyclic case, using as a compact representation of a schedule the concept of profiles. Then the optimal solutions can be described by only two different profile types, called type 1 (small idle) and type 2 (large idle).
We carry over this concept to the finite case, whose complexity status is unknown. We illustrate the increased combinatorics of this problem, where several profiles are now required for the description of the solutions. Then we give our motivation to conjecture that type 1 (small idle) problems are difficult to solve, whereas we show that type 2 (large idle) problems are polynomially solvable.

Reliability and performance optimization of pipelined real-time systems

SpeakerAlain Girault

Co-authorAnne Benoit, Fanny Dufosse, and Yves Robet (ENS-Lyon and LIP)

We consider pipelined real-time systems, commonly found in assembly lines, consisting of a chain of tasks executing on a distributed platform. Their processing is pipelined: each processor executes only one interval of consecutive tasks. We are therefore interested in minimizing both the input-output latency and the period. For dependability reasons, we are also interested in maximizing the reliability of the system. We therefore assign several processors to each interval of tasks, so as to increase the reliability of the system. We assume that both processors and communication links are unreliable and subject to transient failures, the arrival of which follows a constant parameter Poisson law. We also assume that the failures are statistically independent events. We study several variants of this multiprocessor mapping problem with several hypotheses on the target platform (homogeneous/heterogeneous speeds and/or failure rates). We provide NP-hardness complexity results, and optimal mapping algorithms for polynomial problem instances.

SpeakerClaire Hanen

No abstract yet

Path Planning for Groups

SpeakerHan Hoogeveen

Co-authorsMarjan van den Akker, Roland Geraerts, and Corien Prins

In computer games groups of characters have to move from one location to another as quickly as possible. If there is only one group, then it can be solved efficiently as a dynamic flow problem. If there are several groups with different origins and destinations, then the problem becomes NP-hard. In current games, these problems are solved by using greedy ad-hoc rules. We present a heuristic solution that is based on ILP techniques.

Solving the Transshipment Yard Scheduling Problem efficiently

SpeakerFlorian Jaehn

Co-authorNils Boysen, Erwin Pesch

In modern rail-rail transshipment yards huge gantry cranes transship containers between different freight trains, so that hub-and-spoke railway systems are enabled. In this context, we consider the transshipment yard scheduling problem (TYSP) in which trains have to be assigned to bundles, which jointly enter and leave the yard. Although feasible solutions can easily be obtained, the problem is NP-hard if certain, realistic objectives are chosen. We present several heuristics as well as one exact algorithm for solving the problem. The presentation concludes with some computational results.

Fast approximation scheme for the multiple knapsack problem

SpeakerKlaus Jansen

In this talk we propose an improved efficient approximation scheme for the multiple knapsack problem (MKP). Given a set A of n items and set B of m bins with possibly different capacities, the goal is to find a subset S of all items in A of maximum total profit that can be packed into B without exceeding the capacities of the bins. Kellerer gave a polynomial time approximation scheme (PTAS) for MKP with identical capacities and Chekuri and Khanna presented a PTAS for MKP with arbitrary capacities with running time n^{O(1/\epsilon^8 \log(1/\epsilon))}. Recently we found an efficient polynomial time approximation scheme (EPTAS) for MKP with running time 2^{O(1/\epsilon^5 \log(1/\epsilon))} poly(n). Here we present an improved EPTAS with running time 2^{O(1/\epsilon \log(1/\epsilon)^4)} + poly(n). If the modified round-up property for bin packing with different sizes is true, the running time can be improved to 2^{O(1/\epsilon \log(1/\epsilon)^2)} + poly(n).

Just-in-time scheduling on identical parallel machines

SpeakerJoanna Jozefowska

In the mass production environment it is too costly to define and control due dates for individual items. Instead, the model proposed in Toyota is applied that assumes monitoring the actual production rate of particular products. The objective is to construct schedules with minimum deviation from an ideal product rate. We consider the so called Product Rate Variation model and scheduling algorithms developed to solve this problem with two types of objectives: to minimize the total or maximum deviation from the ideal production rate and we show that the algorithms can be generalized to solve the scheduling problem in case of identical parallel machines.

Sports Scheduling: Progress to Date and Work in Progress

SpeakerGraham Kendall

I will present two different sports scheduling problems. One is based on the English Football league and the other is a more generic problem which enables scheduling of different sporting events. The talk will outline the progress made to date, the work that is currently ongoing and some of the challenges that remain. As we are addressing real world problems, modeling the problem is one challenge. However, another challenge, which is often overlooked, is collecting relevant data. I will discuss how we have done this, and the additional problems that this presents.

Shift scheduling for tank trucks

SpeakerSigrid Knust

In this talk we deal with shift scheduling of tank trucks for a small oil company. Given are a set of tank trucks with different characteristics and a set of drivers with different skills. The objective is to assign a feasible driver to every shift of the tank trucks such that legal and safety restrictions are satisfied, the total working times of the drivers are within desired intervals, requested vacation of the drivers is respected and the trucks are assigned to the most favored drivers. We propose a two-phase solution algorithm which is based on a mixed integer linear programming formulation and an improvement procedure. Computational results are reported showing that the algorithm is able to generate good schedules in a small amount of time.

SpeakerMarek Kubale

No abstract yet

SpeakerWieslaw Kubiak

No abstract yet

Simulation Studies of Multi-Criteria Resource Management Strategies in Grid Environments with Dynamic Descriptions of Jobs and Resources

SpeakerKrzysztof Kurowski

The accuracy of the results of any performance study depends largely on the quality of the workload model driving it. While many research efforts have focused on the modeling of workloads, a little has been done in the context of comprehensive evaluation of different scheduling strategies, especially in the form of hierarchical parallel computing structures. We present results of simulation studies of scheduling algorithms using GSSIM in which both synthetic and realistic job workloads were used. We compare example scheduling algorithms in the light of many evaluation criteria relevant for end-users, e.g. total waiting time, and resource providers, such as utilization or load balancing. Based on this analysis, a new multi-criteria resource management model has been formulated to reflect hierarchical architectures of many complex parallel computing systems, their dynamic nature, and stakeholders preferences. We have proposed and tested a new multi-criteria heuristic called MGM which outperfors well-known scheduling strategies on some evaluation criteria. Our simulation studies can be used as a reference repository for further comparative studies.

Multi-Objective Scheduling: An Agent-based Approach

SpeakerJoachim Lepping

We apply naturally inspired parallel model for multi-objective optimization to a single machine scheduling problem. Exemplarily, we optimize sequences of 50 jobs for an instance of the bi-criteria scheduling problem 1|d_j|sum{C_j},L_{max} with this approach. The modular building block architecture of the optimization model and the distribution of acting entities enables the analysis of separated problem knowledge and the design of corresponding variation operators. The actual modules are derived from local heuristics that tackle fractions of the complete problem. We unveil that it is possible to cover different areas of the Pareto-front with special property operators and make evident that the whole front can be covered if those operators are applied simultaneously. Further, we extend this concept to more important multi-objective scheduling problems like e.g. MaxAndSum that include also parallel machines.

Braess-like Paradoxes on a Bipartite Exchange Network: More Connections Are Not Always Better

SpeakerVitus Leung

Co-authorRandall A. LaViolette

We study a model of exchanges in which price is fixed and the amount transferred depends only on the supply, the demand, and the existence of a link between actors. The links induce a simply-connected bipartite graph. We prove that a trading session on the graph can reduce the demand to zero iff the graph consists of components each of which are complete bipartite and for each, the supply equals or exceeds the demand. Consequently, a Braess-like paradox can be generated for a minimally connected bipartite graph whose demand can be reduced to zero, because it may fail to do so as links are added.

A Fully Polynomial Algorithm for a Cyclic Scheduling Problem with Interval Data

SpeakerEugene Levner

Co-authorVladimir Kats

In 1979, Nimrod Megiddo proposed a strongly polynomial method for finding a cycle of the minimum length-to-height ratio in a graph if all the cycle heights are positive. This method can be directly applied for solving cyclic PERT-type scheduling problems with positive data but cannot handle the cyclic problems with interval data, as in the latter case the cycle heights may be either positive or negative. A new algorithm is proposed for the case when the input data are of any sign. The algorithm combines the idea of Megiddo with Levner-Kats's (1998) parametric critical-path algorithm. It runs in O(mn^2 log n) time, where n is the number of nodes and m the number of arcs in the underlying graph. To our knowledge, no strongly polynomial algorithm for this scheduling problem has been known before.

SpeakerGregory Mounie

No abstract yet

Efficient Algorithms for Minimizing Buffer Capacities with Throughput Constraints

SpeakerAlix Munier

Co-authorMohamed benazouz, Olivier Marchetti and Pascal Urard

The design of streaming (e.g. multimedia or network packet processing) applications must consider several optimizations such as the minimization of the whole surface of the memory needed on a Chip. The minimum throughput of the output is usually fixed. In this paper, we present an original methodology to solve this problem.
The application is modelled using a Marked Timed Weighted Event Graphs (in short MTWEG), which is a subclass of Petri nets. Transitions correspond to specific treatments and places model buffers for data transfers. It is assumed that transitions are periodically fired with a fixed throughput.
The problem is first mathematically modelled using an Integer Linear Program. We then study for a unique buffer the optimum throughput according to the capacity. A first polynomial simple algorithm computing the minimum surface for a fixed throughput is derived when there is no circuit in the initial MTWEG, which corresponds to a wide class of applications. We prove in this case that the capacities of every buffer may be optimized independently.
For general MTWEG, the problem is NP-Hard and an original polynomial 2-approximation algorithm is presented. For practical applications, the solution computed is very close to the optimum.

Dominated partial schedules in time-dependent scheduling

SpeakerKrzysztof Ocetkiewicz

In this talk we will consider a single machine time-dependent scheduling problem with linear deterioration rates, i.e. the processing time is given by pi = ai+bi*si, where si is the moment a processor begins its processing the job i, ai > 0 is the base processing time and bi \ge 0 is the job deterioration rate, for i = 1, ..., n. Jobs are non-preemptive and independent, there are neither ready times nor deadlines. The goal is to minimize the total completion time. We will introduce the concept of dominated partial schedules in the 1 | pi = a+bi*si | sumCi scheduling problem. The concept will be used to increase the efficiency of a branch-and-bound search and to design another exact, but not polynomial, algorithm based on elimination of dominated partial schedules. Next, we will extend the concept to the 1 | pi = ai+bi*si | sumwiCi problem and again use it to create an exact algorithm and improve the branch-and-bound algorithm for the problem. We will present the results of computational experiments showing that the elimination of dominated partial schedules is an important step in designing efficient algorithm for the single machine time-dependent scheduling problems.

A Variable Neighborhood Search for Minimizing Total Weighted Tardiness with Sequence Dependent Setup Times on a Single Machine

SpeakerCeyda Oguz

Co-authorGokhan Kirlik

This paper deals with the single machine scheduling problem to minimize the total weighted tardiness in the presence of sequence dependent setup times. Firstly, a mathematical model is proposed to describe the problem formally. Since the problem is NP-hard, then, a general variable neighborhood search (GVNS) heuristic is proposed to solve it. GVNS is a variation of variable neighborhood search heuristic in which a constructive heuristic is used to obtain good initial solutio. Lastly, the effectiveness of the proposed heuristic is shown by using test instances available for the single machine total weighted tardiness problem with sequence dependent setup times. GVNS outperformed the best known solutions so far in the literature for 28 out of 120 instances while performing the same for 59 instances.

An Approach for Fair Scheduling with Efficient Methods for Managing Advance Reservations in Grids

SpeakerAriel Oleksiak

Scheduling with advance reservations is an important class of problems related to resource management in distributed systems. Advance reservation is usually used to run parallel jobs that require allocation of multiple distributed resources at once or to execute interactive applications. Advance reservation becomes particularly important if a user must pay for the utilization of resources. In that case advance reservation capability is crucial to guarantee requested quality of service in terms of time and cost. Nevertheless, this type of scheduling requires efficient methods to manage reservations. To this end, we propose efficient data structures and algorithms to search for resource availability time slots. Furthermore, we define conditions under which particular data structures and algorithms should be applied. Furthermore, we adapt these proposals for a multicriteria resource management problem in which we find fair schedules for all users that express their preferences using criteria related to time and cost. Efficiency of proposed methods is demonstrated using the GSSIM simulator, a tool for Grid scheduling experiments described in the presentation.

Hyper-heuristics and Their Application to an Examination Timetabling Problem

SpeakerEnder Ozcan

Automated neighbourhood selection in an iterative approach that use multiple heuristics is not a trivial task. Hyper-heuristics are methodologies that perform a search over the heuristics space to solve difficult problems. A class of hyper-heuristics, namely; selection hyper-heuristics automate the process of neighbourhood selection mostly based on an iterative single point search that contain two successive stages; heuristic selection and move acceptance. Different operators can be used in either stages. Hyper-heuristics not only aim to provide a general framework for solving problems at different difficulty levels in a given domain, but also extend the level of generality so that different problems from different domains could be solved. This talk focuses on the former issue considering the examination timetabling domain. Examination timetabling problems are well known NP-hard constraint satisfaction problems. Real-world cases often are complicated and challenging for the researchers and practitioners. In this talk, Yeditepe examination timetabling problem will be introduced. An overview of the results obtained by applying different combinations of heuristic selection and acceptance methods as selection hyper-heuristics to this real world problem will be presented from our previous studies to this date.

Energy-aware scheduling for workflow applications on distributed systems using an evolutionary approach and DVFS-techniques

SpeakerJonathan Pecero

Co-authorBernabe Dorronsoro and Pascal Bouvry

Task scheduling problem for workflow applications has been one of the fundamental issues in parallel and distributed computing. It has been extensively studied in recent years addressed to different efforts, traditionally, to minimize the application completion time and to treat time complexity. Nowadays, there is an important interest to reduce energy consumption in distributed computing systems due to performance, environment and operating cost issues. In this talk we address the problem of scheduling workflow applications on distributed computing systems with the objectives of minimizing both the finishing time and the energy consumption. We provide a scheduler based on an evolutionary algorithm which adopts dynamic voltage and frequency scaling (DVFS) to minimize energy consumption. DVFS has been increasingly integrated into many recent commodity processors as an efficient power management technology. DVFS enables these processors to operate with different voltage supply levels at the expense of sacrificing clock frequencies. In this context, this multiple voltage facility implies a trade-off between the quality of schedules and energy consumption. Therefore, we provide a multi-objective evolutionary approach based on a new cellular Genetic Algorithm (cGA). The main characteristic of the cGA algorithm is that the population is structured in a two dimensional toroidal mesh to achieve a good exploration/exploitation trade-off on the search space. This improves the capacity of the algorithm to solve complex problems as the energy-aware scheduling problem. The extensive simulations conducted as a part of this work verified that the performance of our algorithm is very compelling in terms of both application completion time and energy consumption.

Radiotherapy Scheduling

SpeakerSanya Petrovic

Radiotherapy often forms part of the treatment for cancer patients. The problem of efficient scheduling of radiotherapy patients has been recognised as a key to meeting the set waiting time targets and consequently to improving of radiation cure rates. A patient will generally have to first undergo several processes before the radiotherapy treatment: simulation to localise treatment fields using a CT scanner or simulator, planning in which clinicians decide on the best way of delivering the amount of radiotherapy needed, and finally verification of planning using a simulator. Once these processes are completed, the treatment sessions given on a daily basis can begin. The key performance metric is the time elapsed from the decision to treat (when patient and clinician agree the treatment plan for the first time) and first treatment session. Other objective functions are included to reflect the practice of the hospital in the scheduling of patients. The project is carried out in collaboration the Nottingham University Hospitals NHS Trust, UK. Mathematical programming models combined with heuristics were developed for both pre-radiotherapy and radiotherapy treatment phase. Results obtained by using the proposed models with different policies are presented and analysed.

SpeakerLaurent Philippe

No abstract yet

Scheduling Error Correction Operations for a Quantum Computer

SpeakerCynthia Phillips

Co-authorRobert Carr, Anand Ganti, Andrew Landahl

In a (future) quantum computer a single logical quantum bit (qubit) will be made of multiple physical qubits. These extra physical qubits implement mandatory extensive error checking. The efficiency of error correction will fundamentally influence the performance of a future quantum computer, both in latency/speed and in error threshold (the worst error tolerated for an individual gate).
Executing this quantum error correction requires scheduling the individual operations subject to architectural constraints. Since our last talk on this subject, a team of researchers at Sandia National Labortories has designed a logical qubit architecture that considers all relevant architectural issues including layout, the effects of supporting classical electronics, and the types of gates that the underlying physical qubit implementation supports most naturally. This is a two-dimensional system where 2-qubit operations occur locally, so there is no need to calculate more complex qubit/information transportation.
Using integer programming, we found a schedule of qubit operations that obeys the hardware constraints, implements the local-check code in the native gate set, and minimizes qubit idle periods. Even with an optimal schedule, however, parallel Monte Carlo simulation shows that there is no finite error probability for the native gates such that the error-correction system would be benecial. However, by adding dynamic decoupling, a series of timed pulses that can reverse some errors, we found that there may be a threshold. Thus finding optimal schedules for increasingly-refined scheduling problems has proven critical for the overall design of the logical qubit system.
We describe the evolving scheduling problems and the ideas behind the integer programming-based solution methods. This talk assumes no prior knowledge of quantum computing.
Sandia is a multipurpose laboratory operated by Sandia Corporation, a Lockheed-Martin Company, for the United States Department of Energy's National Nuclear Security Admininstration under contract DE-AC04-94AL85000.

SpeakerChris Potts

No abstract yet

SpeakerLars Praedel

No abstract yet

scheduling DAG of tasks with communications on large scale machines

SpeakerJean-Noel Quintin

Co-authorFrederic Wagner

We consider the problem of scheduling DAG of tasks with communications on large scale machines. This problem derives from a practical implementation of a distributed \emph{make} program. Some heuristics like Dominant Sequence Clustering (DSC) and Earliest Task First (ETF) solve this problem by using a high amount of application information such as the task execution time and the data transfer time between tasks. Such information is difficult to obtain in practical cases. Moreover supplied information can easily turn false especially with the time sharing on computers and the network contention. We introduce two online scheduling algorithms trying to balance load while reducing communications costs relying only on DAG topology. Load-balancing is achieved with modified versions of the classical work-stealing algorithm enabling us to avoid centralization points. We exhibit reasonable examples showing that our algorithms on the online problem can outperform DSC and ETF on the offline problem. Moreover our schedule can react if the network or computer performance change during the execution. Algorithms are evaluated through simulations.

SpeakerEric Sanlaville

No abstract yet

Partitioning of Spacially Located Computations with Rectangles

SpeakerErik Saule

Co-authorErdeniz Bas, Umit Catalyurek

In many distributed applications, the computations take place in a 2D or 3D space which is discretized into cells for parallelization purpose. At each iteration of the application, the state of each cell is updated using the state of neighbor cells in a stencil-like fashion. In applications such as particle-in-cell simulation and raycasting, the computation time required to update each cell may vary in function of well known parameters (such as the distribution of the particle in the field or the position of the objects in the scene). When distributing such applications on a parallel computer, the cells must be allocated to the processor meticulously by taking into account both the load balance between the processors and the communication time between two neighboring processors. Methods should also take into account the possible dynamic aspects of such systems. In this talk, we are proposing different algorithms to balance the load between the processors. Since the communication are induced by the locality of the operation, the communication cost are implicitely minimized by restricting our search to rectangular partitioning. We analyze existing algorithms and propose new types of decomposition. In addition to theoretical worst-case analysis, the performance of the algorithm are experimentally evaluated using real logs from a particle-in-cell simulator and sythetically generated instances.

SpeakerChristoph Schwindt

No abstract yet

Caching of Multiple Request Chains

SpeakerVeronika Sonigo

Co-authorKersani, Trystram, Wagner and Xu

In this talk, we deal with the caching problem of multiple request chains on a web server. In the classical approach of web caching only one request chain is considered and we extend this problem to multiple concurrent request chains, which we call multi-threaded caching problem. We consider a single web server with a cache of size K. Users send several requests to the server for treatment. This induces processing times and the server can store intermediate results in the cache to save on processing time. In this context, we are interested in makespan minimization as well as in the minimization of the mean completion time of the request chains. Two caching models are considered. In the first model caching is forced whereas in the second model caching is optional and one can choose whether an intermediate result is stored in the cache or not. All combinations turn out to be NP-hard for fixed cache sizes and we provide a formulation as dynamic program as well as a bound for inapproximation.

Using Techniques of Submodular Optimization for Solving Scheduling Problems with Controllable Processing times on Uniform Machines

SpeakerVitaly Strusevich

Co-author Akiyoshi Shioura, Tohoku University, Sendai, Japan and Natalia V. Shakhlevich, University of Leeds, U.K.

This talk reports on further efforts of our team to establish links between Submodular Optimization and Scheduling. In our previous work, we have reduced several scheduling problems with controllable processing times to linear programs over a submodular polyhedron intersected with a box. In turn, for these submodular optimisation problems, we have shown how to reformulate them in terms of optimizing the same function over a base polyhedron with an updated rank function and developed a decomposition algorithm for their solution. The purpose of this talk is to demonstrate how these techniques can be adapted to solving problems on uniform parallel machines, including problems of finding feasible schedules to minimize total compression costs and their bicriteria counterparts.

Local Search Algorithms for Submodular Maximization

SpeakerMaxim Sviridenko

We study the problem of maximizing a submodular function over the intersection of k matroids (for a constant k>=2). This is a fundamental optimization problem which generalizes the problem of maximum-weight independent set in the intersection of k+1 matroids (and hence also (k+1)-dimensional matching), maximizing entropy, coverage, or cut-type functions under k matroid constraints, and other problems. It is also contains scheduling on parallel machines with profit maximization (as opposed to cost or running time minimization). Our main result is that for any k>= 2 and any epsilon>0, there is a natural local-search algorithm which has approximation guarantee of 1/(k+epsilon) for the problem of maximizing a monotone submodular function subject to k matroid constraints. This improves a 1/(k+1)-approximation of Nemhauser, Wolsey and Fisher [1978]. For maximizing a linear function over k matroids, we obtain a 1/(k-1+epsilon)-approximation, improving a previously known 1/k-approximation. Our analysis can be applied even to general non-monotone submodular maximization subject to k matroid constraints. We show that in this case the approximation guarantee of our algorithm is 1/(k+1+1/(k-1)+epsilon), improving the previously known factor of 1/(k+2+1/k+\varepsilon).

New bounds for distributed list scheduling

SpeakerMarc Tchiboukdjian

No abstract yet

Scheduling a set of Workflows on a grid with a genetic approach

SpeakerLamiel Toch

Co-authorLaurent Philippe

In this talk, we propose an approach to schedule a batch of jobs on an heterogeneous set of resources like a grid. Each job, is modeled by a workflow where each task is a functional box with several inputs but only one output. So the workflow can be represented by a directed acyclic graph (DAG) with typed tasks. Since tasks have only one output, DAGs are limited to in-trees. All of the grid hosts are able to process a set of task types with unrelated processing costs and are able to transmit files through heterogeneous network links. The objective is to minimize the makespan of the batch of jobs execution. To solve this problem we propose an extension of the GATS algorithm take the communication costs into account. The GATS algorithm is a genetic based scheduling algorithm designed to optimize the execution of single DAG-shaped jobs. We will show the contributions of our work which are both the experimental analysis of the GATS extension and the way we approached its design problems.

Lower Bounds for Smith's Rule in Stochastic Scheduling

SpeakerMark Uetz

Co-authorCaroline Jagtenberg, Uwe Schwiegelshohn

We consider the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. In a landmark paper from 1986, Kawaguchi and Kyan showed that scheduling the jobs according to the WSPT rule -also known as Smith's rule- has a performance guarantee of 1.207. They also gave an instance to show that this bound is tight. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We show, somehow counterintuitively, that the performance guarantee of the WSEPT rule, the stochastic analogue of WSPT, is not better than 1.229. This constitutes the first lower bound for WSEPT in this setting. Our analysis sheds new light on the fundamental differences between deterministic and stochastic scheduling

Scheduling Barges in the Port of Rotterdam

SpeakerSteef van de Velde

Co-authorXiandong Zhang, School of Management, Fudan University - Shanghai, China

Motivated by the problem of scheduling barges along container terminals in the part of Rotterdam, we identify various shop scheduling problems with time lags, highlight one of two our results, and identify one intriguing open problems.

Robust PTAS for Machine Covering and Packing

SpeakerJose Verschae

Co-authorMartin Skutella

In general, combinatorial optimization problems are unstable: slight changes on the instance of a problem can render huge changes in the optimal solution. Thus, a natural question arises: Can we achieve stability if we only maintain approximate solutions?. In this talk I will first explain some models that try to formalize these ideas, and then show some results on the parallel machine covering problem. In particular I will derive a robust PTAS, i.e., I will show how to construct a solution that is not only (1-epsilon)-approximate, but is also stable. That is, if the instance is changed by adding or removing a job, then we can construct a new near-optimal solution by only slightly modifying the previous one.

Fine-grain Dynamic Resource Allocation vs. Batch Scheduling

SpeakerFrederic Vivien

Co-authorHenri Casanova and Mark Stillwell

We propose a novel job scheduling approach that shares cluster resources in a precise and controlled manner using virtual machine technology. We formalize the job scheduling problem, assess its complexity, and derive absolute performance bounds. We develop algorithms for the online, non-clairvoyant version of the problem. We evaluate these algorithms in simulation with both synthetic and real-world workloads. We find that our approach improves over batch scheduling by orders of magnitude in term of job stretch, while leading to comparable or better resource utilization. Our results demonstrate that virtualization technology coupled with lightweight scheduling strategies can afford dramatic improvements for executing HPC workload

A Modification of Dynamic Programming to Reduce the Complexity / Running Time

SpeakerFrank Werner

Co-authorEvgeny Gafarov and Alexander Lazarev

We present graphical algorithms which are a modification of dynamic programming. These algorithms are also based on Bellman's recursive equations but they usually combine several states into a new one. In this way, they often reduce the running time or / and the complexity of the dynamic programming algorithm. In the talk, the focus is on such single machine problems, where in contrast to standard dynamic programming, the corresponding graphical algorithm results in a polynomial time algorithm.

Online unrelated parallel machine scheduling with resource dependent processing times

SpeakerDeshi Ye

Co-author Guochuan Zhang

We consider a new variant of online unrelated machine scheduling. In addition to m unrelated machines, we are given a speeding-up renewable resource of k units. The processing time of a job is dependent on both the machine allocated and the amount of resource assigned. We assume that, the more units of resource a job receives, the smaller is its processing time. Moreover, at any time, the total amount of the resource simultaneously used by jobs are at most k. The jobs arrive over list and we have to irrevocably schedule the coming job without any future information. Our goal is to minimize the makespan. This problem contains online unrelated machine scheduling as a special case. Thus, any online algorithms cannot have a competitive ratio smaller than \Omega(logm). In this paper, we design an online algorithm that based on the framework of online primal-dual scheme. The competitive ratio is shown to be O(logm) + min{O(log k);O(mlogm)}, which is best possible if k is a polynomial of m.

Approximation algorithms for scheduling with a variable machine maintenance

SpeakerGuochuan Zhang

Co-author Lin Chen and Wenchang Luo

In this talk, we investigate the problem of scheduling weighted jobs on a single machine with a maintenance whose starting time is prior to a given deadline and the duration is an function of the starting time. We are asked not only to schedule the jobs but also the maintenance such that the total weighted job completion time is minimum. The problem is shown to be weakly NP-hard. In the case that the duration of the maintenance is a concave (and nondecreasing) function of its starting time, we provide two approximation algorithms with worst-case ratio of 2 and at most $1+\sqrt{2}/2+\epsilon$, respectively. Finally, for the general case, we present a fully polynomial time approximation scheme.

Exact methods for resource levelling problems

SpeakerJuergen Zimmermann

We present exact solution methods for resource levelling problems with minimum and maximum time lags among the project activities. In particular, we consider a time-window based enumeration method and two tree-based branch-and-bound procedures both with a sophisticated constructive lower bound. Furthermore, we propose a mixed integer linear programming formulation that can be solved by standard solvers such as CPLEX. All approaches a compared in a comprehensive computational study using well-known test sets from literature. Instances with up to 50 activities could be solved to optimality