Online scheduling with reassignment

This paper studies online scheduling problems with reassignment on two identical machines. We can reassign some jobs under certain rules after all the jobs have been assigned. Three different versions are studied and optimal algorithms are proposed.     

THE FFD ALGORITHM FOR THE BIN PACKING PROBLEM WITH KERNEL ITEMS

The FFD algorithm is one of the most famous algorithms for the classical bin packing problem. In this paper,some versions of the FFD algorithm are considered in several bin packing problems. Especially,two of them applied to the bin packing problem with kernel items are analyzed. Tight worst-case performance ratios are obtained.     

Single machine scheduling with controllable release and processing parameters

This paper considers single machine scheduling problems in which the job processing times and/or their release dates are controllable. Possible changes to the controllable parameters are either individual or done by controlling the relevant processing or release rate. The objective is to minimize the sum of the makespan plus the cost for changing the parameters. For the problems of this type, we provide a number of polynomial-time algorithms and give a fairly complete complexity classification.     

A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows

This paper deals with several bicriteria open-shop scheduling problems where jobs are pre-emptable and their corresponding time-windows must be strictly respected. The criteria are a performance cost and the makespan. Network flow approaches are used in a lexmin procedure with a bounded makespan and the considered bicriteria problems are solved. Finally, the computational complexity of the algorithm and a numerical example are reported.     

The Hertz contact problem,coupled Volterra integral equations and a linear complementarity problem

This paper is concerned with the indentation of an elastic half-space by an axisymmetric punch under a monotonically applied normal force and under the assumption of Coulomb friction with coefficient μ$\mu$ in the region of contact. Within an inner (unknown) circle the contact is adhesive, while in the surrounding annulus the surface moves inwards with increasing load. In this paper it is shown how this problem is equivalent to two coupled Abel's equations with an unknown free point, the inner circumference of the annulus. It is further shown that a product integration finite difference approximation of those integral equations leads to a mixed linear complementarity problem (mixed LCP). A method based on Newton's method for solving non-smooth nonlinear equations is demonstrated to converge under restrictive assumptions on the physical parameters defining the system; and numerical experimentation verifies that it has much wider applicability. The method is also validated against the approach of Spence. The advantage of the mixed LCP formulation is that it provides the radius of the inner adhesive circle directly using the physical parameters of the problem.     

Experimental study of scheduling with memory constraints using hybrid methods

In this paper we study divisible load scheduling in systems with limited memory. Divisible loads are parallel computations which can be divided into independent parts processed in parallel on remote computers, and the part sizes may be arbitrary. The distributed system is a heterogeneous single level tree. The total size of processor memories is too small to accommodate the whole load at any moment of time. Therefore, the load is distributed in many rounds. Memory reservations have block nature. The problem consists in distributing the load taking into account communication time, computation time, and limited memory buffers so that the whole processing finishes as early as possible. This problem is both combinatorial and algebraic in nature. Therefore, hybrid algorithms are given to solve it. Two algorithms are proposed to solve the combinatorial component. A branch-and-bound algorithm is nearly unusable due to its complexity. Then, a genetic algorithm is proposed with more tractable execution times. For a given solution of the combinatorial part we formulate the solution of the algebraic part as a linear programming problem. An extensive computational study is performed to analyze the impact of various system parameters on the quality of the solutions. From this we were able to infer on the nature of the scheduling problem.     

NOTE ON INVERSE PROBLEM WITH l∞ OBJECTIVE FUNCTION

In this note, the author proves that the inverse problem of submodular function on digraphs with l∞ objective function can be solved by strongly polynomial algorithm. The result shows that most inverse network optimization problems with l∞ objective function can be solved in the polynomial time.     

Some generalizations of the criss-cross method for the linear complementarity problem of oriented matroids

Combinatorica - Quadratic programming, symmetry, positive (semi) definiteness and the linear complementary problem were generalized by Morris and Todd to oriented matroids. Todd gave a constructive...     

The Cauchy-Neumann problem for a viscous Hamilton-Jacobi equation

We study the weak solvability of viscous Hamilton-Jacobi equation: \,0,\,x\,\in\,\Omega,$" align="middle" border="0"> with Neumann boundary condition and irregular initial data ₀. The domain is a bounded open set and p > 0. The last part deals with the case a convex set and the initial data ₀ = in a open set D such that and      

Quality of move-optimal schedules for minimizing total weighted completion time

We study the minimum total weighted completion time problem on identical machines. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio . In a special case, the approximation ratio is .     

The Brezis-Nirenberg problem near criticality in dimension 3

