改进人工蜂群算法求解分布式柔性作业车间调度问题

针对分布式柔性作业车间调度问题的特点,提出一种改进人工蜂群算法.首先,建立以最小化最大完工时间为优化目标的分布式柔性作业车间调度优化模型;然后,改进基本人工蜂群算法以使其适用于求解分布式柔性作业车间调度问题,具体的改进包括设计一种包含三维向量的编码方案,结合问题特点针对性地设计多种策略用于种群初始化,在雇佣蜂改良搜索操作中设计多种有效的进化操作算子,并在跟随蜂搜索操作中引入基于关键路径的局部搜索算子以提升算法的局部搜索能力;最后,利用扩展柔性作业车间通用测试集得到的测试数据设计实验验证算法性能,使用正交试验法优化算法参数设置.仿真实验结果表明,改进后的人工蜂群算法能有效求解分布式柔性作业车间调度问题.     

双种群混合遗传算法求解具有预防性维护的分布式柔性作业车间调度问题

在实际生产过程中,生产调度和设备维护相互影响,因此两者应该统筹优化.为研究具有预防性维护的分布式柔性作业车间调度问题,以最小化最大完工时间为目标,提出一种双种群混合遗传算法.结合问题特性,设计三维编码以及对应的机器解码方案,采用不同的策略初始化种群以均衡一部分工厂负载,为双种群设计不同的交叉变异算子提高算法的多样性,并利用交换精英解的方法实现两个种群的协作优化,同时针对关键工厂和预防性维护操作设计相应的局部搜索.最后对比现有算法,在同构和异构工厂的算例上进行实验,使用正交试验法优化算法参数设置.实验结果验证了局部搜索以及种群协作的有效性和双种群混合遗传算法求解具有预防性维护的分布式柔性作业车间调度问题的优越性.     

求解区间柔性作业车间调度的多目标进化算法

针对不确定多目标柔性作业车间调度问题,将工序加工时间采用区间数表示,以区间最大完工时间和区间机器总负荷为优化目标,构建多目标区间柔性作业车间调度模型,并设计一种多目标进化优化算法对该模型进行求解.算法采用混合策略生成初始化种群,并采用贪婪插入法对染色体进行解码,通过基于可能度的占优关系评价个体性能,将区间目标归一化结合拥挤距离反映优化解的分布情况.实验结果验证了所提出算法的有效性.     

基于最小机器数的柔性作业车间调度研究

针对期望以最小机器数完成生产的柔性作业车间调度问题,建立了最小化最大完工时间为内层目标,最小机器数为外层目标的双层优化模型,即在满足交货期、最小化最大完工时间的条件下,尝试减少机器数量,以寻求车间调度的最少机器数.依据模型、算法特点,设计了一种基于大变异策略的遗传算法,该算法采用二维染色体编码、顺序选择策略,同时运用优...     

基于遗传算法的多工序多机器调度优化研究

随着人民生活质量的提高,消费者对定制化生产提出了更高的要求,此外,在新的经济环境下,降本增效对于提升制造企业的发展能力具有重要的意义,基于此,本文提出了基于遗传算法的多工序多机器调度优化研究。首先,设计了基于完工时间最小化的多工序多机器加工约束的生产调度优化模型;其次,采用遗传算法设计了求解上述生产调度优化模型的算法;最后,通过案例验证了本文构建的优化模型及设计的优化算法,并绘制了以最小化完工时间为优化目标的生产调度甘特图。研究结果表明,本文构建的模型及设计的算法具有一定的实用性,可指导企业制定较优的生产调度方案。     

基于多Agent柔性制造单元的生产调度研究

针对基于制造单元的作业车间的生产调度问题进行了研究,结合多代理的智能性、灵活性和遗传算法的智能优化能力,建立基于多智能体的柔性制造单元的作业车间的调度系统模型.然后,提出了集成多智能体和遗传算法的动态调度策略和调度协商机制;最后,应用此方法完成了常规调度和异常调度的仿真算例.结果表明所开发系统可以解决基于加工单元的制造...     

