Polynomial time approximation schemes for general multiprocessor job shop scheduling

We study preemptive and non-preemptive versions of the general multiprocessor job shop scheduling problem: Given a set of n tasks each consisting of at most μ ordered operations that can be processed on different (possibly all) subsets of m machines with different processing times, compute a schedule (preemptive or non-preemptive, depending on the model) with minimum makespan where operations belonging to the same task have to be scheduled according to the specified order. We propose algorithms for both preemptive and non-preemptive variants of this problem that compute approximate solutions of any positive ε accuracy and run in O(n) time for any fixed values of m, μ, and ε. These results include (as special cases) many recent developments on polynomial time approximation schemes for scheduling jobs on unrelated machines, multiprocessor tasks, and classical open, flow and job shops.     

On the Expected Condition Number of Linear Programming Problems

Summary.   Let A be an n×m real matrix and consider the linear conic system

Preemptive scheduling with rejection

 We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation algorithm for it. All other considered variants are weakly -hard, and we provide fully polynomial time approximation schemes for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open shop scheduling problem with rejection. Received: October 30, 2000 / Accepted: September 26, 2001 Published online: September 5, 2002 Key words. scheduling – preemption – approximation algorithm – worst case ratio – computational complexity – in-approximability Supported in part by the EU Thematic Network APPOL, Approximation and Online Algorithms, IST-1999-14084 Supported by the START program Y43-MAT of the Austrian Ministry of Science.     

Scheduling Malleable Tasks on Parallel Processors to Minimize the Makespan

The problem of optimal scheduling n tasks in a parallel processor system is studied. The tasks are malleable, i.e., a task may be executed by several processors simultaneously and the processing speed of a task is a nonlinear function of the number of processors allocated to it. The total number of processors is m and it is an upper bound on the number of processors that can be used by all the tasks simultaneously. It is assumed that the number of processors is sufficient to process all the tasks simultaneously, i.e. n≤m. The objective is to find a task schedule and a processor allocation such that the overall task completion time, i.e. the makespan, is minimized. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. An O(n) algorithm is presented to solve this problem when all the processing speed functions are convex. If these functions are all concave and the number of tasks is a constant, the problem can be solved in polynomial time. A relaxed problem, in which the number of processors allocated to each task is not required to be integer, can be solved in O(nmax {m,nlog ² m}) time. It is proved that the minimum makespan values for the original and relaxed problems coincide. For n=2 or n=3, an optimal solution for the relaxed problem can be converted into an optimal solution for the original problem in a constant time.     

Seshadri-exceptional foliations

 The maximal Seshadri number μ(L) of an ample line bundle L on a smooth projective variety X measures the local positivity of the line bundle L at a general point of X. By refining the method of Ein-Küchle-Lazarsfeld, lower bounds on μ(L) are obtained in terms of L ⁿ , n=dim(X), for a class of varieties. The main idea is to show that if a certain lower bound is violated, there exists a non-trivial foliation on the variety whose leaves are covered by special curves. In a number of examples, one can show that such foliations must be trivial and obtain lower bounds for μ(L). The examples include the hyperplane line bundle on a smooth surface in ℙ³ and ample line bundles on smooth threefolds of Picard number 1. Received: 29 June 2001 / Published online: 16 October 2002 RID="⋆" ID="⋆" Supported by Grant No. 98-0701-01-5-L from the KOSEF. RID="⋆⋆" ID="⋆⋆" Supported by Grant No. KRF-2001-041-D00025 from the KRF.     

Scheduling on semi-identical processors

Givenm parallel processors each of them having the same speed but different intervals of availability, the problem of constructing a preemptive schedule forn independent tasks which completes each task in the given intervals is examined. We present an 0 (n+m logm) time algorithm to obtain such a schedule if there exists one. We show that the number of induced preemptions is proportional to the total number of processing intervals of all processors.

---

