Lower bounds on precedence-constrained scheduling for parallel processors

We consider two general precedence-constrained scheduling problems that have wide applicability in the areas of parallel processing, high performance compiling, and digital system synthesis. These problems are intractable so it is important to be able to compute tight bounds on their solutions. A tight lower bound on makespan scheduling can be obtained by replacing precedence constraints with release and due dates, giving a problem that can be efficiently solved. We demonstrate that recursively applying this approach yields a bound that is provably tighter than other known bounds, and experimentally shown to achieve the optimal value at least 90.3% of the time over a synthetic benchmark.We compute the best known lower bound on weighted completion time scheduling by applying the recent discovery of a new algorithm for solving a related scheduling problem. Experiments show that this bound significantly outperforms the linear programming-based bound. We have therefore demonstrated that combinatorial algorithms can be a valuable alternative to linear programming for computing tight bounds on large scheduling problems.     

An efficient algorithm for finding ideal schedules

We study the problem of scheduling unit execution time jobs with release dates and precedence constraints on two identical processors. We say that a schedule is ideal if it minimizes both maximum and total completion time simultaneously. We give an instance of the problem where the min-max completion time is exceeded in every preemptive schedule that minimizes total completion time for that instance, even if the precedence constraints form an intree. This proves that ideal schedules do not exist in general when preemptions are allowed. On the other hand, we prove that, when preemptions are not allowed, then ideal schedules do exist for general precedence constraints, and we provide an algorithm for finding ideal schedules in O(n ³) time, where n is the number of jobs. In finding such ideal schedules we resolve a conjecture of Baptiste and Timkovsky (Math. Methods Oper. Res. 60(1):145–153, 2004) Further, our algorithm for finding min-max completion-time schedules requires only O(n ³) time, while the most efficient solution to date has required O(n ⁹) time.     

Minimizing Makespan and Preemption Costs on a System of Uniform Machines

It is well known that for preemptive scheduling on uniform machines there exist polynomial time exact algorithms, whereas for non-preemptive scheduling there are probably no such algorithms. However, it is not clear how many preemptions (in total, or per job) suffice in order to guarantee an optimal polynomial time algorithm. In this paper we investigate exactly this hardness gap, formalized as two variants of the classic preemptive scheduling problem. In generalized multiprocessor scheduling (GMS) we have a job-wise or total bound on the number of preemptions throughout a feasible schedule. We need to find a schedule that satisfies the preemption constraints, such that the maximum job completion time is minimized. In minimum preemptions scheduling (MPS) the only feasible schedules are preemptive schedules with the smallest possible makespan. The goal is to find a feasible schedule that minimizes the overall number of preemptions. Both problems are NP-hard, even for two machines and zero preemptions. For GMS, we develop polynomial time approximation schemes, distinguishing between the cases where the number of machines is fixed, or given as part of the input. Our scheme for a fixed number of machines has linear running time, and can be applied also for instances where jobs have release dates, and for instances with arbitrary preemption costs. For MPS, we derive matching lower and upper bounds on the number of preemptions required by any optimal schedule. Our results for MPS hold for any instance in which a job, J_j, can be processed simultaneously by ρ_j machines, for some ρ_j ≥ 1.     

Efficient Construction of Minimum Makespan Schedules for Tasks with a Fixed Number of Distinct Execution Times

This paper addresses scheduling problems for tasks with release and execution times. We present a number of efficient and easy to implement algorithms for constructing schedules of minimum makespan when the number of distinct task execution times is fixed. For a set of independent tasks, our algorithm in the single processor case runs in time linear in the number of tasks; with precedence constraints, our algorithm runs in time linear in the sum of the number of tasks and the size of the precedence constraints. In the multi-processor case, our algorithm constructs minimum makespan schedules for independent tasks with uniform execution times. The algorithm runs in O(n log m) time where n is the number of tasks and m is the number of processors. Received September 25, 1997; revised June 11, 1998.     

Scheduling precedence constrained task graphs with non-negligibleintertask communication onto multiprocessors

The multiprocessor scheduling problem is the problem of scheduling the tasks of a precedence constrained task graph (representing a parallel program) onto the processors of a multiprocessor in a way that minimizes the completion time. Since this problem is known to be NP-hard in the strong sense in all but a few very restricted eases, heuristic algorithms are being developed which obtain near optimal schedules in a reasonable amount of computation time. We present an efficient heuristic algorithm for scheduling precedence constrained task graphs with nonnegligible intertask communication onto multiprocessors taking contention in the communication channels into consideration. Our algorithm for obtaining satisfactory suboptimal schedules is based on the classical list scheduling strategy. It simultaneously exploits the schedule-holes generated in the processors and in the communication channels during the scheduling process in order to produce better schedules. We demonstrate the effectiveness of our algorithm by comparing with two competing heuristic algorithms available in the literature     

混合优先约束下带模糊交货期的单机调度问题的研究

