随机需求下考虑半成品库存的多周期生产决策优化

为了更好地应对需求的不确定性,在需求实现之前,企业既可以生产成品直接满足需求,亦可生产部分半成品,在观察到实际需求之后短时间内迅速完成剩余生产环节以满足需求。未加工的半成品和未售出的成品可用于满足后续周期的需求。作为一种提高生产灵活性的手段,分阶段生产的方式会产生更高的成本。企业需要在成本和灵活性之间作出权衡,优化生产决策。模型通过动态规划的方法,研究需求不确定情况下考虑半成品库存的多周期生产决策问题,通过分析目标函数以及最优值函数的结构性质,推导出最优的多周期生产策略为修正的目标库存策略,并且分析了不同参数对最优策略的影响。     

Linear programming for the 0–1 quadratic knapsack problem

In this paper we consider the quadratic knapsack problem which consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We propose a new method for computing an upper bound. This method is based on the solution of a continuous linear program constructed by adding to a classical linearization of the problem some constraints rebundant in 0–1 variables but nonredundant in continuous variables. The obtained upper bound is better than the bounds given by other known methods. We also propose an algorithm for computing a good feasible solution. This algorithm is an elaboration of the heuristic methods proposed by Chaillou, Hansen and Mahieu and by Gallo, Hammer and Simeone. The relative error between this feasible solution and the optimum solution is generally less than 1%. We show how these upper and lower bounds can be efficiently used to determine the values of some variables at the optimum. Finally we propose a branch-and-bound algorithm for solving the quadratic knapsack problem and report extensive computational tests.     

Mathematical programming models for some smallest-world problems

Given a weighted graph G, in the minimum-cost-edge-selection problem (MCES), a minimum weighted set of edges is chosen subject to an upper bound on the diameter of graph G. Similarly, in the minimum-diameter-edge-selection problem (MDES), a set of edges is chosen to minimize the diameter subject to an upper bound on their total weight. These problems are shown to be equivalent and proven to be NP-complete. MCES is then formulated as a 0–1 integer programming problem. The problems MCES and MDES provide models for determining smallest-world networks and for measuring the “small-worldness” of graphs.     

A new upper bound for the 0-1 quadratic knapsack problem

The 0-1 quadratic knapsack problem (QKP) consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We present in this paper a new method, based on Lagrangian decomposition, for computing an upper bound of QKP. We report computational experiments which demonstrate the sharpness of the bound (relative error very often less than 1%) for large size instances (up to 500 variables).     

Fair upper bounds for the curvature in univariate convex interpolation

In convex interpolation the curvature of the interpolants should be as small as possible. We attack this problem by treating interpolation subject to bounds on the curvature. In view of the concexity the lower bound is equal to zero while the upper bound is assumed to be piecewise constant. The upper bounds are called fair with respect to a function class if the interpolation problem becomes solvable for all data sets in strictly convex position. We derive fair a priori bounds for classes of quadraticC ¹, cubicC ², and quarticC ³ splines on refined grids.     

Asymptotically optimal production policies in dynamic stochastic jobshops with limited buffers

We consider a production planning problem for a jobshop with unreliable machines producing a number of products. There are upper and lower bounds on intermediate parts and an upper bound on finished parts. The machine capacities are modelled as finite state Markov chains. The objective is to choose the rate of production so as to minimize the total discounted cost of inventory and production. Finding an optimal control policy for this problem is difficult. Instead, we derive an asymptotic approximation by letting the rates of change of the machine states approach infinity. The asymptotic analysis leads to a limiting problem in which the stochastic machine capacities are replaced by their equilibrium mean capacities. The value function for the original problem is shown to converge to the value function of the limiting problem. The convergence rate of the value function together with the error estimate for the constructed asymptotic optimal production policies are established.     

A scheme of approximation solution of problem 1 |r j|L max

The strongly NP-hard scheduling problem of minimizing the maximum lateness on one machine subject to job release dates is under study. We present a general scheme of approximation solution of the problem which is based on searching for a given problem instance another instance, closest to the original in some metric and belonging to a known polynomially solvable class of instances. For a few concrete variants of the scheme (using different polynomially solvable classes of instances) some analytic formulas are found that make it possible, given a problem instance, to compute easily an upper bound on the absolute error of the solution obtained by a chosen scheme.     