基于约束模型的多目标柔性作业车间调度问题求解

针对遗传算法求解柔性作业车间调度问题的特性,对现有基于机器的互换交叉方式及基于工序的插入变异方式进行了改进,避免算法在运行过程中出现非法解,以节省算法的运算时间。同时,验证了改进后的交叉及变异方式的有效性。使用余弦相似度对个体进行相似度计算,避免算法在运算过程中丢失种群的多样性。使用极大极小法对调度模型进行约束,优化为旺季生产调度模型和淡季生产调度模型。最后,对多目标柔性作业车间调度问题的实例进行仿真运算,验证了算法的性能及方法的可行性。     

分布式测量系统服务窗口动态调度算法研究

在网络制造环境下,分布式测量系统(Distributed Measurement System,DMS)的负载是动态变化的,需要根据负载情况对测量系统上的资源进行动态调度.针对基于CORBA和DMIS的分布式测量系统,根据多用户非抢占优先排队网络静态性能模型,提出基于无穷小摄动分析(Infinitesimal Perturbation Analysis,IPA)的分布式测量系统服务窗口动态调度算法.算法以DMS系统负载的在线变化为输入,动态调整排队网络系统服务台的窗口数量,从而实现测量用户对动态时间性能的要求.最后在一个制造工厂中进行的应用实验,证明了算法的有效性.     

基于柔性维护的堕化单机系统调度研究

针对单机系统,在假设生产系统为堕化系统,且生产过程中作业的加工不可中断的情况下,对考虑柔性时间窗口[[u,v]]下进行长度为[w]的周期预防性维护的调度问题进行了研究。建立了综合考虑生产调度和设备维护的混合整数规划模型,并设计了一套基于贪婪的启发式算法对所研究问题进行优化求解。通过Cplex和启发式算法求解结果的对比证明了算法可以快速、有效地解决此类问题。     

考虑柔性机器检修的钢管热轧批量调度方法

本文从无缝钢管生产管理中提取并定义了周期性机器柔性检修环境下的钢管热轧批量调度问题,针对无缝钢管热轧阶段的生产特点,将其抽象为一类考虑序列相关设置成本和机器柔性检修的单机调度问题,建立了以最小化机器闲置时间和机器调整时间为优化目标的数学模型。分析闲置时间和检修时点的关系,证明了闲置时间最小化性质,结合问题特征设计了两阶段启发式算法。算法第一阶段采用最小轧机调整时间规则获取具有最小机器调整时间的初始批量轧制序列,第二阶段对初始轧制序列进行全局寻优搜索。基于实际生产数据设计了多种问题规模的对比实验,实验结果表明模型和算法对求解该类问题具有较好效果。     

基于几何可靠性机器模型的装配系统实时性能分析

装配系统是生产系统的基本结构之一, 广泛应用于汽车、电器、电子产品等实际生产环境中.与传统的串行生产线取得的研究成果相比, 装配系统的研究, 特别是对系统暂态过程的实时性能分析的研究仍然未得到深入探讨.本文针对具有三台几何可靠性机器模型和有限缓冲区容量框架下的装配系统, 首先建立了用于此类系统暂态性能分析的数学模型, 通过马尔科夫方法导出了系统性能分析的解析公式.然后, 提出了一种基于分解的性能评估算法来近似系统的实时性能.具体来说, 本文推导出了用于计算具有三台几何可靠性机器模型的装配系统的实时生产率、消耗率、在制品数量, 以及完成一个生产批次所需时间的解析表达式.最后, 通过数值实验对所提出算法的准确性进行验证.     

Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach

