Resource-requirements planning in flexible manufacturing systems

In this paper, we address the problem of planning the requirements of some of the important resources in flexible manufacturing systems. Specifically, we model the problem of estimating the required numbers and types of machines and tools in the context of a cellular layout. A two-stage procedure is developed which first forms the part families, using the complete-linkage clustering method based on a new similarity index defined in terms of the tooling requirements, and then subsequently estimates the resource requirements to manufacture the part families using an integer programming model. Several variations of the model are discussed and a numerical example is given.     

A parallel multiple Markov chain simulated annealing for multi-period manufacturing cell formation problems

Simulated annealing (SA) is a general purpose optimization technique capable of finding optimal or near optimal solutions in various applications. The major disadvantage of this technique is its slow convergence making it not suitable for solving many complex optimization problems. This limitation may be alleviated by parallel computing using a multiprocessor computer or a cluster of workstations. In this paper, we present an integer programming model for solving a multi-period cell formation problem in cellular manufacturing system. In order to solve the mathematical model efficiently, we developed a multiple Markov chain simulated annealing algorithm which allows multiple search directions to be traced simultaneously. Our computational results on a single processor machine showed that multiple Markov chain SA is much more efficient than a conventional single Markov chain SA. The parallel implementation of the multiple Markov chain SA further improves its computational efficiency in terms of solution quality and execution time.     

Loading problems with tool management in flexible manufacturing systems: A few integer programming models

In automated production systems like flexible manufacturing systems (FMSs), an important issue is to find an adequate workload for each machine for each time period. Many integer linear programming (ILP) models have been proposed to solve the FMS loading problems, but not all of them take tools into account. Those that do not consider tooling are quite unrealistic, especially when setup times are important with respect to processing times. When tool loading has to be handled by the model, the load assignment may have to be changed completely.In this article we consider FMSs with a tool management of the following type: the system works in time periods whose durations are fixed or not; and tools are loaded on the machines at the beginning of each time period and stay there for the whole time period. Tool changes may occur only at the end of each time period when the system is stopped.We present some integer programming models for handling these situations with several types of objectives. Emphasis is laid on the ILP formulations. Computational complexities are discussed.     

产品回收模型研究

讨论了废旧产品回收的各种方案和回收过程，提出了产品回收的混合整数规划模型，模型的目标是最大化产品回收过程的净利润。在模型中考虑了产品回收处、加工工厂、回收方案的选择。该模型具有很强的通用性。     

基于面向负荷的生产控制的紧急订单插单问题

面向负荷的生产控制及与其相应的交货期设置方法的订货生产系统中,存在紧急订单的插单问题。针对此问题提出了一种重排插单方法。建立了订单重排问题的混合整数规划模型,并采用一种基于动态规划思想的启发式求解方法进行求解。通过仿真实验比较了在含有面向负荷的生产控制和基于面向负荷生产控制的交货期设置方法的生产系统中,重排插单、退单插单和顺延插单三种插单方法的表现。结果表明,重排插单方法优于另外两种插单方法,证明了重排插单方法的有效性。     

Storage location assignment and order picking optimization in the automotive industry

The objective of this study is to design storage assignment and order picking system using a developed mathematical model and stochastic evolutionary optimization approach in the automotive industry. It is performed in two stages. At the first stage, storage location assignment problem is solved with a class-based storage policy with the aim of minimizing warehouse transmissions by using integer programming. At the second stage, batching and routing problems are considered together to minimize travel cost in warehouse operations. A warehouse in the automotive industry is analyzed, and an optimum solution is obtained from an integer programming model. Due to the computational time required for solving the integer programming problem, a faster genetic algorithm is also developed to form optimal batches and optimal routes for the order picker. The main advantage of the algorithm is the quick response to production orders in real-time applications. The solutions showed that the proposed approach based on genetic algorithms can be applied and integrated to any kind of warehouse layout in automotive industry.     

Integer programming approach to process planning