The unbounded parallel-batch scheduling with rejection

In this paper, we consider the unbounded parallel-batch scheduling with rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and processed in batches on a machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. Four problems are considered: (1) to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs; (2) to minimize the total completion time of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs; (3) to minimize the total rejection penalty of the rejected jobs subject to an upper bound on the total completion time of the accepted jobs; (4) to find the set of all the Pareto optimal schedules. We provide a polynomial-time algorithm for the first problem. Furthermore, we show that all the other three problems are binary NP-hard and present a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for them.     

Real-time production scheduling of an automated cardline

In this paper, we describe a flow model of an automated-printed circuit card assembly line at the International Business Machines Corporation (IBM) plant at Tucson, Arizona. We use a simulation based on this model as a test bed to discuss the performance of a hierarchical scheduling policy described in [3]. We compare this with other policies for loading parts into a flexible manufacturing system. We demonstrate that the hierarchical strategy is effective in meeting production requirements (both total volume and balance among part types) while limiting average work-in-process (WIP). This is a consequence of the feedback nature of the policy. Hedging (i.e. building up buffer stock) compensates for machine failures, thus resulting in high production percentages. The work-in-process (WIP) is low, as the policy reduces internal queues by respecting the capacity constraints of the system at every instant.     

A note on upper bounds to the robust knapsack problem with discrete scenarios

We consider the knapsack problem in which the objective function is uncertain, and given by a finite set of possible realizations. The resulting robust optimization problem is a max–min problem that follows the pessimistic view of optimizing the worst-case behavior. Several branch-and-bound algorithms have been proposed in the recent literature. In this short note, we show that by using a simple upper bound that is tailored to balance out the drawbacks of the current best approach based on surrogate relaxation, computation times improve by up to an order of magnitude. Additionally, one can make use of any upper bound for the classic knapsack problem as an upper bound for the robust problem.     

A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times

In this paper, we address the three-machine flowshop scheduling problem. Setup times are considered separate from processing times, and the objective is to minimize total completion time. We show that the three-site distributed database scheduling problem can be modeled as a three-machine flowshop scheduling problem. A lower bound is developed and a dominance relation is established. Moreover, an upper bound is developed by using a three-phase hybrid heuristic algorithm. Furthermore, a branch-and-bound algorithm, incorporating the developed lower bound, dominance relation, and the upper bound is presented. Computational analysis on randomly generated problems is conducted to evaluate the lower and upper bounds, the dominance relation, and the branch-and-bound algorithm. The analysis shows the efficiency of the upper bound, and, hence, it can be used for larger size problems as a heuristic algorithm.     

A strengthened Barvinok-Pataki bound on SDP rank

The Barvinok-Pataki bound provides an upper bound on the rank of extreme points of a spectrahedron. This bound depends solely on the number of affine constraints of the problem, i.e., on the algebra of the problem. Specifically, the triangular number of the rank r is upper bounded by the number of affine constraints. We revisit this bound and provide a strengthened upper bound on the rank using the singularity degree of the spectrahedron. Thus we bring in the geometry and stability of the spectrahedron, i.e., increased instability as seen by higher singularity degree, yields a lower, strengthened rank bound.     

Operations planning for a multi-stage kanban system

A multi-stage production line which operates under a just-in-time production philosophy with linear demand is considered here. The first workstation processes the raw materials after receiving them from suppliers, a kanban mechanism between the workstations transports the work-in-process to the succeeding workstation, and after processing them, delivers the finished products to a buyer or a warehouse. The problem is to find optimally the number of raw material orders, kanbans circulated between workstations, finished goods shipments to the buyers, and the batch size for each shipment (lot). A cost function is developed based on the costs incurred due to the raw materials, the work-in-process between workstations, and the finished goods. Optimal number of raw material orders that minimizes the total cost is obtained, which is then used to find the optimal number of kanbans, finished goods shipments, and the batch sizes for shipments. Numerical examples are used to demonstrate the computations of optimal parameters, and to configure the kanban mechanism on a timescale. Several avenues for future research are also indicated.     

