多群体并行遗传算法在动态车间调度中的应用

生产调度对企业的生产作业过程具有重要的作用。有效的调度方法和优化技术是实现先进制造和提高生产效益的基础和关键。本文论述利用多群体并行遗传算法可满足动态车间调度的应用,采用一种特殊构造遗传编码方法采改进遗传算法,提供有效的最优化查询。利用MATLaB工具以实例证明该算法的有效性。该算法特别适合于job-shop调度问题。     

等待时间受限的置换流水车间调度启发式算法

针对等待时间受限的置换流水车间调度问题,分析了其可行解与流水车间调度最优解的关系,给出了计算最大完工时间的有向图,证明了等待时间受限的置换流水车间调度问题的可逆性,并以此为基础提出了一种启发式算法.算法首先根据等待时间受限约束与无等待(no-wait)约束的相似特征,生成初始工件序列集;然后利用问题可逆性给出了复杂度为O(n2m)的插入优化机制,进一步优化初始解.数据实验的结果验证了启发式算法的可行性和有效性.     

基于改进遗传算法的置换装配线调度问题研究

企业的置换装配线调度问题（Permutation Assembly-line Scheduling Problem,PASP）是一类典型的NP-hard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明：本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。     

启发式算法求解等待时间受限的两阶段流水车间调度问题

等待时间受限的两阶段流水车间调度问题具有强NP难的复杂性,有必要探索问题特征来开发近似求解算法。本文分析了此问题与一般两阶段流水车间调度和无等待两阶段流水车间调度的关系,给出了两类特殊问题的多项式求解方法,探讨了最优调度的工件序列特征。在此基础上,设计了基于排列排序的启发式算法,算法应用Gilmore-Gomory启发式生成初始序列,构造调度解的可替换集合实现迭代寻优,并利用工件序列特征调整工件顺序以优化当前调度。通过对算法的求解性能进行理论分析和实验验证,进一步表明了该算法的有效性。     

基于改进模糊遗传算法的混合车辆路径问题

本文建立了多配送中心、多车型、多产品的车辆路径问题的混合数学模型,提出了一种新的模糊遗传算法求解混合车辆路径问题,通过改进的模糊逻辑控制器实现交叉概率和变异概率的动态调整,以加快算法收敛速度并避免算法陷入局部最优解。采用标准算例进行对比,证明模糊遗传算法有较好的计算结果和计算效率,并用模糊遗传算法对混合车辆路径模型进行仿真测试,取得了理想的结果。     

服务水平约束下流水车间成套订单调度研究

本文针对流水车间环境,研究了服务水平约束下成套订单的调度问题,通过建立与分析该问题的模型,研究并设计了用于排序的三种构造式启发算法,以及用于确定订单成套数的构造式启发算法、改进遗传算法和模拟退火算法,最后通过各种规模及不同约束度的算例进行模拟计算与比较分析,结果表明了改进遗传算法的有效性,但其它两种算法也各有优点。     

基于遗传算法的资源约束型项目调度优化

资源约束型项目调度的优化是一个NP-hard问题,其求解难度随着资源约束项的增多呈指数方式增长,传统的基于Excel表的手工优化方法不能及时计算出有效的资源配置方式,从而影响项目管理人员的资源调度.针对多资源约束型项目调度的优化问题提出基于遗传算法的资源约束型项目调度的优化方法,该算法采用基于活动优先权的十进制编码方式,结合活动的存储邻接矩阵,有效地解决活动调度违例现象;运用优先抢占模式的资源分配方式安排活动资源,避免资源分配中的冲突问题;并为该算法设计了启发式遗传算法的C语言程序,通过计算机的多次迭代运算得出满足资源约束的最优工期.实践结果表明,遗传算法可以快速有效地解决企业项目调度的优化问题,适合在企业项目进度管理中推广运用.     

一种求解柔性工作车间调度问题的混合遗传算法

针对柔性工作车间调度问题(Flexible job-shop scheduling problem, FJSP),提出了一种基于混合遗传算法的求解方案,在初始种群中引入基于启发式规则生成的优良个体,并使用有效的交叉、变异算子避免不可行个体的产生,同时利用混沌序列的随机性和遍历性特点,在遗传进化的过程中增加基于混沌序列的邻域搜索功能,以提高遗传算法的执行效率.通过仿真实验验证了该算法的可行性和有效性.     