We consider the problem of finding positive solutions of Δu+λu+u^q=0 in a bounded, smooth domain Ω in , under zero Dirichlet boundary conditions. Here q is a number close to the critical exponent 5 and 0<λ<λ₁. We analyze the role of Green's function of Δ+λ in the presence of solutions exhibiting single and multiple bubbling behavior at one point of the domain when either q or λ are regarded as parameters. As a special case of our results, we find that if , where λ∗ is the Brezis-Nirenberg number, i.e., the smallest value of λ for which least energy solutions for q=5 exist, then this problem is solvable if q>5 and q−5 is sufficiently small.     

From fluid relaxations to practical algorithms for job shop scheduling: the makespan objective

We design an algorithm, called the fluid synchronization algorithm (FSA), for the job shop scheduling problem with the objective of minimizing the makespan. We round an optimal solution to a fluid relaxation, in which we replace discrete jobs with the flow of a continuous fluid, and use ideas from fair queueing in the area of communication networks in order to ensure that the discrete schedule is close to the one implied by the fluid relaxation. FSA produces a schedule with makespan at most C _max+(I+2)P _max J _max, where C _max is the lower bound provided by the fluid relaxation, I is the number of distinct job types, J _max is the maximum number of stages of any job-type, and P _max is the maximum processing time over all tasks. We report computational results based on all benchmark instances chosen from the OR library when N jobs from each job-type are present. The results suggest that FSA has a relative error of about 10% for N=10, 1% for N=100, 0.01% for N=1000. In comparison to eight different dispatch rules that have similar running times as FSA, FSA clearly dominates them. In comparison to the shifting bottleneck heuristic whose running time and memory requirements are several orders of magnitude larger than FSA, the shifting bottleneck heuristic produces better schedules for small N (up to 10), but fails to provide a solution for larger values of N. Received: September 1999 / Accepted: September 2001?Published online March 14, 2002     

The multifit algorithm for set partitioning containing kernels

This pager investigates the set partitioning containing kernels. This problem can alsobe considered as the identical machine scheduling prohlem with nonsimultaneous machine release times. That the algorithm MULTIFIT has a worst ease bound of 6/5 is proved. Throughcombining MULTIFIT and LPT. an algorithm MULTILPT with a worat case bound of 7/6 has been obtained.     

On the stability of the Serrin problem

We investigate stability issues concerning the radial symmetry of solutions to Serrin's overdetermined problems. In particular, we show that, if u is a solution to Δu=n in a smooth domain Ω⊂Rn, u=0 on ∂Ω and |Du| is “close” to 1 on ∂Ω, then Ω is “close” to the union of a certain number of disjoint unitary balls.     

The Dirichlet problem for the Bellman equation at resonance

We generalize the Donsker-Varadhan minimax formula for the principal eigenvalue of a uniformly elliptic operator in nondivergence form to the first principal half-eigenvalue of a fully nonlinear operator which is concave (or convex) and positively homogeneous. Examples of such operators include the Bellman operator and the Pucci extremal operators. In the case that the two principal half-eigenvalues are not equal, we show that the measures which achieve the minimum in this formula provide a partial characterization of the solvability of the corresponding Dirichlet problem at resonance.     

The Cauchy problem for the Schrödinger-KdV system

In this paper we prove that in the general case (i.e. β not necessarily vanishing) the Cauchy problem for the Schrödinger-Korteweg-de Vries system is locally well-posed in , and if β=0 then it is locally well-posed in with . These results improve the corresponding results of Corcho and Linares (2007) [5]. Idea of the proof is to establish some bilinear and trilinear estimates in the space Gs×Fs, where Gs and Fs are dyadic Bourgain-type spaces related to the Schrödinger operator and the Airy operator , respectively, but with a modification on Fs in low frequency part of functions with a weaker structure related to the maximal function estimate of the Airy operator.     

Mutual exclusion scheduling with interval graphs or related classes. Part II

This paper is the second part of a study devoted to the mutual exclusion scheduling problem. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted by χ(G,k). When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender, K. Jansen, Restrictions of graph partition problems. Part I. Theoret. Comput. Sci. 148 (1995) 93-109]. In this paper, the problem is approached from a different point of view by studying a non-trivial and practical sufficient condition for optimality. In particular, the following proposition is demonstrated: if an interval graph G admits a coloring such that each color appears at least k times, then χ(G,k)=⌈n/k⌉. This proposition is extended to several classes of graphs related to interval graphs. Moreover, all our proofs are constructive and provide efficient algorithms to solve the MES problem for these graphs, given a coloring satisfying the condition in input.     

Models and Complexity of Multibin Packing Problems

This paper extends the previous work on multibin packing problems and gives a deeper insight into these models and their complexity, so as to provide a strong framework for future application-oriented studies. In a multibin problem, an object requires several bins to be packed. New models are represented, including the maximum cardinality multibin packing. Their complexity is studied and several pseudo-polynomial time algorithms are described, together with a fully polynomial time approximation scheme (FPTAS) for a fixed number of bins.