A Genetic Algorithm for the Allocation of Buffer Storage Capacities in a Production Line with Unreliable Machines

In this paper, we consider a flow-line manufacturing system organized as a series of workstations separated by finite buffers. The failure and repair times of machines are supposed to be exponentially distributed. The production rate of each machine is deterministic, and different machines may have different production rates. The buffer allocation problem consists in determining the buffer capacities with respect to a given optimality criterion, which depends on the average production rate of the line, the buffer acquisition and installation cost, and the inventory cost. For this problem we propose a genetic algorithm where the tentative solutions are evaluated with an approximate method based on the Markov-model aggregation approach.     

Properties of Continous Models of Transfer Lines with Unreliable Machines and Finite Buffers

We consider a transfer line consisting of a series of machinesseparated by buffers of finite capacity. The processing of apart on a machine requires a fixed amount of time. In thesesystems, blocking and starvation, which occur as a consequenceof machine failures, are important phenomena. Except for transferlines without buffer storage, no exact models of such systemshave been reported in the literature, even in the case of two-machinelines. Two approximate models have been proposed: the discrete-timemodel and the continuous-flow model. Exact solutions of theemodels have been reported in the case of two-machine Lines,and approximations have been proposed for longer lines. Thepurpose of this paper is to provide properties of the continuous-flowmodel. The main result of the paper is to show that lower andupper bounds on the exact production rate of the transfer linecan be obtained using the continuous flow model. These boundsare obtained by making an appropriate choice of the buffer capacities     

非均匀节拍生产线缓冲库存设计的结构特性

本文考察具有缓冲库存的随机加工时间的非均匀节拍生产线运行特点，通过对非均匀节拍生产线缓冲库存容量设计的两类模型的分析，综合并总结了缓冲库存容量最优设计的一些结构特性．     

Average Cost Optimality for an Unreliable Two-Machine Flowshop with Limited Internal Buffer

We consider a production planning problem in a two-machine flowshop subject to breakdown and repair of machines and subject to nonnegativity and upper bound constraints on work-in-process. The objective is to choose machine production rates over time to minimize the long-run average inventory/backlog and production costs. For sufficiently large upper bound on the work-in-process, the problem is formulated as a stochastic dynamic program. We then establish a verification theorem and a partial characterization of the optimal control policy if it exists.     

Heuristic Solution Methods for Two Location Problems with Unreliable Facilities

In this paper, the p-median and p-centre problems are generalized by considering the possibility that one or more of the facilities may become inactive. The unreliable p-median problem is defined by introducing the probability that a facility becomes inactive. The (p, q)-centre problem is defined when p facilities need to be located but up to q of them may become unavailable at the same time. An heuristic procedure is presented for each problem. A rigorous procedure is discussed for the (p, q)-centre problem. Computational results are presented.     

Capacity Constrained Transit Assignment with Common Lines

This paper proposes the use of absorbing Markov chains to solve the capacity constrained transit network loading problem taking common lines into account. The approach handles congested transit networks, where some passengers will not be able to board because of the absence of sufficient space. The model also handles the common lines problem, where choice of route depends on frequency of arrivals. The mathematical formulation of the problem is presented together with a numerical example. This revised version was published online in July 2006 with corrections to the Cover Date.     

Complexity of Workforce Scheduling in Transfer Lines

Consider a production system that consists of m assembly stations arranged in series. All jobs enter the assembly line at station 1 and proceed with subsequent stations in the same order as in a flow shop. Each job spends a fixed amount of time c in each station, known as the production cycle. This production system is synchronous or paced because jobs move one station forward synchronously, every c time units. To ensure that all required work is performed in precisely c periods, the appropriate number of workers is assumed to be known for every task in each station. Hence, each job is specified by an m-tuple of workforce requirements. We are interested in ``level' workforce schedules where workforce size fluctuations are minimal during the production horizon. In this article we define level workforce scheduling objectives and analyze the complexity status of the associated problems. We find that most of these problems are NP-complete even when m=2.     

考虑顾客使用行为的汽车租赁容量分配策略研究

