We consider the problem of scheduling streaming applications in order to minimize the number of cache-misses. Streaming applications are represented as a directed graph (or multigraph), where nodes are computation modules and edges are channels. When a module fires, it consumes some data-items from its input channels and produces some items on its output channels. In addition, each module may have some state (either code or data) which represents the memory locations that must be loaded into cache in order to execute the module. Our main contribution is to show that for a large and important class of streaming computations, cache-efficient scheduling is essentially equivalent to solving a constrained graph partitioning problem. Given a good partition, we describe a runtime strategy for scheduling streaming graphs and prove that this runtime strategy is asymptotically optimal with constant factor cache-augmentation.

Joint work with Neal Barcelo, Mario Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs and Michele Scquizzato. We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade-off schedule for a speed-scalable processor with discrete speeds. Our algorithm uses a geometric approach that is based on structural properties obtained from a primal-dual formulation of the problem.

Joint work with M. Shantharam, A. Benoit, Y. Robert and P. Raghavan. This paper investigates co-scheduling algorithms for processing a set of parallel applications. Instead of executing each application one by one, using a maximum degree of parallelism for each of them, we aim at scheduling several applications concurrently. We partition the original application set into a series of packs, which are executed one by one. A pack comprises several applications, each of them with an assigned number of processors, with the constraint that the total number of processors assigned within a pack does not exceed the maximum number of available processors. The objective is to determine a partition into packs, and an assignment of processors to applications, that minimize the sum of the execution times of the packs. We thoroughly study the complexity of this optimization problem, and propose several heuristics that exhibit very good performance on a variety of workloads, whose application execution times model profiles of parallel scientific codes. We show that co-scheduling leads to to faster workload completion time and to faster response times on average (hence increasing system throughput and saving energy), for significant benefits over traditional scheduling from both the user and system perspectives.

To be defined: It deals with energy efficient scheduling.

In traditional on-line resource-allocation problems, such as scheduling problems, requests arrive over time, demanding available resources. As each request arrives, some resources may have to be irrevocably committed to servicing that request. In many situations, however, it is possible to reallocate previously allocated resources in order to satisfy a new request. This reallocation has a cost. This talk shows how to maintain efficient schedules while minimizing the reallocation cost.

The task of automated (off-line) algorithm configuration includes finding a good parameter configuration for an algorithm based on some performance measure and a problem instance distribution. This could be considered as an expensive optimization problem. Currently, most algorithms treat the target (configured) algorithm as a black-box, i.e., only the final result of each run of the target algorithm on a problem instance is taken into account. If we "open the box", we could have a gray-box or even a white-box configuration problem. We study an algorithm for resource constrained project scheduling.

Joint work with I. Bladek, F. Guinand and X. Schepler. We study differences between the contiguous and the non-contiguous parallel task schedules. Parallel tasks can be executed on more than one processor simultaneously. In the contiguous schedules indices of the processors assigned to a task must be a sequence of consecutive numbers. In the non-contiguous schedules processor indices may be arbitrary. Nonpreemptive schedules are considered. Given a parallel task instance, optimum contiguous and non-contiguous schedules can be of different length. We analyze minimum instances where such a difference may arise, provide bounds on the difference of the two schedules lengths and prove that deciding whether the difference in schedule length exists is NP-complete.

Joint work with Claudio Arbib and Mara Servilio. Common operation scheduling (COS) is a special case of precedence constrained scheduling. In COS, distinct jobs may share operations, and when an operation is done, it is done for all the jobs that share it. We provide a methodological framework for solving COS problems with the objective of minimizing the weighted number of tardy jobs. The framework consists of a 0-1 linear programming formulation with exponentially many inequalities. Separation of inequalities is in NP provided that an ordinary min Lmax scheduling problem is in P. We develop a branch- and-cut algorithm for the special cases of single machine with precedence relation, and identical parallel machines with unit operation times. In these cases the separation problem is the constrained maximization of a submodular set function.

Joint work with Alexander Kononov, Wieslaw Kurc and Lidia Pankowska. We discuss results describing the structure of schedules for time-dependent scheduling problems, where variable job processing times depend on time when the jobs start. First, we summarize results concerning two known classes of pairs of mutually related time-dependent scheduling problems: equivalent problems and conjugate problems. Next, we present results concerning a new class of similar pairs of problems called isomorphic problems. Finally, we discuss new results concerning properties of schedules for time-dependent scheduling problems with $l_p$ norm criterion.

