柔性作业车间生产计划与调度集成优化求解策略

针对柔性作业车间(Flexible job-shop, FJS)生产计划(Production planning, PP)与调度紧密衔接的特点, 建立了生产计划与调度集成优化模型. 模型综合考虑了安全库存、需求损失及工件加工路线柔性等方面因素. 提出了一种基于拉格朗日松弛(Lagrangian relaxation, LR)的分解算法, 将原问题分解为计划子问题与调度子问题. 针对松弛的生产计划子问题, 提出一种新的费用结构, 以保证生产计划决策与实际情况相符, 并设计了一种变量固定—松弛策略与滚动时域组合算法进行求解. 对于调度子问题中的加工路线柔性问题, 提出了一种新的机器选择策略. 通过数值实验验证了模型与算法的有效性.     

基于果蝇优化算法的多工位装配序列规划

为同时解决产品装配序列规划和多工位分配问题,提出一种面向复杂产品的基于果蝇优化算法的多工位装配序列规划方法。首先,基于果蝇优化算法设计了针对求解序列的编码体系;其次,采用多子种群并行搜索模式,重新设计了果蝇优化算法的搜索过程;然后,为了综合考虑多工位上相关装配操作成本的影响,提出了新的适应度函数表达式,并将适应度函数与优先序列矩阵结合起来对进化过程进行引导,实现了对产品装配序列和工位分配顺序的优化;最后,以飞机起落架为例,验证了所提方法在解决多目标优化问题方面的有效性。     

面向大规模定制的柔性生产计划研究

针对大规模定制条件下传统生产计划在主生产计划、产品结构管理和生产计划过程三个方面柔性不足的问题,应用模块化方法构建了双层柔性主生产计划、产品族结构模型和"PUSH/PULL"结合的生产计划过程模型,在此基础上,构建了柔性的生产计划体系结构。通过实证分析,验证了该体系结构可实现快速响应大规模定制下产品多样化的需求。     

Integration of product design,process planning,scheduling, and FMS control using XML data representation

An efficient model for communications between CAD, CAPP, and CAM applications in distributed manufacturing planning environment has been seen as key ingredient for CIM. Integration of design model with process and scheduling information in real-time is necessary in order to increase product quality, reduce the cost, and shorten the product manufacturing cycle. This paper describes an approach to integrate key product realization activities using neutral data representation. The representation is based on established standards for product data exchange and serves as a prototype implementation of these standards. The product and process models are based on object-oriented representation of geometry, features, and resulting manufacturing processes. Relationships between objects are explicitly represented in the model (for example, feature precedence relations, process sequences, etc.). The product model is developed using XML-based representation for product data required for process planning and the process model also uses XML representation of data required for scheduling and FMS control. The procedures for writing and parsing XML representations have been developed in object-oriented approach, in such a way that each object from object-oriented model is responsible for storing its own data into XML format. Similar approach is adopted for reading and parsing of the XML model. Parsing is performed by a stack of XML handlers, each corresponding to a particular object in XML hierarchical model. This approach allows for very flexible representation, in such a way that only a portion of the model (for example, only feature data, or only the part of process plan for a single machine) may be stored and successfully parsed into another application. This is very useful approach for direct distributed applications, in which data are passed in the form of XML streams to allow real-time on-line communication. The feasibility of the proposed model is verified in a couple of scenarios for distributed manufacturing planning that involves feature mapping from CAD file, process selection for several part designs integrated with scheduling and simulation of the FMS model using alternative routings.     

A multi-plant production planning model considering non- repeated setup and aperiodic shipment

A new model for multi-plant production planning is developed. As the important actual features of some manufacturers, non-repeated setup and aperiodic shipment are appropriately introduced into the multi-plant production planning model and the corresponding constraints are accurately linearized. The new model is also applicable in the case of periodic shipment or backorder prohibition. Its effectiveness is examined by an instance which simulates many real characteristics. The experimental results indicate that the new model achieves the optimal profit. The sensitivity of unit setup cost and unit shipment cost is analyzed. The significance of backorder and the limitation of shipment at a time are discussed in detail.     

Integrated process planning and scheduling in a supply chain

This paper deals with the integration of process planning and scheduling, which is one of the most important functions in a supply chain to achieve high quality products at lower cost, lower inventory, and high level of performance. Solving the problem is essential for the generation of flexible process sequences with resource selection and for the decision of the operation schedules that can minimize makespan. We formulate a mixed integer programming model to solve this problem of integration. This model considers alternative resources: sequences and precedence constraints. To solve the model, we develop a new evolutionary search approach based on a topological sort. We use the topological sort to generate a set of feasible sequences in the model within a reasonable computing time. Since precedence constraints between operations are handled by the topological sort, the developed evolutionary search approach produces only feasible solutions. The experimental results using various sizes of problems provide a way to demonstrate the efficiency of the developed evolutionary search approach.     

考虑非确定加工时间的柔性作业车间调度问题研究

