An Experimental Study of Algorithms for Weighted Completion Time Scheduling

We consider the total weighted completion time scheduling problem for parallel identical machines and precedence constraints, P| prec|\sum w _i C _i . This important and broad class of problems is known to be NP-hard, even for restricted special cases, and the best known approximation algorithms have worst-case performance that is far from optimal. However, little is known about the experimental behavior of algorithms for the general problem. This paper represents the first attempt to describe and evaluate comprehensively a range of weighted completion time scheduling algorithms. We first describe a family of combinatorial scheduling algorithms that optimally solve the single-machine problem, and show that they can be used to achieve good performance for the multiple-machine problem. These algorithms are efficient and find schedules that are on average within 1.5\percent of optimal over a large synthetic benchmark consisting of trees, chains, and instances with no precedence constraints. We then present several ways to create feasible schedules from nonintegral solutions to a new linear programming relaxation for the multiple-machine problem. The best of these linear programming-based approaches finds schedules that are within 0.2\percent of optimal over our benchmark. Finally, we describe how the scheduling phase in profile-based program compilation can be expressed as a weighted completion time scheduling problem and apply our algorithms to a set of instances extracted from the SPECint95 compiler benchmark. For these instances with arbitrary precedence constraints, the best linear programming-based approach finds optimal solutions in 78\percent of cases. Our results demonstrate that careful experimentation can help lead the way to high quality algorithms, even for difficult optimization problems. Received October 30, 1998; revised March 28, 2001.     

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

We present polylogarithmic approximations for the R|prec|C _max and R|prec|∑ _j w _j C _j problems, when the precedence constraints are “treelike”—i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated machines with precedence constraints of any kind. We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment—this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion + dilation”, as in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617–632, 1994). The first step in our algorithm for the R|prec|C _max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function. A preliminary version of this paper appeared in the Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 146–157, 2005. V.S. Anil Kumar supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. M.V. Marathe supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. Part of this work by S. Parthasarathy was done while at the Department of Computer Science, University of Maryland, College Park, MD 20742, and in part while visiting the Los Alamos National Laboratory. Research supported in part by NSF Award CCR-0208005 and NSF ITR Award CNS-0426683. Research of A. Srinivasan supported in part by NSF Award CCR-0208005, NSF ITR Award CNS-0426683, and NSF Award CNS-0626636.     

Speed Scaling of Tasks with Precedence Constraints

We consider the problem of speed scaling to conserve energy in a multiprocessor setting where there are precedence constraints between tasks, and where the performance measure is the makespan. That is, we consider an energy bounded version of the classic problem Pm | prec | C _max. We extend the standard 3-field notation and denote this problem as Sm | prec, energy | C _max. We show that, without loss of generality, one need only consider constant power schedules. We then show how to reduce this problem to the problem Qm | prec | C _max to obtain a poly-log(m)-approximation algorithm. A preliminary version of this paper appears in Proceedings of the 3rd Workshop on Approximation and Online Algorithms (WAOA 2005). Research of K. Pruhs supported in part by NSF grants CCR-0098752, ANI-0123705, CNS-0325353, CCF-0448196, CCF-0514058, and IIS-0534531. Research of R. van Stee supported by Alexander von Humboldt-Stiftung.     

Tighter Bounds on Preemptive Job Shop Scheduling with Two Machines

We consider the preemptive job shop scheduling problem with two machines, with the objective to minimize the makespan. We present an algorithm that finds a schedule of length at most P _max/2 greater than the optimal schedule length, where P _max is the length of the longest job. Received June 13, 2000     

NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow

We consider the version of broadcast scheduling where a server can transmit W messages of a given set at each time-step, answering previously made requests for these messages. The goal is to minimize the average response time (ART) if the amount of requests is known in advance for each time-step and message. We prove that this problem is NP-hard, thus answering an open question stated by Kalyanasundaram, Pruhs and Velauthapillai (Proceedings of ESA 2000, LNCS 1879, 2000, pp. 290–301). Furthermore, we present an approximation algorithm that is allowed to send several messages at once. Using six channels for transmissions, the algorithm achieves an ART that is at least as good as the optimal solution using one channel. From the NP-hardness of broadcast scheduling we derive a new inapproximability result of (2 − ε, 1) for the (congestion, cost) bicriteria version of the single source unsplittable min-cost flow problem, for arbitrary ε > 0. The result holds even in the often considered case where the maximum demand is less than or equal to the minimum edge capacity (d _max ≤ u _min), a case for which an algorithm with ratio (3, 1) was presented by Skutella.     