In general, distributed scheduling problem focuses on simultaneously solving two issues: (i) allocation of jobs to suitable factories and (ii) determination of the corresponding production scheduling in each factory. The objective of this approach is to maximize the system efficiency by finding an optimal planning for a better collaboration among various processes. This makes distributed scheduling problems more complicated than classical production scheduling ones. With the addition of alternative production routing, the problems are even more complicated. Conventionally, machines are usually assumed to be available without interruption during the production scheduling. Maintenance is not considered. However, every machine requires maintenance, and the maintenance policy directly affects the machine's availability. Consequently, it influences the production scheduling. In this connection, maintenance should be considered in distributed scheduling. The objective of this paper is to propose a genetic algorithm with dominant genes (GADG) approach to deal with distributed flexible manufacturing system (FMS) scheduling problems subject to machine maintenance constraint. The optimization performance of the proposed GADG will be compared with other existing approaches, such as simple genetic algorithms to demonstrate its reliability. The significance and benefits of considering maintenance in distributed scheduling will also be demonstrated by simulation runs on a sample problem.     

Distributed joint dynamic maintenance and production scheduling in manufacturing systems: Framework based on model predictive control and Benders decomposition

Scheduling the maintenance based on the condition, respectively the degradation level of the system leads to improved system's reliability while minimizing the maintenance cost. Since the degradation level changes dynamically during the system's operation, we face a dynamic maintenance scheduling problem. In this paper, we address the dynamic maintenance scheduling of manufacturing systems based on their degradation level. The manufacturing system consists of several units with a defined capacity and an individual dynamic degradation model, seeking to optimize their reward. The units sell their production capacity, while maintaining the systems based on the degradation state to prevent failures. The manufacturing units are jointly responsible for fulfilling the demand of the system. This induces a coupling constraint among the agents. Hence, we face a large-scale mixed-integer dynamic maintenance scheduling problem. In order to handle the dynamic model of the system and large-scale optimization, we propose a distributed algorithm using model predictive control (MPC) and Benders decomposition method. In the proposed algorithm, first, the master problem obtains the maintenance scheduling for all the agents, and then based on this data, the agents obtain their optimal production using the distributed MPC method which employs the dual decomposition approach to tackle the coupling constraints among the agents. The effectiveness of the proposed method is investigated on two case studies.     

Use of (max, +) algebra for scheduling and optimization of HVLV systems subject to preventive maintenance

High-Variety, Low-Volume (HVLV) manufacturing systems are built to produce parts of several types in small quantities and under multiple production objectives. They relate to job-shop systems well known by researchers. One of the most studied assumptions of HVLV systems scheduling is considering that machines may be periodically unavailable during the production scheduling. This article deals with an analytical integrating method using (max, +) algebra to model HVLV scheduling problems subject to preventive maintenance (PM) while considering machines availability constraints. Each machine is subject to PM while maintaining flexibility for the start time of the maintenance activities during the planning period. The proposed model controls the placement of maintenance activities along the production operations. Indeed, the sequencing of maintenance activities on the machines depends on the criteria to minimize and may be different for each criteria value. For preventive maintenance, the proposed model aims to generate the best sequencing between activities while respecting the planning program that satisfy the optimal criteria values. In order to illustrate the performance of the proposed methodology, a simulation example is given.     

Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm

Most flexible job shop scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines may be unavailable due to maintenances, pre-schedules and so on. In this paper, we study the flexible job shop scheduling problem with availability constraints. The availability constraints are non-fixed in that the completion time of the maintenance tasks is not fixed and has to be determined during the scheduling procedure. We then propose a hybrid genetic algorithm to solve the flexible job shop scheduling problem with non-fixed availability constraints (fJSP-nfa). The genetic algorithm uses an innovative representation method and applies genetic operations in phenotype space in order to enhance the inheritability. We also define two kinds of neighbourhood for the problem based on the concept of critical path. A local search procedure is then integrated under the framework of the genetic algorithm. Representative flexible job shop scheduling benchmark problems and fJSP-nfa problems are solved in order to test the effectiveness and efficiency of the suggested methodology. Received: June 2005 /Accepted: December 2005     

