...algorithms for single machine scheduling with precedence relations and deferral costs. Operations Research 23 283-298). We look at the problem from a polyhedral perspective and uncover a relation between Sidney's decomposition theorem and different linear programming relaxations. More specifically, we present a generalization of Sidney's result, which particularly allows us to reason that virtually all known 2-approximation algorithms are consistent with his decomposition. Moreover, we establish a connection between the single-machine scheduling problem and the vertex cover problem. Indeed, in the special case of series-parallel precedence constraints, we prove that the sequencing problem can be seen as a special case of the vertex cover problem. We also argue that this result is true for general precedence constraints if one can show that a certain integer program represents a valid formulation of the sequencing problem. Finally, we give a 3/2-approximation algorithm for two-dimensional partial orders, and we also provide a characterization of the active inequalities of a linear programming relaxation in completion time variables.

Key words: linear ordering; scheduling; vertex cover; linear programming relaxation; integer programming formulation; approximation algorithm; partial order

MSC2000 subject classification: Primary: 90B35, 90C57, 90C59; secondary: 06A07, 68W25, 90C08, 90C09, 90C27

OR/MS subject classification: Primary: Production/scheduling: sequencing, deterministic, single machine; secondary: mathematics, combinatorics

History: Received August 18, 2004; revised December 27, 2004.

1. Introduction. We consider the following scheduling problem. A set N = {1, ..., n} of n jobs has to be processed on a single machine, which can handle at most one job at a time. Each job j has a positive processing time, [p.sub.j] > 0, and a nonnegative weight, [w.sub.j] [greater than or equal to] 0, and we want to find a schedule of the jobs that minimizes the weighted sum of job completion times, [[summation].sub.j [member of] N] [w.sub.j] [C.sub.j]. Here, [C.sub.j] denotes the time at which job j is completed in a feasible schedule. In this basic form, the problem can be solved efficiently using Smith's rule [33], which sequences the jobs in nonincreasing order of their ratios [w.sub.j]/[p.sub.j] of weight to processing time. In this paper, we focus on the case when the jobs have to be consistent with precedence constraints. The precedence constraints are given in the form of a directed acyclic graph (i.e., a partial order) G = (N, P), where (i, j) [member of] P implies that job i must be completed before job j can be started. We assume that G is transitively closed; i.e., if (i, j), (j, k) [member of] P, then (i, k) [member of] P. In standard scheduling notation (Graham et al. [10]), this problem is known as 1 [absolute value of prec] [summation] [w.sub.j][C.sub.j]. Lawler [15] and Lenstra and Rinnooy Kan [16] showed that this problem is strongly NP-hard.

Several integer programming formulations and linear programming relaxations have been proposed for this problem. They can basically be divided into three groups according to the decision variables used: some formulations exploit time-indexed variables (e.g., Dyer and Wolsey [7]), which are binary variables indicating when a job is completed; others make direct use of completion time variables (e.g., Balas [1]); and yet others borrow their decision variables from the underlying linear ordering polytope (e.g., Wolsey [36]). We refer to Queyranne and Schulz [27] for an overview and a collection of further references.

Linear programming relaxations in these variables have been successfully used to obtain constant-factor approximation algorithms for this problem. (1) The first one, proposed by Hall et al. [11], relies on a time-indexed linear programming relaxation and has performance guarantee 4 + [epsilon]. Subsequently, Schulz [30] presented a 2-approximation algorithm based on solving a weaker linear programming relaxation in completion time variables; see also Hall et al. [12]. The analysis also implies that a linear programming relaxation in linear ordering variables suggested by Potts [25] can be used to obtain another 2-approximation algorithm. Later on, Chudak and Hochbaum [5] proposed a relaxation of Potts' linear

program that suffices to get yet another approximation algorithm of the same performance guarantee. Moreover, they showed that the weaker linear program can be solved by one min-cut computation, which yields a combinatorial 2-approximation algorithm. Independently, Chekuri and Motwani [4] and Margot et al. [17] used Sidney's decomposition theorem [32] to give an entire family of combinatorial 2-approximation algorithms. Afterwards, Goemans and Williamson [9] revived the two-dimensional Gantt charts of Eastman et al. [8] to illustrate the findings of Margot et al. [17] and Chekuri and Motwani [4]. They also proved the correctness of Lawler's polynomial-time, exact algorithm for series-parallel precedence constraints [15] by relating it to the dual of a linear programming relaxation in completion time variables due to Queyranne and Wang [28]. Woeginger [34] argued that the approximability behavior of 1 [absolute value of prec] [summation] [w.sub.j][C.sub.j] and that of several of its (NP-hard) special cases (e.g., precedence constraints of height 1 where all minimal jobs have unit processing time and zero weight while all maximal jobs have zero processing time and unit weight) is essentially identical. He also explored a relationship between 1 [absolute value of prec] [summation] [w.sub.j][C.sub.j] and the partially-ordered knapsack problem, which can be used to derive (1.618 + [epsilon])-approximation algorithms for particular classes of precedence constraints, including interval orders and two-dimensional orders. The latter result is due to Kolliopoulos and Steiner [14].