A robust approach for the single machine scheduling problem

This paper describes a robust approach for the single machine scheduling problem 1|r _i |L _max. The method is said to be robust since it characterizes a large set of optimal solutions allowing to switch from one solution to another, without any performance loss, in order to face potential disruptions which occur during the schedule execution. It is based on a dominance theorem that characterizes a set of dominant sequences, using the interval structure defined by the relative order of the release and the due dates of jobs. The performance of a set of dominant sequences can be determined in polynomial time by computing the most favorable and the most unfavorable sequences associated with each job, with regard to the lateness criterion. A branch and bound procedure is proposed which modifies the interval structure of the problem in order to tighten the dominant set of sequences so that only the optimal sequences are conserved.     

A new solution branch for the Blasius equation—A shrinking sheet problem

In this work, a similarity equation of the momentum boundary layer is studied for a moving flat plate with mass transfer in a stationary fluid. The solution is applicable to the practical problem of a shrinking sheet with a constant sheet velocity. Theoretical estimation of the solution domain is obtained. It is shown that the solution only exists with mass suction at the wall surface. The equation with the associated boundary conditions is solved using numerical techniques. Greatly different from the continuously stretching surface problem and the Blasius problem with a free stream, quite complicated behavior is observed in the results. It is seen that there are three different solution zones divided by two critical mass transfer parameters, f₀₁≈1.7028 and f₀₂≈1.7324. When f₀<f₀₁, there is no solution for this problem, multiple solutions for f₀₁<f₀≤f₀₂, and one solution when (f₀=f₀₁)(f₀>f₀₂). There is a terminating point for the solution domain and the terminating point corresponds to a special algebraically decaying solution for the current problem. The current results provide a new solution branch of the Blasius equation, which is greatly different from the previous study and provide more insight into the understanding of the Blasius equation.     

Scheduling task graphs optimally with A*

Scheduling tasks onto the processors of a parallel system is a crucial part of program parallelisation. Due to the NP-hard nature of the task scheduling problem, scheduling algorithms are based on heuristics that try to produce good rather than optimal schedules. Nevertheless, in certain situations it is desirable to have optimal schedules, for example for time-critical systems or to evaluate scheduling heuristics. This paper investigates the task scheduling problem using the A* search algorithm which is a best-first state space search. The adaptation of the A* search algorithm for the task scheduling problem is referred to as the A* scheduling algorithm. The A* scheduling algorithm can produce optimal schedules in reasonable time for small to medium sized task graphs with several tens of nodes. In comparison to a previous approach, the here presented A* scheduling algorithm has a significantly reduced search space due to a much improved consistent and admissible cost function f(s) and additional pruning techniques. Experimental results show that the cost function and the various pruning techniques are very effective for the workload. Last but not least, the results show that the proposed A* scheduling algorithm significantly outperforms the previous approach.     

The optimal control approach to generalized multiprocessor scheduling

In this paper we present several new results in the theory of homogeneous multiprocessor scheduling. We start with some assumptions about the behavior of tasks, with associated precedence constraints, as processor power is applied. We assume that as more processors are applied to a task, the time taken to compute it decreases, yielding some speedup. Because of communication, synchronization, and task scheduling overhead, this speedup increases less than linearly with the number of processors applied. We also assume that the number of processors which can be assigned to a task is a continuous variable, with a view to exploiting continuous mathematics. The optimal scheduling problem is to determine the number of processors assigned to each task, and task sequencing, to minimize the finishing time.These assumptions allow us to recast the optimal scheduling problem in a form which can be addressed by optimal control theory. Various theorems can be proven which characterize the optimal scheduling solution. Most importantly, for the special case where the speedup function of each task isp , wherep is the amount of processing power applied to the task, we can directly solve our equations for the optimal solution. In this case, for task graphs formed from parallel and series connections, the solution can be derived by inspection. The solution can also be shown to be shortest path from the initial to the final state, as measured by anl _1/ distance metric, subject to obstacle constraints imposed by the precedence constraints.This research has been funded in part by the Advanced Research Project Agency monitored by ONR under Grant No. N00014-89-J-1489, in part by Draper Laboratory, in part by DARPA Contract No. N00014-87-K-0825, and in part by NSF Grant No. MIP-9012773. The first author is now with AT&T Bell Laboratories and the second author is with BBN Incorporated.     

