Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem

This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r _i , q _i |C _max. The link between P||C _max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r _i , q _i |C _max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported.     

An improved max-flow-based lower bound for minimizing maximum lateness on identical parallel machines

In this paper, we introduce a new concept of semi-preemptive scheduling and we show how it can be used to derive a maximum-flow-based lower bound for the P|r_j|L_max which dominates the well-known preemptive lower bound. We show that, in some cases, the proposed bound strictly dominates the preemptive one while having the same complexity.     

Minimax linear programming problem

In this paper, we consider the following minimax linear programming problem: min z = max_{1 ≤ j ≤ n}{C_jX_j}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem.     

Pareto optima for total weighted completion time and maximum lateness on a single machine

We consider the single-machine bicriterion scheduling problem of enumerating the Pareto-optimal sequences with respect to the total weighted completion time and the maximum lateness objectives. We show that the master sequence concept originally introduced for 1|r_j|∑w_jU_j by Dauzère-Pérès and Sevaux is also applicable to our problem and a large number of other sequencing problems. Our unified development is based on exploiting common order-theoretic structures present in all these problems. We also show that the master sequence implies the existence of global dominance orders for these scheduling problems. These dominance results were incorporated into a new branch and bound algorithm, which was able to enumerate all the Pareto optima for over 90% of the 1440 randomly generated problems with up to n=50 jobs. The identification of each Pareto optimum implicitly requires the optimal solution of a strongly NP-hard problem. The instances solved had hundreds of these Pareto solutions and to the best of our knowledge, this is the first algorithm capable of completely enumerating all Pareto sequences within reasonable time and space for a scheduling problem with such a large number of Pareto optima.     

On Harary index of graphs

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. For a connected graph G=(V,E) and two nonadjacent vertices v_i and v_j in V(G) of G, recall that G+v_iv_j is the supergraph formed from G by adding an edge between vertices v_i and v_j. Denote the Harary index of G and G+v_iv_j by H(G) and H(G+v_iv_j), respectively. We obtain lower and upper bounds on H(G+v_iv_j)−H(G), and characterize the equality cases in those bounds. Finally, in this paper, we present some lower and upper bounds on the Harary index of graphs with different parameters, such as clique number and chromatic number, and characterize the extremal graphs at which the lower or upper bounds on the Harary index are attained.     

An improved upper bound in the maximum dispersal problem

For integral? m?2, let x₁,…, x_m be any unit vectors in R_n, the real Euclidean space of n dimensions. We obtain an upper bound for the quantity min_i≠j|x_i-x_j| which, though not as simple, is uniformly sharper than one recently obtained by the author. The result has application to the so-called maximum-dispersal problem, an open problem recently popularized by Klee.     

Scheduling transmissions in a network

Consider k stations wishing to transmit messages over a network of channels to a common receiver. The capacity of a channel is the maximum amount of data which can be transmitted in a time unit. In addition to the transmission stations, the network contains switching nodes. Given that the jth station has σ_j messages (j = 1,…, k) to transmit, it is desired to find a schedule with minimum completion time T. The amount of data sent over a channel may vary in time. A schedule is stationary if the amount of data sent in a time unit is constant throughout the schedule. It is first shown that for every schedule there exists a stationary schedule with the same completion time. Thus, the search for an optimum schedule is confined to stationary schedules. The problem of finding an optimum stationary schedule is formulated as a multisource single-sink network flow problem, in which the net amount of outgoing flow from each source (transmission station) within one time unit is $\text{σ}{}_{\mathrm{j}}\text{T}$. An O(k|E||V|²) time algorithm to find the minimum T similar to Dinic's flow algorithm is suggested. Using Sleator and Tarjan's techniques an O(k²|E||V|log|V|) algorithm is derived. The running time of both algorithms is independent of the σ_j's and the capacities.     

Computer difference scheme for a singularly perturbed convection-diffusion equation

