A simple proof of diffusion approximations for LBFS re-entrant lines

For a re-entrant line operating under the last-buffer-first-serve service policy, there have been two independent proofs of a heavy traffic limit theorem. The key to these proofs is to prove the uniform convergence of a critical fluid model. We give a new proof for the uniform convergence of the fluid model.     

Performance analysis in a re-entrant operation with combinational routing and yield probabilities

Queuing networks arising from multistage processes with probabilistic re-entrant lines are common in manufacturing environments. Probabilistic re-entrant operation is defined as lots entering the operation with different repeated cycle requirements. This paper extends our work [S. Kumar, M.K. Omar, Stochastic re-entrant line modeling for an environmental stress testing in a semiconductor assembly industry, Appl. Math. Comput. 173 (2006) 603–615.] and proposes a modified analytical method based on the mean value analysis (MVA) technique and considering a probabilistic re-entrant line with yield loss probabilities. Introducing probabilities consideration into the MVA approach will substantially increase the complexity of the modeling and results analysis. However, the contribution of this paper is the introduction of a solution methodology that can overcome such complexity and allow operational managers to compute performance measures such as total cycle time and the mean throughput.     

Fluid model criterion for instability of re-entrant line with infinite supply of work

Using a fluid model approach, we obtain a sufficient condition for re-entrant lines with infinite supply of work to be unstable, which generalizes the results for re-entrant line of Dai (Ann. Appl. Probab. 6: 751–757, 1996). We apply the result to two special re-entrant lines with infinite supply of work as follows. In addition, we get necessary conditions for the corresponding fluid model to be weakly stable.     

非强占FBFS服务规则下Re-entrant Line排队网络的扩散逼近

本文研究了-个非强占静态优先权first-buffer-first-served(FBFS)服务规则下的re-entrant line排队网络.文章首先建立了-个极限定理,后通过分析队长和斜反射映射的关系,建立了队长过程和闲期过程的扩散逼近.     

A new continuous model for multiple re-entrant manufacturing systems

The semiconductor manufacturing systems that involve a large number of products and many steps can be modeled through conservation laws for a continuous density variable on production processes. In this paper, the basic partial differential equation (PDE) models for single-product re-entrant manufacturing systems are proposed first. However, through the validation of numerical examples, the basic continuous models do not perform well for single-product re-entrant systems. Then, a new state equation that takes into account the re-entrant degree of a product is introduced to improve the basic continuous models. The applicability of the modified continuous model is illustrated through numerical examples. The influence of the influx variation on the outflux is also discussed. With the changes of influx, the outflux has a reverse phenomenon. Based on the new state equation, the continuous model for multi-product re-entrant systems with different priorities is established, and an example is provided to illustrate the applicability of the new continuous model.     

带有无限到达源的Re-entrant Line的稳定性

用Foster判别准则,Weiss[13]给出了带有无限到达源的两站三步re-entrant line的稳定性的充分条件．本文用两种不同的方法得到了其稳定性的充分必要条件,即: 二维随机游动方法和Foster判别准则．同时,我们又用流体模型方法得到了系统稳定的充分条件,大大地简化了Weiss[13]的证明．     

Asymptotic loss of priority scheduling policies in closed re-entrant lines: A computational study

In this paper we present an approximate but efficient analytical method to compute the asymptotic loss of buffer priority scheduling policies in closed re-entrant lines. For simple two-station closed re-entrant lines, this enables the verification of Harrison-Wein conjectures and Jin-Ou-Kumar resuts. For multi-station re-entrant lines, this provides an efficient way of comparing different buffer priority scheduling policies. We also use the method to evaluate the effect of high priority jobs in re-entrant lines.     

Analysis and control of a scalar conservation law modeling a highly re-entrant manufacturing system

In this paper, we study a scalar conservation law that models a highly re-entrant manufacturing system as encountered in semi-conductor production. As a generalization of Coron et al. (2010) [14], the velocity function possesses both the local and nonlocal character. We prove the existence and uniqueness of the weak solution to the Cauchy problem with initial and boundary data in L^∞. We also obtain the stability (continuous dependence) of both the solution and the out-flux with respect to the initial and boundary data. Finally, we prove the existence of an optimal control that minimizes, in the Lp-sense with 1?p?∞, the difference between the actual out-flux and a forecast demand over a fixed time period.     

Analysis of a simple Markovian re-entrant line with infinite supply of work under the LBFS policy

We consider a two machine 3 step re-entrant line, with an infinite supply of work. The service discipline is last buffer first served. Processing times are independent exponentially distributed. We analyze this system, obtaining steady state behavior and sample path properties. AMS Subject Classifications 60K25 · 90B22 I. Adan and G. Weiss: Research supported in part by Network of Excellence Euro-NGI. G. Weiss: Research supported in part by Israel Science Foundation Grant 249/02.     

重入排序问题综述

重入排序问题打破传统假设：工件在加工过程中不止一次地访问某台机器,是一种新型的排序问题. 重入的特点源于半导体生产, 并广泛存在于其他领域. 对重入排序问题已有文献中的成果进行梳理和分析,按问题所处机器环境的不同, 对内容和方法进行分类介绍和总结：包括单机问题、流水作业问题、混合流水作业问题及其他机器环境下的重入排序问题. 最后展望未来的趋势和研究方向.     

Buckling Analysis of Re-Entrant Honeycomb Structures Under General Macroscopic Stress States北大核心CSCD

