基于元胞机和改进GA的大型零件柔性作业车间调度算法

针对大型零件柔性作业车间调度问题,采用改进遗传算法优化元胞机局部演化规则,提出了元胞机和改进遗传算法相结合的混合调度算法。依据总加工时间最短、各工位负荷率高、同一工位组各工位负荷平衡率高的优化目标,建立了离散化后单个静态调度单元的遗传算法优化模型,并结合算例具体说明了优化过程。通过文献实例演算验证了混合算法求解大型零件柔性作业车间调度问题的可行性和有效性。     

Hybrid evolutionary algorithm with marriage of genetic algorithm and extremal optimization for production scheduling

This paper presents a hybrid evolutionary algorithm with marriage of genetic algorithm (GA) and extremal optimization (EO) for solving a class of production scheduling problems in manufacturing. The scheduling problem, which is derived from hot rolling production in steel industry, is characterized by two major requirements: (i) selecting a subset of orders from manufacturing orders to be processed; (ii) determining the optimal production sequence under multiple constraints, such as sequence-dependant transition costs, non-execution penalties, earliness/tardiness (E/T) penalties, etc. A combinatorial optimization model is proposed to formulate it mathematically. For its NP-hard complexity, an effective hybrid evolutionary algorithm is developed to solve the scheduling problem through combining the population-based search capacity of GA and the fine-grained local search efficacy of EO. The experimental results with production scale data demonstrate that the proposed hybrid evolutionary algorithm can provide superior performances in scheduling quality and computation efficiency.     

Applying simulated annealing to cellular manufacturing system design

Cell formation and cellular layout design are the two main steps in designing a cellular manufacturing system (CMS). In this paper, we will present an integrated methodology based on a new concept of similarity coefficients and the use of simulated annealing (SA) as an optimization tool. In comparison with the previous works, the proposed methodology takes into account relevant production data, such as alternative process routings and the production volumes of parts. The SA-based optimization tool is parallel in nature and, hence, can reduce the computation time significantly, so it is capable of handling large-scale problems. Finally, the SA-based procedure is compared with a genetic algorithm (GA) based procedure and it will be shown that the SA-based algorithm can be as effective as a GA-based algorithm, but with less computational time and effort.     

A scheduling model for serial jobs on parallel machines with different preventive maintenance (PM)

In factories during production, preventive maintenance (PM) scheduling is an important problem in preventing and predicting the failure of machines, and most other critical tasks. In this paper, we present a new method of PM scheduling in two modes for more precise and better machine maintenance, as pieces must be replaced or be repaired. Because of the importance of this problem, we define multi-objective functions including makespan, PM cost, variance tardiness, and variance cost; we also consider multi-parallel series machines that perform multiple jobs on each machine and an aid, the analytic network process, to weight these objectives and their alternatives. PM scheduling is an NP-hard problem, so we use a dynamic genetic algorithm (GA) (the probability of mutation and crossover is changed through the main GA) to solve our algorithm and present another heuristic model (particle swarm optimization) algorithm against which to compare the GA’s answer. At the end, a numerical example shows that the presented method is very useful in implementing and maintaining machines and devices.     

变扰动强度下柔性装配作业车间调度性能分析

柔性装配作业车间是柔性作业车间的一类现实化扩展,其调度问题既要考虑复杂的加工路径柔性,还要考虑零件间的装配关联约束,以及由其带来的关联零件生产进度协同难题.首先给出了柔性装配作业车间调度问题的数学模型;然后考虑现实生产中普遍存在的随机扰动,采用了完全反应式与预测-反应式两类动态调度策略,并提出了相应的优先度规则算法和周...     

基于混合遗传算法的混流混合车间协同调度问题

为解决一类具有多品种混流生产特征和作业车间与流水车间集成的混流混合车间协同调度问题,给出了以在制品成本最小为目标的混流混合车间调度问题模型;采用零件加工、部件装配、产品总装的三段协同编码方法,给出了一种集成模拟退火算法的混合遗传算法,并在模拟退火算法中引入变温度参数来平衡算法效率。最后,通过某冰箱混流装配企业典型实例验证了模型和算法的有效性。     

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.     