讨论了一类模糊交货期和混合优先约束下的单机调度问题．模糊交货期表示对任务完成时间的满意程度；混合优先约束包括普通优先关系和模糊优先关系，模糊优先关系反映了对任务间优先次序的满意程度．调度的目的是同时最大化模糊交货期和混合优先约束的最小满意程度．对于上述双目标函数调度问题，通过搜索非支配解，得到最优调度．     

A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

Minimizing makespan subject to minimum flowtime on two identical parallel machines

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime.     

Power and performance management for parallel computations in clouds and data centers

We address scheduling independent and precedence constrained parallel tasks on multiple homogeneous processors in a data center with dynamically variable voltage and speed as combinatorial optimization problems. We consider the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint on multiple processors. Our approach is to use level-by-level scheduling algorithms to deal with precedence constraints. We use a simple system partitioning and processor allocation scheme, which always schedules as many parallel tasks as possible for simultaneous execution. We use two heuristic algorithms for scheduling independent parallel tasks in the same level, i.e., SIMPLE and GREEDY. We adopt a two-level energy/time/power allocation scheme, namely, optimal energy/time allocation among levels of tasks and equal power supply to tasks in the same level. Our approach results in significant performance improvement compared with previous algorithms in scheduling independent and precedence constrained parallel tasks.     

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.     

The parallel complexity of scheduling with precedence constraints

We study the problem of parallel computation of a schedule for a system of n unit-length tasks on m identical machines, when the tasks are related by a set of precedence constraints. We present NC algorithms for computing an optimal schedule in the case where m, the number of available machines, does not vary with time and the precedence constraints are represented by a collection of outtrees. The algorithms run on an exclusive read, exclusive write (EREW) PRAM. Their complexities are O(log n) and O((log n)²) parallel time using O(n²) and O(n) processors, respectively. The schedule computed by our algorithms is a height-priority schedule. As a complementary result we show that it is very unlikely that computing such a schedule is in NC when any of the above conditions is significantly relaxed. We prove that the problem is P-complete under logspace reductions when the precedence constraints are a collection of intrees and outtrees, or for a collection of outtrees when the number of available machines is allowed to increase with time. The time span of a height-priority schedule for an arbitrary precedence constraints graph is at most 2 − 1/(m − 1) times longer than the optimal (N. E Chen and C. L. Liu, Proc. 1974 Sagamore Computer Conference on Parallel Processing, T. Fend (Ed.), Springer-Verlag, Berlin, 1975, pp. 1–16). Whereas it is P-complete to produce the classical height-priority schedules even for very restricted precedence constraints graphs, we present a simple NC parallel algorithm which produces a different schedule that is only 2 − 1/m times the optimal.     

中厚板热轧生产调度优化方法

中厚板热轧生产调度, 是一个有优先约束、等待时间和缓冲容量有限的单机调度问题. 用AON (Activity-on-node)网络对问题进行描述, 提出并证明了面向单机调度问题的AON网络平衡定理, 根据平衡定理, 建立了以轧机利用率最大为优化目标的非线性约束优化数学模型, 并利用优化软件LINGO进行求解. 计算实例表明, 所提出的数学优化方法, 与现有的启发式方法相比, 能够获得更好的优化目标, 所得到的生产调度方案, 生产节奏稳定, 更有利于组织生产.     

A preemptive bound for the Resource Constrained Project Scheduling Problem

The Resource Constrained Project Scheduling Problem is one of the most intensively investigated scheduling problems. It requires scheduling a set of interrelated activities, while considering precedence relationships, and limited renewable resources allocation. The objective is to minimize the project duration. We propose a new destructive lower bound for this challenging ${\mathcal {NP}}$ -hard problem. Starting from a previously suggested LP model, we propose several original valid inequalities that aim at tightening the model representation. These new inequalities are based on precedence constraints, incompatible activity subsets, and nonpreemption constraints. We present the results of an extensive computational study that was carried out on 2,040 benchmark instances of PSPLIB, with up to 120 activities, and that provide strong evidence that the new proposed lower bound exhibits an excellent performance. In particular, we report the improvement of the best known lower bounds of 5 instances.     

Task scheduling with precedence constraints to minimize the total completion time

The authors study the problem of scheduling a set of tasks with known execution times and arbitrary precedence constraints to computing systems. The objective function used to measure the performance of a schedule in this paper is the sum of completion times of all tasks, which is called total completion time. Finding the minimum total completion time of tasks with precedence constraints on the uniprocessor system is known to be NP-complete, let alone on the multiprocessor system (Garey and Johnson 1979) Based on the well-known A? algorithm proposed in the field of artificial intelligence (Nilson 1980) two algorithms are developed to solve efficiently the scheduling problems on the uniprocessor system and multiprocessor system. Some evaluation functions are proposed to accelerate the search of an optimal schedule. A table named the backwards range-limited table is used to assist the computation of the evaluation function. Experimental results show that the proposed approaches can achieve the optimal schedule with greatly reduced search tree size, especially when bounding rules are applied.     