In this paper an integer programming approach to the process planning problem is presented. Although the presented approach can be applied to any type of manufacturing system, some implications of the flexible manufacturing environment on process planning models are discussed. The relationship between the process planning models and the FMS software environment is shown. Algorithms for solving the developed models as well as computational results are discussed.     

A Simple Branch-and-Bound Algorithm for the k-Cut Problem for Applications with k Target Vertices,e.g. VLSI Design

The problems studied here belong to a class called graph partition. They are combinatorial problems which consist of finding a partition of vertices into components in order to optimise a given measure. A variety of applications have been suggested, such as communication cost minimisation in parallel computing systems, clustering problems, VLSI design, and net-work reliability. A 0–1 integer programming is proposed first to define and solve the k-cut problem. Then, an efficient branch-and-bound algorithm is developed to solve this problem. As evidence of the utility of the proposed approach, the extensive computational results on random test problems are presented. In computational experiments on problems with up to 37 vertices, the proposed branch-and-bound algorithm is more efficient when compared to two branch-and-bound algorithms that are the same but without some bounds and dominance rules, and the proposed 0–1 integer programming model. The results show that both the lower and upper bounds are very tight, and the branch-and-bound algorithm performs very well.     

Component Grouping for Automatic Printed Circuit Board Assembly

This paper addresses a component grouping problem in an automatic printed circuit board (PCB) assembly line with several non-identical placement machines. After the problem is defined, an integer linear programming model is formulated with the objective of minimising the cycle time of the assembly line. The integer linear programming model can be solved by the general branch-and-bound (B&B) algorithm; however, it is not efficient. So, the integer linear programming model is relaxed as a linear programming formulation because a near-optimal solution is acceptable in the real situation. A new algorithm is developed for the dual of the linear programming model. To demonstrate the efficiency of this algorithm, an example is presented and compared with its integer solution from a commercial package, CPLEX.     

A two-phase linear programming methodology for fuzzy multi-objective mixed-model assembly line problem

We develop a fuzzy multi-objective linear programming (FMOLP) model for solving multi-objective mixed-model assembly line problem. In practice, vagueness and imprecision of the goals in this problem make the fuzzy decision-making complicated. The proposed model considers minimizing total utility work, total production rate variation, and total setup cost, using a two-phase linear programming approach. In the first phase, the problem is solved using a max–min approach. The max–min solution not being efficient, in general, we propose a new model in the second phase to maximize a composite satisfaction degree at least as good as the degrees obtained by phase one. To show the effectiveness of the proposed approach, a numerical example is solved and the results are compared with the ones obtained by the fuzzy mixed integer goal programming and weighted additive methods. The computational results show that the proposed FMOLP model achieves lower objective functions as well as higher satisfaction degrees.     

面向订单制造的可重构制造系统中虚拟制造单元构建技术

为适应单件、小批、个性化和市场需求动态多变的特点.研究了多种不同交货期生产订单并存时的可重构制造系统中虚拟制造单元构建问题.构造了以连续加工产品间相似系数之和最大、工作加班时间最少、单元的封闭性最好(工件跨单元搬运次数最少)、制造系统重构成本最小及设备生产负荷均衡为目标的非线性多目标0-1整数规划模型.采用两阶段的求解策略进行求解.在第一阶段采用启发式方法对非瓶颈设备和工艺进行预处理,以缩小问题解的搜索空间;第二阶段采用一种基于网格计算的分布式平行协同多目标粒子群算法,随机搜索Pareto优化解集.最后,利用globus 4.0 工具箱搭建计算网格和Java语言实现了算法.从生产实际出发给出了算例,证明结果可行,从而验证了算法的有效性.     

A hybrid scatter search for the partial job shop scheduling problem

This paper presents a special case of the general shop called partial job shop problem. The partial job shop is a more realistic generalization of the mixed shop problem. The problem is formulated as a mixed integer programming model. A scatter search algorithm combined with tabu search and path relinking is used to tackle this problem with makespan criterion. The computational experiments are performed on some problem instances. The results are compared with a lower bound and the effectiveness of the algorithm is shown.     