RECONFIGURABLE PRODUCTION LINE MODELING AND SCHEDULING USING PETRI NETS AND GENETIC ALGORITHM

In response to the production capacity and functionality variations, a genetic algorithm (GA) embedded with deterministic timed Petri nets(DTPN) for reconfigurable production line(RPL) is proposed to solve its scheduling problem. The basic DTPN modules are presented to model the corresponding variable structures in RPL, and then the scheduling model of the whole RPL is constructed. And in the scheduling algorithm, firing sequences of the Petri nets model are used as chromosomes, thus the selection, crossover, and mutation operator do not deal with the elements in the problem space, but the elements of Petri nets model. Accordingly, all the algorithms for GA operations embedded with Petri nets model are proposed. Moreover, the new weighted single-objective optimization based on reconfiguration cost and E/T is used. The results of a DC motor RPL scheduling suggest that the presented DTPN-GA scheduling algorithm has a significant impact on RPL scheduling, and provide obvious improvements over the conventional scheduling method in practice that meets duedate, minimizes reconfiguration cost, and enhances cost effectivity.     

Scheduling optimisation of flexible manufacturing systems using particle swarm optimisation algorithm

The increased use of flexible manufacturing systems (FMS) to efficiently provide customers with diversified products has created a significant set of operational challenges. Although extensive research has been conducted on design and operational problems of automated manufacturing systems, many problems remain unsolved. In particular, the scheduling task, the control problem during the operation, is of importance owing to the dynamic nature of the FMS such as flexible parts, tools and automated guided vehicle (AGV) routings. The FMS scheduling problem has been tackled by various traditional optimisation techniques. While these methods can give an optimal solution to small-scale problems, they are often inefficient when applied to larger-scale problems. In this work, different scheduling mechanisms are designed to generate optimum scheduling; these include non-traditional approaches such as genetic algorithm (GA), simulated annealing (SA) algorithm, memetic algorithm (MA) and particle swarm algorithm (PSA) by considering multiple objectives, i.e., minimising the idle time of the machine and minimising the total penalty cost for not meeting the deadline concurrently. The memetic algorithm presented here is essentially a genetic algorithm with an element of simulated annealing. The results of the different optimisation algorithms (memetic algorithm, genetic algorithm, simulated annealing, and particle swarm algorithm) are compared and conclusions are presented .     

面向复杂零件协同制造的资源优化配置技术研究

面向复杂零件的异地协同制造，提出依据工艺流程进行制造任务分解，研究了以工艺流程为核心的逻辑制造单元（LMU）和逻辑加工路线（LMP）设计，有效利用LMP和LMU描述针对复杂零件的协同制造任务。对复杂零件异地协同制造的制造资源优化配置问题进行了数学分析和描述，阐述了问题的目标与约束条件，将资源优化配置问题归结为多目标优化问题，利用遗传算法进行求解，并进行了应用实例分析，证明了采用制造资源优化配置方法可以有效解决复杂零件网络化异地协同制造的资源优化配置问题。     

A flexible artificial neural network–fuzzy simulation algorithm for scheduling a flow shop with multiple processors

One of the most popular approaches for scheduling manufacturing systems is dispatching rules. Different types of dispatching rules exist, but none of them is known to be globally the best. A flexible artificial neural network–fuzzy simulation (FANN–FS) algorithm is presented in this study for solving the multiattribute combinatorial dispatching (MACD) decision problem. Artificial neural networks (ANNs) are one of the commonly used metaheuristics and are a proven tool for solving complex optimization problems. Hence, multilayered neural network metamodels and a fuzzy simulation using the α-cuts method were trained to provide a complex MACD problem. Fuzzy simulation is used to solve complex optimization problems to deal with imprecision and uncertainty. The proposed flexible algorithm is capable of modeling nonlinear, stochastic, and uncertain problems. It uses ANN simulation for crisp input data and fuzzy simulation for imprecise and uncertain input data. The solution quality is illustrated by two case studies from a multilayer ceramic capacitor manufacturing plant. The manufacturing lead times produced by the FANN–FS model turned out to be superior to conventional simulation models. This is the first study that introduces an intelligent and flexible approach for handling imprecision and nonlinearity of scheduling problems in flow shops with multiple processors.     