Joint work with Yiannis Georgiou, Krzysztof Rzadca and Denis Trystram. Energy is one of the most challenging problem in HPC today. The energy consumption of a big cluster can be compared to the energy consumption of a city. Reducing and mastering energy is crucial for reaching performance at a controlled cost. Most of existing approaches deal with energy as an additional constraint to classical scheduling problems. In this work we propose an alternative model where energy is considered as the main resource. By making a clear distinction between power and energy, we consider jobs as malleable tasks.

Resource assignment problems occur in a vast variety of applications, from scheduling problems over image recognition to communication networks. Often these problems can be modeled by a maximum weight matching problem in (bipartite) graphs or generalizations thereof, and efficient and practical algorithms are known for these problems. We consider the problem of determining optimal resource assignments sequentially over a given time horizon, where consecutive assignments are coupled by constraints which control the cost of reconfiguration. We develop fast approximation and online algorithms for this problem with provable approximation guarantees and competitive ratios. We demonstrate the applicability of our approach by conducting a computational study for scheduling in OFDMA wireless networks.

In the field of production scheduling, we address the problem of maximizing the production horizon of a heterogeneous platform composed of identical parallel machines and which has to provide a given production service. Each machine is supposed to be able to provide several throughputs corresponding to different operating conditions. The key point is to select the appropriate profile for each machine during the whole production horizon. The use of Prognostics and Health Management (PHM) results in the form of Remaining Useful Life (RUL) allows to adapt the schedule to the wear and tear of machines. Some complexity results for different problem classes will be provided. Many heuristics will then be proposed to cope with the decision problem and compared through simulation results. Simulations assess the efficiency of these heuristics. Distance to the theoretical maximal value comes close to 5% for the most efficient ones.