A Generic Model to Solve Tactical Planning Problems in Flexible Manufacturing Systems

This paper is an attempt to develop a generic modeling framework that addresses tactical planning problems of flexible manufacturing systems in a coherent manner. We propose a generic 0-1 mixed integer programming formulation, that integrates batching, loading, and routing problems with their critical aspects related to a system's performance. For this purpose, a thorough analysis is made to determine and relate system components, their attributes, and alternatives together with performance measures specific to tactical planning. This provided the justification to support our argument about generality of the model. A linear programming formulation is provided to approximate the mixed integer formulation proposed so as to overcome the problem's combinatorial complexity. The potential capability of the linear approximation proposed also is demonstrated via a small set of test problems.     

A dynamic multi-commodity inventory and facility location problem in steel supply chain network design

Logistics network design is a major strategic issue due to its impact on the efficiency and responsiveness of the supply chain. This paper focuses on strategic and tactical design of steel supply chain (SSC) networks. Ever-increasing demand for steel products enforces the steel producers to expand their production and storage capacities. The main purpose of the paper includes preparing a countrywide production, inventory, distribution, and capacity expansion plan to design an SSC network. The SSC networks consist of iron ore mines as suppliers, raw steel producer companies as producers, and downstream steel companies as customers. Demand is assumed stochastic with normal distribution and known at the beginning of planning horizon. To achieve the service level of interest, a potential production capacity along with two kinds of safety stocks including emergency and shared safety stocks are suggested by the authors. A mixed integer nonlinear programming (MINLP) model and a mixed integer linear programming (MILP) model are presented to design dynamic multi-commodity SSC networks. To evaluate the performance of the MILP model, a real case of SSC network design is solved. Furthermore, solving two proposed models by using a commercial solver for a set of numerical test cases shows that the MILP model outperforms MINLP in medium- and large-scale problems in terms of computational time. Finally, the complexity of the linear model is investigated by relaxing some major assumptions.     

自组织制造网格及其任务调度算法

通过分析制造系统自组织的特征，以及网格技术在制造业应用的理论基础和系统框架，提出了自组织制造网格的概念，指出资源动态管理和调度是自组织制造网格中建立虚拟组织、实现资源共享和协同工作的瓶颈点，提出基于T，Q，C，S的多层次、多目标整数规划调度算法。同时，结合自组织制造网格的应用实例和一个具体的加工任务，验证了自组织制造网格理论的合理性和调度算法的可行性。     

A simultaneous planning of production and scheduling operations in flexible flow shops: case study of tile industry

The aim of this paper is to study a simultaneous lot-sizing and scheduling in multi-product, multi-period flexible flow shop environments. A new mixed integer programming (MIP) model is proposed to formulate the problem. The objective function includes the total cost of production, inventory, and external supply. In this study, in case of not meeting the demand of customers, this demand should be met by foreign suppliers in higher price. Due to the high computational complexity of the studied problem, a rolling horizon heuristic (RHH) and particle swarm optimization algorithm (PSO) are implemented to solve the problem. These algorithms find a feasible and near-optimal from production planning and scheduling. Additionally, Taguchi method is conducted to calibrate the parameters of the PSO algorithm and select the optimal levels of the influential factors. The computational results show that the algorithms are capable of achieving results with good quality in a reasonable time and PSO has better objective values in comparison with RHH. Also, the real case study for tile industry with real features is applied. Sensitivity analysis is used to evaluate the performance of the model.     

基于社会化库存的多回程物流配送问题的拉格朗日松弛算法