An effective heuristic for flexible job-shop scheduling problem with maintenance activities

Most production scheduling problems, including the standard flexible job-shop scheduling problem (FJSP), assume that machines are continuously available. However, in most realistic situations, machines may become unavailable during certain periods due to preventive maintenance (PM). In this paper, a flexible job-shop scheduling problem with machine availability constraints is considered. Each machine is subject to preventive maintenance during the planning period and the starting times of maintenance activities are either flexible in a time window or fixed beforehand. Moreover, two cases of maintenance resource constraint are considered: sufficient maintenance resource available or only one maintenance resource available. To deal with this variant FJSP problem with maintenance activities, a filtered beam search (FBS) based heuristic algorithm is proposed. With a modified branching scheme, the machine availability constraint and maintenance resource constraint can be easily incorporated into the proposed algorithm. Simulation experiments are conducted on some representative problems. The results demonstrate that the proposed filtered beam search based heuristic algorithm is a viable and effective approach for the FJSP with maintenance activities.     

A modeling technique for loading and scheduling problems in FMS

In recent years, due to highly competitive market conditions, it has become necessary for manufacturing systems to have quick response times and high flexibility. Flexible manufacturing systems (FMS's) have gained attention in response to this challenge. FMS has the ability to produce a variety of parts using the same system. However this flexibility comes at the price, which is the development of efficient and effective methods for integrated production planning, and control.In this paper, we analyze the production planning problem in flexible manufacturing systems. We address the problems of part loading, tool loading, and part scheduling. We assume that there is a set of tools with known life and a set of machines that can produce a variety of parts. A batch of various part types is routed through this system with the assumption that the processing time and cost vary with the assignment of parts to different machines and assignment of various tool sets to machines. We developed a mathematical model to select machines and assign operations and the required tools to machines in order to minimize the summation of maximum completion time, material handling time, and total processing time.We first integrate and formulate loading, and routing, two of the most important FMS planning problems, as a 0–1 mixed integer programming problem. We then take the output from the integrated planning model and generate a detailed operations schedule. The results reported in this paper demonstrate the model efficiency and examine the performance of the system with respect to measures such as production rate and utilization.     

基于EDF调度策略的端到端实时系统可调度性分析算法

端到端实时任务调度模型可用于描述许多分布式实时系统.提出一种基于EDF调度策略的端到端实时任务调度模型,给出了端到端实时系统的可调度性判定条件,并提出其可调度性分析算法,该可调度性判定条件及可调度性分析算法适用于采用非连续工作型同步协议和连续工作型同步协议控制下的端到端实时系统.与固定优先级的端到端实时任务调度模型及其算法相比,基于EDF调度策略的端到端实时任务调度模型和算法更加简单和易于实现,仿真结果也表明具有较高的性能.     

Feedback utilization control in distributed real-time systems with end-to-end tasks

An increasing number of distributed real-time systems face the critical challenge of providing quality of service guarantees in open and unpredictable environments. In particular, such systems often need to enforce utilization bounds on multiple processors in order to avoid overload and meet end-to-end deadlines even when task execution times are unpredictable. While recent feedback control real-time scheduling algorithms have shown promise, they cannot handle the common end-to-end task model where each task is comprised of a chain of subtasks distributed on multiple processors. This paper presents the end-to-end utilization control (EUCON) algorithm that adaptively maintains desired CPU utilization through performance feedbacks loops. EUCON is based on a model predictive control approach that models utilization control on a distributed platform as a multivariable constrained optimization problem. A multi-input-multi-output model predictive controller is designed based on a difference equation model that describes the dynamic behavior of distributed real-time systems. Both control theoretic analysis and simulations demonstrate that EUCON can provide robust utilization guarantees when task execution times deviate from estimation or vary significantly at runtime.