Zusammenfassung Fürm identische Prozessoren, die nur in vorgegebenen Zeitintervallen zur Verfügung stehen, undn unabhängige Verrichtungen wird ein präemptiver Ablaufplan gesucht, so daß alle Verrichtungen innerhalb dieser Intervalle durchgeführt werden können. Es wird gezeigt, daß ein solcher Plan, falls er existiert, mit einem Aufwand von 0 (n + m logm) konstruiert werden kann und die Anzahl der dabei erzeugten Unterbrechungen proportional zur Anzahl der gegebenen Verfügbarkeitsintervalle aller Prozessoren ist.

     

On complexity reduction of Σ<Subscript>1</Subscript> formulas

 For a fixed q  ℕ and a given Σ₁ definition φ(d,x), where d is a parameter, we construct a model M of 1 Δ₀ + ? exp and a non standard d  M such that in M either φ has no witness smaller than d or phgr; is equivalent to a formula ϕ(d,x) having no more than q alternations of blocks of quantifiers. Received: 29 September 1998 / Revised version: 7 November 2001 Published online: 10 October 2002 RID="⋆" ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13. RID="⋆" ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13.     

Graph models for scheduling systems with machine saturation property

Let be a set of n independent tasks and a set of m processors. During each time instant, each processor can be used by a single task at most. A schedule is for each task an allocation of one or more time intervals to one or more processors. A schedule is said to be optimal if it minimizes the maximum completion time. We say a schedule S has the machine saturation property (MS property) if, at any time instant of task execution, all the machines are simultaneously busy. In this paper, we analyze the conditions under which a parallel scheduling system allows a schedule with the MS property. While for some simple models the analytical conditions can be easily stated, a graph model approach is required when conflicts of processor usage are present. For this reason, we define the class of saturated graphs that correspond to scheduling systems with the MS property. We present efficient graph recognition algorithms to verify the MS property directly on some classes of saturated graphs     

On the geometry,preemptions and complexity of multiprocessor and shop scheduling

In this paper we study multiprocessor and open shop scheduling problems from several points of view. We explore a tight dependence of the polynomial solvability/intractability on the number of allowed preemptions. For an exhaustive interrelation, we address the geometry of problems by means of a novel graphical representation. We use the so-called preemption and machine-dependency graphs for preemptive multiprocessor and shop scheduling problems, respectively. In a natural manner, we call a scheduling problem acyclic if the corresponding graph is acyclic. There is a substantial interrelation between the structure of these graphs and the complexity of the problems. Acyclic scheduling problems are quite restrictive; at the same time, many of them still remain NP-hard. We believe that an exhaustive study of acyclic scheduling problems can lead to a better understanding and give a better insight of general scheduling problems. We show that not only acyclic but also a special non-acyclic version of periodic job-shop scheduling can be solved in polynomial (linear) time. In that version, the corresponding machine dependency graph is allowed to have a special type of the so-called parti-colored cycles. We show that trivial extensions of this problem become NP-hard. Then we suggest a linear-time algorithm for the acyclic open-shop problem in which at most m−2 preemptions are allowed, where m is the number of machines. This result is also tight, as we show that if we allow one less preemption, then this strongly restricted version of the classical open-shop scheduling problem becomes NP-hard. In general, we show that very simple acyclic shop scheduling problems are NP-hard. As an example, any flow-shop problem with a single job with three operations and the rest of the jobs with a single non-zero length operation is NP-hard. We suggest linear-time approximation algorithm with the worst-case performance of ( , respectively) for acyclic job-shop (open-shop, respectively), where (‖ℳ‖, respectively) is the maximal job length (machine load, respectively). We show that no algorithm for scheduling acyclic job-shop can guarantee a better worst-case performance than . We consider two special cases of the acyclic job-shop with the so-called short jobs and short operations (restricting the maximal job and operation length) and solve them optimally in linear time. We show that scheduling m identical processors with at most m−2 preemptions is NP-hard, whereas a venerable early linear-time algorithm by McNaughton yields m−1 preemptions. Another multiprocessor scheduling problem we consider is that of scheduling m unrelated processors with an additional restriction that the processing time of any job on any machine is no more than the optimal schedule makespan C _max^*. We show that the (2m−3)-preemptive version of this problem is polynomially solvable, whereas the (2m−4)-preemptive version becomes NP-hard. For general unrelated processors, we guarantee near-optimal (2m−3)-preemptive schedules. The makespan of such a schedule is no more than either the corresponding non-preemptive schedule makespan or max {C _max^*,p _max}, where C _max^* is the optimal (preemptive) schedule makespan and p _max is the maximal job processing time. E.V. Shchepin was partially supported by the program “Algebraical and combinatorial methods of mathematical cybernetics” of the Russian Academy of Sciences. N. Vakhania was partially supported by CONACyT grant No. 48433.     