社会化库存是同城配送快速发展所呈现出的一种新特征。在社会化库存模式下,顾客可从多个同城商店订购货物,其物流配送服务需要通过配送车辆在商店与顾客间的多次往返而实现,这是一类特殊的多回程混合取送物流配送问题。针对该问题,建立了混合整数规划模型及改进的拉格朗日松弛算法;考虑到传统拉格朗日松弛算法存在无法有效提供上界的缺陷,引入了基于次短路的可行解生成思想,实现了问题上界的有效求解。仿真算例表明,所提算法能够取得优于CPLEX求解器的计算效率。     

Ant colony optimization algorithm for stochastic project crashing problem in PERT networks using MC simulation

This paper describes a new approach based on ant colony optimization (ACO) metaheuristic and Monte Carlo (MC) simulation technique, for project crashing problem (PCP) under uncertainties. To our knowledge, this is the first application of ACO technique for the stochastic project crashing problem (SPCP), in the published literature. A confidence-level-based approach has been proposed for SPCP in program evaluation and review technique (PERT) type networks, where activities are subjected to discrete cost functions and assumed to be exponentially distributed. The objective of the proposed model is to optimally improve the project completion probability in a prespecified due date based on a predefined probability. In order to solve the constructed model, we apply the ACO algorithm and path criticality index, together. The proposed approach applies the path criticality concept in order to select the most critical path by using MC simulation technique. Then, the developed ACO is used to solve a nonlinear integer mathematical programming for selected path. In order to demonstrate the model effectiveness, a large scale illustrative example has been presented and several computational experiments are conducted to determine the appropriate levels of ACO parameters, which lead to the accurate results with reasonable computational time. Finally, a comparative study has been conducted to validate the ACO approach, using several randomly generated problems.     

Solving reverse logistics vehicle routing problems with time windows

A vehicle routing problem with simultaneous pick-up and delivery in closed-loop logistics network optimization is studied in this paper. Since, in practice, material pick-up and delivery are only allowed to take place on certain time periods, we consider the reverse logistics vehicle routing problem with time windows. A mixed integer programming model is proposed to formulate the considered problem. A heuristic solution approach for solving the model is developed due to the NP-hard nature of solving the model. The heuristic solution is then used as an initial solution of a simulated annealing procedure for improved solutions. The proposed heuristic method and the simulated annealing procedure yield very promising solutions in much less computational time when compared with optimal solutions generated by exact solution procedures. Numerical examples are presented to illustrate the developed model and solution methods.     

A genetic algorithm for solving a multi-floor layout design model of a cellular manufacturing system with alternative process routings and flexible configuration

This paper presents a novel integer linear programming model for designing multi-floor layout of cellular manufacturing systems (CMS). Three major and interrelated decisions are involved in the design of a CMS; namely cell formation (CF), group layout (GL), and group scheduling (GS). A novel aspect of this model is concurrently making the CF and GL decisions to achieve an optimal design solution in a multi-floor factory. Other compromising aspects are: multi-floor layout to form cells in different floors is considered, multi-rows layout of equal area facilities in each cell is allowed, cells in flexible shapes are configured, and material handling cost based on the distance between the locations assigned to machines are calculated. Such an integrated CMS model with an extensive coverage of important manufacturing features has not been proposed before and this model incorporates several design features including alternative process routings, operation sequence, processing time, production volume of parts, duplicate machines, machine capacity, new machine purchasing, lot splitting, material flow between machines, intra-cell layout, inter-cell layout, multi-floor layout and flexible configuration. The objective is to minimize the total costs of intra-cell, inter-cell, and inter-floor material handling, new machines purchasing and machine processing. Two numerical examples are solved by the Lingo software to verify the performance of the proposed model and illustrate the model features. Sensitive analysis is also implemented on some model parameters. An improved genetic algorithm (GA) is proposed to derive near-optimal solutions for the integrated model because of its NP hardness. It is then tested using several problems with different sizes and settings to verify the computational efficiency of the developed algorithm in comparison to a classic simulated annealing algorithm and the Lingo software. The obtained results show the efficiency of proposed GA in terms of objective function value and computational time.