Integrating employee timetabling with scheduling of machines and transporters in a job-shop environment: A mathematical formulation and an Anarchic Society Optimization algorithm

This paper addresses a ternary-integration scheduling problem that incorporates employee timetabling into the scheduling of machines and transporters in a job-shop environment with a finite number of heterogeneous transporters where the objective is to minimize the completion time of all jobs. The problem is first formulated as a mixed-integer linear programming model. Then, an Anarchic Society Optimization (ASO) algorithm is developed to solve large-sized instances of the problem. The formulation is used to solve small-sized instances and to evaluate the quality of the solutions obtained for instances with larger sizes. A comprehensive numerical study is carried out to assess the performance of the proposed ASO algorithm. The algorithm is compared with three alternative metaheuristic algorithms. It is also compared with several algorithms developed in the literature for the integrated scheduling of machines and transporters. Moreover, the algorithms are tested on a set of adapted benchmark instances for an integrated problem of machine scheduling and employee timetabling. The numerical analysis suggests that the ASO algorithm is both effective and efficient in solving large-sized instances of the proposed integrated job-shop scheduling problem.     

Lower bounds for minimizing total completion time in a two-machine flow shop

For the -hard problem of scheduling n jobs in a two-machine flow shop so as to minimize the total completion time, we present two equivalent lower bounds that are computable in polynomial time. We formulate the problem by the use of positional completion time variables, which results in two integer linear programming formulations with O(n ²) variables and O(n) constraints. Solving the linear programming relaxation renders a very strong lower bound with an average relative gap of only 0.8% for instances with more than 30 jobs. We further show that relaxing the formulation in terms of positional completion times by applying Lagrangean relaxation yields the same bound, no matter which set of constraints we relax.     

Scheduling of manufacturing systems using the Lagrangian relaxationtechnique

The practical solutions for three manufacturing scheduling problems are examined. As each problem is formulated, constraints are added or modified to reflect increasing real world complexity. The first problem considers scheduling single-operation jobs on identical machines. The second problem is concerned with scheduling multiple-operation jobs with simple fork/join precedence constraints on identical machines. The third problem is the job shop problem in which multiple-operation jobs with general precedence constraints are scheduled on multiple machine types Langrangian relaxation is used to decompose each of the scheduling problems into job- or operation-level subproblems. The subproblems are easier to solve than the original problem and have intuitive appeal. This technique results in algorithms which generate near-optimal schedules efficiently, while giving a lower bound on the optimal cost. In resolving the scheduling problem from one time instant to the next, the Lagrange multipliers from the last schedule can be used to initialize the multipliers, further reducing the computation time     

Minimizing total weighted flowtime subject to minimum makespan on two identical parallel machines

We study the problem of scheduling n jobs on two identical parallel processors or machines where an optimal schedule is defined as one with the shortest total weighted flowtime (i.e., the sum of the weighted completion time of all jobs), among the set of schedules with minimum makespan (i.e., the completion time of the last job finished). We present a two phase non-linear Integer Programming formulation for its solution, admittedly not to be practical or useful in most cases, but theoretically interesting since it models the problem. Thus, as an alternative, we propose an optimization algorithm, for small problems, and a heuristic, for large problems, to find optimal or near optimal solutions. Furthermore, we perform a computational study to evaluate and compare the effectiveness of the two proposed methods.     

Converging to periodic schedules for cyclic scheduling problems with resources and deadlines

Cyclic scheduling has been widely studied because of the importance of applications in manufacturing systems and in computer science. For this class of problems, a finite set of tasks with precedence relations and resource constraints must be executed repetitively while maximizing the throughput. Many applications also require that execution schedules be periodic i.e. the execution of each task is repeated with a fixed global period w.The present paper develops a new method to build periodic schedules with cumulative resource constraints, periodic release dates and deadlines. The main idea is to fix the period w, to unwind the cyclic scheduling problem for some number of iterations, and to add precedence relations so that the minimum time lag between two successive executions of any task equals w. Then, using any usual (not cyclic) scheduling algorithm to compute task starting times for the unwound problem, we prove that either the method converges to a periodic schedule of period w or it fails to compute a schedule. A non-polynomial upper bound on the number of iterations to unwind in order to guarantee that cyclic precedence relations and resource constraints are fulfilled is also provided. This method is successfully applied to a real-life problem, namely the software pipelining of inner loops on an embedded VLIW processor core by using a Graham list scheduling algorithm.     

Improved approaches to the exact solution of the machine covering problem

For the basic problem of scheduling a set of n independent jobs on a set of m identical parallel machines with the objective of maximizing the minimum machine completion time—also referred to as machine covering—we propose a new exact branch-and-bound algorithm. Its most distinctive components are a different symmetry-breaking solution representation, enhanced lower and upper bounds, and effective novel dominance criteria derived from structural patterns of optimal schedules. Results of a comprehensive computational study conducted on benchmark instances attest to the effectiveness of our approach, particularly for small ratios of n to m.