Based on the negative Poisson’s ratio effect of the re-entrant honeycomb, the finite element simulation of its buckling mechanical properties was carried out, and 2 buckling modes other than those of the traditional hexagonal honeycomb structures were obtained. The beam-column theory was applied to analyze the buckling strength and mechanism of the 2 buckling modes, where the equilibrium equations including the beam end bending moments and rotation angles were established. The stability equation was built through application of the buckling critical condition, and then the analytical expression of the buckling strength was obtained. The re-entrant honeycomb specimen was printed with the additive manufacturing technology, and its buckling performance was verified by experiments. The results show that, the buckling modes vary significantly under different biaxial loading conditions; the re-entrant honeycomb would buckle under biaxial tension due to the auxetic effect, being quite different from the traditional honeycomb structure; the typical buckling bifurcation phenomenon emerges in the analysis of the buckling failure surfaces under biaxial stress states. This research provides a significant guide for the study on the failure of re-entrant honeycomb structures due to instability, and the active application of this instability to achieve special mechanical properties. © 2023 Editorial Office of Applied Mathematics and Mechanics. All rights reserved.     

Tutte uniqueness of line graphs

We prove that if a graph H has the same Tutte polynomial as the line graph of a d-regular, d-edge-connected graph, then H is the line graph of a d-regular graph. Using this result, we prove that the line graph of a regular complete t-partite graph is uniquely determined by its Tutte polynomial. We prove the same result for the line graph of any complete bipartite graph.     

Diffusion approximations for re-entrant lines with a first-buffer-first-served priority discipline

The diffusion approximation is proved for a class of queueing networks, known as re-entrant lines, under a first-buffer-first-served (FBFS) service discipline. The diffusion limit for the workload process is a semi-martingale reflecting Brownian motion on a nonnegative orthant. This approximation has recently been used by Dai, Yeh and Zhou [21] in estimating the performance measures of the re-entrant lines with a FBFS discipline.Supported in part by a grant from NSERC (Canada).Supported in part by a grant from NSERC (Canada); the research was done while the author was visiting the Faculty of Commerce and Business Administration, UBC, Canada.     

On guided waves in 3-D photonic crystals

The propagation of guided waves in 3-D photonic crystals is studied. In this paper, we suppose that the spectrum of reference medium (a perfectly 3-D photonic crystal) has band gaps. If a line defect is introduced along one of the lattice vectors, we prove that spectrum can be created inside the gaps of the reference spectrum if the line defect is sufficiently strong. Furthermore, we also prove that the generalized eigenfunctions corresponding to the generalized eigenvalues created by line defect are exponentially decaying away from the line defect.     

Minimizing makespan on a two-machine re-entrant flowshop

This paper focuses on a two-machine re-entrant flowshop scheduling problem with the objective of minimizing makespan. In the re-entrant flowshop considered here, all jobs must be processed twice on each machine, that is, each job should be processed on machine 1, machine 2 and then machine 1 and machine 2. We develop dominance properties, lower bounds and heuristic algorithms for the problem, and use these to develop a branch and bound algorithm. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 200 jobs in a reasonable amount of CPU time.     

A constructive Schwarz reflection principle

We prove a constructive version of the Schwarz reflection principle. Our proof techniques are in line with Bishop's development of constructive analysis. The principle we prove enables us to reflect analytic functions in the real line, given that the imaginary part of the function converges to zero near the real line in a uniform fashion. This form of convergence to zero is classically equivalent to pointwise convergence, but may be a stronger condition from the constructivist point of view.

     

Near optimal control of queueing networks over a finite time horizon

We propose a method for the control of multi-class queueing networks over a finite time horizon. We approximate the multi-class queueing network by a fluid network and formulate a fluid optimization problem which we solve as a separated continuous linear program. The optimal fluid solution partitions the time horizon to intervals in which constant fluid flow rates are maintained. We then use a policy by which the queueing network tracks the fluid solution. To that end we model the deviations between the queuing and the fluid network in each of the intervals by a multi-class queueing network with some infinite virtual queues. We then keep these deviations stable by an adaptation of a maximum pressure policy. We show that this method is asymptotically optimal when the number of items that is processed and the processing speed increase. We illustrate these results through a simple example of a three stage re-entrant line. Research supported in part by Israel Science Foundation Grant 249/02 and 454/05 and by European Network of Excellence Euro-NGI.     

A topological splitting theorem for sub-Riemannian manifolds

We prove an analogue of the Cheeger–Gromoll splitting theorem for sub-Riemannian manifolds with the measure contraction property instead of the nonnegativity of the Ricci curvature. If such a sub-Riemannian manifold contains a straight line, then the manifold splits diffeomorphically, where the splitting is not necessarily isometric. We prove that such a sub-Riemannian manifold containing a straight line cannot split isometrically under some typical condition in sub-Riemannian geometry. Heisenberg groups are such examples.     

Minimizing total tardiness on a two-machine re-entrant flowshop

We present a branch and bound algorithm for a two-machine re-entrant flowshop scheduling problem with the objective of minimizing total tardiness. In the re-entrant flowshop considered here, all jobs must be processed twice on each machine, that is, each job should be processed on machine 1, machine 2 and then machine 1 and machine 2. By regarding a job as a pair of sub-jobs, each of which represents a pass through the two machines, we develop dominance properties, a lower bound and heuristic algorithms for the problem, and use these to develop a branch and bound algorithm. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems and results are reported. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 20 sub-jobs in a reasonable amount of CPU time, and the average percentage gap of the heuristic solutions is about 13%.     

Stability of multi-class queueing networks with infinite virtual queues

We generalize the standard multi-class queueing network model by allowing both standard queues and infinite virtual queues which have an infinite supply of work. We pose the general problem of finding policies which allow some of the nodes of the network to work with full utilization, and yet keep all the standard queues in the system stable. Toward this end we show that re-entrant lines, systems of two re-entrant lines through two service stations, and rings of service stations can be stabilized with priority policies under certain parameter restrictions. The analysis throughout the paper depends on model and policy and illustrates the difficulty in solving the general problem.