New Challenges on Scheduling Theory

We consider scheduling problems arising when two agents, each owning a set of nonpreemptive jobs, compete to perform them on a shared resource. Each agent wants to minimize a certain cost function which depends on the completion times of his/her jobs only.

We consider two scenarios. In the first scenario, both agents want to minimize the total weighted completion time of their respective jobs. In the second scenario, the two cost functions are total weighted completion time (WC) and maximum lateness (Lmax) respectively.

In the first scenario (WC/WC), we address the problem of finding a compromise schedule that extends the notion of Nash Bargaining Solution to our discrete setting. Such problem is NP-hard, but it can be efficiently solved by enumerating a portion of the set of Pareto optimal solutions (which contains a pseudopolynomial number of points).

In the second scenario (WC/Lmax), we address the epsilon-constrained version of the problem, i.e., minimizing the first s cost with a constraint on the maximum cost for the second agent. We propose an exact branch and bound based on a Lagrangean relaxation of the problem. Note that this problem is a special case of the classical, single-agent problem of minimizing total weighted completion time with deadlines, for which the most efficient methods are based on a combinatorial lower bound by Posner. We prove that in the two-agent setting the bound given by the Lagrangean dual dominates Posner's.

Extensive computational results illustrate the effectiveness of the proposed solution approaches.

Co-authorRuslan Sadykov

Airborne radars are widely used to perform a large variety of tasks in an aircraft (searching, tracking, identifying targets, etc.) Such tasks play a crucial role for the aircraft and they are repeated in more or cyclic fashion. This defines a scheduling problem that impacts a lot on the quality of the radar output and on the overall safety of the aircraft.

In our model, jointly defined with Thales Airborne Systems, the radar executes the schedule of the current time frame while the schedule of the next frame is computed. The radar is a single machine and a radar task is a job to be scheduled on the machine. A job consists of a chain of operations with identical processing times. The operations of the same job should be ideally scheduled with a given frequency, and any deviation from this frequency is penalized using a V-shape function. Our objective is then to minimize the total penalty.

In this paper, we present three time-indexed formulations for the problem. Two of the formulations are compact and can be solved directly by a MIP solver. The third formulation relies on a Branch-and-Price algorithm. Theoretical and experimental comparisons of the formulations are reported.

Co-authorsPierre-Francois Dutot, Erik Saule

We present an extension of the 2 approximation of Gonzalez, Ibarra and Sahni[SIAM 77] for the problem of minimizing makespan when scheduling independent tasks on heterogeneous processors (Q||C_max).

We will first consider two classical list algorithms for this problem : Earliest Finish Time (EFT), and Earliest Finish Time with sorting tasks (EFT-LPT). After showing why EFT has an approximation ratio of Ω( log n), we will sketch the Gonzalez, Ibarra and Sahni analysis of ratio 2 for EFT-LPT.

Then we present our 3/2 dual approximation, with the proof of the bound and a worst case example which reaches the bound, proving its tightness.

Co-authorsEmmanuel Jeannot

We are considering the problem of scheduling task graphs when computation and communication durations are subject to uncertainties. The main objective is thus to minimize the makespan while maximizing the robustness. As these two metrics are not equivalent, we need a bicriteria approach to solve this problem. Moreover, as computing these two criteria is very time consuming we propose different approaches: from an evolutionary metaheuristic (best solutions but longer computation time) to more simple heuristics making approximations (bad quality solutions but fast computation time). We compare these different strategies experimentally and show that we are able to find different approximations of the Pareto front of this bicriteria problem.

Co-authorsRenaud Sirdey, Herve Kerivin and Dritan Nace

This conference is devoted to the study of a resource constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. It is also known as the problem of payments of debts. We present the two applications, we prove the NP-hardness of the problem and exhibit a few polynomial special cases. Because of the real time context, we then focus on a simulated annealing algorithm which has nice properties. We subsequently present a branch and bound algorithm which we have used to empirically evaluate the performances of our approximate resolution algorithm. We also describe briefly some polyhedral methods. Extensive computational results illustrate the conference.

We consider the basic problem of reconstructing an image in an (m * n) array from its horizontal and vertical projections: we are given the numbers h_i^s of pixels of color s in each row i | (i ≤ m) and the numbers v_j^s of pixels of color s in each column j | (j ≤ n).

It is known that this problem can be solved in polynomial time if the number k of colors is 2. It is NP-complete when k ≥ 4. The case k = 3 is apparently open.