The Dirichlet problem for a singularly perturbed ordinary differential convection-diffusion equation with a perturbation parameter ? (that takes arbitrary values from the half-open interval (0, 1]) is considered. For this problem, an approach to the construction of a numerical method based on a standard difference scheme on uniform meshes is developed in the case when the data of the grid problem include perturbations and additional perturbations are introduced in the course of the computations on a computer. In the absence of perturbations, the standard difference scheme converges at an \(\mathcal{O}\) (δ _st ) rate, where δ _st = (? + N ^?1)^?1 N ^?1 and N + 1 is the number of grid nodes; the scheme is not ?-uniformly well conditioned or stable to perturbations of the data. Even if the convergence of the standard scheme is theoretically proved, the actual accuracy of the computed solution in the presence of perturbations degrades with decreasing ? down to its complete loss for small ? (namely, for ? = \(\mathcal{O}\) (δ^?2max _i,j |δa _i ^j | + δ^?1 max _{i, j} |δb _i ^j |), where δ = δ _st and δa _i ^j , δb _i ^j are the perturbations in the coefficients multiplying the second and first derivatives). For the boundary value problem, we construct a computer difference scheme, i.e., a computing system that consists of a standard scheme on a uniform mesh in the presence of controlled perturbations in the grid problem data and a hypothetical computer with controlled computer perturbations. The conditions on admissible perturbations in the grid problem data and on admissible computer perturbations are obtained under which the computer difference scheme converges in the maximum norm for ? ∈ (0, 1] at the same rate as the standard scheme in the absence of perturbations.     

A new heuristic for open shop total completion time problem

The m  -machine open shop problem to minimize the sum of the completion times is investigated in our paper. First, a heuristic algorithm, Shortest Processing Time Block, is presented to deal with problem _Om|n=km|∑_Cj$O_m|n=\mathit{km}|\sum C_j$, where k   is positive integer. And then, the heuristic is extended to solve the general problem _Om‖∑_Cj$O_m\Vert \sum C_j$. It is proved that the heuristic is asymptotically optimal when the job number goes to infinity. At the end of this paper, numerical experimentation results show the effectiveness of the heuristic algorithm.     

Point estimation for multi-spectral distributed random matrices

In this communication, we consider a p×n random matrix which is normally distributed with mean matrix M and covariance matrix Σ, where the multivariate observation x_i=y_i+?_i with p dimensions on an object consists of two components, the signal y_i with mean vector μ and covariance matrix Σ_s and noise with mean vector zero and covariance matrix Σ_?, then the covariance matrix of x_i and x_j is given by Σ=Cov(x_i,x_j)=Γ⊗(B_|i-j|Σ_s+C_|i-j|Σ_?), where Γ is a correlation matrix; B_|i-j| and C_|i-j| are diagonal constant matrices. The statistical objective is to consider the maximum likelihood estimate of the mean matrix M and various components of the covariance matrix Σ as well as their statistical properties, that is the point estimates of Σ_s,Σ_? and Γ. More importantly, some properties of these estimators are investigated in slightly more general models.     

Vector packing in finite dimensional vector spaces

Let m be an integer ? 2. The effect of crowding m unit vectors x₁,…,x_m into the real Euclidean space R_n of n dimensions is investigated. In particular, several upper bounds for the quantity min_i≠j∥x_i ? x_j∥ are obtained. These are simpler than any previously known and, at least in some cases, almost as sharp. The results have application to the so-called maximum-dispersal (or “misanthrope”) problem, an open problem recently popularized by Klee.     

A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs

The scheduling problem 1|pmtn, r _j |w _j U _j calls forn jobs with arbitrary release dates and due dates to be preemptively scheduled for processing by a single machine, with the objective of minimizing the sum of the weights of the late jobs. A dynamic programming algorithm for this problem is described. Time and space bounds for the algorithm are, respectively,O(nk ² W ²) andO(k ² W), wherek is the number of distinct release dates andW is the sum of the integer job weights. Thus, for the problem 1|pmtn, r _j |U _j , in which the objective is simply to minimize the number of late jobs, the pseudopolynomial time bound becomes polynomial, i.e.O(n ³ k ²).     

Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems

This paper presents an exact algorithm for the identical parallel machine scheduling problem over a formulation where each variable is indexed by a pair of jobs and a completion time. We show that such a formulation can be handled, in spite of its huge number of variables, through a branch cut and price algorithm enhanced by a number of practical techniques, including a dynamic programming procedure to fix variables by Lagrangean bounds and dual stabilization. The resulting method permits the solution of many instances of the P||∑w _j T _j problem with up to 100 jobs, and having 2 or 4 machines. This is the first time that medium-sized instances of the P||∑w _j T _j have been solved to optimality.     

