When Is The Economic Lot Scheduling Problem Easy?

The Economic Lot Scheduling Problem, common in industry and the literature as well, is NP-hard and remains unsolved in general. We show 'that the very simple Rotation Cycle scheduling rule produces optimal or nearly optimal schedules in very many realistic situations and we give upper bounds for the maximum percentage deviation of the Rotation Cycle's schedule fro m optimality. An implication for Group Technology is discussed.     

经济批量与运送排产问题中的协调机制研究

针对现有研究采用集中决策的局限,研究了分散决策情形下经济批量与运送排产问题的最优决策。分析表明在无协调机制作用时,分散决策无法实现供应链系统的最优绩效,进一步提出一种利润共享和成本分担协议（PCS）,并证明在PCS协议作用下,采用分散决策可以实现供应链协调,同时供应链利润可以在供需双方任意分配,具有很好的柔性。     

The Application of Marginal Analysis to the Economic Lot Scheduling Problem

Application of marginal analysis to the Economic Lot Scheduling Problem reduces the solution search to a simple systematic calculation and feasibility check. Compared with mathematical programming methods and heuristic approaches advocated previously, marginal analysis results in lower optimum cost solution with shorter optimum basic period lengths. For comparative purposes, data are included which allow evaluation of marginal analysis results with dynamic programming results of previous researchers.     

An Improved Extended Basic Period Procedure for Solving the Economic Lot Scheduling Problem

This paper describes an easily programmable procedure for solving the problem of determining lot sizes for n products to be produced on a single machine. The procedure is based upon the extended basic period approach of Elmagrahby. Feasible solutions are obtained by restricting the number of periods between runs for each product to the powers of 2. The effectiveness of the procedure is demonstrated by solving six problems originally solved by Fujita. Significantly better answers were found for five of the six while in one case the procedure generated a solution that was only slightly inferior.     

Das Economic Lot Scheduling Problem –Überblick und LP-basiertes Verfahren

Zur L?sung des Economic Lot Scheduling Problems (ELSP) finden sich in der Literatur drei Ans?tze mit unterschiedlich einschr?nkenden Annahmen: – Ansatz des gemeinsamen Produktzyklus (Common-Cycle-Approach)     

The Effect of Restricting Cycle Times in the Economic Lot Scheduling Problem

The economic lot scheduling problem (ELSP) involves specifying economic cycle times for each of several products produced by a set of machines. The extensive, usually experimentally based, literature on the ELSP indicates that it may be desirable to restrict the possible choice of cycle times for each product to a small and very structured set of possible cycle times. In this paper we examine the economic impacts of such a restriction and give evidence that is highly supportive of this type of restriction; in particular, the “powers of 2” sets of possible cycle times used in practice appear to be very desirable from an economic viewpoint.     

WRLSP: A Single-Machine, Warehouse Restricted Lot Scheduling Problem

This paper treats a single-machine, multi-product scheduling problem arising from an application in an automobile factory. The problem is to sequence the production lots of N products in a common cycle schedule to minimize the maximum storage space required by the machine's output, given constant production and demand rates, sequence-independent setup times and sharing of the storage space among the products. As the problem is strongly NP-hard, a heuristic and a branch and bound algorithm are developed for solving it. The algorithms are assessed on a set of random test problems similar in size and complexity to the original application.     

A solution procedure for Economic Lot Scheduling Problems even in high utilisation facilities

Economic lot scheduling problem (ELSP) handles the problem of deciding what order quantities to use when different products/items are produced in the same capacity constrained production facility. It has previously been shown, and it is shown in this article, that it is possible to find a feasible solution fulfilling true feasibility conditions. However, if the utilisation of the production facility is high the production often has to start before the inventory reaches zero to avoid future shortages. Such ‘early starts’ creates an extra inventory holding cost that the traditional approximation for the inventory holding cost does not account for. This article presents an iterative solution procedure that computes the true inventory holding cost and minimises the total costs. Contrary to previous solution procedures, this procedure requires that the production is scheduled in detail. The heuristic solution procedure is illustrated by a numerical example, it is programmed in MATLAB and variants of the problem are presented.     

An Extension to the Class of Easy Economic Lot Scheduling Problems

We extend known conditions under which a rotation schedule is optimal in the Economic Lot Scheduling Problem by using a tighter lower bound that explicitly considers machine capacity. We also show how these results can be used when backorders are allowed.     

带准备时间的作业车间分批调度算法

研究了带有准备时间的作业车间分批排序问题,通过模拟计算将3种算法进行了对比分析.结果表明,遗传退火两阶段算法不受等分批限制,产生的各子批大小可以不同,这使得解空间更大,因而得到满意解的可能性大大增加.     

A Heuristic Production Lot Scheduling Model

This article describes a model which seeks to schedule the production of m products over the next n production planning periods in a manner which minimizes total setup, production, and inventory costs while observing all constraints imposed by the capacities of the productive resources. The model formulates this problem as a fixed charge problem, and then uses a modified version of the simplex method to locate optimal or near optimal solutions of this nonlinear programming problem. A discrete optimizing approach is used to estimate the effectiveness of the model.     

A Two-Product Newsboy Problem with Satisficing Objective and Independent Exponential Demands