Multi-task scheduling of distributed 3D printing services in cloud manufacturing

The problem of service matching and scheduling in cloud manufacturing (CMfg) is complex for different types of manufacturing services. 3D printing, as a rapidly developing manufacturing technology, has become an important service form in the CMfg platform due to its characteristics of personalized manufacturing. How to solve the task scheduling problem for distributed 3D printing services in CMfg needs further research. In this paper, a service transaction model of 3D printing services in CMfg is built. Based on the service transaction model, we propose 3D printing service matching strategies and matching rules of different service attributes, including model size, printing material, printing preciseness, task cost, task time, and logistics. To reduce the delivery time of tasks from service suppliers to service demanders, a 3D printing service scheduling (3DPSS) method is proposed to generate optimal service scheduling solutions. In 3DPSS, optimization objective, constraints, and optimization algorithm are presented in detail. Experimental results show that the average task delivery time of 3DPSS is shorter than that of typical scheduling methods, such as particle swarm optimization, pattern search, and sequential quadratic programming, when the amounts of tasks change.     

基于蚁群算法的复合材料结构件的返修计划问题

为解决目前生产中出现的复合材料结构件的质量缺陷问题,G公司设立了复合材料结构件返修工序.针对结构件返修计划问题,以最大化返修计划中的结构件数量为目标,同时兼顾公司出货计划延迟和WIP成本(在制品成本)增加的情况,建立了0-1整数规划模型,进而以蚁群算法为基础提出了2种伪随机选择规则.根据实际情况采用不同参数设计算例来验证算法的性能.结果表明在最大化返修结构件数量方面,算法一优于算法二,而在减小公司出货延迟和控制WIP成本方面,算法二优于算法一.     

A game-theory approach for job scheduling in networked manufacturing

This paper presents a new kind of scheduling solution for jobs in networked manufacturing environments. The main contributions of this study can be focused on three points: The first is to distinguish the concepts and requirements of job scheduling in the networked manufacturing environment form those in the traditional manufacturing environment. The second is to construct a game-theory mathematical model to deal with this new job scheduling problem. In this presented mathematical model, this new job scheduling problem is formulated as an N-person non-cooperative game with complete information. The players correspond to the jobs submitted, respectively, by related customers and the payoff of each job is defined as its makespan. Each player has a set of strategies which correspond to the feasible geographical distributive machines. Therefore, obtaining the optimal scheduling results is determined by the Nash equilibrium (NE) point of this game. In order to find the NE point, the last point is to design and develop a genetic algorithm (GA)-based solution algorithm to effectively solve this mathematical model. Finally, a numerical example is presented to demonstrate the feasibility of the approach.     

工艺路线可变的双资源双目标车间调度优化

将遗传算法与启发式调度规则相结合 ,研究了工艺路线可变的双资源双目标的作业车间调度优化问题。在探讨过程中 ,不仅考虑到了每个工件有几条可行的工艺路线 ,而且考虑到了工件的调度受到机床、工人等资源的制约 ,以及在加工过程中发生的储存费用、机床的加工费用和工人的劳动费用对工件调度的影响 ,设计了以生产周期和生产成本综合优化为目标的适应度函数。启发式调度规则使该算法具有较高的局部搜索效率 ,遗传算法保证了解的全局最优性。最后给出了算例 ,并对计算结果进行了分析和讨论     

A new approach to solve time–cost trade-off problem with fuzzy decision variables

Time–cost trade-off problem is one of the main aspects of project scheduling. Due to variations in the real world, usually, risks in estimation of project parameters are considerably high. Therefore, use of uncertain models, which is capable of formulating vagueness in the real world, to solve time–cost trade-off problems, gives a scheduling with more stability against environmental variations. On the other hand, crisp decision making in uncertain environment causes loss of some parts of information. This paper presents a new optimal model for time–cost trade-off problem in a fuzzy environment. In order to solve this problem, a new solution method for possibility goal programming problems is developed. The significant feature of this model is the determination of optimal duration for each activity in the form of triangular fuzzy numbers. To validate the algorithm developed here, a case study will be presented.     