The basic cyclic scheduling problem with deadlines

The purpose of this paper is to study the latest schedule existence, calculation and properties of a basic cyclic scheduling problem with deadlines. First it is shown that, in the general case, a latest schedule exists but may be difficult to compute. Then we focus on a special case we call the optimal cyclic production problem. We derive an upper bound for the number of maximal-path values needed to compute the latest starting times and show the K-periodic structure of the latest starting time sequences.     

Optimization with Variable Sets of Constraints and an Application to Truss Design

We discuss the minimization of a continuous function on a subset of Rⁿ subject to a finite set of continuous constraints. At each point, a given set-valued map determines the subset of constraints considered at this point. Such problems arise e.g. in the design of engineering structures.After a brief discussion on the existence of solutions, the numerical treatment of the problem is considered. It is briefly motivated why standard approaches generally fail. A method is proposed approximating the original problem by a standard one depending on a parameter. It is proved that by choosing this parameter large enough, each solution to the approximating problem is a solution to the original one. In many applications, an upper bound for this parameter can be computed, thus yielding the equivalence of the original problem to a standard optimization problem.The proposed method is applied to the problem of optimally designing a loaded truss subject to local buckling conditions. To our knowledge this problem has not been solved before. A numerical example of reasonable size shows the proposed methodology to work well.     

Solving the capacitated lot-sizing problem with backorder consideration

In this research, we formulate and solve a type of the capacitated lot-sizing problem. We present a general model for the lot-sizing problem with backorder options, that can take into consideration various types of production capacities such as regular time, overtime and subcontracting. The objective is to determine lot sizes that will minimize the sum of setup costs, holding cost, backorder cost, regular time production costs, and overtime production costs, subject to resource constraints. Most existing formulations for the problem consider the special case of the problem where a single source of production capacity is considered. However, allowing for the use of alternate capacities such as overtime is quite common in many manufacturing settings. Hence, we provide a formulation that includes consideration of multiple sources of production capacity. We develop a heuristic based on the special structure of fixed charge transportation problem. The performance of our algorithm is evaluated by comparing the heuristic solution value to lower bound value. Extensive computational results are presented.     

A heuristic algorithm for a production planning problem in an assembly system

This paper focuses on a production planning problem in an assembly system operating on a make-to-order basis. Due dates are considered as constraints in the problem, that is, tardiness is not allowed. The objective of the problem is to minimise holding costs for final product inventory as well as work-in-process inventory. A non-linear mathematical model is presented and a heuristic algorithm is developed using a solution property and a network model for defining solutions of the problem. A series of computational tests were done to compare the algorithm with a commercial planning/scheduling software and backward finite-loading methods that employ various priority rules. The results showed that the suggested algorithm outperformed the others.     

Heat Kernel Estimates for Operators with Boundary Conditions

We prove Gaussian upper bounds for kernels associated with non – symmetric, non – autonomous second order parabolic operators of divergence form subject to various boundary conditions. The growth of the kernel in time is determined by theboundary conditions and the geometric properties of the domain. The theory gives a unified treatment for Dirichlet, Neumann and Robin boundary conditions, and the existence of a Gaussian type bound is essentially reduced to verifying some properties of the Hilbert space in the weak formulation of the problem.     

A sequential elimination algorithm for computing bounds on the clique number of a graph

We consider the problem of determining the size of a maximum clique in a graph, also known as the clique number. Given any method that computes an upper bound on the clique number of a graph, we present a sequential elimination algorithm which is guaranteed to improve upon that upper bound. Computational experiments on DIMACS instances show that, on average, this algorithm can reduce the gap between the upper bound and the clique number by about 60%. We also show how to use this sequential elimination algorithm to improve the computation of lower bounds on the clique number of a graph.     

Level sets for the stationary solutions of the Ginzburg-Landau equation

We establish an upper bound of the measure of any level set of a stationary solution of theGinzburg-Landau equation subject to periodic boundary conditions. The obtained bound depends polynomially on the parameter . Received October 17, 1996 / Accepted November 7, 1996