A genetic algorithm for integrating lot-sizing and sequencing in scheduling a capacitated flow line

In this paper we present a genetic algorithm for solving an important but difficult scheduling problem: that of integrating the lot-sizing and sequencing decisions in scheduling a flow line involving sequence dependent setup times, capacity constraints, limited buffer capacity between machines, and due dates. The problem is based on a real world manufacturing facility that is also described. Novel crossover and mutation operators are presented for both the lot-sizing and sequencing parts of the scheduling problem and the performance of the genetic algorithm is compared to a heuristic approach of integration previously shown to have been effective.     

Multi-product valid inequalities for the discrete lot-sizing and scheduling problem

We consider a problem arising in the context of industrial production planning, namely the multi-product discrete lot-sizing and scheduling problem with sequence-dependent changeover costs. We aim at developing an exact solution approach based on a Cut & Branch procedure for this combinatorial optimization problem. To achieve this, we propose a new family of multi-product valid inequalities which corresponds to taking into account the conflicts between different products simultaneously requiring production on the resource. We then present both an exact and a heuristic separation algorithm which form the basis of a cutting-plane generation algorithm. We finally discuss computational results which confirm the practical usefulness of the proposed inequalities at strengthening the MILP formulation and at reducing the overall computation time.     

Capacitated lot sizing and sequence dependent setup scheduling: an iterative approach for integration

We consider here the lot sizing and scheduling problem in single-level manufacturing systems. The shop floor is composed of unrelated parallel machines with sequence dependent setup times. We propose an integer programming model embedding precise capacity information due to scheduling constraints in a classical lot-sizing model. We also propose an iterative approach to generate a production plan taking into account scheduling constraints due to changeover setup times. The procedure executes two decision modules per iteration: a lot-sizing module and a scheduling module. The capacitated lot-sizing problem is solved to optimality considering estimated data and aggregate information, and the scheduling problem is solved by a GRASP heuristic. In the proposed scheme the information flow connecting the two levels is managed in each iteration. We report a set of computational experiments and discuss future work.     

Integrating the lot-sizing and sequencing decisions for scheduling a capacitated flow line

In this paper we consider a general problem of scheduling a single flow line consisting of multiple machines and producing a given set of jobs. The manufacturing environment is characterized by sequence dependent set-up times, limited intermediate buffer space, and capacity constraints. In addition, jobs are assigned with due dates that have to be met. The objectives of the scheduling are: (1) to meet the due dates without violating the capacity constraints, (2) to minimize the makespan, and (3) to minimize the inventory holding costs. While most of the approaches in the literature treat the problem of scheduling in flow lines as two independent sub-problems of lot-sizing and sequencing, our approach integrates the lot-sizing and sequencing heuristics. The integrated approach uses the Silver-Meal heuristic (modified to include lot-splitting) for lot-sizing and an improvement procedure applied to Palmer's heuristic for sequencing, which takes into account the actual sequence dependent set-up times and the limited intermedite buffer capacity. We evaluate the performance of the integrated approach and demonstrate its efficacy for scheduling a real world SMT manufacturing environment.     

多阶段多产品调度问题的链式智能体遗传算法

将遗传算法的编码方式与智能体系统的演化结构相结合,提出一种求解多阶段多产品调度问题的链式智能体遗传算法.算法采用基于订单序列的编码方式,采用一种新的后向指派规则实现编码和可行调度间的一一对应.通过各智能体与其邻域环境的竞争与合作以及自身的自学习操作实现种群的演化过程.对多阶段多产品调度问题的仿真结果表明:链式智能体遗传...     

MRP rescheduling heuristics with capacity extension under deterministic demand