On polynomial collocation for second kind integral equations with fixed singularities of Mellin type

Summary.  We consider a polynomial collocation for the numerical solution of a second kind integral equation with an integral kernel of Mellin convolution type. Using a stability result by Junghanns and one of the authors, we prove that the error of the approximate solution is less than a logarithmic factor times the best approximation and, using the asymptotics of the solution, we derive the rates of convergence. Finally, we describe an algorithm to compute the stiffness matrix based on simple Gau? quadratures and an alternative algorithm based on a recursion in the spirit of Monegato and Palamara Orsi. All together an almost best approximation to the solution of the integral equation can be computed with 𝒪(n ²[log n]²) resp. 𝒪(n ²) operations, where n is the dimension of the polynomial trial space. Received February 18, 2002 / Revised version received May 15, 2002 / Published online October 29, 2002 RID="⋆" ID="⋆" Correspondence to: A. Rathsfeld Mathematics Subject Classification (1991): 65R20     

Espaces de Thom et contre-exemples de J.L. Verdier et M. Goresky

Résumé SoitS une variété algébrique complexe singulière, de dimension réelle 2s. M.H. Schwartz et R. Mac-Pherson ont défini des classes caractéristiques, généralisation des classes de Chern, dans l'homologie deS (de telles classes n'existent pas en cohomologie). D'autre part l'homomorphisme de PoincaréH ^2s−⋆ (S)→H _⋆ (S) n'est en géneral, ni injectif, ni surjectif. Cet homomorphisme se factorise par l'homologie d'intersectionIH _⋆ (S). Il est naturel de se demander quel est le “comportement” des classes deS (classes de M.H. Schwartz-R. Mac-Pherson) vis-à-vis du morphisme canonique α:IH _⋆(S)→H_⋆(S). J. L. Verdier a construit un exemple dans lequel, le morphisme canonique α n'étant pas injectif, les classes deS peuvent ètre réalisées de plusieurs manières comme images de classes de Chern de variétés lisses, désingularisations deS, et dont l'homologie est isomorphe àIH _⋆ (S). M. Goresky a construit une variation de cet exemple dans laquelle les classes de Chern ne sont pas dans l'image de α. Nous montrons que ces deux exemples sont cas particuliers d'une même situation:S est un espace de Thom associé à un plongement d'une variétéB dans un espaceIP ^k . L'essentiel de cet article a été écrit lors d'un séjour des auteurs à l'Université du Rio Grande do Sul (Porto-Alegre-Brésil), sur invitation de M. Sebastiani. Nous le remercions ici, ainsi que l'Université de Porto-Alegre, de leur accueil et de leur hospitalité      

A uniqueness result for a Neumann problem involving the critical Sobolev exponent

 In this paper we consider the problem