面向并行制造的多生产单元协同调度研究

为提升多生产单元制造系统整体效率，在其系统内开展面向并行制造的协同调度研究，在考虑运输、换线等时间的基础上，构建多生产单元并行协同调度模型，采用并行分段协同遗传算法求解；在此基础上，将所研究协同调度方法应用于某复杂机电产品多生产单元制造车间，并与变批量调度与等批量调度比较。研究表明，所提的并行协同调度方法可以显著提升生产单元效率，提高生产单元设备和人员利用率。     

作业车间的模糊动态调度问题研究

本文针对作业车间的模糊动态调度问题,给出了该问题的生产系统描述、建模,给出了基于工件到达时间三角模糊数的计算确定重调度时段划分点的模糊动态调度策略,通过一种基于时间分解的策略将作业车间的模糊动态调度问题转化为一系列不一定被完全执行的静态模糊子调度问题求解。针对模型的求解给出了改进的G&T算法,将改进的基于关键路径的邻域交换技术引入遗传算法变异算子的设计,改善了算法解的局部寻优能力。仿真实验结果表明,本文给出的作业车间模糊动态调度模型是正确的,提出的算法有效,且动态调度策略具有鲁棒性。     

A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs,financial budget,and resource constraint in multiple manufacturers

We study a coordinated serial-batching scheduling problem that features deteriorating jobs, financial budget, resource constraints, resource-dependent processing times, setup times, and multiple manufacturers simultaneously. A unique feature but also a significant challenge in this problem is the dual constraints on resources, i.e., financial budget and resource quantity. Some key structural properties are first identified for the setting where the jobs and resources are already assigned to each manufacturer, which enables us to develop the optimal resource allocation scheme. Then, a polynomial-time scheduling rule is proposed to search for the optimal solution for each manufacturer in this setting. Then, a hybrid BA-VNS algorithm combining Bat algorithm (BA) and variable neighborhood search (VNS) is proposed to tackle the studied problem, and the optimal scheduling rule is implemented in its encoding procedure. Finally, computational experiments are conducted to test the performance of the proposed algorithm, and the efficiency and improvements are compared with those of BA, VNS, and Particle Swarm Optimization (PSO), with respect to convergence speed as well as computational stability.     

Implementation of holonic scheduling and control in flow-line manufacturing systems: die-casting case study

The success of a flow-line manufacturing system depends on effective production scheduling and control. However, it has been found that current flow-line manufacturing scheduling and control algorithms lack the flexibility to handle interruptions or resource breakdowns; hence, system performance drops automatically and rapidly when interruptions occur. The objective of this research is to investigate if the performance of a flow-line manufacturing system can be improved by integrating agent-based, holonic scheduling and production control. A holonic manufacturing scheduling model has been developed and implemented into a die-casting manufacturing flow line throughout a simulation model. The analysis takes into account the comparisons of overall performances of the system models with the holonic scheduling and conventional scheduling approaches. Simulation results indicate that the holonic manufacturing scheduling and control can significantly increase the uptime efficiency and the production rate of the flow-line manufacturing system.     

现代工业制造模式的变迁及比较研究

本文针对未来工业生产的发展方向,界定了工业制造的三种模式———减量制造、等量制造和增量制造,在此基础上总结了三种模式之间的本质区别。     

炼钢连铸计划调度优化系统

钢铁企业的炼钢连铸计划调度问题一直是学术界和企业界研究的热门课题.炼钢连铸生产计划调度系统是钢铁企业制造执行系统的重要组成部分,在企业的生产管理中起着承上启下的作用.本文首先简述了炼钢连铸计划调度理论的发展历程和生产工艺流程,并进一步描述了炼钢连铸计划编制的流程.针对炼钢连铸计划调度的现场要求,架构了炼钢连铸计划调度优化系统的功能模块,并较详细地说明了各功能模块的功能特点.该系统不仅能对静态调度计划应用多种优化方法进行编制,而且对复杂生产环境的各类响应事件可以做到快速响应,满足动态调度的要求,保证生产的稳定顺行.     

MC模式下供应链动态调度的蚁群寻优分析

