A graph-oriented approach for the minimization of the number of late jobs for the parallel machines scheduling problem

An O(n²) algorithm is presented for the n jobs m parallel machines problem with identical processing times. Due dates for each job are given and the objective is the minimization of the number of late jobs. Preemption is permitted. The problem can be formulated as a maximum flow network model. The optimality proof as well as other properties and a complete example are given.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches

Let p≥2 be an integer and T be an edge-weighted tree. A cut on an edge of T is a splitting of the edge at some point on it. A p-edge-partition of T is a set of p subtrees induced by p−1 cuts. Given p and T, the max-min continuous tree edge-partition problem is to find a p-edge-partition that maximizes the length of the smallest subtree; and the min-max continuous tree edge-partition problem is to find a p-edge-partition that minimizes the length of the largest subtree. In this paper, O(n²)-time algorithms are proposed for these two problems, improving the previous upper bounds by a factor of log (min{p,n}). Along the way, we solve a problem, named the ratio search problem. Given a positive integer m, a (non-ordered) set B of n non-negative real numbers, a real valued non-increasing function F, and a real number t, the problem is to find the largest number z in {b/a|a∈[1,m],b∈B} such that F(z)≥t. We give an O(n+t_F×(logn+logm))-time algorithm for this problem, where t_F is the time required to evaluate the function value F(z) for any real number z.     

