Heuristic Procedures for the Single Operation, Multi-Item Loading Problem

This paper considers the planning of individual machine groups or work centers producing many different products such as components, subassemblies or assemblies. The deterministic multi-item lot size problem with limited capacity has attracted much attention during the past two decades but no efficient optimization techniques are available up to now. We therefore suggest an efficient heuristic which is an extension of the Eisenhut heuristic. The resulting production programs always adhere to the characteristics of the dominant schedules. Special attention is given to the characterization of these dominant schedules.     

Column Generation Based Heuristic Algorithm for Multi-Item Scheduling

The column generation algorithm for the multi-item lot-size scheduling problem under resource constraints is examined and improved upon by augmenting simpler heuristic routines in place of the time-consuming Wagner-Whitin dynamic programming routine. The heuristic algorithms thus developed are tested by controlling problem size, setup time, demand variability, and capacity change costs in test problems. The empirical results indicate that the proposed heuristic algorithms reduce CPU time as well as the number of iterations with only a slight loss in optimality.     

Multi-Item Inventory Management with Monetary Objective Function

This paper summarizes an actual multi-item periodic-review inventory control study where the “order-up-to-S” policy is employed. The objective function is expressed in monetary terms and is optimized subject to a budgetary limit on the maximum amount of money that can be tied up in inventories. The optimal solution is obtained by employing the generalized Lagrange multipliers method. Findings indicate that it is possible to decrease by at least 37.5% the amount of money currently invested in inventories while maintaining an 85-90% service level to customers. In this study a considerable amount of effort is also spent on the estimation of cost parameters, especially the shortage cost.     

A Heuristic Algorithm for the Multi-Item Lot-Sizing Problem with Capacity Constraints

A heuristic algorithm is presented for solving the scheduling of several items in parallel under capacity constraints with setup and carrying costs. The method is based upon finding a lower bound solution for these costs, securing the feasibility of the solution, and improving the feasible solution so obtained until no further improvements can be made. Comparison of the performance of the proposed heuristic algorithm to that of an exact mixed-integer programming model showed that best solution costs found by the heuristic deviated on an average by 1% from the optimal values, while the computing time was on an average 1/140 of that required by the exact method.     

Lagrangean Relaxation for the Multi-Item Capacitated Lot-Sizing Problem: A Heuristic Implementation

The multi-item capacitated lot-sizing problem consists of determining the magnitude and the timing of some operations of durable results for several items in a finite number of processing periods so as to satisfy a known demand in each period. The subgradient algorithm implemented to minimize the processing costs is based on a Lagrangean relaxation of the capacity constraints imposed on the resources. The method incorporates a primal partitioning scheme—with a network flow subproblem—to obtain good feasible solutions.     

等待时间受限的并行批处理调度问题研究

研究了任务等待时间受限的并行批处理调度问题,建立它的约束规划模型,设计调度任务的“小s大S”规则,该调度规则最重要的参数为临界队长参数和考虑受限时间的紧急时间参数.基于该规则进行模拟实验,用RSM响应面方法进行参数优化,将模拟结果同约束规划模型(CP方法)在CPLEX环境下求得的解进行比较,分析“小s大S”规则的性能和效果.     

Planning Procedures for a Process Industry

The purpose of this article is to illustrate the application of planning procedures for a process industry. The procedures deal with the determination of (i) optimal production rates and workforce requirements based on future sales forecasts, (ii) optimal capacity of a plant based on the above optimal production rates, (iii) optimal times for expanding capacities, and (iv) total required investment outlay. The optimal production rates and workforce requirements are established by a modified version of Holt's et al. linear decision rule. The methodology is illustrated by using cost, production, inventory and investment data supplied by a domestic paint industry     

Optimal Stock Levels and Service Channel Allocations in a Multi-Item Repairable Asset Inventory System

A methodology is described for determining the optimum allocation of repairable item inventories and repair channels to support operating systems consisting of different components. The steady-state probability distribution for die number of failed components is based upon the M/M/s finite population queueing model. Dynamic programming is then used to allocate a fixed budget among the components in order to maximize system availability. At each stage of the dynamic program, optimum trade-offs between stock levels and repair channels are made. An illustrative example is provided.     

考虑库存信息的钢管批量计划优化算法

在考虑库存信息的基础上对钢管批量计划优化问题进行研究,建立了批量计划轧制位置与垛位钢坯多对多关系的批量计划模型,实现对倒垛次数的优化。结合问题特征,设计了一种基于钢坯连续倒垛的两阶段批量计划优化算法：第1阶段,确定当前最优钢坯,进而搜索同垛位上的下层钢坯,匹配最佳的连续轧制钢坯;第2阶段,针对每个轧制位置搜索垛位上的连续轧制钢坯,改进第1阶段的解。通过基于实际生产数据的实验验证,相对经典启发式算法,倒垛次数显著降低,算法和模型是可行且有效的。     