Simultaneous scheduling of parts and automated guided vehicles in an FMS environment using adaptive genetic algorithm

Automated Guided Vehicles (AGVs) are among various advanced material handling techniques that are finding increasing applications today. They can be interfaced to various other production and storage equipment and controlled through an intelligent computer control system. Both the scheduling of operations on machine centers as well as the scheduling of AGVs are essential factors contributing to the efficiency of the overall flexible manufacturing system (FMS). An increase in the performance of the FMS under consideration would be expected as a result of making the scheduling of AGVs an integral part of the overall scheduling activity. In this paper, simultaneous scheduling of parts and AGVs is done for a particular type of FMS environment by using a non-traditional optimization technique called the adaptive genetic algorithm (AGA). The problem considered here is a large variety problem (16 machines and 43 parts) and combined objective function (minimizing penalty cost and minimizing machine idle time). If the parts and AGVs are properly scheduled, then the idle time of the machining center can be minimized; as such, their utilization can be maximized. Minimizing the penalty cost for not meeting the delivery date is also considered in this work. Two contradictory objectives are to be achieved simultaneously by scheduling parts and AGVs using the adaptive genetic algorithm. The results are compared to those obtained by conventional genetic algorithm.     

Scheduling optimization of flexible manufacturing system using cuckoo search-based approach

In the present work, a cuckoo search (CS)-based approach has been developed for scheduling optimization of a flexible manufacturing system by minimizing the penalty cost due to delay in manufacturing and maximizing the machine utilization time. To demonstrate the application of cuckoo search (CS)-based scheme to find the optimum job, the proposed scheme has been applied with slight modification in its Levy flight operator because of the discrete nature of the solution on a standard FMS scheduling problem containing 43 jobs and 16 machines taken from literature. The CS scheme has been implemented using Matlab, and results have been compared with other soft computing-based optimization approaches like genetic algorithm (GA) and particle swarm optimization found in the literature. The results shown by CS-based approach have been found to outperform the results of existing heuristic algorithms such as GA for the given problem.     

Simultaneous scheduling of parts and automated guided vehicles in an FMS environment using adaptive genetic algorithm

Automated Guided Vehicles (AGVs) are among various advanced material handling techniques that are finding increasing applications today. They can be interfaced to various other production and storage equipment and controlled through an intelligent computer control system. Both the scheduling of operations on machine centers as well as the scheduling of AGVs are essential factors contributing to the efficiency of the overall flexible manufacturing system (FMS). An increase in the performance of the FMS under consideration would be expected as a result of making the scheduling of AGVs an integral part of the overall scheduling activity. In this paper, simultaneous scheduling of parts and AGVs is done for a particular type of FMS environment by using a non-traditional optimization technique called the adaptive genetic algorithm (AGA). The problem considered here is a large variety problem (16 machines and 43 parts) and combined objective function (minimizing penalty cost and minimizing machine idle time). If the parts and AGVs are properly scheduled, then the idle time of the machining center can be minimized; as such, their utilization can be maximized. Minimizing the penalty cost for not meeting the delivery date is also considered in this work. Two contradictory objectives are to be achieved simultaneously by scheduling parts and AGVs using the adaptive genetic algorithm. The results are compared to those obtained by conventional genetic algorithm.     

A memetic algorithm approach to the cell formation problem

In the past three decades many studies have been carried out on cellular manufacturing. The main problem in the development of cellular manufacturing is that of machine cell formation. In this paper a new metaheuristic called a memetic algorithm (MA) is introduced to solve the machine cell formation problem in group technology. The objective functions considered in this work are (a) minimization of total number of moves and (b) minimization of cell load variation and the constraints considered are minimum number of machines in each cell as two and each machine should be assigned in one cell only. Effort has been made to develop an algorithm that is more reliable than conventional methods and some non-traditional optimization techniques like the genetic algorithm (GA) and the tabu search algorithm (TS) for solving machine cell formation problem. In the memetic algorithm approach local optimization is applied to each newly generated offspring at the end of genetic algorithm.