After reviewing some special cases with k = 3 colors which can be solved in polynomial time, we will introduce an extension of the image reconstruction problem by allowing the presence of some pre-assignments. For this generalized problem, it will be shown that the boundary between easy and difficult problems can be located in a satisfactory way.

Co-authorsJ.Berlinska and M.Lawenda

Scheduling divisible load in systems with limited memory is considered. The load is distributed in multiple installments, memory reservations have block nature, the distributed system is a heterogeneous single level tree (star). This problem can be formulated as a mixed nonlinear programming problem. Since a branch-and-bound algorithm is nearly unusable due to its complexity, a genetic algorithm is proposed to study characteristic features of near-optimum solutions.

Co-authorsOlivier Beaumont, Nicolas Bonichon

In this talk, we discuss complexity issues for scheduling divisible workloads on heterogeneous systems under the bounded multi-port model. To our best knowledge, this paper is the first attempt to consider divisible load scheduling under a realistic communication model, where the master node can communicate simultaneously to several slaves, provided that bandwidth constraints are not exceeded. In this paper, we concentrate on one round distribution schemes, where a given node starts its processing only once all data has been received. Our main contributions are (i) the proof that processors start working immediately after receiving their work (ii) the study of the optimal schedule in the case of 2 processors and (iii) the proof that scheduling divisible load under the bounded multi-port model is NP-complete. This last result strongly differs from divisible load literature and represents the first NP-completeness result when latencies are not taken into account.

Co-authorsChristopher Y. Crutchfield, Zoran Dzunic, David R. Karger, and Jacob H. Scott

This talk presents improved approximation algorithms for the problem of "multiprocessor scheduling under uncertainty" (SUU), in which the execution of each job may fail probabilistically. This problem is motivated by the increasing use of distributed computing to handle large, computationally intensive tasks. In the SUU problem we are given n unit-length jobs and m machines, a directed acyclic graph of precedence constraints among jobs, and unrelated failure probabilities q_ij for each job j when executed on machine i for a single timestep. Our goal is to find a schedule that minimizes the expected makespan.

