A Note on an Economic Lot-sizing Problem with Perishable Inventory and Economies of Scale Costs:Approximation Solutions and Worst Case Analysis

This paper presents an economic lot-sizing problem with perishable inventory and general economies of scale cost functions. For the case with backlogging allowed, a mathematical model is formulated, and several properties of the optimal solutions are explored. With the help of these optimality properties, a polynomial time approximation algorithm is developed by a new method. The new method adopts a shift technique to obtain a feasible solution of subproblem and takes the optimal solution of the subproblem as an approximation solution of our problem. The worst case performance for the approximation algorithm is proven to be （4√2 ＋ 5）/7. Finally, an instance illustrates that the bound is tight.

粒子群算法在Lot-sizing问题中的应用

针对无能力限制的Lot-sizing问题,提出一种改进的离散粒子群优化算法.设计粒子编码为生产设备的调整状态,通过有效的解码程序将粒子解释为生产计划.区别于传统的粒子群算法,算法采用单切点交叉算子来提高算法的局部求精能力,并引入变异算子和速度扰动策略保持种群的多样性,使算法在局部求精和空间探索间取得了较好的平衡.在随机生成的90组测试实例中对算法性能进行仿真实验,结果表明该算法具有良好的性能.

Evolutionary Algorithms for Solving Unconstrained Multilevel Lot-Sizing Problem with Series Structure

This paper presents a comparative study of evolutionary algorithms which are considered to be effective in solving the multilevel lot-sizing problem in material requirement planning(MRP)systems.Three evolutionary algorithms(simulated annealing(SA),particle swarm optimization(PSO)and genetic algorithm(GA))are provided.For evaluating the performances of algorithms,the distribution of total cost(objective function)and the average computational time are compared.As a result,both GA and PSO have better cost performances with lower average total costs and smaller standard deviations.When the scale of the multilevel lot-sizing problem becomes larger,PSO is of a shorter computational time.

Two-level uncapacitated lot-sizing problem considering the financing cost of working capital requirement

During financial crisis,companies constantly need free cash flows to efficiently react to any uncertainty,thus ensuring solvency.Working capital requirement(WCR)has been recognized as a key factor for releasing tied up cash in companies.However,in literatures related to lot-sizing problem,WCR has only been studied in the single-level supply chain context.In this paper,we initially adopt WCR model for a multi-level case.A two-level(supplier–customer)model is established on the basis of the classic multi-level lot-sizing model integrated with WCR financing cost.To tackle this problem,we propose sequential and centralized approaches to solve the two-level case with a serial chain structure.The ZIO(Zero Inventory Ordering)property is further confirmed valid in both cases.This property allows us to establish a dynamic programming-based algorithm,which solves the problem in O(T).Finally,numerical tests show differences in optimal plans obtained by both approaches and the influence of varying delays in payment on the WCR of both actors.

Modeling and Solving Lot-Splitting Scheduling Problem Based on Process

In flexible job-shop batch scheduling problem, the optimal lot-size of different process is not always the same because of different processing time and set-up time. Even for the same process of the same workpiece, the choice of machine also affects the optimal lot-size. In addition, different choices of lot-size between the constrained processes will impact the manufacture efficiency. Considering that each process has its own appropriate lot-size, we put forward the concept of scheduling with lot-splitting based on process and set up the scheduling model of lot-splitting to critical path process as the core. The model could update the set of batch process and machine selection strategy dynamically to determine processing route and arrange proper lot-size for different processes, to achieve the purpose of optimizing the makespan and reducing the processing batches effectively. The experiment results show that, comparing with lot-splitting scheduling scheme based on workpiece, this model optimizes the makespan and improves the utilization efficiency of the machine. It also greatly decreases the machined batches （42%） and reduces the complexity of shop scheduling production management.