We consider the problem of determining optimal appointment schedule for a given sequence of jobs (e.g., medical procedures) on a single processor (e.g., operating room, examination facility), to minimize the expected total underage and overage costs when each job has a random processing duration given by a joint discrete probability distribution. Simple conditions on the cost rates imply that the objective function is submodular and L-convex. Then there exists an optimal appointment schedule which is integer and can be found in polynomial time. Our model can handle a given due date for the total processing (e.g., end of day for an operating room) after which overtime is incurred and, no-shows and emergencies.

An important class of scheduling problems concerns parallel machines and precedence constraints. We consider precedence delays, which associate with each precedence constraint a certain amount of time that must elapse between the completion and start times of the corresponding jobs. Together with ordinary precedence constraints, release dates and delivery times can be modeled in this manner. We present a 4-approximation algorithm for the total weighted completion time objective for this general class of problems. The algorithm is a rather simple form of list scheduling. The list is in order of job midpoints derived from a linear programming relaxation. Our analysis unifies and simplifies that of a number of special cases heretofore separately studied, while actually improving many of the former approximation results.

Many applications in the area of production and statistical estimation are problems of convex optimization subject to ranking constraints that represent a given partial order. This problem, which we call the convex cost closure (CCC) problem, is a generalization of the known maximum (or minimum) closure problem and the isotonic regression problem. For a CCC problem on n variables and m constraints we describe an algorithm that has the complexity of the minimum cut problem plus the complexity of finding the minima of up to n convex functions. Since the CCC problem is a generalization of both minimum cut and minimization of n convex functions, this complexity is the fastest one possible. For the quadratic problem the complexity of our algorithm is strongly polynomial, $O(mn\log {\frac{n^2}{m}})$. For the isotonic regression problem the complexity is O(n log U,) for U the largest range for a variable value.

We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completion-time formulation. We show their equivalence by proving that a O(n log n) greedy algorithm leads to optimal solutions to both relaxations. The proof relies on the notion of mean busy times of jobs, a concept which enhances our understanding of these LP relaxations. Based on the greedy solution, we describe two simple randomized approximation algorithms, which are guaranteed to deliver feasible schedules with expected objective function value within factors of 1.7451 and 1.6853, respectively, of the optimum. They are based on the concept of common and independent $\alpha$-points, respectively. The analysis implies in particular that the worst-case relative error of the LP relaxations is at most 1.6853, and we provide instances showing that it is at least $e/(e-1) \approx 1.5819$. Both algorithms may be derandomized; their deterministic versions run in O(n 2 ) time. The randomized algorithms also apply to the on-line setting, in which jobs arrive dynamically over time and one must decide which job to process without knowledge of jobs that will be released afterwards.

We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation schemes for several variants of this problem. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our schemes are efficient: for all variants the running time for /spl alpha/(1+/spl epsiv/) approximation is of the form f(1//spl epsiv/, m)poly(n).

We study the two-level uncapacitated facility location (TUFL) problem. Given two types of facilities, which we call y-facilities and z-facilities, the problem is to decide which facilities of both types to open, and to which pair of y- and z-facilities each client should be assigned, in order to satisfy the demand at maximum profit. We first present two multi-commodity flow formulations of TUFL and investigate the relationship between these formulations and similar formulations of the one-level uncapacitated facility location (UFL) problem. In particular, we show that all nontrivial facets for UFL define facets for the two-level problem, and derive conditions when facets of TUFL are also facets for UFL. For both formulations of TUFL, we introduce new families of facets and valid inequalities and discuss the associated separation problems. We also characterize the extreme points of the LP-relaxation of the first formulation. While the LP-relaxation of a multi-commodity formulation provides good bounds in general, the number of variables and constraints grows rapidly with the size of the problem instance. An alternative model of TUFL is a single-commodity fixed-charge network flow problem. Rardin and Wolsey showed that by projecting a so-called multi-commodity extended formulation of fixed-charge network flow problems onto the space of flow variables used in the weaker flow formulation, a broad class of valid inequalities can be obtained. We discuss a subclass of these inequalities for TUFL that seems particularly useful for computational purposes.

We consider a dynamic network flow model for the control problem of a production-distribution system with periodic demand in the presence of storage and transportation capacity constraints. Unlike most papers dealing with control problems of dynamic networks, we derive a control strategy in feedback form. It is optimal in the sense that it involves, for any initial time, the set of all the initial states for which there exists a control strategy allowing the network variables (flows, storage levels) to remain in their constraint domain for all future times. The evaluation of such a strategy requires the previous computation of these maximal sets. We show that, due to the particular structure of the system, they are submodular polyhedra; in particular, they are finitely represented and the representation complexity is a priori known. Moreover, the evaluation of this sequence, even for the infinite horizon problem, can be performed in a finite number of steps that has a known upper bound depending on the dimension of the problem only. As a consequence of these results, the optimal strategy requires, at each step, to solve a submodular flow problem. The finite horizon problem is solved by the proposed method as a particular case. © 1996 John Wiley & Sons, Inc.

We consider mixed networks, which may include both directed and undirected edges. For a nontrivial vertex subset S, an S-disconnecting set is a set of edges and vertices which intersects every path from any vertex in S to any vertex not in S. Given nonnegative edge and vertex costs, we show that the minimum cost of an S-disconnecting set defines a submodular function. This implies that the set of all S inducing minimum-cost disconnecting sets is the set of closures of a binary relation, thus extending Picard-Queyranne's (1980) result on ordinary minimum cuts. We apply this result to two-pair multicommodity problems in undirected networks, extending Hu's (1963) result to disconnecting sets that may include vertices as well as edges. These results and a result of Provan and Shier (1994) may be used for generating all sets S that induce such minimum-cost disconnecting sets and ranking such sets in order of corresponding costs, for both one-pair problems in mixed networks and two-pair problems in undirected networks. © 1996 John Wiley & Sons, Inc.

Abstract A network flow technique is used to solve the unconstrained nonlinear 0‐1 programming problem, which is maximizing the ratio of two polynomials, assuming that all the nonlinear coefficients in the numerator are non‐negative and all the nonlinear coefficients in the denominator are nonpositive. Two examples are an investment selection problem to maximize the rate of return, and a decomposition approach to a scheduling problem studied by Sidney and Lawler. The proposed algorithm requires the solution of a sequence of minimum‐cut problems in a related network, and can be extended to some more general problems of the same type. This approach is also applied to find the density of a graph (the maximum ratio, among its subgraphs, of the number of edges to the number of nodes) and its arboricity, for which polynomial algorithms are described. It is also useful in providing a bounding scheme for the maximum‐clique and vertex packing problems.