While all previous research on the newsboy problem considered the single-product case, a recently published paper studied a two-product newsboy problem under the objective of maximizing the probability of achieving a profit target. Numerical solutions to this problem reveal some very intriguing properties, but little analytical results were obtained. This paper presents an analytical solution procedure to the problem for the case of exponentially distributed independent demands. Our analytical structure reveals even more intriguing properties, and confirms that the multiproduct extension of the newsboy problem is a very challenging and fruitful research area.     

Priority Scheduling and Inventory Control in Job Lot Manufacturing Systems

This paper examines the relationship between the problems of priority scheduling and inventory control and describes several priority scheduling rules that use inventory information in making machine scheduling decisions. These rules include: Minimum Slack Time Per Remaining Operation? Critical Ratio, and a modification of the Shortest Processing Time Rule. Simulation experiments evaluate the gain in shop and inventory performance resulting from the inclusion of inventory data in scheduling rules. The results indicate that an increase in the timeliness of inventory information for scheduling purposes may not lead to improved performance.     

Heuristic Algorithms for Multistage Flowshop Scheduling Problem

This paper describes three heuristic algorithms for seeking a quick and near optimal solution to the n-job M-machine flowshop scheduling problem where jobs are processed on all machines in the same order, and the objective is to minimize either the mean flowtime or the maximum flowtime (make-span). The proposed heuristic algorithms are extensions of the heuristic rules of the author and are comparatively more effective in finding the optimal or near optimal solution to the problem. Computational experience pertaining to the effectiveness of proposed heuristic algorithms is discussed, indicating that the solutions obtained by proposed heuristic algorithms are compared to the Campbell-Dudek-Smith algorithm.     

The Economic Lot Sizes in Multistage Production Systems

This article develops a model for a single-product multistage production-inventory system with static deterministic demand, where the product moves between the stages in a serial fashion. In this model, it is assumed that the unfilled demand of the finished product is backlogged. Overproduction (with limitation) is allowed at the different stages so that each stage t may produce ki batches once every ki cycles. The decision variables for each stage i are the number of batches per run k_i the batch size Q_i, and the shortage quantity of the finished product Q_s. These are determined by minimizing the total cost per unit time which includes the inventory holding cost, the shortage cost, and the setup cost. The problem is also considered for the case with storage constraints at the different stages.     

飞机移动生产线作业调度问题的启发式算法

飞机移动生产线作业调度问题是一种具有特殊约束的项目调度问题。综合分析了飞机移动生产线的作业顺序关序、资源约束、空间限制的多重特点,建立了以最小装配完工时间为目标的模型。将问题分为确定作业的优先顺序和选择作业人数的两个阶段进行决策,设计了由不同规则组合成27种启发式方法。通过比较启发式方法在250个测试问题集的表现,确定最有效的解决此问题的方法。     

A Dual-Cost Heuristic For The Capacitated Lot Sizing Problem

This paper examines a mathematical programming method of accounting for capacity costs for the deterministic, multi-item, single operation lot sizing problem. With the capacity constraints of CLSP removed with Lagrangian relaxation, the problem decomposes into a set of uncapacitated single product lot sizing problems which are solved with dynamic programming. The Lagrangian dual costs are updated by subgradient optimization. Feasible solutions (production plans within the capacity limitations) are constructed with a heuristic smoothing procedure. The dual-cost heuristic gave solutions which were better on average than the other algorithms tested (and was faster than some comparable algorithms).     

有模具约束的并行机批量流调度问题研究

大多数调度问题均假设产品以单个或整批的方式进行生产,而实际生产过程中,会把产品分批后再进行生产。但当考虑模具约束时,对如何解决产品分批以及制定合理调度方案的问题,本文以最小化最大完工时间为优化目标,建立了考虑模具约束的并行机批量流调度模型,并提出了一种基于遗传算法和差分算法结合的混合差分遗传算法（DEGA）,实现分批与调度两个问题并行优化。最后通过对算例测试,DEGA算法得到更优的解,证明了该算法的优越性和稳定性。结合实际案例,验证了模型和算法的可行性。     

公交车调度问题的研究

本题为带软时间窗的单线路单车型的公交调度问题,针对其多目标、多变量的动态特点,我们为满足不同的实际需求建立两个多目标规划模型:双车场模型和单车场模型.双车场模型的主要目标是使运客能力与运输需求(实际客运量)达到最优匹配,单车场模型的主要目标是使乘客的平均不方便程度和公交公司的成本达最小,其目的都是为了兼顾乘客与公司双方的利益.两个模型的主体都是采用时间步长法,模拟实际的运营过程,从而得出符合实际要求的调度方案:静态调度和动态调度方案.     

面向柔性作业调度问题的启发性规则改进遗传算法

对柔性作业调度问题,提出了一种启发性规则的改进遗传求解方法,此方法从启发性规则出发产生初始调度解。通过对初始调度解进行比较而产生初始种群。对初始种群通过启发规则的改进遗传算法进行优化计算,对染色体进行交叉、变异、交换和选择操作,应用启发式规则搜索关键工序并提高关键工序的交换、变异操作概率,在变异操作中利用启发式规则对变异过程加以引导,从而得到优化解。将此方法运用于一系列典型柔性调度问题进行了实验求解,并将求解结果与其他的计算方法进行了比较,表明此方法能提高求解效率,适合复杂的柔性作业调度问题求解。