On representations and <Emphasis Type="Italic">K</Emphasis>-theory of the braid groups

 Let Γ be the fundamental group of the complement of a K(Γ, 1) hyperplane arrangement (such as Artin's pure braid group) or more generally a homologically toroidal group as defined below. The triviality of bundles arising from orthogonal representations of Γ is characterized completely as follows. An orthogonal representation gives rise to a trivial bundle if and only if the representation factors through the spinor groups. Furthermore, the subgroup of elements in the complex K-theory of BΓ which arises from complex unitary representations of Γ is shown to be trivial. In the case of real K-theory, the subgroup of elements which arises from real orthogonal representations of Γ is an elementary abelian 2-group, which is characterized completely in terms of the first two Stiefel-Whitney classes of the representation. In addition, quadratic relations in the cohomology algebra of the pure braid groups which correspond precisely to the Jacobi identity for certain choices of Poisson algebras are shown to give the existence of certain homomorphisms from the pure braid group to generalized Heisenberg groups. These cohomology relations correspond to non-trivial Spin representations of the pure braid groups which give rise to trivial bundles. Received: 6 February 2002 / Revised version: 19 September 2002 / Published online: 8 April 2003 RID="⋆" ID="⋆" Partially supported by the NSF RID="⋆⋆" ID="⋆⋆" Partially supported by grant LEQSF(1999-02)-RD-A-01 from the Louisiana Board of Regents, and by grant MDA904-00-1-0038 from the National Security Agency RID="⋆" ID="⋆" Partially supported by the NSF Mathematics Subject Classification (2000): 20F36, 32S22, 55N15, 55R50     

A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs

 The authors of this paper recently introduced a transformation [4] that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based on the transformation, we proposed a globally convergent, first-order (i.e., gradient-based) log-barrier algorithm for solving a class of linear SDPs. In this paper, we discuss an efficient implementation of the proposed algorithm and report computational results on semidefinite relaxations of three types of combinatorial optimization problems. Our results demonstrate that the proposed algorithm is indeed capable of solving large-scale SDPs and is particularly effective for problems with a large number of constraints. Received: June 22, 2001 / Accepted: January 20, 2002 Published online: December 9, 2002 RID="†" ID="†"Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. RID="⋆" ID="⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203426 RID="⋆⋆" ID="⋆⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203113 RID="⋆⋆⋆" ID="⋆⋆⋆"This author was supported in part by DOE Grant DE-FG03-97ER25331, DOE/LANL Contract 03891-99-23 and NSF Grant DMS-9973339. Key Words. semidefinite program – semidefinite relaxation – nonlinear programming – interior-point methods – limited memory quasi-Newton methods. Mathematics Subject Classification (1991): 90C06, 90C27, 90C30.     

Minimal surfaces of rotation in Finsler space with a Randers metric

 We consider Finsler spaces with a Randers metric F=α+β, on the three dimensional real vector space, where α is the Euclidean metric and β=bdx ₃ is a 1-form with norm b,0≤b<1. By using the notion of mean curvature for immersions in Finsler spaces introduced by Z. Shen, we get the ordinary differential equation that characterizes the minimal surfaces of rotation around the x ₃ axis. We prove that for every b,0≤b<1, there exists, up to homothety, a unique forward complete minimal surface of rotation. The surface is embedded, symmetric with respect to a plane perpendicular to the rotation axis and it is generated by a concave plane curve. Moreover, for every there are non complete minimal surfaces of rotation, which include explicit minimal cones. Received: 30 November 2001 / Published online: 10 February 2003 RID="⋆" ID="⋆" Partially supported by CAPES RID="⋆⋆" ID="⋆⋆" Partially supported by CNPq and PROCAD.     

Extension of primal-dual interior point algorithms to symmetric cones

 In this paper we show that the so-called commutative class of primal-dual interior point algorithms which were designed by Monteiro and Zhang for semidefinite programming extends word-for-word to optimization problems over all symmetric cones. The machinery of Euclidean Jordan algebras is used to carry out this extension. Unlike some non-commutative algorithms such as the XS+SX method, this class of extensions does not use concepts outside of the Euclidean Jordan algebras. In particular no assumption is made about representability of the underlying Jordan algebra. As a special case, we prove polynomial iteration complexities for variants of the short-, semi-long-, and long-step path-following algorithms using the Nesterov-Todd, XS, or SX directions. Received: April 2000 / Accepted: May 2002 Published online: March 28, 2003 RID="⋆" ID="⋆" Part of this research was conducted when the first author was a postdoctoral associate at Center for Computational Optimization at Columbia University. RID="⋆⋆" ID="⋆⋆" Research supported in part by the U.S. National Science Foundation grant CCR-9901991 and Office of Naval Research contract number N00014-96-1-0704.     

A direct impedance tomography algorithm for locating small inhomogeneities

Summary.  Impedance tomography seeks to recover the electrical conductivity distribution inside a body from measurements of current flows and voltages on its surface. In its most general form impedance tomography is quite ill-posed, but when additional a-priori information is admitted the situation changes dramatically. In this paper we consider the case where the goal is to find a number of small objects (inhomogeneities) inside an otherwise known conductor. Taking advantage of the smallness of the inhomogeneities, we can use asymptotic analysis to design a direct (i.e., non-iterative) reconstruction algorithm for the determination of their locations. The viability of this direct approach is documented by numerical examples. Received May 28, 2001 / Revised version received March 15, 2002 / Published online July 18, 2002 RID="⋆" ID="⋆" Supported by the Deutsche Forschungsgemeinschaft (DFG) under grant HA 2121/2-3 RID="⋆⋆" ID="⋆⋆" Supported by the National Science Foundation under grant DMS-0072556 Mathematics Subject Classification (2000): 65N21, 35R30, 35C20     

Little-Preemptive Scheduling on Unrelated Processors

We consider the preemptive scheduling of n independent jobs on m unrelated machines to minimize the makespan. Preemptive schedules with at most 2m–3 preemptions are built, which are optimal when the maximal job processing time is no more than the optimal schedule makespan. We further restrict the maximal job processing time and obtain optimal schedules with at most m–1 preemptions. This is better than the earlier known best bound of 4m ²–5m+2 on the total number of preemptions. Without the restriction on the maximal job processing time, our (2m–3)-preemptive schedules have a makespan which is no more than either of the following two magnitudes: (a) the maximum between the longest job processing time and the optimal preemptive makespan, and (b) the optimal nonpreemptive makespan. Our (m–1)-preemptive schedules might be at most twice worse than an optimal one.     

Degree complexity for a modified pigeonhole principle

 We consider a modification of the pigeonhole principle, M P H P, introduced by Goerdt in [7]. M P H P is defined over n pigeons and log n holes, and more than one pigeon can go into a hole (according to some rules). Using a technique of Razborov [9] and simplified by Impagliazzo, Pudlák and Sgall [8], we prove that any Polynomial Calculus refutation of a set of polynomials encoding the M P H P, requires degree Ω(log n). We also prove a simple Lemma giving a simulation of Resolution by Polynomial Calculus. Using this lemma, and a Resolution upper bound by Goerdt [7], we obtain that the degree lower bound is tight. Our lower bound establishes the optimality of the tree-like Resolution simulation by the Polynomial Calculus given in [6]. Received: 29 March 2001 / Published online: 2 September 2002 RID="⋆" ID="⋆" A prelimianry version appeared as part of the paper A Study of Proof Search Algorithms for Resolution and Polynomial Calculus published in the Proceedings of the 40-th IEEE Conference on Foundations of Computer Science, 1999 RID="†" ID="†" Partly supported by Project CICYT, TIC 98-0410-C02-01 and Promoción General del Conocimiento PB98-0937-C04-03. RID="††" ID="††" Part of this work was done while the author was a member of the School of Mathematics at Institute for Advanced Study supported by a NSF grant n. 9987845