Joint work with Marjan van den Akker and Kevin van Blokland. Although combinatorial algorithms have been designed for problems with given, deterministic data, they are often used to find good, approximate solutions for practical problems in which the input data are stochastic variables. To compensate for the stochasticity, in many cases the stochastic data are replaced, either by some percentile of the distribution, or by the expected value multiplied by a `robustness' factor; the resulting, deterministic instance is then solved, and this solution is run in practice. We apply a different approach based on a combination of local search and simulation. In the local search, the comparison between the current solution and a neighbor is based on simulating both solutions a number of times. Because of the flexibility of simulation, each stochastic variable can have its own probability distribution, and the variables do not have to be independent. We have applied this method to the job shop scheduling problem, where we used simulated annealing as our local search method. It turned out that this method clearly outperformed the traditional rule-of-thumb methods.

Due to the increasing number of cores of current parallel machines and the growing need for a concurrent execution of tasks, the problem of parallel task scheduling is more relevant than ever, especially under the moldable task model, in which tasks are allocated to a fixed number of processors before execution. Much research has been conducted to develop efficient scheduling algorithms for moldable tasks, both in theory and practice. The problem is that theoretical as well as practical approaches expose shortcomings, e.g., many approximation algorithms only guarantee bounds under assumptions, which are unrealistic in practice, or most heuristics have not been rigorously compared to competing approximation algorithms. In particular, it is often assumed that the speedup function of moldable tasks is either non-decreasing, sub- linear or concave. In practice, however, the resulting speedup of parallel programs on current hardware with deep memory hierarchies is most often neither non-decreasing nor concave.
We present a new algorithm for the problem of scheduling moldable tasks with precedence constraints for the makespan objective and for arbitrary speedup functions. We show through simulation that the algorithm not only creates competitive schedules for moldable tasks with arbitrary speedup functions, but also outperforms other published heuristics and approximation algorithms for non-decreasing speedup functions.

Joint work with Thijs van der Klauw, University of Twente, Netherlands. This paper investigates the complexity of the scheduling problems for electrical energy storage, whereby the storage devises are used to reduce the peaks of production and consumption within the power supply chain, while minimizing device wearing. The presented mathematical model of the storage devise captures the general characteristic of electrical energy storage while omitting details of specic techniques, allowing its application on various situations. Within the model, the wearing of the storage devices is modelled by either 1) the total energy throughput or 2) the number of switches between charging and discharging, so called charging cycles. For the case where the energy throughput determines the wearing, a linear programming formulation is given, resulting in a well understood problem. For the case where charging cycles are considered, however, an adaption of the formulation for the first case leads to a mixed-integer linear program. An NP-hardness proof is given when multiple devices are considered. Furthermore, several observations about the structure of the problem are given when considering a single device. These observations allow the determination of an optimal solution for this case. The result is a polynomial time algorithm of low complexity. This allows applications of the algorithm in various areas of the power supply chain.

Joint work with Helmut Sedding (University of Augsburg). In this presentation, we introduce a novel single machine scheduling problem where the processing time of a job grows linearly when the job's start time deviates from its ideal start time. Ordering the jobs such that the makespan is minimized, is a NP complete problem. Its application lies in the scheduling of a worker at an assembly line who should minimize walk times between supplies and the moving product. We present an efficient branch-and-bound algorithm to quickly solve the problem.

We consider the online version of the so-called strip packing problem, where a number of rectangles are to be packed (without rotating items) into a strip of width 1 and infinite height. The task is to minimize the height of the resulting packing. We report on work with J.J. Paulus and R. Harren, investigating a special class of instances consisting of only two types of rectangles (width 1 resp. almost 0) leading to a lower bound of 2.589 for the competitive ratio. Our sequences are obtained by varying an original idea of Brown, Baker and Katseff (1982). These bounds (still) leave a large gap between 2.589 and the upper bound of 6.662 due to Ye, Han and Zhang (2009) and, independently, Hurink and Paulus (2008).

We consider scheduling problems where processing of each job simultaneously requires a prespecified subset of dedicated machines. We present a branch-and-bound algorithm which allows for the problems with small number of machines to obtain the following results: (i) the algorithm returns tight bounds for the optima localization intervals; (ii) the algorithm output solutions with provable performance guarantee; (iii) the algorithm distinguishes non-trivial polynomially solvable classes of instances; (iv) the algorithm helps to prove NP-hardness.

Joint work with Sergey Sevastyanov (Russia), Bertrand Lin (Taiwan) and Feng-Jang Hwang (Australia). We study a problem, in which an interval has to be cut into K parts at K-1 out of N-1 marked internal points so that the difference between the largest and the smallest parts is minimized. The problem admits several natural interpretations. It was introduced by Barany and Grinberg who presented an O(KN^3) time algorithm to find an approximate solution with a non-trivial absolute error bound. We present two optimal algorithms. One algorithm employs the dynamic programming methodology and runs in O(KN^4) time. The other algorithm solves at most N^2 auxiliary feasibility problems and runs in O(KN^3) time.

Joint work with D. Bunde, J. Ebbers, S. Feer, N. Price, Z. Rhodes, and M. Swank. We examine task mapping algorithms for systems that allocate jobs non-contiguously. Several studies have shown that task placement affects job running time. We focus on jobs with a stencil communication pattern and use experiments on a Cray XE to evaluate novel task mapping algorithms as well as some adapted to this setting. This is done with the miniGhost miniApp which mimics the behavior of CTH, a shock physics application. Our strategies improve average and single-run times by as much as 28% and 36% over a baseline strategy, respectively.

We addresses a recent open scheduling problem which aims to minimize the summation of total weighted completion time and the total machine time slot cost. Focusing on the case of non-increasing time slot cost, we show that the problem can be solved in polynomial time when the time slot cost decreases with certain patterns, and that the problem is NP-hard in the strong sense when the time slot cost decreases in an arbitrary way.

Joint work with Nicole Megow, Roman Rischke and Leen Stougie. We consider a natural generalization of classical scheduling problems in which using a time unit for processing a job causes some cost. Precisely speaking, we consider the unrelated machine scheduling problem in which every job has a weight, release date and machine-dependent processing time. During any time interval $[t-1,t)$, if there are jobs processed on one or more machines, then a uniform buying cost $c$ is incurred. The objective is to minimize the weighted completion time plus the total buying costs. We consider such a problem in a stochastic setting in which the set of jobs to be scheduled is not deterministic but attributed to some distribution, and we aim to give a buying and scheduling strategy so that the expected objective value is minimized. We provide a $(8+\eps)$-approximation algorithm for this general model and also approximation algorithms for special cases.

Joint work with Olivier Beaumont. The tremendous increase in the size and heterogeneity of supercomputers makes it very difficult to predict the performance of a scheduling algorithm. Therefore, dynamic solutions, where scheduling decisions are made at runtime have overpassed static allocation strategies. The simplicity and efficiency of dynamic schedulers such as Hadoop are a key of the success of the MapReduce framework. Dynamic schedulers such as StarPU, PaRSEC or StarSs are also developed for more constrained computations, e.g. task graphs coming from linear algebra. To make their decisions, these runtime systems make use of some static information, such as the distance of tasks to the critical path or the affinity between tasks and computing resources (CPU, GPU,...) and of dynamic information, such as where input data are actually located. In this talk, we concentrate on two elementary linear algebra kernels, namely the outer product and the matrix multiplication. For each problem, we propose several dynamic strategies that can be used at runtime and we provide an analytic study of their theoretical performance. We prove that the theoretical analysis provides very good estimate of the amount of communications induced by a dynamic strategy and can be used in order to efficiently determine thresholds used in dynamic scheduler, thus enabling to choose among them for a given problem and architecture.

Joint work Aurélien Carlier and Claire Hanen. We consider a finite set of unit time execution tasks with release dates, due dates and precedence delays. The machines are partitioned into k classes. Each task requires one machine from a fixed class to be executed. The problem is the existence of a feasible schedule. This general problem is known to be NP-complete. Many studies were devoted to the determination of polynomial time algorithms for some special sub-problems; most of them are based on a particular list schedule.
The Garey-Johnson and Leung-Palem-Pnueli algorithms (respectively GJ and LPP in short) are two well-known algorithms in this area based on a computation of feasible due dates used as a priority list. Due dates are modified using necessary conditions until a fixed point is reached or a contradiction is observed. It is proved that these two algorithms are different implementations of a same generic one. The main consequence is that all the results valid for GJ algorithm, are also for LPP and vice-versa.

Joint work with Krzysztof Kurowski. The main aim of the presentation is to discuss new models and algorithms to decrease the total energy consumption in future generation computing and networking systems by limiting the cost of traditional cooling and heat reuse at the data center level and also to improve the overall efficiency of local management and operating systems. We will also propose models and algorithms that minimize data center energy consumption and carbon footprint by taking into consideration sources of energy and their characteristics. Specific constraints and requirements of this case make its management different from traditional data centers. To ensure sufficient performance and reliability, such a data center should adapt its operation modes to current situation in an autonomic way (in a similar way as today laptops change power management modes depending on a battery state and other factors). Additionally, the performance of high-end supercomputers will probably reach the exascale level through the advent of core counts in the billions. Heterogeneous, many-core processors have the potential to overcome a major exascale challenge — power consumption — by providing two orders of magnitude more flops per watt than multi-core processors today. As the number of cores is going to continue to increase, exascale applications will need to find a way to exploit an additional thousand times in concurrency. This approach will have simultaneously a tremendous impact on the programming challenge. Even at the petascale there is today a comparative dearth of codes that scale beyond a few thousand cores. Therefore, within the scope of this presentation is to present initial computing models experimentally verified for scaling applications up and out, and managing composite application schemas which reach from peta- to exascale.

Joint work with Shahriar Asta. A selection hyper-heuristic operates on the space formed by a predefined set of low level heuristics which operate directly on the space of solutions. Hyper-heuristics are often structured as low cost methods which are general and can be reused on unseen problem instances as well as other problem domains, desirably without any domain expert intervention. Machine learning techniques are vital components of hyper-heuristics and tensors are one of the powerful tools in machine learning. In this talk, we introduce an effective tensor-based approach to design a multi-stage selection hyper-heuristic for cross-domain heuristic search.

Joint work with: Michael Bender (Stony Brook University), David Bunde (Knox College), Vitus Leung (Sandia National Laboratories) and Samuel McCauley (Stony Brook University). Integrated Stockpile Evaluation (ISE) is a program to test nuclear weapons periodically. Tests are performed by machines that may require occasional calibration. These calibrations are expensive, so finding a schedule that minimizes calibrations allows more testing to be done for a given amount of money. In the ISE theoretical framework, machines run jobs with release times and deadlines. Calibrating a machine requires unit cost. The machine remains calibrated for T time steps, after which it must be recalibrated before it can resume running jobs. The objective is to complete all jobs while minimizing the number of calibrations. We give several algorithms to solve the ISE problem for the case where jobs have unit processing times. For one available machine, there is an optimal polynomial-time algorithm. For multiple machines, there is a 2-approximation algorithm, which finds an optimal solution when all jobs have distinct deadlines.

Joint work with Antonios Antoniadis, Neal Barcelo, Michael Nugent and Michele Scquizzato. We initiate the theoretical investigation of energy-efficient circuit design. We assume that the circuit design specifies the circuit layout as well as the supply voltages for the gates. To obtain maximum energy efficiency, the circuit design must balance the conflicting demands of minimizing the energy used per gate, and minimizing the number of gates in the circuit; If the energy supplied to the gates is small, then functional failures are likely, necessitating a circuit layout that is more fault-tolerant, and thus that has more gates. By leveraging previous work on fault-tolerant circuit design, we show general upper and lower bounds on the amount of energy required by a circuit to compute a given relation. We show that some circuits would be asymptotically more energy-efficient if heterogeneous supply voltages were allowed, and show that for some circuits the most energy-efficient supply voltages are homogeneous over all gates. Additionally, we show hardness and approximation results for the problem of finding the minimum energy required by a fixed circuit to compute a relation.

Joint work with Piotr Skowron. We consider a multi-organizational system in which each organization contributes processors to the global pool but also jobs to be processed on the common resources. The fairness of the scheduling algorithm is essential for the stability and even for the existence of such systems (as organizations may refuse to join an unfair system). We consider on-line, non-clairvoyant scheduling of sequential jobs. The started jobs cannot be stopped, canceled, preempted, or moved to other processors. We consider identical processors, but most of our results can be extended to related or unrelated processors. We model the fair scheduling problem as a cooperative game and we use the Shapley value to determine the ideal fair schedule. In contrast to the current literature, we do not use money to assess the relative utilities of jobs. Instead, to calculate the contribution of an organization, we determine how the presence of this organization influences the performance of other organizations. Our approach can be used with arbitrary utility function (e.g., flow time, tardiness, resource utilization), but we argue that the utility function should be strategy resilient. The organizations should be discouraged from splitting, merging or delaying their jobs. We present the unique (to within a multiplicative and additive constants) strategy resilient utility function. We show that the problem of fair scheduling is NP-hard and hard to approximate. However, for unit-size jobs, we present a fully polynomial-time randomized approximation scheme (FPRAS). We also show that the problem parametrized with the number of organizations is fixed parameter tractable (FPT). In cooperative game theory, the Shapley value is considered in many contexts as “the” fair solution. Our results show that, although the problem for the large number of organizations is computationally hard, this solution concept can be used in scheduling (for instance, as a benchmark for measuring fairness of heuristic algorithms).

Joint work with Jakub Gasior. We present a distributed solution to a secure-aware job scheduling problem in Cloud environment. We assume that an assignment of the resources available within the Cloud is governed exclusively by brokers assigned to Cloud users submitting their jobs to the system. The goal of this scheme is allocating a limited quantity of resources to a specific number of jobs minimizing their execution failure probability and total completion time. Our scheduling approach is based on the Pareto dominance relationship and implemented at an individual user level, instead of a more popular global scheduling approach for the whole system. To select the best scheduling strategies from the Pareto frontier we develop a decision-making mechanisms based on a game-theoretic model of Spatial Prisoner's Dilemma and realized by selfish agents operating in the two-dimensional cellular automata space. Their behavior is conditioned by objectives of the various entities involved in the scheduling process and driven towards a Nash equilibrium solution by the employed social welfare criteria. The performance of the applied scheduler is verified by a number of numerical experiments.

Joint work with Peter Brucker. A forward optimization problem consists in finding an optimal solution that minimizes a given objective function under an assumption that all input data are precisely known and fixed. In an inverse optimization problem, some typical parameters and a target solution are given. The objective is to modify the parameters as little as possible so that the target solution becomes optimal. While many classical optimization problems have been studied from the point of view of inverse optimization, the results in the area of scheduling are quite limited. The talk will present a general methodology for addressing inverse scheduling problems and an overview of the results.

Rail network infrastructure requires periodic maintenance and inspection in order to keep the network functional and safe. Freight networks typically run continuously, so any scheduled or unscheduled maintenance has the potential to disrupt operations. Inspection and routine maintenance is performed frequently and quickly, whereas major work is done infrequently and is disruptive for a longer period of time. In this talk we first discuss a theoretical model of maintenance scheduling on networks with flows. We use this model to comment on the complexity of the problem in general. We then describe a more detailed approach developed for a long-distance, high-throughput rail networks, with an additional complexity of scheduling maintenance crew as they perform tasks and travel between locations on the network.

This work investigates the execution of tree-shaped task graphs using multiple processors. Each edge of such a tree represents a large data. A task can only be executed if all input and output data fit into memory. Such trees arise in the multifrontal method of sparse matrix factorization. The maximum amount of memory needed depends on the execution order of the tasks. With one processor, the problem of finding the tree traversal with minimum required memory was well studied and optimal polynomial algorithms has been proposed. Here, we extend the problem by considering multiple processors. With the multiple processors comes the additional objective to minimize the makespan. Not surprisingly, this problem proves to be much harder. We study its computational complexity and provide an inapproximability result even for unit weight trees. Several heuristics are proposed, especially for the realistic problem of minimizing the makespan under a strong memory constraint. They are analyzed in an extensive experimental evaluation using realistic trees.

Joint work with Peter Brucker, Patrick De Causmaecker and Greet Vanden Berghe. Nurse rostering is a personnel scheduling problem in healthcare that constitutes a particularly challenging task due to complex organizational and contractual constraints. Academic advances in this domain mainly focus on solving specific variants of this problem using intricate exact or (meta)heuristic algorithms, while little attention is devoted to studying the complexity and underlying structure of nurse rostering problems. In this talk we present a new network flow formulation for a class of nurse rostering problems, thereby identifying problems that can be solved in polynomial time. Furthermore, we discuss the results of computational experiments on an academic benchmark dataset to demonstrate the efficiency of the new formulation compared to different state of the art techniques for nurse rostering.

Joint work with Anne Benoit and Jean-Marc Nicod. Mapping linear workflow applications onto a set of homogeneous processors can be optimally solved in polynomial time for the throughput objective with fewer processors than stages. This result even holds true, when setup times occur in the execution and homogeneous buffers are available for the storage of intermediate results. In this kind of applications, several computation stages are interconnected as a linear application graph, and each stage holds a buffer of limited size where intermediate results are stored and a processor setup time occurs when passing from one stage to another. In this paper, we tackle the problem where the buffer sizes are not given beforehand and have to be fixed before the execution to maximize the throughput within each processor. The goal of this work is to minimize the cost induced by the setup times allocating buffers with proportional sizes of each other. We present a closed formula to compute the optimal buffer allocation in the case of non-decreasing setup costs in the linear application. For the case of unsorted setup times, we provide competitive heuristics that are validated via extensive simulation.

Joint work with Yves Crama, and Trivikram Dokka. We consider a special class of axial multi-dimensional assignment problems called multi-dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by m disjoint sets, each of which contains the same number n of p-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an m-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the m sets of vectors into n m-tuples so that no two vectors from the same set are in the same m-tuple and so that the total cost of the m-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We provide constant-factor approximation algorithms under various assumptions on the cost function.

Joint work with Denis Trystram. We consider the classical problem of scheduling n jobs with release dates on single machine and on identical parallel machines. We measure the quality of service provided to each job, by the its stretch, which is defined as ratio of response time to its processing time. In our analysis, we measure the performance of the algorithm by the average stretch achieved by jobs. So far, there have been very few results for average stretch minimization. For preemptive version, the Shortest remaining processing time algorithm is known to give 2-approximation for average stretch on single machine while its is 14-approximation for m-identical parallel machines. Leonardi and Kellerer have given the strong lower bound for more general problem of average (weighted) flow time in single machine and identical parallel machines, respectively. Therefore, we study this problem with some additional assumptions and present two new competitive ratio for existing algorithms. We show that the Shortest processing time (SPT) algorithm is constant order competitive under this assumption for non-preemptive average stretch minimization on single machine and identical parallel machines.

Joint work with Mateusz Cichenski, Mateusz Jarus, Michał Miszkiewicz and Jaroslaw Szymczak. We study the cost optimization problem arising in charitable organizations during supply process. Such institutions are especially interested in minimizing the total cost of purchase which consists of the prices at which particular products are bought and the cost of their transportation. We present the formal mathematical model of the problem, which is NP-hard, and propose list heuristics as well as the genetic algorithm solving it. The efficiency of implemented methods, designed for web service, was checked in extensive computational experiments.

Joint work with Shashi Mittal and Andreas S. Schulz. Health care providers are under tremendous pressure to reduce costs and increase the quality of their services. It has long been recognized that well-designed appointment systems have the potential to improve the utilization of expensive personnel and medical equipment and to reduce the waiting times for patients. In a widely influential survey on outpatient scheduling, Cayirli and Veral (2003) concluded that the “biggest challenge for future research will be to develop easy-to-use heuristics”. In this paper, we analyze the appointment scheduling problem from a robust-optimization perspective, and we establish the existence of a closed-form optimal solution–arguably, the simplest and best ‘heuristic’ possible. In case the order of patients is changeable, the robust optimization approach yields a novel formulation of the appointment scheduling problem as that of minimizing a concave function over a supermodular polyhedron. We devise the first (constant-factor) approximation algorithm for this case.

Joint work with Uwe Schwiegelshohn. We address scheduling problems for infrastructure as a service (IaaS). In a typical IaaS scenario, an infrastructure provider offers his resources on demand and with different service levels to his customers. These service levels are mainly distinguished by the amount of computing power a customer is guaranteed to receive within a time frame.
In our model, each service level is described by a slack factor and a price for a processing time unit. If the provider accepts a job it is guaranteed to complete by its deadline, that is its submission time plus its processing time times the slack factor of assigned service level. After a job has been submitted, the provider must decide immediately and irrevocably whether he accepts or rejects the job. We suggest various algorithms and use competitive analysis to discuss different scenarios for this model. These scenarios combine fixed services levels with the single machine model or the parallel identical machines model.

Joint work with Haroldo G. Santos, Janniele A. Soares, Greet Vanden Berghe and Tony Wauters. The Project Scheduling Problem, in its general form, consists of scheduling the processing times of jobs (or activities) contained in a project, while respecting precedence constraints between the jobs. This class of problems models many situations of practical interest in engineering and management science in general, and has been addressed by experts of various fields. The subject of this talk is an extension of the PSP that considers multiple projects with resource constraints and multiple possibilities to execute the activities. We produced a hybrid algorithm with several heuristics and Integer Programming (IP) based components: (i) a mode selection IP model, (ii) an IP constructive algorithm, (iii) a forward-backward improvement procedures and (iv) an IP local search algorithm. We present results of computational experiments on different PSP benchmark datasets to demonstrate the efficiency of the proposed approach. These experiments improved best known solutions for several instances of two different problem extensions.

Joint work with M. Skutella and M. Sviridenko, STACS 2014. Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the sizes of jobs. In this talk we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. By means of a novel time indexed linear programming relaxation, we compute in polynomial time a scheduling policy with performance guarantee (3+D)/2+e. Here, e>0 is arbitrarily small, and D is an upper bound on the squared coefficient of variation of the processing times. When jobs also have individual release dates, our bound is 2+D+e. We also show that the dependence of the performance guarantees on D is tight. Interestingly, via D=0 the currently best known bounds for deterministic scheduling on unrelated machines are contained as special case.

Joint work with J. R. Correa, A. Marchetti-Spaccamela, J. Matuschke, O. Svensson, L. Stougie and V. Verdugo. In this talk I will present a natural generalization of the problem of minimizing makespan on unrelated machines. In our variant jobs may be split into parts, where each part can be (simultaneously) processed on different machines. Splitting jobs can clearly help to diminish the makespan, but there is a catch: each part requires a setup time before it can be processed. I'll first show that a natural adaptation of the 2- approximation for R||Cmax yields a 3-approximation algorithm, equal to the integrality gap of the corresponding LP relaxation. Through a stronger LP relaxation, obtained by applying a lift-and-project procedure, we are able to improve both the integrality gap and the implied approximation factor to 1 + φ, where φ ≈ 1.618 is the golden ratio. This ratio is also best possible for this LP relaxation. On the negative we show that the problem is NP-hard to approximate within a factor 1.582.

Joint work with Keramat Hasani and Svetlana Kravchenko. We consider the problem of scheduling a set of jobs on two identical parallel machines with a single server for the objectives to minimize the makespan or total flow time. For the makespan problem, we present three MILP models (namely a setup sequence model and two block models) and two metaheuristic algorithms (namely a simulated annealing and a genetic algorithm). While in the literature only instances with up to 100 jobs were considered so far, one of our block models can treat instances with up to 250 jobs within a time limit of one hour. The metaheuristic algorithms have been tested on instances with up to 1000 jobs, and they perform much better than existing algorithms. We also present two polynomial constructive heuristics which perform extremely well on large instances: the average percentage deviation from the lower bound for instances with 10000 jobs is only 0.04 %. For the mean flow time problem, our new MILP model can also treat instances with up to 250 jobs satisfactorily, and it is compared with two metaheuristic algorithms.

Joint work with Wiebke Höhn and Julián Mestre. Generalizing many well-known and natural scheduling problems, scheduling with job-specific cost functions has gained a lot of attention recently. In this setting, each job incurs a cost depending on its completion time, given by a private cost function, and one seeks to schedule the jobs to minimize the total sum of these costs. The framework captures many important scheduling objectives such as weighted flow time or weighted tardiness. Still, the general case as well as the mentioned special cases are far from being very well understood yet, even for only one machine. Aiming for better general understanding of this problem, in this paper we focus on the case of uniform job release dates on one machine for which the state of the art is a 4-approximation algorithm. This is true even for a special case that is equivalent to the covering version of the well-studied and prominent unsplittable flow on a path problem, which is interesting in its own right. For this covering problem, we present a quasi-polynomial time (1+eps)-approximation algorithm that yields an (e+eps)-approximation algorithm for the above scheduling problem. Moreover, for the latter we devise the best possible resource augmentation result regarding speed: a polynomial time algorithm which computes a solution with optimal cost at (1+eps) speedup. Finally, we present an elegant QPTAS for the special case where the cost functions of the jobs fall into at most log(n) many classes. This algorithm allows the jobs even to have up to log(n) many distinct release dates.

We study an offline scheduling problem arising in demand response management in smart grid. Consumers send in power requests with a flexible set of timeslots during which their requests can be served. For example, a consumer may request the dishwasher to operate for one hour during the periods 8am to 11am or 2pm to 4pm. The grid controller, upon receiving power requests, schedules each request within the specified duration. The electricity cost is measured by a convex function of the load in each timeslot. The objective of the problem is to schedule all requests with the minimum total electricity cost. As a first attempt, we consider a special case in which the power requirement and the duration a request needs service are both unit-size. For this problem, we present a polynomial time online algorithm that gives an optimal solution and show that the time complexity can be further improved if the given set of timeslots forms a contiguous interval.

Heuristic algorithms are typically manually designed. They are often developed and tested on the same benchmark instances. However we should separate the instances on which we develop the heuristic from the instances on which we test the heuristic. In other words we should adopt a machine learning methodology with the well-known approach of disjoint sets of training and testing examples. A second inspiration we can take from machine learning is that the training and test examples should be drawn from the same distribution of examples, if we intend the heuristic to generalize from the training set to the test set.
A hyper-heuristic approach operates at a higher level of abstraction than standard metaheuristics. Hyper-heuristic are a bridge between optimization and machine learning and allow us to adopt a machine learning approach to optimization problems. There are two methods of realizing this approach. When the design is done "in vitro" it is called Genetic Programming as a Hyper-Heuristic. When the design is done "in situ" it is called Genetic Improvement.
We give an example of bin-packing with applications in container shipping in logistics, and scheduling virtual machines in cloud computing.

Joint work with Malgorzata Sterna, Xin Han and Jacek Blazewicz. In the paper, we consider the problem of scheduling jobs on parallel identical machines with late work criterion, both offline and online cases. For offline case, we prove that $P|d_j=d|Y$ is NP-hard and give a dynamic programming method solving $P2|d_{j}=d|Y$ in pseudo-polynomial time $O(nd^4)$, deciding on the binary NP-hardness of this problem. For online case, we give an algorithm with competitive ratio $\frac{\sqrt{2m^2-2m+1}-1}{m-1}$ for $P|d_{j}=d, online \over \list|Y$, and prove its optimality for two identical machines $P2|d_{j}=d, online \over \list|Y$.

Joint work with Ceyda Oğuz. The regular flowshop scheduling problems have been studied over the years. Many metaheuristic methods have been proposed such as genetic algorithm, simulated annealing and tabu search for the flowshop problem with makespan objective. Flowshop problem with sequence dependent setup time (SDST), which is more complex than the regular one, has been studied less although it is often encountered in industry. Hence, we propose a Variable Neighborhood Search (VNS) algorithm for the flowshop problem with SDST where the objective is to minimize the makespan. In the proposed algorithm, we construct an initial solution with Nawaz-Enscore-Ham (NEH) heuristic and improve the initial solution with VNS. The VNS algorithm searches the solution in multiple neighborhood structures and uses local search systematically. Inherently, search space of neighborhoods affects the quality of the algorithm. As a result, selecting neighborhood structure, deciding the sequence of the selected neighborhoods and selecting the local search procedure play important roles in a VNS algorithm. We examine the performance of the various neighborhood structures by using the well-known benchmark set proposed by Taillard (1989). We compare our results with the alternative methods and state-of-art for this problem and observe that preliminary results are promising.

Joint work with Adel Safi and Denis Trystram. In this work, we design a novel algorithm for scheduling parallel and independents tasks in volunteers computing platforms. In these platforms, resources availability is not continuous. Moreover, the begin and the end of the availability intervals dates of the resources are subject to uncertainties due to the fact the owner is it's the unique administrator. The performance of the algorithms is achieved by a suitable adaptation of the algorithm to volunteer environments. The stability of our approach is accomplished by implementing a reputation mechanism of the resources that makes the scheduling decisions more suitable to disturbed environment. Efficiency of our algorithm is demonstrated by an experimentation campaign where we compare our approach to other existing algorithms.

Joint work with Lin Chen, Klaus Jansen, and Deshi Ye. We consider the classical scheduling problem on parallel machines to minimize the makespan, which is one of the first problems in the area of approximation algorithms dated back to 1960s. It is known that for identical or uniform machines, there exist polynomial time approximation schemes, while for unrelated machines no polynomial time approximation algorithms have an upper bound of $3/2-\epsilon$ unless P=NP. This talk is focused on two issues:
(1) Under the exponential time hypothesis, we provide lower bounds on the running times of exact and approximation schemes for identical machines. Most of the lower bounds show that the currently best known algorithms are almost best possible in terms of running times.
(2) By investigating the matrix $P=(p_{ij})_{mxn}$, where $p_{ij}$ is the processing time of job j on machine i, we show the NP-hardness to approximate within a factor of $3/2-\epsilon$ in the case that P is of rank 4.