The multi-stage, multi-machine capacitated lot-sizing problem (MSMMCLSP) consists of scheduling the production of one product in a multi-machine production system with a multi-stage structure. Machine capacity is reserved for the production of the end item but can be extended by working overtime (overtime capacity). When a lot size is positive in a specific period, it can be loaded on all machines without exceeding the sum of the regular and overtime capacity limits. In previous research [Rong, C., Takahashi, K., & Morikawa, K. (2005). A new heuristic method for capacitated lot-sizing in multi-stage, multi-machine production systems. Journal of Japan Industrial Management Association, 56(5), in press], we have proposed a rescheduling heuristic to determine a feasible and sufficient solution for the MSMMCLSP with only regular capacity limits, in comparison with Franca et al.’s heuristic method. However, the mechanism of rescheduling in regular time has not optimum (or near optimum) performance for the MSMMCLSP with capacity extension. Preliminary examination revealed that overtime production also has situation-dependent advantages and disadvantages with the combination of various planning parameters. This study, therefore, develops an integrated heuristic that guarantees an optimal solution for general MSMMCLSP by combining the rescheduling mechanism and overtime production. We also evaluate the effectiveness of the proposed heuristics by using computational tests with various planning parameters.     

CLSP问题的周期调度方法及其PSO求解

采用分解思想考虑多阶段CLSP问题,从多阶段生产系统抽象出单阶段生产环节,提出以周期方式对该生产环节进行生产批量调度。在对CLSP周期调度问题进行描述和界定的基础上,建立了相应的数学模型,讨论了周期调度方法中的周期上界以及周期长度与物料批量大小之间的关系等性质,采用基于三层编码的粒子群优化算法进行问题求解。源于冷轧生产实际的计算实例表明周期方法能够大大降低问题的规模且所得设备调整费用比人工方法减少约16%。     

Multi-product sequencing and lot-sizing under uncertainties: A memetic algorithm

The paper deals with a stochastic multi-product sequencing and lot-sizing problem for a line that produces items in lots. Two types of uncertainties are considered: random lead time induced by machine breakdowns and random yield to take into account part rejects. In addition, sequence dependent setup times are also included. This study focuses on maximizing the probability of producing a required quantity of items of each type for a given finite planning horizon. A decomposition approach is used to separate sequencing and lot-sizing algorithms. Previous works have shown that the sequencing sub-problem can be solved efficiently, but the lot-sizing sub-problem remains difficult. In this paper, a memetic algorithm is proposed for this second sub-problem. Computational results show that the algorithms developed can be efficiently used for large scale industrial instances.     

一种启发式算法求解批量计划和排序集成问题

文章针对基于JIT思想建立的一种批量计划和作业排序集成问题,建立整体模型,设计了一种启发式算法采用集成方法求求解。针对问题的特点和遗传算法的特性,各层优化时均采用遗传算法求解,借鉴递阶优化方法的思想,首先从优化作业排序层出发,将其优化结果作为约束来优化批量计划层,然后利用利用批量优化的结果再重新来协调优化作业排序层,进而进一步去求解更好的批量计划。基于这种协调传递的思想,使各层的优化形成一个闭环,直到满足循环终止条件,得到比较理想的结果。最后通过算例试验表明,这种启发式算法与采用整体求解方法相比,具有比较满意的寻优性能和收敛速度。     

Multi-stage production planning on the IBM PC — an application

Job shop scheduling is one of the most intriguing and potentially useful problems in Operations Research. It is also a very difficult problem to solve. In this article, we discuss a hybrid approach we have developed which automates the scheduling functions in a plant materials management department. The system performs multi-stage time phased materials planning calculations, while performing capacity checks and job sequencing. The scheduling algorithm performs a heuristic reduction of the n/m/Smin problem to a set of n/l/Smin problems which are solved optimally. The heuristic reduction and optimization algorithms are described. Design criteria which made implementation possible in a plant setting are also discussed.     

A two-stage heuristic for single machine capacitated lot-sizing and scheduling with sequence-dependent setup costs