随着物联网技术的发展, 租赁公司通过智能技术可以实时监测顾客的使用行为, 因此可以根据顾客使用行为设计补贴策略以激励顾客在使用过程中保持良好的行为习惯。本文将租赁价格作为顾客行为的函数, 构建随机动态规划模型, 研究了多产品、多周期下汽车租赁公司的容量分配决策和补贴机制。考虑到所构建模型的状态变量维度较高, 因此提出两种近似算法对模型进行求解, 并通过数值仿真验证了模型的相关性质。在考虑顾客行为可以转变的前提下, 得到相关结论:租赁公司以机会成本作为容量分配决策的重要依据;当所需等级汽车缺货时, 由于低等级汽车的机会成本低于高等级汽车的机会成本, 因此满足升级条件时, 租赁公司总是按照等级顺序进行升级;在合理的补贴策略下, 公司的总收益将会随着补贴的增加而增加。     

Complexity Results for Some Global Optimization Problems

We discuss the complexity of a class of highly structured global optimization problems, namely the maximization of separable functions, with each one-dimensional component convex and nondecreasing, over polytopes defined by a 0-1 constraint matrix with at most two variables involved in each constraint. In particular, we prove some inapproximability and approximability results.     

Complexity Analysis for Certain Convex Programming Problems

We study the complexity of a barrier method for linear-inequality constrained optimization problems where the objective function is only assumed to be analytic and convex. As a special case, we obtain the usual complexity bounds for the linear programming problem and for when the objective function is convex and quadratic.     

Complexity Results for Flow-Shop and Open-Shop Scheduling Problems with Transportation Delays

We consider shop problems with transportation delays where not only the jobs on the machines have to be scheduled, but also transportation of the jobs between the machines has to be taken into account. Jobs consisting of a given number of operations have to be processed on machines in such a way that each machine processes at most one operation at a time and a job is not processed by more than one machine simultaneously. Transportation delays occur if a job changes from one machine to another. The objective is to find a feasible schedule which minimizes some objective function. A survey of known complexity results for flow-shop and open-shop environments is given and some new complexity results are derived.     

Shares Allocation Methods for Generalized Game Problems with Joint Constraints

We consider an extension of a noncooperative game problem where players have joint binding constraints. We suggest a shares allocation approach, which replaces the initial problem with a sequence of Nash equilibrium problems together with an upper level set-valued variational inequality as master problem. This transformation maintains the monotonicity properties of the underlying mappings. We also show that the regularization yields a decomposable penalty method, which removes complex functions in constraints within the custom noncooperative game framework and provides the single-valued master problem with strengthened monotonicity of its cost mapping.     

A Hybrid Bounding Procedure for the Workload Allocation Problem on Parallel Unrelated Machines with Setups

A nonpreemptive single stage manufacturing process with parallel, unrelated machines and multiple job types with setups (PUMS) is considered. We propose a hybrid approximation procedure where a Lagrangean relaxation dual and a Lagrangean decomposition dual are solved one after the other to generate a good lower bound on the optimal makespan value. Computational results are reported.     

On Resource Allocation Problems with Interval-Scale Coefficients

In this paper we discuss the classical problem of the allocation of a single finite resource among many competing activities for the specific case where the coefficients of the objective function form an interval scale. In this case there is no longer a single optimal solution, but rather a set of efficient solutions. We recommend a technique equivalent to parametric objective function analysis to generate the set of efficient solutions to the problem.     

The Complexity of Indefinite Elliptic Problems with Noisy Data