Semi-Online Algorithms for Parallel Machine Scheduling Problems

This paper considers two semi-online versions of scheduling problem P2||C_max where one type of partial information is available and one type of additional algorithmic extension is allowed simultaneously. For the semi-online version where a buffer of length 1 is available and the total size of all jobs is known in advance, we present an optimal algorithm with competitive ratio 5/4. We also show that it does not help that the buffer length is greater than 1. For the semi-online version where two parallel processors are available and the total size of all jobs is known in advance, we present an optimal algorithm with competitive ratio 6/5.The second author is supported by TRAPOYT of China, National Natural Science Foundation of China (10271110). Corresponding author: Y. He.     

Packet Routing in Networks with Long Wires

In this paper, we examine the packet routing problem for networks with wires of differing length. We consider this problem in a network independent context, in which routing time is expressed in terms of "congestion" and "dilation" measures for a set of packet paths. We give, for any constant ε > 0, a randomized on-line algorithm for routing any set of N packets in O((C lg^ε(Nd) + D lg(Nd))/lg lg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into account, and d is the longest path in terms of number of wires. We also show that for edge-simple paths, there exists a schedule (which could be found off-line) of length O((cd_max + D) (lg(d_max)/lg lg (d_max))), where d_max is the maximum wire delay in the network. These results improve upon previous routing results which assume that unit time suffices to traverse a wire of any length. They also yield improved results for job-shop scheduling as long as we incorporate a technical restriction on the job-shop problem.     

A probabilistic solution of robust H∞ control problem with scaled matrices

This paper addresses the robust H_∞ control problem with scaled matrices. It is difficult to find a global optimal solution for this non-convex optimisation problem. A probabilistic solution, which can achieve globally optimal robust performance within any pre-specified tolerance, is obtained by using the proposed method based on randomised algorithm. In the proposed method, the scaled H_∞ control problem is divided into two parts: (1) assume the scaled matrices be random variables, the scaled H_∞ control problem is converted to a convex optimisation problem for the fixed sample of the scaled matrix and a optimal solution corresponding to the fixed sample is obtained; (2) a probabilistic optimal solution is obtained by using the randomised algorithm based on a finite number N optimal solutions, which are obtained in part (1). The analysis shows that the worst case complexity of proposed method is a polynomial.     

Generalization of EDF and LLF: Identifying All Optimal Online Algorithms for Minimizing Maximum Lateness

It is well known that the Earliest-Deadline-First (EDF) and the Least-Laxity-First (LLF) algorithms are optimal algorithms for the problem of preemptively scheduling jobs that arrive over time on a single machine to minimize the maximum lateness (1|r _j ,pmtn|L _max). It was not previously known what other online algorithms are optimal for this problem. As this problem is fundamental in machine scheduling, it deserves a thorough investigation. In this paper, the concept of compound laxity is introduced, and a complete characterization of all optimal online algorithms for this problem is derived.     

Series production in a basic re-entrant shop to minimize makespan or total flow time

This paper addresses a real life shop scheduling problem in a manufacturing company. In this problem, a set of n identical jobs are to be processed on two machines. Every job visits one of the machines more than once. This is therefore a re-entrant shop. Due to the fact that the jobs are identical, the decision version of this problem is even not in the class NP. We give an optimal schedule to minimize the makespan. Since the total flow time depends on the relations between the processing times, we decompose this problem into sub-problems according to the relations between the processing times. We prove various properties of optimal solutions and, based on these properties, we provide an optimal solution for all the sub-problems except one of them. For the sole remaining sub-problem, we prove a dominance property which allows to consider a part of schedules to find an optimal one.     

The hybrid heuristic genetic algorithm for job shop scheduling

Scheduling for the job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem with traditional optimization methods owing to the high computational complexity (NP-hard). Genetic algorithms (GA) have been proved to be effective for a variety of situations, including scheduling and sequencing. Unfortunately, its efficiency is not satisfactory. In order to make GA more efficient and practical, the knowledge relevant to the problem to be solved is helpful. In this paper, a kind of hybrid heuristic GA is proposed for problem n/m/G/C_max, where the scheduling rules, such as shortest processing time (SPT) and MWKR, are integrated into the process of genetic evolution. In addition, the neighborhood search technique (NST) is adopted as an auxiliary procedure to improve the solution performance. The new algorithm is proved to be effective and efficient by comparing it with some popular methods, i.e. the heuristic of neighborhood search, simulated annealing (SA), and traditional GA.     

Minimizing total weighted completion time with uncertain data: A stability approach

A single-machine scheduling problem is investigated provided that the input data are uncertain: The processing time of a job can take any real value from the given segment. The criterion is to minimize the total weighted completion time for the n jobs. As a solution concept to such a scheduling problem with an uncertain input data, it is reasonable to consider a minimal dominant set of job permutations containing an optimal permutation for each possible realization of the job processing times. To find an optimal or approximate permutation to be realized, we look for a permutation with the largest stability box being a subset of the stability region. We develop a branch-and-bound algorithm to construct a permutation with the largest volume of a stability box. If several permutations have the same volume of a stability box, we select one of them due to one of two simple heuristics. The efficiency of the constructed permutations (how close they are to a factually optimal permutation) and the efficiency of the developed software (average CPU-time used for an instance) are demonstrated on a wide set of randomly generated instances with 5 ≤ n ≤ 100.     

Implementation of FIR control for H ∞ output feedback stabilisation of linear systems

In this article, finite impulse response (FIR) control is addressed for H _∞ output feedback stabilisation of linear systems. The problem we deal with is the construction of an output feedback controller with a certain FIR structure such that the resulting closed-loop system is asymptotically stable and a prescribed H _∞ norm bound constraint is guaranteed. Some solvability conditions are suggested in this article. Sufficient conditions are derived to obtain a suboptimal solution of the H _∞ FIR control problem via convex optimisation. Also, an equivalent condition for the existence of H _∞ FIR control is presented in the set of linear matrix inequalities (LMIs) and a reciprocal matrices equality constraint. An effective computational algorithm involving LMIs is suggested to solve a concave minimisation problem characterising a local optimal solution of the H _∞ FIR control problem. Numerical examples demonstrate the validity of the proposed H _∞ FIR control and the numerical efficiency of the proposed algorithm for FIR control.     

Tight Results on Minimum Entropy Set Cover

In the minimum entropy set cover problem, one is given a collection of k sets which collectively cover an n-element ground set. A feasible solution of the problem is a partition of the ground set into parts such that each part is included in some of the k given sets. Such a partition defines a probability distribution, obtained by dividing each part size by n. The goal is to find a feasible solution minimizing the (binary) entropy of the corresponding distribution. Halperin and Karp have recently proved that the greedy algorithm always returns a solution whose cost is at most the optimum plus a constant. We improve their result by showing that the greedy algorithm approximates the minimum entropy set cover problem within an additive error of 1 nat =log ₂ e bits ≃1.4427 bits. Moreover, inspired by recent work by Feige, Lovász and Tetali on the minimum sum set cover problem, we prove that no polynomial-time algorithm can achieve a better constant, unless P = NP. We also discuss some consequences for the related minimum entropy coloring problem. G. Joret is a Research Fellow of the Fonds National de la Recherche Scientifique (FNRS).     

Using a sparse promoting method in linear programming approximations to schedule parallel jobs

In this paper, we tackle the well‐known problem of scheduling a collection of parallel jobs on a set of processors either in a cluster or in a multiprocessor computer. For the makespan objective, that is, the completion time of the last job, this problem has been shown to be NP‐hard, and several heuristics have already been proposed to minimize the execution time. In this paper, we consider both rigid and moldable jobs. Our main contribution is the introduction of a new approach to the scheduling problem, based on the recent discoveries in the field of compressed sensing. In the proposed approach, all possible positions and shapes of the jobs are encoded into a matrix, and the scheduling is performed by selecting the best columns under natural constraints. Thus, the solution to the new scheduling formulation is naturally sparse, and we may use appropriate relaxations to achieve the optimization task in the quickest possible way. Among many possible relaxation strategies, we choose to minimize the ℓ_p‐quasi‐norm for p∈(0,1). Minimization of the ℓ_p‐quasi‐norm is implemented via a successive linear programming approximation heuristic. We propose several new algorithms based on this approach, and we assess their efficiency through simulations. The experiments show that the scheme outperforms the classic Largest Task First list based algorithm for scheduling small to medium instances but needs improvements to compete on larger numbers of jobs. Copyright © 2014 John Wiley & Sons, Ltd.