After setting the stage in [section] 2, we establish in [section] 3.1 a connection between Sidney's decomposition theory and the linear programming relaxations in linear ordering variables by Potts [25] and Chudak and Hochbaum [5]. In [section] 3.2, we propose a new relaxation in linear ordering variables that suggests a strong relationship between 1 [absolute value of prec] [summation] [w.sub.j][C.sub.j] and the vertex cover problem. We also show that the sequencing problem is indeed a special case of the vertex cover problem when the precedence constraints are series-parallel ([section] 3.3). In [section] 3.4, we show that the new linear ordering relaxation is integer if and only if the precedence constraints are two-dimensional. We also give a simple 3/2-approximation algorithm for the class of two-dimensional precedence constraints. In [section] 3.5, we provide a bound on the optimal value of the considered linear ordering relaxations, which implies that the family of 2-approximation algorithms by Chekuri and Motwani [4] and Margot et al. [17] already has performance guarantee 2 for the weighted sum of starting times objective. We study relaxations in completion time variables in [section] 4, extending results by Margot et al. [17] on the structure of optimal solutions. The results in [subsection] 3.1 and 4 imply that all known 2-approximation algorithms follow Sidney's decomposition and are therefore special cases of the class of algorithms described by Chekuri and Motwani [4] and Margot et al. [17].

2. Definitions and preliminaries. For a job j [member of] N, we denote the ratio [w.sub.j]/[p.sub.j] by [[rho].sub.j]. We generalize these quantities to sets S [subset or equal to] N of jobs in the usual way: p(S) := [[summation].sub.j [member of] S] [p.sub.j], w(S) := [[summation].sub.j [member of] S] [w.sub.j], and [rho](S) := w(S)/p(S). For S [subset or equal to] N, [G.sub.s] denotes the subgraph of G induced by S, and P([G.sub.S]) is the set of arcs (precedence constraints) in [G.sub.S]. A set of jobs I [subset or equal to] S is called initial in [G.sub.S] if j [member of] I and (i, j) [member of] P([G.sub.S]) imply i [member of] I. Analogously, F [subset or equal to] S is called final in [G.sub.S] if S\F is initial in [G.sub.S]. We simply say that S [subset or equal to] N is initial (respectively, final) if S is initial (final) in G. If there exists some final set F [subset or equal to] N such that w(F) = 0, the jobs in F can be scheduled in an arbitrary feasible sequence after all jobs in N\F without affecting the objective function value. We assume for the rest of this paper that w(F) > for all final sets F [subset or equal to] N.

A nonempty set [S.sup.*] [subset of equal to] S is a [rho]-maximal initial set in [G.sub.S] if [S.sup.*] is an initial set in [G.sub.S] with maximum value of [rho]. In other words, [S.sup.*] [member of] arg max{[rho](S') : S' [not equal to] [empty set] initial in [G.sub.S]}. An initial set S [subset or equal to] N is said to be non-Sidney-decomposable if the only [rho]-maximal initial set contained in S is S itself; i.e., S is a minimal (with respect to inclusion) [rho]-maximal initial set.

LEMMA 2.1 (SIDNEY [32]). If S [subset or equal to] N is a [rho]-maximal initial set, F is final in Gs, and I is initial in [G.sub.N\S], then [rho](I) [less than or equal to] [rho](S) [less than or equal to] [rho](F).

PROOF. It suffices to note that for two disjoint sets A and B of jobs, [rho](A [union] B) can be written as a convex combination of [rho](A) and [rho](B). Indeed,

[rho](A [union] B) = w(A) + w(B)/p(A) + p(B) = [rho](A) p(A)/p(A [union] B) + [rho](B)/p(A [union] B). []

We now review the concept of Sidney decomposition. Consider a partition of N into disjoint sets [S.sub.1], [S.sub.2], ..., [S.sub.k] such that each [S.sub.i] is a [rho]-maximal initial set of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for i = 1, ..., k. The partition ([S.sub.1], [S.sub.2], ..., [S.sub.k]) is called a Sidney decomposition of N. Sidney [32] proved that there exists an optimal solution to 1 [absolute value of prec] [summation] [w.sub.j][C.sub.j] that processes the jobs in [S.sub.i] before those in [S.sub.j], whenever i [rho]([S.sub.j]), then i ... > [[lambda].sub.q] of distinct values [rho]([S.sub.i]) and showed that all Sidney decompositions of a given instance have the same [rho]-profile. In particular, there is a unique coarsest Sidney decomposition, which they called the reduced Sidney decomposition: ([R.sub.1], [R.sub.2], ..., [R.sub.q]) with [R.sub.i] := [union]{[S.sub.j]: [rho]([S.sub.j]) = [[lambda].sub.i]} for i = 1, ..., q. We say that a scheduling algorithm is consistent with Sidney's decomposition if, for the reduced Sidney decomposition ([R.sub.1], [R.sub.2], ..., [R.sub.q]), the algorithm schedules the jobs in [R.sub.i] before the ones in [R.sub.j], whenever i < j. The reduced Sidney decomposition can be computed in polynomial time (Lawler...

NOTE: All illustrations and photos have been removed from this article.



More articles from Mathematics of Operations Research
Expected residual minimization method for stochastic linear complement..., November 01, 2005

Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.