加工时间不确定的柔性作业车间调度问题已逐渐成为生产调度研究的热点。采用区间表示加工时间范围,利用时间Petri网建立区间柔性作业车间调度问题形式化模型,并运用网模型的状态类图进行可达性分析,计算出所有可行变迁触发序列。通过对触发序列的时序分析,提出一种有效的逆向分步法来构造触发序列的时间约束不等式,进而求解线性规划问题来获得最小完工时间下界(上界)的优化调度策略。最后利用实例分析验证了模型及所提方法的正确性和可行性,为实际的区间柔性作业车间调度问题提供有效方案。     

A grammatical optimization approach for integrated process planning and scheduling

Rapid developments in computerized manufacturing environments and increasing overlapping in the capability of manufacturing resources provoked integration of many manufacturing functions including process planning scheduling. Several approaches have been developed in the literature in order to integrate process planning and scheduling. In this paper a novel approach which makes use of grammatical representation of generic process plans is used within a multiple objective tabu search framework in order to integrate process planning and scheduling effectively. Detailed explanations along with an example problem are presented in the paper. Proposed approach is tested on literature problems and also hypothetically generated flexible job shop scheduling problems with alternative process plans to analyze its performance and efficiency.     

基于归约的柔性工艺过程模型

该文提出了一种基于“与/或”归约的柔性工艺表达模型,为实现工艺过程动态设计与生产规划提供了一种新的技术方法。同时,详细描述了柔性工艺归约的有序搜索的算法,其中,宽度算法用来进行寻找可替代的工序、加工方法或设备,可拓宽工艺的柔性;深度算法用来进行工艺的可加工性设计和设备的负荷总体平衡,可预防决策短见。     

邻域规模对共生进化算法搜索性能的影响

共生进化算法求解复杂组合问题时表现了良好的性能,其选择邻域实现局部进化。对于复杂的的柔性作业调度组合问题,作业调度结果的好坏首先依赖流程设计的质量。以共生进化算法求解复杂柔性作业调度为例,测试不同邻域规模对共生进化算法搜索性能的影响。仿真结果表明,局部进化邻域规模的大小对共生进化算法在平均求解质量及对最优解的逼近能力两个方面均没有显著影响,过大的局部进化邻域会增加算法中排序操作计算量。     

Scheduling Optimization Modelling: A Case Study of a Woven Label Manufacturing Company

Production scheduling involves all activities of building production schedules, including coordinating and assigning activities to each person, group of people, or machine and arranging work orders in each workplace. Production scheduling must solve all problems such as minimizing customer wait time, storage costs, and production time; and effectively using the enterprise’s human resources. This paper studies the application of flexible job shop modelling on scheduling a woven labelling process. The labelling process includes several steps which are handled in different work-stations. Each workstation is also comprised of several identical parallel machines. In this study, job splitting is allowed so that the power of work stations can be utilized better. The final objective is to minimize the total completion time of all jobs. The results show a significant improvement since the new planning may save more than 60% of lead time compared to the current schedule. The contribution of this research is to propose a flexible job shop model for scheduling a woven labelling process. The proposed approach can also be applied to support complex production scheduling processes under fuzzy environments in different industries. A practical case study demonstrates the effectiveness of the proposed model.     

多目标等量分批柔性作业车间调度集成优化方法

针对多目标等量分批柔性作业车间调度问题,提出了一种集成优化方法。构建了一种以完工时间最短、生产成本最低为优化目标的多目标等量分批柔性调度集成优化模型。提出并设计了一种改进的非支配排序遗传算法对模型加以求解。算法中引入面向对象技术处理复杂的实体逻辑关系,采用三段式分段编码技术分别对分批方案、加工顺序、设备进行编码,采用三段式分段交叉和变异的混合遗传算子实现遗传进化,采用两种精细化调度技术进行解码以缩短流程时间。通过案例分析验证了所提方法的有效性。     

Adaptive genetic algorithm for advanced planning in manufacturing supply chain

A main function for supporting global objectives in a manufacturing supply chain is planning and scheduling. This is considered such an important function because it is involved in the assignment of factory resources to production tasks. In this paper, an advanced planning model that simultaneously decides process plans and schedules was proposed for the manufacturing supply chain (MSC). The model was formulated with mixed integer programming, which considered alternative resources and sequences, a sequence-dependent setup and transportation times.The objective of the model was to analyze alternative resources and sequences to determine the schedules and operation sequences that minimize makespan. A new adaptive genetic algorithm approach was developed to solve the model. Numerical experiments were carried out to demonstrate the efficiency of the developed approach. Received: June 2005 / Accepted: December 2005     

基于TSAPO的柔性作业车间计划和调度

为使多目标柔性作业车间计划与调度的制定更适合实际生产的动态变化,提出增加动态反馈的闭环柔性作业车间计划模型及二阶式蚁群粒子群混合优化算法TSAPO。通过增加动态监视功能,及时更新和反馈实际生产数据。利用对优化目标的二阶段分解,设计带有反馈机制的调度算法。实验结果证明,该算法在求解多目标柔性作业车间调度问题中具有较好的优化效果。     

Evaluation of assembly sequences using generalized flexible assembly systems scheduling problem