在对MC模式下供应链调度的基本运作特征描述及界定基础上,分析了调度过程中主导矛盾的缓解思路;通过将该思路引入动态调度的运作过程,分析了MC模式下的供应链动态调度机理.在调度求解过程中,引入蚁群觅食的寻优机理并对其进行特定的算法设计及改进,提出了供应链动态调度的蚂蚁寻优算法.算法特点为在运算过程中不仅能够反映该生产方式独特的运作特征要求,而且能够融入对主导矛盾的缓解思路.通过仿真,验证了算法的可行性.     

一种求解双目标flow shop排序问题的进化算法

提出一种求解双目标flow shop排序的递进多目标进化算法.算法采用改进的精英复制策略,在实现精英保留的前提下降低了计算复杂性;通过递进进化模式增加群体多样性,改善了算法收敛性;通过群体进化过程中对非劣解集进行竞争型可变邻域启发式搜索,增强了算法局部搜索性能.采用新算法和参照算法NSGA-II对31个标准双目标flow shop算例进行优化.研究结果表明,新算法在所有算例的求解中均获得了优于NSGA-II的非劣解集,验证了算法的有效性.     

Supporting Quick Response Through Scheduling of Make-to-Stock Production/Inventory Systems*

Scheduling of traditional job shops in make-to-order systems has seen extensive research over the past three decades. In such systems, performance is often related to various job completion metrics such as average flow time, average lateness, etc. This paper examines a scheduling problem in a make-to-stock environment where individual job completion measures are irrelevant. In this case, customer orders are satisfied through on-hand inventory where customer service is more closely related to the manufacturer's ability to quickly satisfy demand. We consider the role of scheduling in reducing inventories and improving customer service in the context of a manufacturer who assembles several different products on a single assembly line. We develop scheduling rules for such a system and experimentally compare their performance to those typically used in such environments. Our results indicate that rules which consider the inventory position and demand forecast outperform traditional fixed cycle rules.     

第三方负责回收的再制造闭环供应链决策结构的效率分析

本文研究了第三方负责回收的再制造闭环供应链在不同决策结构下的供应链收益,以及与集成式"超组织"结构相比的效率损失。结果表明:回收物品的潜在期望收益是回收行为的驱动因素,期望的残余收益越大、回收价格越低,则越能激发回收行为努力且增加供应链成员企业收益;在分散式决策结构中,不论是生产商还是销售商占据市场地位,供应链效率损失不可避免;通过契约先谋求供应链的整体收益最大,然后根据约定的比例进行收益分享,是实现逆供应链成员"双赢"目的的有效策略。     

Cross dock scheduling: Classification,literature review and research agenda

At cross docking terminals incoming deliveries of inbound trucks are unloaded, sorted, moved across the dock and finally loaded onto outbound trucks, which immediately leave the terminal towards their next destination in the distribution chain. Accordingly, a cross dock is a consolidation point in a distribution network, where multiple smaller shipments can be merged to full truck loads in order to realize economies in transportation. In this context, the truck scheduling problem, which decides on the succession of truck processing at the dock doors, is especially important to ensure a rapid turnover and on-time deliveries. Due to its high real-world significance, several truck scheduling procedures have been introduced during recent years, which all treat specific cross dock settings. In order to structure and promote scientific progress, this paper introduces a classification of deterministic truck scheduling. With the help of this classification, existing literature is reviewed and future research needs are identified. Moreover, we represent a yet unexplored class of truck scheduling problems which is highly relevant in real-world distribution networks.     

Real-time scheduling and control of one-of-a kind production

Due to the great diversity of product types in one-of-a-kind production (OKP), the production scheduling and control in OKP is much more difficult than production scheduling and control of other production systems, e.g. mass production and batch production. Hence, the production efficiency in OKP companies is relatively lower. To improve productivity in OKP, a dynamic hierarchy production control system is presented. Using this control structure, a production system in an OKP company can be flexibly organized or re-organized according to the structure of a customized product (or an OKP product). Production synchronizing and scheduling algorithms for OKP shop floor production control are presented. Using these algorithms, a cybernetic model can be developed for shop floor control in OKP. The algorithms are applied to two alternate production scheduling goals in OKP, namely ASAP (as soon as possible) production and JIT (just in time) production.