Fast algorithms for determining the linear complexities of sequences over GF(p m) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p ? 1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(p ^m) (any positive integer m) with the period 3n (n and p ^m ? 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-Imamura algorithm, we can determine the linear complexity of any sequence over GF(p ^m) with the period 3n (n and p ^m ? 1 are coprime) more efficiently.     

Construction of universal one-way hash functions: Tree hashing revisited

We present a binary tree based parallel algorithm for extending the domain of a universal one-way hash function (UOWHF). For t?2, our algorithm extends the domain from the set of all n-bit strings to the set of all ((2^t-1)(n-m)+m)-bit strings, where m is the length of the message digest. The associated increase in key length is 2m bits for t=2; m(t+1) bits for 3?t?6 and m×(t+⌊log₂(t-1)⌋) bits for t?7.     

Scheduling an unbounded batching machine with family jobs and setup times

We consider the problem of scheduling n jobs on an unbounded batching machine that can process any number of jobs belonging to the same family simultaneously in the same batch. All jobs in the same batch complete at the same time. Jobs belonging to different families cannot be processed in the same batch, and setup times are required to switch between batches that process jobs from different families. For a fixed number of families m, we present a generic forward dynamic programming algorithm that solves the problem of minimizing an arbitrary regular cost function in pseudopolynomial time. We also present a polynomial-time backward dynamic programming algorithm with time complexity O (mn(n/m+1) ^m ) for minimizing any additive regular minsum objective function and any incremental regular minmax objective function. The effectiveness of our dynamic programming algorithm is shown by computational experiments based on the scheduling of the heat-treating process in a steel manufacturing plant.     

Maximal sum-free sets in finite Abelian groups,III

The main result of this paper is the complete characterization of maximal sum-free sets in Abelian groups of order 3^mn(m ≥ 1) where every prime divisor p of n (if n > 1) is congruent to 1 modulo 3. A few previous results of the author on addition theorems of group theory are also sharpened and/or improved.     

Generalized congruence properties of the restricted partition function p(n,m)

Ramanujan-type congruences for the unrestricted partition function p(n) are well known and have been studied in great detail. The existence of Ramanujan-type congruences are virtually unknown for p(n,m), the closely related restricted partition function that enumerates the number of partitions of n into exactly m parts. Let ? be any odd prime. In this paper we establish explicit Ramanujan-type congruences for p(n,?) modulo any power of that prime ? ^α . In addition, we establish general congruence relations for p(n,?) modulo ? ^α for any n.     

Multivariable monotonic optimization over multivalued logics and rectangular design lattices

A minimum dichotomous direct search procedure is given for finding the optimum combination of N variables, each having M(n) possible values, when a certain monotonicity condition is satisfied. The least upper bound on the number of objective function evaluations is 1 + Σ^N_n=1Q(n), where Q(n) is defined by 2^Q(n)-1<M(n) < 2^Q(n), whereas the total number of possibilities is Π^N_R=1M(n). An example shows where the procedure applies to restricted problems in multivalued logic and engineering design.     

On the largest prime factor of the partition function of n

Let p(n) be the function that counts the number of partitions of n. For a positive integer m, let P(m) be the largest prime factor of m. Here, we show that P(p(n)) tends to infinity when n tends to infinity through some set of asymptotic density 1. In fact, we show that the inequality P(p(n))>loglogloglogloglogn holds for almost all positive integers n. Features of the proof are the first term in Rademacher??s formula for p(n), Gowers?? effective version of Szemerédi??s theorem, and a classical lower bound for a nonzero homogeneous linear form in logarithms of algebraic numbers due to Matveev.     

Finite groups with the set of the number of subgroups of possible order containing exactly two elements

Let G be a finite group, and n(G) be the set of the number of subgroups of possible order of G. We investigate the structure of G satisfying that n(G)?=?{1, m} for any positive integer m?>?1. At first, we prove that the nilpotent length of G is less than 2. Secondly, we investigate nilpotent groups with m?=?p?+?1 or p ²?+?p?+?1 (p is a prime), and we get the classification of such kinds of groups. At last, we investigate non-nilpotent groups with m?=?p?+?1 and get the classification of the groups under consideration.     

On upper domination Ramsey numbers for graphs

The classical Ramsey number r(m,n) can be defined as the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, β(B)⩾m or β(R)⩾n, where β(G) denotes the independence number of a graph G. We define the upper domination Ramsey number u(m,n) as the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, Γ(B)⩾m or Γ(R)⩾n, where Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. The mixed domination Ramsey number v(m,n) is defined to be the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, Γ(B)⩾m or β(R)⩾n. Since β(G)⩽Γ(G) for every graph G, u(m,n)⩽v(m,n)⩽r(m,n). We develop techniques to obtain upper bounds for upper domination Ramsey numbers of the form u(3,n) and mixed domination Ramsey numbers of the form v(3,n). We show that u(3,3)=v(3,3)=6, u(3,4)=8, v(3,4)=9, u(3,5)=v(3,5)=12 and u(3,6)=v(3,6)=15.     

Minimizing the number of early jobs on a proportionate flowshop

A proportionate flowshop is a special case of the classical flowshop, where the job processing times are machine-independent. We study the problem of minimizing the number of early jobs in this machine setting. This objective function has hardly been investigated on a single machine, and never on a flowshop. We introduce an efficient iterative solution algorithm. In each iteration, a single job is moved to the first position (and is added to the set of early jobs), and the remaining jobs are rescheduled such that the maximum earliness is minimized. The algorithm guarantees an optimal solution in O(n³) time, where n is the number of jobs.     

Binary tree algebraic computation and parallel algorithms for simple graphs

In this paper we define the binary tree algebraic computation (BTAC) problem and develop an efficient parallel algorithm for solving this problem. A variety of graph problems (minimum covering set, minimum r-dominating set, maximum matching set, etc.) for trees and two terminal series parallel (TTSP) graphs can be converted to instances of the BTAC problem. Thus efficient parallel algorithms for these problems are obtained systematically by using the BTAC algorithm. The parallel computation model is an exclusive read exclusive write PRAM. The algorithms for tree problems run in O(log n) time with O(n) processors. The algorithms for TTSP graph problems run in O(log m) time with O(m) processors where n (m) is the number of vertices (edges) in the input graph. These algorithms are within an O(log n) factor of optimal.     

Minmax regret location–allocation problem on a network under uncertainty

We consider a robust location–allocation problem with uncertainty in demand coefficients. Specifically, for each demand point, only an interval estimate of its demand is known and we consider the problem of determining where to locate a new service when a given fraction of these demand points must be served by the utility. The optimal solution of this problem is determined by the “minimax regret” location, i.e., the point that minimizes the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. For the case where the demand points are vertices of a network we show that the robust location–allocation problem can be solved in O(min{p, n − p}n³m) time, where n is the number of demand points, p (p < n) is the fixed number of demand points that must be served by the new service and m is the number of edges of the network.     

Piecewise-linear programming: The compact (CPLP) algorithm

A compact algorithm is presented for solving the convex piecewise-linear-programming problem, formulated by means of a separable convex piecewise-linear objective function (to be minimized) and a set of linear constraints. This algorithm consists of a finite sequence of cycles, derived from the simplex method, characteritic of linear programming, and the line search, characteristic of nonlinear programming. Both the required storage and amount of calculation are reduced with respect to the usual approach, based on a linear-programming formulation with an expanded tableau. The tableau dimensions arem×(n+1), wherem is the number of constraints andn the number of the (original) structural variables, and they do not increase with the number of breakpoints of the piecewise-linear terms constituting the objective function.     

Bilinear Relative Equilibria of Identical Point Vortices

A new class of bilinear relative equilibria of identical point vortices in which the vortices are constrained to be on two perpendicular lines, conveniently taken to be the x- and y-axes of a Cartesian coordinate system, is introduced and studied. In the general problem we have m vortices on the y-axis and n on the x-axis. We define generating polynomials q(z) and p(z), respectively, for each set of vortices. A second-order, linear ODE for p(z) given q(z) is derived. Several results relating the general solution of the ODE to relative equilibrium configurations are established. Our strongest result, obtained using Sturm’s comparison theorem, is that if p(z) satisfies the ODE for a given q(z) with its imaginary zeros symmetric relative to the x-axis, then it must have at least n?m+2 simple, real zeros. For m=2 this provides a complete characterization of all zeros, and we study this case in some detail. In particular, we show that, given q(z)=z ²+η ², where η is real, there is a unique p(z) of degree n, and a unique value of η ²=A _n , such that the zeros of q(z) and p(z) form a relative equilibrium of n+2 point vortices. We show that $A_{n} \approx\frac{2}{3}n + \frac{1}{2}$ , as n→∞, where the coefficient of n is determined analytically, the next-order term numerically. The paper includes extensive numerical documentation on this family of relative equilibria.     

Recurrence relations for the coefficients of the Fourier series expansions with respect to q-classical orthogonal polynomials

We propose an algorithm to construct recurrence relations for the coefficients of the Fourier series expansions with respect to the q-classical orthogonal polynomials p_k(x;q). Examples dealing with inversion problems, connection between any two sequences of q-classical polynomials, linearization of ϑ_m(x) p_n(x;q), where ϑ_m(x) is x^mor (x;q)_m, and the expansion of the Hahn-Exton q-Bessel function in the little q-Jacobi polynomials are discussed in detail. This revised version was published online in June 2006 with corrections to the Cover Date.     

PBIB designs with m associate classes induced by full rank matrices modulo pm

This paper presents series of PBIB designs with m associate classes in which the treatment set is a subset of the Z(p^m)-module of n × 1 vectors over the ring of integers modulo p^m, p any prime. The association scheme of this series of designs is determined by the Fuller canonical form under row equivalence of n × 2 matrices [a,b] for vectors a and b in the treatment set. The blocking procedure utilizes full rank s × n matrices over Z(p^m), 1 ? s ? n ? 2, n ? 3. For m = 2, n = 3, s =1 and for each prime p, each PBIB is regular divisible and yields a finite proper uniform projective Hjelmslev plane with parameters j = p and k = p(p + 1).