A Heuristic for a Class of Production Planning and Scheduling Problems

This paper describes a solution technique for a general class of problems referred to as aggregate planning and master scheduling problems. The technique is also applicable to multi-item single level capacitated lot sizing problems. The solution technique presented here is a heuristic that is practical for large problems e.g. 9 products and 36 periods. We have tested it for problems with varying number of time periods, number of products, setup costs, holding costs, overtime costs and capacity levels. For those problems that we could solve exactly using a branch and bound algorithm, the solutions produced by the heuristic were all within 1 % of optimality. For problems that we could not solve exactly, we are able to compute a lower bound on the optimal cost. Using the bound we are able to show that our heuristic solutions were within 2.93% of optimality on the average. Except for those problems having very high setup cost or problems with extreme seasonality, the algorithm produced solutions that were within 1 % of optimality on average.     

一种改进的拉普拉斯边缘算法和启发式搜索的道路提取方法

本文针对ADS40影像,试验了改进的拉普拉斯边缘提取算法,获得了包含完整道路信息中间结果,并在此基础上,采用了一种启发式搜索算法,从中间结果中提取出了道路目标。实验证明,该方法提取道路目标的效果较好,能够顺利将主要道路提取出来,达到了预期目的。     

The Output of A Two-Stage System with Unreliable Machines and Limited Storage

Buffer storage allows the decoupling of successive stages of large automatic production systems, which can be important when the machines sometimes fail. System designers should know how much added buffer capacity increases the hourly output of such systems. Previously available methods for predicting this increase treat systems with one machine in each stage. We present a computationally simple heuristic procedure for estimating hourly line output for two stage systems in which each stage may have several machines.     

有限修理能力下的可修件库存优化研究

针对传统可修件库存模型的假设与实际应用不符的问题,提出了一个基于有限修理能力的可修件库存模型,并且假设备件需求服从非稳态分布,分析了各种系统效能指标,并运用相关方法和排队理论进行了求解,最后结合实例进行了算法分析。结果表明,该模型既满足系统成本最低的要求,又实现了总短缺数最少的目标。     

Some Network Flow Models and Heuristics for Multiproduct Production and Inventory Planning

The focus of this paper is on modelling dynamic, deterministic, multiproduct, multistage production planning problems as single commodity network flow problems. The advantages of such formulations are discussed relative to computation of good integer solutions and continuous solutions with additional constraints. Special results for a single period problem are developed.     

The Segregated Storage Problem: Some Properties and an Effective Heuristic

The segregated storage problem is formulated as an integer programming problem. Some special cases are shown to reduce to ordinary assignment problems. A special property of the integer formulation is used to develop a new heuristic procedure which produces near optimal solutions and which can be used as a tight bound in branch and bound procedures. Computational comparisons with heuristics proposed by other authors indicate this method to be superior in solving large problems.     

A Model for Optimizing the Buffer Inventory Storage Size in a Sequential Production System

A model is presented here for optimizing the inventory storage capacity of an in-process buffer stock. The buffer stock is present between two operations, each of which has processing time which is exponentially distributed. The benefit or gain from the system of carrying buffer stock is assumed to be proportional to the rate of flow of production. Two costs are incurred by the buffer inventory: one is proportional to the expected on-hand stock, and the second is a facility cost which is proportional to the maximum buffer stock size.     

考虑产能限制及缺货惩罚的MTO投产计划决策

较低的生产重复性使MTO企业的生产系统具有较大随机性,导致其产品投产量计划制定面临易过量或不足的风险.针对这一问题,考虑MTO企业的生产能力限制及其产品合格率的随机性,综合权衡初始投产过量、初始投产不足需补产及缺货等因素导致的总成本损失,以成本损失最小化为目标,建立了产品投产量计划决策模型来解决最优产品投产量计划的获得问题,并进行了相应的理论分析和数值仿真.研究表明:模型可有效求解出最优的产品计划投产量;考虑产能限制和缺货损失可降低企业的综合成本损失;企业产能对综合成本损失的影响同单位缺货成本与欠产再投产的单位产品成本之比有关;提高合格品率中值对降低综合成本损失至关重要.     

Heuristic procedures for the parallel machine problem with tool switches

We address the problem of scheduling a set of parts with given processing times and tool requirements on m identical parallel machines. The problem is to find an allocation of the machines to the parts, a proper sequence for the parts assigned to each machine, and a corresponding tool-switching plan for each machine so as to minimize the makespan. It is demonstrated that this problem is np-hard , and three heuristic procedures are proposed for solving it. The first procedure is a multi-start local improvement procedure, and various neighborhood structures and search strategies are discussed in this context. The second procedure is a variation of the list-processing routine that is commonly used for the parallel machine problem. Finally, the last procedure is an adaptation of a well-known constructive procedure for the k -travelling salesman problem. Results of a limited computational experiment are also presented in which the makespan obtained via each heuristic procedure is compared with a proposed lower bound and with other reference values.