This paper considers a single machine capacitated lot-sizing and scheduling problem. The problem is to determine the lot sizes and the sequence of lots while satisfying the demand requirements and the machine capacity in each period of a planning horizon. In particular, we consider sequence-dependent setup costs that depend on the type of the lot just completed and on the lot to be processed. The setup state preservation, i.e., the setup state at the end of a period is carried over to the next period, is also considered. The objective is to minimize the sum of setup and inventory holding costs over the planning horizon. Due to the complexity of the problem, we suggest a two-stage heuristic in which an initial solution is obtained and then it is improved using a backward and forward improvement method that incorporates various priority rules to select the items to be moved. Computational tests were done on randomly generated test instances and the results show that the two-stage heuristic outperforms the best existing algorithm significantly. Also, the heuristics with better priority rule combinations were used to solve case instances and much improvement is reported over the conventional method as well as the best existing algorithm.     

A new approach to solve the multi-product multi-period inventory lot sizing with supplier selection problem

This research work deals with the multi-product multi-period inventory lot sizing with supplier selection problem. Formerly, this kind of problem was formulated and solved using an exhaustive enumeration algorithm and a heuristic algorithm. In this paper, a new algorithm based on a reduce and optimize approach and a new valid inequality is proposed to solve the multi-product multi-period inventory lot sizing with supplier selection problem. Numerical experiments ratify the success of the proposed heuristic algorithm. For the set of 150 benchmark instances, including 75 small-sized instances, 30 medium-sized instances, and 45 large-sized instances, the algorithm always obtained better solutions compared with those previously published. Furthermore, according to the computational results, the developed heuristic algorithm outperforms the CPLEX MIP solver in both solution quality and computational time.     

Combination of genetic algorithm with Lagrange multipliers for lot-size determination in multi-stage production scheduling problems

In this paper a meta-heuristic approach for lot-size determination problems in a complex multi-stage production scheduling problems with production capacity constraint has been developed. This type of problem has multiple products with sequential production processes which are manufactured in different periods to meet customer’s demand. By determining the decision variables, machinery production capacity and customer’s demand, an integer linear program with the objective function of minimization of total costs of set-up, inventory and production is has been provided. In the first step, the original problem is converted to several individual problems using a heuristic approach based on the limited resource Lagrange multiplier. Thus, each individual problem can be solved using one of the easier methods. In the second step, through combining the genetic algorithm with one of the neighborhood search techniques, a new approach has been developed for the individual problems. In the third step, to obtain a better result, resource leveling is performed for the smaller problems using a heuristic algorithm. Using this method, each product’s lot-size is determined through several steps. We have verified our results through several empirical experiments.     

A Lagrangean-based heuristic for multi-plant,multi-item,multi-period capacitated lot-sizing problems with inter-plant transfers

This paper addresses scheduling of lot sizes in a multi-plant, multi-item, multi-period, capacitated environment with inter-plant transfers. A real-world problem in a company manufacturing steel rolled products provided motivation to this research. A Lagrangean-based approach, embedded with a lot shifting–splitting–merging routine, has been used for solving the multi-plant, capacitated lot-sizing problem. A “good” solution procedure developed by Sambasivan (Ph.D. Dissertation, University of Alabama, Tuscaloosa, 1994) has been used for solving the relaxed problem. About 120 randomly generated instances of the problem have been solved and it has been found that Lagrangean-based approach works quite “efficiently” for this problem.     

A genetic algorithm/mathematical programming approach to solve a two-level soft drink production problem

This study applies a genetic algorithm embedded with mathematical programming techniques to solve a synchronized and integrated two-level lot sizing and scheduling problem motivated by a real-world problem that arises in soft drink production. The problem considers a production process compounded by raw material preparation/storage and soft drink bottling. The lot sizing and scheduling decisions should be made simultaneously for raw material preparation/storage in tanks and soft drink bottling in several production lines minimizing inventory, shortage and setup costs. The literature provides mixed-integer programming models for this problem, as well as solution methods based on evolutionary algorithms and relax-and-fix approaches. The method applied by this paper uses a new approach which combines a genetic algorithm (GA) with mathematical programming techniques. The GA deals with sequencing decisions for production lots, so that an exact method can solve a simplified linear programming model, responsible for lot sizing decisions. The computational results show that this evolutionary/mathematical programming approach outperforms the literature methods in terms of production costs and run times when applied to a set of real-world problem instances provided by a soft drink company.     

