Mathematical models for job-shop scheduling problems with routing and process plan flexibility

As a result of rapid developments in production technologies in recent years, flexible job-shop scheduling problems have become increasingly significant. This paper deals with two NP-hard optimization problems: flexible job-shop scheduling problems (FJSPs) that encompass routing and sequencing sub-problems, and the FJSPs with process plan flexibility (FJSP-PPFs) that additionally include the process plan selection sub-problem. The study is carried out in two steps. In the first step, a mixed-integer linear programming model (MILP-1) is developed for FJSPs and compared to an alternative model in the literature (Model F) in terms of computational efficiency. In the second step, one other mixed-integer linear programming model, a modification of MILP-1, for the FJSP-PPFs is presented along with its computational results on hypothetically generated test problems.     

The snowblower problem

We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a short tour for the snowblower to follow to remove all the snow from a domain (driveway, sidewalk, etc.). When a snowblower passes over each region along the tour, it displaces snow into a nearby region. The constraint is that if the snow is piled too high, then the snowblower cannot clear the pile.We give an algorithmic study of the SBP. We show that in general, the problem is NP-complete, and we present polynomial-time approximation algorithms for removing snow under various assumptions about the operation of the snowblower. Most commercially available snowblowers allow the user to control the direction in which the snow is thrown. We differentiate between the cases in which the snow can be thrown in any direction, in any direction except backwards, and only to the right. For all cases, we give constant-factor approximation algorithms; the constants increase as the throw direction becomes more restricted. Our results are also applicable to robotic vacuuming (or lawnmowing) with bounded-capacity dust bin.     

LOCALLY STABILIZED FINITE ELEMENT METHOD FOR STOKES PROBLEM WITH NONLINEAR SLIP BOUNDARY CONDITIONS

Based on the low-order conforming finite element subspace （Vh, Mh） such as the P1-P0 triangle element or the Q1-P0 quadrilateral element, the locally stabilized finite element method for the Stokes problem with nonlinear slip boundary conditions is investigated in this paper. For this class of nonlinear slip boundary conditions including the subdifferential property, the weak variational formulation associated with the Stokes problem is an variational inequality. Since （Vh, Mh） does not satisfy the discrete inf-sup conditions, a macroelement condition is introduced for constructing the locally stabilized formulation such that the stability of （Vh, Mh） is established. Under these conditions, we obtain the H1 and L2 error estimates for the numerical solutions.     

Entropy, independent sets and antichains: A new approach to Dedekind's problem

For -regular, -vertex bipartite graphs with bipartition , a precise bound is given for the sum over independent sets of the quantity . (In other language, this is bounding the partition function for certain instances of the hard-core model.) This result is then extended to graded partially ordered sets, which in particular provides a simple proof of a well-known bound for Dedekind's Problem given by Kleitman and Markowsky in 1975.

     

Scheduling in network flow shops

We consider the general problem of static scheduling of a set of jobs in a network flow shop. In network flow shops, the scheduler not only has to sequence and schedule but also must concurrently determine the process routing of the jobs through the shop. In this paper, we establish the computational complexity of this new class of scheduling problem and propose a general purpose heuristic procedure. The performance of the heuristic is analyzed when makespan, cycle time and average flow time are the desired objectives.This research has been supported by the UCLA Academic Senate Grant #95.     

Three Classes of Reaction-Diffusion Systems with Neumann Boundary Condition

ＴｈｒｅｅＣｌａｓｓｅｓｏｆＲｅａｃｔｉｏｎ－ＤｉｆｆｕｓｉｏｎＳｙｓｔｅｍｓｗｉｔｈＮｅｕｍａｎｎＢｏｕｎｄａｒｙＣｏｎｄｉｔｉｏｎ￥（严子谦）ＹａｎＺｉｑｉａｎ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈ...     

Computational experience with the Chow—Yorke algorithm

The Chow—Yorke algorithm is a nonsimplicial homotopy type method for computing Brouwer fixed points that is globally convergent. It is efficient and accurate for fixed point problems. L.T. Watson, T.Y. Li, and C.Y. Wang have adapted the method for zero finding problems, the nonlinear complementarity problem, and nonlinear two-point boundary value problems. Here theoretical justification is given for applying the method to some mathematical programming problems, and computational results are presented.This work was partially supported by NSF Grant MCS 7821337.     

A numerical technique for three-dimensional compressible boundary layers

The non-linear two-point boundary value problem for three-dimensional compressible boundary layers is solved through the application of a boundary value technique for a range of parameters characterizing the nature of stagnation point flows. The analytical boundary conditions, at infinity, are applied at the edge of the computational mesh with iterations on the size of the domain. The solutions obtained show excellent agreement with the established similarity solutions for three-dimensional flows. The present method has the potential advantage of yielding the wall values of f″_w, g″_w and θ′_w as a part of the solution, contrary to the previously used ‘shooting’ methods. The algorithm is computationally simple and numerically stable and extremely suitable for engineering design applications.     

Analysis of additive metals in fuel and emission aerosols of diesel vehicles with and without particle traps

Fuel additives used in particle traps have to comply with environmental directives and should not support the formation of additional toxic substances. The emission of metal additives from diesel engines with downstream particle traps has been studied. Aspects of the optimisation of sampling procedure, sample preparation and analysis are described. Exemplary results in form of a mass balance calculation are presented. The results demonstrate the high retention rate of the studied filter system but also possible deposition of additive metals in the engine.     

A free boundary problem for a fluid flow in a heterogeneous porous medium

In this paper we study the problem of seepage of a fluid through a porous medium, assuming the flow governed by a nonlinear Darcy law and nonlinear leaky boundary conditions. We prove the continuity of the free boundary and the existence and uniqueness of minimal and maximal solutions. We also prove the uniqueness of theS ₃-connected solution in various situations.