Lin and Rajaraman [SPAA 07] gave the first approximations for this NP-hard problem for the special cases of independent jobs, precedence constraints forming disjoint chains, and precedence constraints forming trees. Our results include several asymptotically better approximations. In particular, we improve upon the previously best O( log n)-approximation for independent jobs, giving an O( log log (u))-approximation, where u=min(m,n). We also have an O( log (n+m) log log (u))-approximation algorithm for precedence constraints that form disjoint chains (improving on the previously best bound by a ( log (n) / log log (n))² factor when n=m^Θ(1).

Our techniques include reducing SUU to a problem in "stochastic scheduling", where machines must process a set of jobs with randomly distributed lengths. Our algorithms for SUU also apply to standard problem in this stochastic setting, giving the first approximation algorithms for preemptive stochastic scheduling on unrelated machines.

Co-authorGuochuan Zhang

We usually define an optimization problem from the viewpoint of a user. For examples, Bin Packing is to minimize the number of bins used while Knapsack aims at maximizing the total profit gained with a feasible packing. However, if we change the role of the decision maker to be the owner of the resource (bins, knapsack) who wants to sell his resource, the problem becomes different. In this talk, we will discuss several combinatorial optimization problems with such reverse objectives by considering the computational complexity and design and analysis of online/offline algorithms. Topics will cover the lazy bureaucrat scheduling problem, the maximum resource bin packing problem, and the lazy bin covering problem etc.

Co-authorsNicolas Navet and Jorn Migge

In this talk, two scheduling policies for real Time Systems namely background scheduling (BS) and dual priority (DP) are compared in terms of response times for soft real time traffic (SRT). We will show that in the preemptive and in the non-preemptive cases, DP always outperforms BS if and only if the SRT traffic is FIFO. When the SRT traffic is not FIFO but all tasks are of equal size then DP also outperforms BS on average. However, some non-FIFO non-equal examples are provided where BS outperforms DP on average. The proofs are based on a trajectorial method that proves useful in many other situations as well.

Co-authorsChris Potts, Vitaly Strusevich and Jonathan Whitehead

Single machine scheduling under several rules of processing time deterioration and given precedence constraints is considered. We study either start time deterioration when the actual processing time depends linearly on the start time of a job or positional deterioration when the processing time depends polynomially or exponentially on the position in which a job is sequenced. Under various models of deterioration, we prove that the objective functions are priority-generating for several scheduling problems of minimizing either the makespan or the (weighted) sum of completion times, and thereby the corresponding problems with series-parallel precedence constraints are solvable in O(n log n) time.

Co-authorsWladyslaw Janiak, Radoslaw Rudek

This paper is devoted to scheduling problems with a learning effect, which is understood as a process of an acquiring experience that increases the efficiency of a processor. A measurable result of this effect is decreasing of job processing times. The existence of this phenomenon in many manufacturing systems is undoubted, thus it is perceived as a worthwhile to be taken into consideration during production planning to increase production efficiency. To carry out a reliable study on the learning effect in the scheduling domain a short survey of related results is presented. In particular, the existing models of the experience are presented along with a discussion on different shapes of the learning curve. On this basis, it is observed that the computational complexity of the classical problems usually increase with the learning effect. Namely, we show that if the learning effect is taken into consideration some polynomially solvable classical problems become NP-hard. Moreover, some classical problem equivalencies do not longer hold, i.e., the single processor makespan minimization with release dates and the single processor minimization of maximum lateness. However, some special polynomially solvable cases and properties of optimal solutions are also provided. Finally, directions of further research are given.

Co-authorRalf Thole

In this paper we study variants of the non-preemptive parallel job scheduling problem where the number of machines is polynomially bounded in the number of jobs.

For this problem we show that a schedule with length at most (1+ε)OPT can be calculated in polynomial time, which is the best possible result (in the sense of approximation ratio), since the problem is strongly NP-hard. For the case when all (non-malleable) jobs must be allotted to a subset of machines with consecutive indices a schedule with length at most (1.5+ε)OPT can be calculated in polynomial time. The previously best known results are algorithms with absolute approximation ratio 2.

Moreover, we outline extensions of both algorithms with the same ratio to the case of malleable jobs (without monotonic properties of the processing times).

Co-authorsLukasz Jozefowski and Wieslaw Kubiak

Fairness is one of the most important issues considered in the control of IT systems where clients compete for shared resources. In the most desired situation the algorithm that allocates the resources to clients should do its job fairly. Although the fairness as a term is extremely hard to define there are some metrics that are used to measure it. The most important and popular ones are known as Relative Fairness Bound (RFB) and Absolute Fairness Bound (AFB). They are used for example in packet-switched networks to evaluate fairness of packet-scheduling algorithms. It seems to be reasonable to optimize this measure in order to improve the fairness of a scheduling algorithm. We show that RFB is closely related to one of the objective functions proposed in the theory of apportionment, while AFB is equivalent to an objective function considered in the Product Rate Variation (PRV) problem. Both problems can be generalized to proportional allocation of any discrete resource. We prove that the optimization of the RFB leads to the Alabama paradox found in the apportionment theory. In order to avoid the consequences of this effect the optimal sequence may be constructed only after arrival of all packets which is impractical.

Previously, I described a sports scheduling problem where the aim was to minimise the distances travelled by English Football teams over the Christmas period. In this talk, I will discuss some extensions to this work. Depending on the progress made by the time of the conference I will describe the following.

• Instead of using a computationally expensive depth first search, I will replace this phase of the search with CPLEX.
• Restricting the maximum distance travelled by a single team so that the quality of the overall solution is not achieved at the expense of one, or a few, teams. We will explore how this changes the overall solution quality.
• Investigate a multi-objective approach so as to balance two conflicting objectives (distance travelled and pair conflicts).
• Rather than scheduling two fixtures for each team, schedule four fixtures. This is a requirement in some years (e.g. World up Years).

Co-authorMarton Drotos

We address a resource levelling problem in a parallel machine environment. Given a set of m parallel machines, one renewable resource, and a set of n tasks each dedicated to exactly one of the parallel machines. Each task has a processing time, an earliest start time, a deadline, and a resource requirement. The resource has a capacity, but it can be used above this capacity which is the overtime usage of the resource. A schedule with minimum overtime resource usage is sought. We provide several complexity results and propose a heuristic algorithm which reduces the problem to single machine ones, where each single machine problem is equivalent to a TSP with time windows and start time dependent costs.

We consider a single round robin sports tournament (i.e. each team plays against each other team once), partitioned into rounds, where for every round only a single sports court is available and all teams have to travel to this location. In order to reduce the number of travels, each team is supposed to play twice in each round. Such tournaments arise for example in soccer tournaments where on several consecutive weekends all teams travel to a common place, play two matches there and travel home afterwards. Due to the fact that only a single court is available, at any time only a single match can be played and waiting times for the teams between their two matches cannot be avoided.

The objective is to find a schedule which minimizes the waiting times for the teams in some sense. If we assume that a team does not arrive before its first match and leaves immediately after its second match, only the free slots between its two matches have to be considered as waiting times.

We study two variants in which zero waiting times are allowed or not and construct schedules for any odd number of teams minimizing the number of long waiting times and the total waiting time simultaneously.

Co-authorsA. Dolgui and V. Eremeev

We study a problem of optimal scheduling and lot-sizing a number of products on m unrelated parallel machines to satisfy given demands. A sequence dependent setup time is required between lots of different products. The products are assumed to be all continuously divisible or all discrete. The criterion is to minimize the time, at which all the demands are satisfied, C_max, or the maximum lateness of the product completion times from the given due dates, L_max. The problem is motivated by the real-life scheduling applications in multi-product plants. We derive properties of optimal solutions, NP-hardness proofs, enumeration and dynamic programming algorithms for various special cases of the problem. The major contribution is an NP-hardness proof and pseudo-polynomial algorithms linear in m for the case, in which the number of products is a given constant. The results can be adapted for solving a production line design problem. Research of M.Y. Kovalyov was conducted within the scientific "Mathematical models 28" of the Republic of Belarus.

This talk is about online scheduling algorithms in the dynamic speed scaling model, where a processor can scale its speed between 0 and some maximum speed T so as to manage its energy consumption. Energy is consumed at rate s^α when the processor runs at speed s, where α > 1 is a constant. Given a set of jobs, it is desirable to find a schedule that is energy efficient and still performs well regarding some quality of service like the total flow time. This talk will discuss online algorithms that are O(1)-competitive for minimizing the total flow time plus energy usage on a single processor, as well as on a pool of parallel processors. In particular, the latter result reveals an online algorithm that does not require job migration, yet it is O(1)-competitive against any migratory offline algorithm.

In this talk, we present a fully decentralized algorithm for fair resource sharing between multiple bag-of-tasks applications in a grid environment. This algorithm is inspired from related work on multi-path routing in communication network. An interesting feature of this algorithm is that it allows the choice of wide variety of fairness criteria and achieves both optimal path selection and flow control. In addition, this algorithm only requires local information at each slave computing tasks and at each buffer of the network links while minimal computation is done by the schedulers. A naive adaptation is unstable and inefficient though. Fortunately, a simple and effective scaling mechanism is sufficient to circumvent this issue. This scaling mechanism is motivated by a careful study of the subtle differences with the classical multi-path routing problem. We prove its efficiency through a detailed analysis of a simple simulation.

Co-authorsMichael Bender, David Bunde, Kevin Pedretti, Cindy Phillips

On supercomputers, job runtime depends not only on the number of processors but also on the particular set of processors assigned to it. Jobs should be allocated to localized clusters of processors to minimize communication costs and avoid bandwidth contention caused by overlapping jobs.

Experimental results indicate that the "average number of communication hops" between the processors allocated to a job correlates with the job's completion time. We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of communication hops.

The associated clustering problem is as follows: Given n points in R^d, find a size-k subset with minimum average pairwise L₁ distance. We review the problem, previous experimental and theoretical results, and we report on new experimental results.

Scheduling problems are already difficult on traditional parallel machines. They become extremely challenging on heterogeneous clusters, even when embarrassingly parallel applications are considered. In this paper we deal with the problem of scheduling multiple applications, made of collections of independent and identical tasks, on a heterogeneous master-worker platform. The applications are submitted online, which means that there is no a priori (static) knowledge of the workload distribution at the beginning of the execution. The objective is to minimize the maximum stretch, i.e. the maximum ratio between the actual time an application has spent in the system and the time this application would have spent if executed alone. On the theoretical side, we design an optimal algorithm for the offline version of the problem (when all release dates and application characteristics are known beforehand). We also introduce several heuristics for the general case of online applications. On the practical side, we have conducted extensive simulations and MPI experiments, showing that we are able to deal with very large problem instances in a few seconds. Also, the solution that we compute totally outperforms classical heuristics from the literature, thereby fully assessing the usefulness of our approach.

Co-authorEric Sanlaville

Grids provide a way to share computing resources for virtual communities in a ser setting. In such an environment problems of fair resource sharing arise.

In this talk we will study the problem in which we have to allocate resources in the case of uniprocessor jobs with large or unlimited duration.

Each user has a set of jobs to be processed on a set of machines. The evaluation criterion for a given user is the number of machines allocated to him. We use the leximin order as our fairness measurement between allocations. The difficulty arises from the fact that demands arrive on-line. This is modeled by a set of possible scenarios.

We will characterize the Pareto set for that problem and give an enumeration algorithm of it.

In this talk, we examine simultaneous order acceptance and scheduling decisions in a make-to-order system modeled in a single machine environment. Given a set of orders coming from customers with known release dates, due dates, deadlines, processing times, sequence dependent setup times and revenues, the manufacturer has to decide on the subset of orders to select, considering the limited production capacity to maximize total revenue. The revenue from an order is defined as a function of its tardiness and deadline. This problem generalizes some well-known NP-hard scheduling problems such as the single machine total weighted tardiness problem with sequence dependent setup times. We give an MILP formulation for the problem which can be solved to optimality up to 15 orders within reasonable CPU time. We develop three heuristic algorithms to solve large size problems. We compare the performance of these algorithms with respect to either the optimal solution or the bound obtained from the LP relaxation strengthened with valid inequalities. Computational tests indicate that the proposed algorithms are both computationally efficient and effective even for instances up to 300 orders.

Co-authorsJan Weglarz and Krzysztof Kurowski, Jarek Nabrzyski

Most of the existing approaches to resource management in Grids assume a single scheduling objective to be optimized. Even if multiple objectives are taken into account they are usually selected a priori, globally for all users' jobs. Another common assumption concerns centralized scheduling. Although local resource management systems are considered, Grid resource broker is the only decision point. These assumptions are often not valid in Grid infrastructures. First, users may have diverse preferences depending on their applications, available budget and time constraints. Second, Grids are by definition distributed across administrative domains so local systems may make decisions according to their own resource management policies. We address these issues in a model and a method proposed for Grids with required Quality of Service (QoS). To this end we show how to aggregate various criteria to find a schedule that satisfies users' preferences and requirements in the best possible and equitable way. To reflect local policies of organizations participating in the Grid we also propose simple strategies for managing and offering advance reservations. We study the influence of these strategies on a performance of both local systems and end-users' applications. The results of experiments using the Grid Scheduling Simulator (GSSIM) are presented. We also discuss how the presented model is applied in practice.

Co-authorsSekou Diakite and Jean-Marc Nicod

We consider the scheduling of one batch of identical jobs on a grid of heterogeneous computers. Each job of the batch is an application described by a Directed Acyclic Graph (DAG) of tasks without forks (intree) and executed independently from the others jobs. Each job is an instance of the same DAG and the tasks of the DAG are typed, ie. there may be two identical tasks in one job and a task of one type can only be executed on the computers where the corresponding program is installed. The execution resources are distributed and each resource can carry out a set of task types, the installed programs, so several hosts may be able to carry out the same task. The objective function of our problem is to minimize the makespan of the batch execution. An example that matches these definitions, is a workflow to process a set of data in several steps on a grid where the softwares installed on the hosts differs: each step could be a filter applied to one or more images and only some filters are available on each host.

In this context, we consider the optimization of the schedule depending on the size, from small to large sized batches, on the characteristics of the batches, etc. Different scheduling techniques could be used to schedule such applications: off-line or online, flow oriented, etc. Classical off-line scheduling techniques for DAGs are heuristics, as there is no direct optimal solution to this problem. They just take one job into account so that multiple jobs will be scheduled as if they were just one application, without benefiting from the knowledge that there are several identical jobs nor of the structure of the jobs. Moreover, if the size of the batch is large, some heuristics may become very costly. On-line techniques are usually simple but they do not either take benefit of the identical structure of the jobs. Steady state oriented scheduling techniques provides an optimal solution in this case but for an infinite number of jobs.

We compare three scheduling techniques: a simple on-line scheduler, a steady-state scheduling technique and a genetic heuristic based algorithm. The on-line algorithm just schedule the tasks as soon as they are free of their dependencies. The genetic based algorithm start from a list-scheduling solution and improve it by selecting the best individuals from the makespan of their schedule. The steady-state technique generates a periodic schedule from the result of a linear program, built with the constraints that characterize the problem.

By using an experimental evaluation based on simulation, we show that the platform architecture and the DAG structure affect the performances of the schedule differently depending on the used algorithm. Then, we propose some adaptations to these scheduling algorithms to improve their performances on the execution of the batch.

Co-authorsRobert Carr, Anand Ganti

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 and moving qubits, or the information associated with qubits, to locations where they can interact in gates. This is a multiprocessor, precedence-constrained scheduling problem, with additional routing constraints.

In this talk, we will consider a reasonably simple architecture: the bilinear array, introduced by Hollenberg et al. We will describe this scheduling problem and discuss our early integer-programming-based and heuristic methods for solving this problem.

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.

Co-authorsNicholas G. Hall, Marc E. Posner

We consider an online scheduling environment where decisions are made without knowledge of the data of jobs that may arrive later. However, additional jobs can only arrive at known future times. This environment interpolates between the classical offline and online scheduling environments, and approaches the classical online environment when there are many equally spaced potential job arrival times. The objective is to minimize the sum of weighted completion times, a widely used measure of work-in-process inventory cost and customer service. For a nonpreemptive single machine environment, we show that a lower bound on the competitive ratio of any online algorithm is the solution of a mathematical program. This lower bound is between (1+√5)/2 and 2, with the exact value depending on the potential job arrival times. We also provide a 'best online' scheduling algorithm, and show that its competitive ratio matches this lower bound. We analyze two practically motivated special cases where the potential job arrival times have a special structure. When there are many equally spaced potential job arrival times, the competitive ratio of our online algorithm approaches the best possible competitive ratio of 2 for the classical online problem.

We describe and illustrate a model for realizing ant-inspired algorithms that coordinate robots within a fixed, geographically constrained environment --- such as a factory floor. The model, which we name *Cellular ANTomata*, inverts the relationship between ant-robots and the enviroment that they navigate: intelligence now resides in the environment rather than in the ants! We illustrate the Cellular ANTomaton model via three proof-of-concept problems: (1) having ants "park" in the nearest corner; (2) having ants seek food items (both with and without impenetrable obstacles); (3) having ants thread a maze. We describe algorithms for all three problems, that accomplish these goals provably more efficiently than traditional, "intelligent," ant-robots can; indeed, "intelligent" ant-robots cannot park at all! All of our algorithms are *scalable* in the sense that they provably work within any finite-size environment --- i.e., they do not depend on the number of cells. The challenge that we concentrate on in this talk is to determine whether or not the algorithms are optimally efficient for the model.

Co-authorDenis Trystram

Most of the high performance computing applications developed today are running on parallel and distributed platforms (clusters, computational grids, multi-core machines, etc.). Whatever the high performance computing system, many users compete to perform their respective jobs on the shared resources. Each user has specific needs or wishes for computing his/her jobs. In this work, we are interested in studying the problem of optimizing simultaneously a large number of different objectives.

Our goal is to propose and analyze simple policies for sharing the resources taking into account the objectives of the users using Multi-objective Optimization. In this field, some methods for optimizing simultaneously two or three objectives have been developed. Several sophisticated analyses have been done for specific problems; however, those results are difficult to extend to a large set of objectives. No generic combinatorial method is known for many objectives.

Our contribution is to solve the multi-user scheduling problem as a classical multi-objective problem with one objective per user. Some results have already been proposed for two users on a single computing resource. The analysis proposed in this paper concerns an arbitrarily fixed number of users and is not restricted to a single resource. We investigate objectives that are functions of the completion time, namely, maximum completion time (makespan), sum of completion times (weighted or not) and maximum flow time. We first derive inapproximability bounds; then we analyze several greedy heuristics and compute the corresponding approximation ratios.

Co-authorsSascha Herrmann, Hanno Sagebiel

We consider the short-term planning of multistage continuous multiproduct plants. In the literature this problem is generally modeled as a monolithic mixed-integer linear or nonlinear program. In this paper we propose a closed-loop decomposition approach which starts from separating the problem into an operations planning and an operations scheduling problem. The operations planning problem consists in fixing the operating conditions of the processes and can be formulated as a nonlinear program of moderate size. The solution to the operations planning problem provides a set of continuous operations, which have to be scheduled on the processing units of the plant. For solving this operations scheduling problem we present a novel mixed-integer linear programming formulation as well as a fast priority-rule based scheduling method. Having computed a feasible production schedule, we return to the operations planning phase, where we re-optimize the operating conditions in such a way that we can guarantee the existence of a feasible solution to the operations scheduling problem. We proceed with scheduling the operations again and iterate the planning and scheduling phases until a fixed-point solution has been reached. It can be shown that the sequence of the production schedules generated in this way is monotonically improving. The method is able to find good feasible schedules for complex benchmark instances within a few minutes of computation time on a standard PC.

Co-authorPiotr Switalski

We propose a solution to the multiprocessor scheduling problem based on applying a relatively new metaheuristic called Generalized Extremal Optimization (GEO). GEO is inspired by a simple coevolutionary model known as a Bak-Sneppen model. The model assumes existing of an ecosystem consisting of N species. Evolution in this model is driven by a process in which the weakest species in the ecosystem, together with its nearest neighbors is always forced to mutate. This process shows characteristics of a phenomena called a punctuated equlibrium and observed in evolutionary biology. It means that in evolution there are periods of stability punctuated by a change in the environment that forces relatively rapid adaptation of the system by generating "avalanches" of changes. We interpret the multiprocessor scheduling problem in terms of the Bak-Sneppen model and apply the GEO algorithm to solve the problem. We show that the model is simple and yet outperforms genetic algorithm-based approach to the multiprocessor scheduling.

Co-authorsTomas Ebenlendr and Marek Krcal

We design a 1.75-approximation algorithm for a special case of scheduling parallel machines to minimize the makespan, namely the case where each job can be assigned to at most two machines, with the same processing time on either machine. (This is a special case of so-called restricted assignment, where the set of eligible machines can be arbitrary for each job.) We also show that even for this special case it is $NP$-hard to compute better than 1.5 approximation.

This is the first improvement of the approximation ratio 2 of Lenstra, Shmoys, and Tardos [Approximation algorithms for scheduling unrelated parallel machines, Math. Program., 46:259--271, 1990], for any special case with unbounded number of machines. Our lower bound yields the same ratio as their lower bound which works for restricted assignment, and which is still the state-of-the-art lower bound even for the most general case.

Co-authorsJacek Juraszek and Erwin Pesch

The work concerns the problem of maximizing revenue from executing a set of jobs on a set of parallel identical machines. Each job is described by the release time at which it becomes available for processing, the execution time for which it has to be performed without preemption, the due date and deadline. Moreover, the revenue is given for each job representing income from its non-delayed execution. If a job is late, revenue is decreased with the weighted tardiness. The goal is to select a subset of jobs and to schedule them in the feasible time intervals between release times and deadlines on the set of identical parallel machines in order to maximize the total revenue. Due to the intractability of the problem, we propose the simulated annealing method (SA) for solving it. Preliminary computational experiments were performed for a set of randomly generated input instances of various characteristics.

Co-authorsNatalia V. Shakhlevich and Akiyoshi Shioura

In scheduling problems with controllable processing times each job is assigned the duration of its processing from a given interval. In bicriteria setting, the goal is to find a set of Pareto-optimal solutions with one function to represent a quality measure of the corresponding schedule and the other function related to the cost of the changing the processing times, known as the compression cost.

Many problems of preemptive scheduling with controllable processing times can be reduced to linear programming (LP) problems over special regions, e.g., a (generalized) polymatroid or a submodular polyhedron. In this talk we focus on a single machine bicriteria problem to simultaneously minimize (i) the maximum penalty that depends on the jobs completion times and (ii) the total compression cost. We show that the problem can be reduced to a polynomial number of parametric LP problems defined over a submodular polyhedron intersected with a box. We prove a fairly general statement that reduces an LP problem over a submodular polyhedron intersected with a box to the problem over a base polyhedron (with a different rank function). The later problem admits a close form solution by a greedy algorithm. This results into an algorithm for the original scheduling problem with the running time that is two orders less that known earlier.

The established link of the scheduling problems to optimization over base polyhedra not only allows a clear justification of the solution algorithms but leads to faster algorithms and can be seen as a general technique of handling the whole range of these problems.

This presentation addresses nonclairvoyant and nonpreemptive online job scheduling in Grids. In the applied basic model, the Grid system consists of a large number of identical processors that are divided into several machines. Jobs are independent, they have a fixed degree of parallelism, and they are submitted over time. Further, a job can only be executed on the processors belonging to the same machine. It is our goal to minimize the total makespan. We show that the performance of Garey and Graham's list scheduling algorithm is significantly worse in Grids than in multiprocessors. Then we present a Grid scheduling algorithm that guarantees a competitive factor of 5. This algorithm can be implemented using a "job stealing" approach and may be well suited to serve as a starting point for Grid scheduling algorithms in real systems.

Co-authorsE. G. Coffman, Jr., D. Matsypura and D. Oron

We consider the problem of finding a minimum total-completion-time schedule of unit-processing-time tasks with release time and precedence constraints on two processors. Polynomial-time solutions to this problem are known in the preemptive case with outtree precedence constraints [1] and in the nonpreemptive case with general precedence constraints [2]. We show that the problem can also be solved in polynomial time in the preemptive case with intree precedence constraints.

[1]Baptiste & Timkovsky, Oper. Res. Lett., 28(5):205-212, 2001

[2]Baptiste & Timkovsky, Math. Methods Oper. Res., 60(1):145-153, 2004

Co-authorsPierre-Francois Dutot, Fanny Pascual, Krzysztof Rzadca

The inherent distributed nature of the new computing platforms (clusters and computational grids composed of collections of clusters) results in the problem of scheduling parallel jobs produced by several independent organizations that have partial control over the system. We consider systems in which each organization owns a cluster of processors. Each organization wants its jobs to be completed as soon as possible.

In this work, we consider a model of platforms consisting of N clusters of m_i processors. We show that it is always possible to produce a collaborative solution that respects the participant's selfish objectives (local makespan), while at the same time improving the global performances of the system. We propose an algorithm with an absolute performance guarantee of 3. We construct an inapproximation bound with reaches asymptotically the bound of 3 (when the number of organizations is arbitrarly large). Then, we study some specific restricted cases. Finally, we give another algorithm that practically improves the previous algorithm. It allows to better balance the load. This is assessed by extensive experiments.

Co-authorsBirgit Heydenreich, Debasis Mishra, and Rudolf Mueller

The design of optimal auctions is recognized as an intriguing issue in auction theory; first studied by Myerson (1981) for the case of single item auctions. In that setting, the goal is to maximize the seller's revenue. We study the design of optimal auctions (more precisely, mechanisms) in a setting where job-agents compete for being processed on a single machine that can only handle one job at a time. Each job has a service time and a weight representing the disutility for waiting. In this setting, it is folklore that the total disutility of the jobs is minimized by Smith's rule: schedule jobs in order of non-increasing ratios weight over service time.

While the jobs' service times are public information, we assume a job's weight is only known to the job itself. Given jobs' reports about their private information, a mechanism for this setting determines both an order in which jobs are served, and for each agent a payment that the agent receives from the provider. The payment can be seen as a reduction of service fees to compensate for waiting. Publicly known probability distributions represent common beliefs about other jobs' weights. We study two cases: discrete and continuous probability distributions.

We aim at finding Bayes-Nash incentive compatible mechanisms that are optimal, that is, minimize the total expected expenses of the system. By a graph theoretic interpretation of the incentive compatibility constraints -first used by Rochet (1987)- we are able to derive optimal mechanisms. For both discrete and continuous distributions of weights, we obtain closed formulae for "virtual" job weights, and show that serving the jobs in the order of non-increasing ratios of virtual weights over service times is optimal, as long as a certain regularity condition is fulfilled. It also turns out that the optimal mechanisms do not necessarily minimize total disutility, but they do so if e.g. all jobs are symmetric.

Co-authorHaifeng Xu

We consider an extension of the standard caching problem for the case of parallel machines. We focus here on the offline case where all data are known in advance. We study different the problem under different cases (number of chains, size of the cache, ...). We present a generic dynamic programming algorithm with exponential complexity giving optimal results for all cases and some polynomial-time algorithms for some cases. We conclude by presenting ongoing work on approximation algorithms.

This talk will survey several stochastic papers, and put them in a scheduling context.

Schedulers know that for most problems only small instances can be solved optimally. For medium sized problems one has to resort to approximations. My own view is that once the problems are really large, we are again in a simplified situation: we can expect statistical averaging, and obtain some simple and effective solutions.

To analyze the behavior under statistical averaging we should use the tools of queueing theory. As we all know queueing theory can very easily also become intractable. However, recent trends, of approximating queueing networks by fluid or diffusion networks, point at some very impressive results.

I will try to bridge these approaches, by showing how concepts of scheduling are translated into queuing concepts, and how controls for queueing networks can be translated back to scheduling algorithms.