A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times

This paper examines the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times, time windows, machine eligibility and preference constraints. Such problems are quite common in the semiconductor manufacturing industry. In particular, this paper pays special attention to the chipset production in the semiconductor Assembly and Test Manufacturing (ATM) factory and constructs a Mixed Integer Programming (MIP) model for the problem. The primal problem is decomposed into a lot-sizing subproblem and a set of single-machine scheduling subproblems by Lagrangian decomposition. A Lagrangian-based heuristic algorithm, which incorporates the simulated annealing algorithm aimed at searching for a better solution during the feasibility construction stage, is proposed. Computational experiments show that the proposed hybrid algorithm outperforms other heuristic algorithms and meets the practical requirement for the tested ATM factory.     

Lot-sizing heuristics for continuous time-varying demand and shortages

In this paper we propose two heuristic procedures for the inventory lot-sizing problem with continuous time-varying demands and shortages. The first heuristic is an extension of the Silver-Meal solution method to general continuous demands. The key idea of the second heuristic is to balance the sum of the holding and backorder costs over each replenishment cycle with the ordering cost. In the case of linearly time-varying demand, the two heuristics procedures are evaluated according to three measures of cost performance and two measures of computation efficiency over 10000 test problems. The results revealed that the modified least-cost approach is generally more effective than the generalized Silver-Meal. It generated comparable cost performance in problems with shortages and a superior cost advantage in problems with infinite shortage cost. Moreover, both heuristics are faster than the exact procedure in execution.     

Network model and optimization of reverse logistics by hybrid genetic algorithm

The interest about recovery of used products and materials have been increased. Therefore, reverse logistics network problem (rLNP) will be powerful and get a great potential for winning consumers in a more competitive context in the future.We formulate a mathematical model of remanufacturing system as three-stage logistics network model for minimizing the total of costs to reverse logistics shipping cost and fixed opening cost of the disassembly centers and processing centers. And we consider a multi-stage, multi-product and some attach condition for disassembly centers and processing centers, respectively.For solving this problem, we propose a genetic algorithm (GA) with priority-based encoding method consisting of 1st and 2nd stages combined a new crossover operator called as weight mapping crossover (WMX). A heuristic approach is applied in the 3rd stage to transportation of parts from processing center to manufacturer. Numerical experiments with various scales of rLNP models show the effectiveness and efficiency of our approach by comparing the recent researches.     

Lot-sizing on a single imperfect machine: ILP models and FPTAS extensions

A single-machine multi-product lot-sizing and sequencing problem is studied. In this problem, items of n different products are manufactured in lots. Demands for products as well as per item processing times are known. There are losses of productivity because of non perfect production. There is also a sequence dependent set-up time between lots of different products. Machine yields and product lead times are assumed to be known deterministic functions. The objective is to minimize the cost of the demand dissatisfaction provided that the total processing time does not exceed a given time limit. We propose two integer linear programming (ILP) models for the NP-hard “fraction defective” case of this problem and compare effectiveness of their ILOG CPLEX realizations with a dynamic programming algorithm in a computer experiment. We also show how an earlier developed fully polynomial time approximation scheme (FPTAS) and one of the ILP models can be extended for a more complex case.     

A note on a single-machine lot scheduling problem with indivisible orders

In this paper, a lot scheduling problem on a single machine with indivisible orders is studied. The objective is to minimize the total completion time of all orders. We show that the problem is NP-hard in the strong sense. Then, a binary integer programming approach and four simple heuristics are proposed to solve the problem. The binary integer programming approach with running time limit is considered as one heuristic method. As compared to a lower bound, the average performances of the heuristic method are really good and better than those of the four simple heuristics.