“Best possible” upper bounds for the first positive zeros of Bessel functions — the finite part

It is shown here that the first three terms of the asymptotic expansion of j_vk, k = 1, 2, 3, provide an upper bound for j_vk in 0 < v ⩽ 10, hence a “best possible” upper bound. Lang and Wong have shown that this is true also for 10 < v < ∞ when k = 1 and 2, so that these “best possible” upper bounds hold in the entire interval 0 < v < ∞ in these cases. We include supplementary comments on lower bounds in 0 ⩽ v ⩽ 10.     

A counter example for nilpotent groups

Let R be a ring with 1, I be a nilpotent subring of R (there exists a natural number n, such that In = 0), and I be generated by {xj |j ∈ J} as ring. Write U = 1 + I, and it is a nilpotent group with class ≤ n - 1. Let G be the subgroup of U which is generated by {1 + xj|j ∈ J}. The group constructed in this paper indicates that the nilpotency class of G can be less than that of U.     

On Modules with Finite Exchange Property

The purpose of this paper is to answer an open problem proposed by Matlis on modules with the finite exchange property. The problem is: Let {M _i | i ∈ I} be an indexed family of indecomposable injective modules and M a direct sum of M _i , i.e. M = ⊕{M _i | i ∈ I} and N a summand of M. Is N a direct sum of indecomposable injective modules, i.e. N = ⊕{M _j |j ∈ J, J ? I}? The answer to this problem is affirmative for module M with finite exchange property.     

Lipschitz homeomorphisms of the Hilbert cube

We study the question whether the Hilbert cube Q is Lipschitz homogeneous. The answer depends on the metric of Q. For example, setting d(x,y)=sup_j|x_j-y_j|/j we obtain a Lipschitz homogeneous metric, but if the last j is replaced by j!, the answer is negative.     

On Local Structure of 9- and 10-Connected Graphs

R. Halin had posed the problem of finding the largest constant c _k such that any minimally and contraction critically k-connected graph has at least c _k|V G| vertices of degree k. Twenty years later, the exact bound for k?=?4(c ₄?=?1) was found by N. Martinov and independently, by M. Fontet. For larger k, exact bounds are unknown. This paper contributes to the study of local structure of minimally and contraction critically k-connected graphs and lower boundsfor c _k . We prove that ${c_k} \geqslant \frac{1}{2}$ for k?=?9,10. This result extends the sequence of lower bounds for c _k which is equal $\frac{1}{2}$ to the values k?=?6,7,8,9,10. Bibliography: 30 titles.     

A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates

In this paper we consider the scheduling problem of minimizing the weighted number of late jobs on a single machine (1|_rj|∑_wjUj)$\left(1|r_j|\sum w_j{U}_j\right)$. A branch-and-check algorithm is proposed, where a relaxed integer programming formulation is solved by branch-and-bound and infeasible solutions are cut off using infeasibility cuts. We suggest two ways to generate cuts. First, tightened “no-good” cuts are derived using a modification of the algorithm by Carlier (1982, EJOR, v.11, 42–47) which was developed for the problem of minimizing maximum lateness on a single machine. Secondly we show how to create cuts by using constraint propagation. The proposed algorithm is implemented in the Mosel modelling and optimization language. Computational experiments on instances with up to 140 jobs are reported. A comparison is presented with the exact approach of Péridy at al. (2003, EJOR, v.148, 591–603).     

Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences

In the paper a single machine time-dependent scheduling problem is considered. The processing time p_j of each job is described by a function of the starting time t of the job, p_j=1+α_jt, where the job deterioration rate α_j?0 for j=0,1,…,n and t?0. Jobs are nonpreemptable and independent, there are no ready times and no deadlines. The criterion of optimality of a schedule is the total completion time.First, the notion of a signature for a given sequence of job deterioration rates is introduced, two types of the signature are defined and their properties are shown. Next, on the basis of these properties a greedy polynomial-time approximation algorithm for the problem is formulated. This algorithm, starting from an initial sequence, iteratively constructs a new sequence concatenating the previous sequence with new elements, according to the sign of one of the signatures of this sequence.Finally, these results are applied to the problem with job deterioration rates which are consecutive natural numbers, α_j=j for j=0,1,…,n. Arguments supporting the conjecture that in this case the greedy algorithm is optimal are presented.