We study the complexity of second-order indefinite elliptic problems −div(au) +bu=f(with homogeneous Dirichlet boundary conditions) over ad-dimensional domain Ω, the error being measured in theH¹(Ω)-norm. The problem elementsfbelong to the unit ball ofW^{r, p}, (Ω), wherep [2, ∞] andr>d/p. Information consists of (possibly adaptive) noisy evaluations off,a, orb(or their derivatives). The absolute error in each noisy evaluation is at most δ. We find that thenth minimal radius for this problem is proportional ton^−r/d+ δ and that a noisy finite element method with quadrature (FEMQ), which uses only function values, and not derivatives, is a minimal error algorithm. This noisy FEMQ can be efficiently implemented using multigrid techniques. Using these results, we find tight bounds on the -complexity (minimal cost of calculating an -approximation) for this problem, said bounds depending on the costc(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation isc(δ) = δ^−s(fors> 0), then the complexity is proportional to (1/)^{d/r + s}.     

The Complexity of Definite Elliptic Problems with Noisy Data

We study the complexity of 2mth order definite elliptic problemsLu=f(with homogeneous Dirichlet boundary conditions) over ad-dimensional domain Ω, error being measured in theH^m(Ω)-norm. The problem elementsfbelong to the unit ball ofW^r,p(Ω), wherep∈ [2, ∞] andr>d/p. Information consists of (possibly adaptive) noisy evaluations offor the coefficients ofL. The absolute error in each noisy evaluation is at most δ. We find that thenth minimal radius for this problem is proportional ton^−r/d+ δ, and that a noisy finite element method with quadrature (FEMQ), which uses only function values, and not derivatives, is a minimal error algorithm. This noisy FEMQ can be efficiently implemented using multigrid techniques. Using these results, we find tight bounds on the ?-complexity (minimal cost of calculating an ?-approximation) for this problem, said bounds depending on the costc(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation isc(δ) = δ^−s(fors> 0), then the complexity is proportional to (1/?)^d/r+s.     

Complexity of Linear Problems with a Fixed Output Basis

We use an information-based complexity approach to study the complexity of approximation of linear operators. We assume that the values of a linear operator may be elements of an infinite dimensional space G. It seems reasonable to look for an approximation as a linear combination of some elements g_i from the space G and compute only the coefficients c_i of this linear combination. We study the case when the elements g_i are fixed and compare it with the case where the g_i can be chosen arbitrarily. We show examples of linear problems where a significant output data compression is possible by the use of a nonlinear algorithm, and this nonlinear algorithm is much better than all linear algorithms. We also provide an example of a linear problem for which one piece of information is enough whereas an optimal (minimal cost) algorithm must use information of much higher cardinality.     

The Complexity of Two-Point Boundary-Value Problems with Analytic Data

Previous work on the complexity of elliptic boundary-value problems Lu = f assumed that class F of problem elements f was the unit ball of a Sobolev space. In this paper, we assume that F consists of analytic functions. To be specific, we consider the ϵ-complexity of a model two-point boundary-value problem −u″ + u = f in I = (−1, 1) with natural boundary conditions u′(−1) = u′(1) = 0, and the class F consists of analytic functions f bounded by 1 on a disk of radius ρ ≥ 1 centered at the origin. We find that if ρ > 1, then the ϵ-complexity is Θ(ln(ϵ⁻¹)) as ϵ → 0, and there is a finite element p-method (in the sense of Babuška) whose cost is optimal to within a constant factor. If ρ = 1, we find that the ϵ-complexity is Θ(ln²(ϵ⁻¹)) as ϵ → 0, and there is a finite element (h, p)-method whose cost is optimal to within a constant factor.     

Worst Case Complexity of Problems with Random Information Noise

We study the worst case complexity of solving problems for which information is partial and contaminated by random noise. It is well known that if information is exact then adaption does not help for solving linear problems, i.e., for approximating linear operators over convex and symmetric sets. On the other hand, randomization can sometimes help significantly. It turns out that for noisy information, adaption may lead to much better approximations than nonadaption, even for linear problems. This holds because, in the presence of noise, adaption is equivalent to randomization. We present sharp bounds on the worst case complexity of problems with random noise in terms of the randomized complexity with exact information. The results obtained are applied to thed-variate integration andL_∞-approximation of functions belonging to Hölder and Sobolev classes. Information is given by function evaluations with Gaussian noise of variance σ². For exact information, the two problems are intractable since the complexity is proportional to (1/ε)^qwhereqgrows linearly withd. For noisy information the situation is different. For integration, the ε-complexity is of order σ²/ε²as ε goes to zero. Hence the curse of dimensionality is broken due to random noise. for approximation, the complexity is of order σ²(1/ε)^q+2ln(1/ε), and the problem is intractable also with random noise.     

可加号的门诊预约能力分配问题

预约服务可以有效优化医院门诊就诊流程,针对我国患者预约意识不强和预约患者爽约率高的特点,本文研究患者需求量较高时可以增加号源的条件下,考虑加号和拒绝患者成本,以门诊收益期望最大为目标,匹配预约患者和现场挂号患者需求量的能力分配问题。证明了门诊收益期望函数的单峰性,给出了最优解满足的条件。通过大量数值实验分析不同参数对门诊能力分配方案的影响,结果表明两类患者需求量对能力分配方案有较大影响,可加号情况下能力分配方案对患者爽约更敏感。