The evaluation and selection of assembly sequences are performed in the planning stage of assembly processes. This paper deals with the effect of selecting particular assembly sequences to the performance of flexible assembly systems(FAS). The performance of FAS is evaluated using the generalized FAS scheduling problem(GFASSP). Compared to the conventional FASSP, GFASSP tries to select the most efficient assembly sequences for each product as well as minimize cycle time to complete the assemblies in FAS environment while considering the transfer time of subassemblies.     

A Petri net-based methodology to increase flexibility in service-oriented holonic manufacturing systems

Distributed control systems such as the holonic manufacturing systems and service-oriented architectures have demonstrated to provide higher levels of flexibility, notably in the planning and scheduling functionalities, if well exploited. In scheduling, the use of fixed process plans generated by traditional planning approaches, usually leads to unrealistic schedules due to the lack of considerations of the workshop status. IPPS approaches try to break the gap between these two functionalities in favor of providing flexible plans adapting to the shop floor's state. A key element in the creation of flexible process plans is the definition of a process model capable of representing alternatives solutions to the sequencing problem and therefore increasing the potential solution space. This paper presents a methodology to increase planning flexibility in service-oriented manufacturing systems (SOHMS). The methodology introduces a Petri net service-oriented process model (SOP model) capable of computing a product's deadlock free sequential space and adapts to the fractal character of holonic architectures. A set of modeling rules, with illustrations, is presented for the automatic generation of the Petri net, based on a set of precedence conditions. To explore the solution space represented by the SOP model a holonic interaction protocol is presented. Moreover, a set of behavioral strategies is proposed in order to cope with the effects of a possible combinatorial explosion. A study case applied workshop example is presented to illustrate the modeling process of SOP models, compute the sequential solution space and demonstrate how this notably increases the number of potentially goods feasible solutions.     

基于柔性job shop的集成化工艺规划与生产调度

为有效利用车间资源管理系统,在研究基于柔性jobshop的工艺规划与生产调度集成问题的基础上,提出基于工艺规划的多agent生产调度系统（Flexible process planning based Multi-Agent production Scheduling System,FMASS）．该系统综合考虑零件的工艺规划柔性和车间生产柔性,采用混合建模的方法建立4类agent及其行动规则,通过各类agent相互之间的协商与竞争得到零件的工艺规划和工序,从而实现工艺规划与车间调度系统的集成．对工艺规划与车间调度的集成算法进行性能测试,结果表明该系统具有一定的预见性和全局优化能力,且柔性和对动态变化的适应性较好．     

考虑多目标的柔性工艺与调度集成优化算法

针对工艺规划与车间调度集成优化问题,在考虑零件的加工工序柔性、工序次序柔性及加工机器柔性的基础上,以最大完工时间、总加工成本和总拖期时间为优化目标,对多目标柔性工艺与车间调度集成问题建模,提出一种基于改进人工蜂群算法的多目标柔性工艺与车间调度集成优化策略,并提出邻域变异操作以及全局交叉操作,对种群进行更新。引入Pareto方法,通过对适应度评价、贪婪准则、Pareto最优解集构造和保存以及解得多样性维护等方面进行改进,设计了一种基于Pareto方法的多目标人工蜂群算法。最后,通过采用基本人工蜂群算法及改进人工蜂群算法对六个工件、五台机床的柔性工艺与车间调度集成问题进行优化,验证了改进算法的有效性。     

Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey

Scheduling is an important tool for a manufacturing system, where it can have a major impact on the productivity of a production process. In order to find an optimal solution to scheduling problems it gives rise to complex combinatorial optimization problems. Unfortunately, most of them fall into the class of NP-hard combinatorial problems. In this paper, we focus on the design of multiobjective evolutionary algorithms (MOEAs) to solve a variety of scheduling problems. Firstly, we introduce fitness assignment mechanism and performance measures for solving multiple objective optimization problems, and introduce evolutionary representations and hybrid evolutionary operations especially for the scheduling problems. Then we apply these EAs to the different types of scheduling problems, included job shop scheduling problem (JSP), flexible JSP, Automatic Guided Vehicle (AGV) dispatching in flexible manufacturing system (FMS), and integrated process planning and scheduling (IPPS). Through a variety of numerical experiments, we demonstrate the effectiveness of these Hybrid EAs (HEAs) in the widely applications of manufacturing scheduling problems. This paper also summarizes a classification of scheduling problems, and illustrates the design way of EAs for the different types of scheduling problems. It is useful to guide how to design an effective EA for the practical manufacturing scheduling problems. As known, these practical scheduling problems are very complex, and almost is a combination of different typical scheduling problems.     

一类求解订单分配和排序问题的集成优化算法

研究大规模订单分配和排序问题.从整体的角度协同优化多工厂供应链排序中的订单分配、生产调度和分批运输调度3个阶段;以总订货提前期与总成本的加权和最小化为目标,建立了问题的数学模型;基于解的最优化条件,设计了禁忌搜索算法与动态规划方法相结合的集成优化算法;在算法中设计了自适应选择机制,以提高算法的搜索效率.数值实验结果验证了采用所提出的集成优化算法求解规模较大问题的有效性.