Tight bounds for the identical parallel machine-scheduling problem: Part II

A companion paper introduces new lower bounds and heuristics for the problem of minimizing makespan on identical parallel machines. The objective of this paper is threefold. First, we describe further enhancements of previously described lower bounds. Second, we propose a new heuristic that requires solving a sequence of 0–1 knapsack problems. Finally, we show that embedding these newly derived bounds in a branch‐and‐bound procedure yields a very effective exact algorithm. Moreover, this algorithm features a new symmetry‐breaking branching strategy. We present the results of computational experiments that were carried out on a large set of instances and that attest to the efficacy of the proposed algorithm. In particular, we report proven optimal solutions for some benchmark problems that have been open for some time.     

综合模块选择、资源共享与任务调度的SoC设计方案搜索算法

在SoC系统的设计中,设计方案将直接决定最终系统的性能和成本.提出一种综合模块选择、资源共享与任务调度的设计方案搜索算法.该算法巧妙地将模块选择、共享方案的搜索与表调度融合在一个分支定界过程中,严格搜索表调度策略下的最优设计方案;将搜索与调度同时进行,具有较快的搜索速度.对多种不同规模的任务图进行测试,并与现有方法进行实验对比的结果表明,对于中小规模的系统设计,该算法能够在很短的时间内找到设计空间中的最优方案.     

面向突发事件的应急资源调度模型的构建和求解

针对突发事件发生后存在多个事故、应急资源有限的情况,提出了基于非合作博弈的应急资源调度模型和算法。在该调度模型中,各个事故点被视为博弈模型的局中人,可能的资源调度方案映射为策略集,将应急资源的调度问题转化为对非合作博弈调度模型的Nash均衡点求解问题,并对基本蚁群算法进行了改进,嵌入了遗传算法的交叉操作和变邻域搜索策略,将其应用于求解该博弈模型的Nash均衡解。最后通过算例测试验证了模型和算法的有效性和可行性。     

A case of rule-based heuristics for scheduling hot rolling seamless steel tube production

Abstract: A production scheduling problem for hot rolling seamless steel tube at Tianjin Pipe Corporation of China is studied. Considering the complexity of the problem and the acceptable time for solving it, a rule-based heuristic approach is proposed and implemented. The proposed approach is a bottleneck scheduling method and considers simultaneously all production processes in three production units and 'optimizes' them as a whole. Additionally, the running result shows, on average, that a 3% increase in throughput and a 5% reduction in late deliveries have been achieved since the system implementation.     

炼钢-连铸生产启发式调度方法

实际炼钢–连铸生产存在着多阶段、多并行机,以及在精炼阶段具有多重精炼方式,从而大大增加了炼钢–连铸生产调度难度.目前已有的炼钢–连铸生产调度研究由于仅仅针对简单生产方式而难以应用于目前大型炼钢–连铸生产调度.而实际生产过程中的以人工为主的调度方法速度慢、优化程度低,极易造成炉次在设备间的冗余等待时间过长,导致钢水温度下降,甚至造成连铸断浇事故.本文针对中国宝钢某大型炼钢厂的多重精炼方式且存在着可重入调度下的炼钢–连铸生产调度问题进行研究,提出了多种调度顺序方法和设备指派方法,通过仿真实验对多种调度顺序方法和多种设备指派方法组合而成的各种启发式方法进行了研究.最后将本文提出的性能最好的启发式方法应用于该大型炼钢厂的炼钢–连铸生产调度,钢水平均日冗余等待时间得到显著降低.     

Scheduling a hybrid flowshop with batch production at the last stage

In this paper, we address the problem of scheduling n$n$ jobs in an s$s$-stage hybrid flowshop with batch production at the last stage with the objective of minimizing a given criterion with respect to the completion time. The batch production at stage s$s$ is referred to as serial batches by Hopp and Spearman where the processing time of a batch is equal to the sum of the processing times of all jobs included in it. This paper establishes an integer programming model and proposes a batch decoupling based Lagrangian relaxation algorithm for this problem. In this algorithm, after capacity constraints are relaxed by Lagrangian multipliers, the relaxed problem is decomposed based on a batch, unlike the commonly used job decoupling, so that it can be decomposed into batch-level subproblems, each for a specific batch. An improved forward dynamic programming algorithm is then designed for solving these subproblems where all operations within a batch form an in-tree structure and the precedence relations exist not only between the operations of a job but between the jobs in this batch at the last stage. A computational comparison is provided for the developed algorithm and the commonly used Lagrangian relaxation algorithm which, after capacity constraints and precedence relations within a batch are relaxed, decomposes the relaxed problem into job-level subproblems and solves the subproblems by using dynamic programming. Numerical results show that the designed Lagrangian relaxation method provides much better schedules and converges faster for small to medium sized problems, especially for larger sized problems.     

生产调度理论和方法研究综述

生产调度理论与方法研究是非常困难的课题,但是对企业或行业提高生产效率和效益是至关重要的,特别是在当前市场经济时代,生产调度理论和方法的研究已经有50多年的历史,但是经典调度理论和实际调度问题之间仍然存在着鸿沟。针对这一特点,指出了当前实际生产调度存在的一些问题和需要考虑的各种因素,例举了主要的生产调度方法和典型应用,指出了各种方法的优缺点。最后,总结并提出了生产调度理论和方法的未来研究方向和今后工作的建议。     

面向炼钢—连铸调度过程的两阶段优化模型与算法

以某钢厂多台转炉及多台精炼炉对多台连铸机的复杂生产线为研究对象,针对其调度过程涉及多设备、多目标、多约束等调度要素,且离散和连续变量混杂,采用常规建模方法难以满足现场对调度的精度及排产速度的需求问题,提出一种新型的两阶段优化建模方法.首先,证明了炉次从炼钢到连铸总等待时间最小的调度目标与该炉次在转炉开始作业时间最大是等价的事实,并以离散型的设备变量为决策变量,以转炉开始作业时间最大为动态规划最优指标,建立设备指派多阶段动态规划基本方程和设备指派优化模型;然后,以炉次在设备开始作业时间的连续型变量为决策变量,并将准时开浇的非线性调度指标转化成与之等价的线性优化目标,以在同一台连铸机上浇铸的炉次之间断浇的时间间隔最小、钢包在设备之间的冗余等待时间最小、提前与滞后理想开浇时间的时间间隔最小为目标,建立线性规划冲突解消模型.工业实验表明所提出两阶段优化建模方法在求解速度与求解精度均满足现场要求.     

基于一体化生产的炼钢一连铸批量计划与调度

基于钢铁企业一体化生产,建立了炼钢—连铸区段炉次和浇次批量计划模型,并通过禁忌搜索算法对模型进行了求解.之后,归纳出了A钢厂3座转炉、6台精炼设备(双工位RH设备3台,CAS设备2台,双环LF设备1台)、3台连铸机流程配置下静态调度的基本原则.最后,提出了一体化生产下炼钢—连铸区段动态调度的策略,并采用规则、算法、数学模型与人机交互相结合的方法解决炼钢一连铸动态调度问题,仿真实验结果表明了此方法的可行性.     

生产作业计划仿真优化研究

将仿真技术和遗传算法相结合,根据生产车间的资源情况、优化目标等建立了生产调度仿真模型,然后对仿真输出结果进行统计,针对统计结果应用遗传算法对调度决策进行优化。仿真优化结果说明了该集成优化方法是有效性的。     

AJ—System生产作业调度系统的柔性设计及其实现

从柔性设计的角度出发,围绕一个具体的机械加工车间,详细阐述了AJ-System系统的柔性设计方法,并简单介绍了系统的框架及其应用。这种柔性设计方法也为其它相关系统的开发提供借鉴。     

间歇过程生产调度建模的研究

生产调度是为实现某一目的而对共同使用的资源进行时间上的分配.调度中存在大量的模糊因素,将模糊的思想运用到调度领域可以帮助决策者进行有效决策.本文提出一种基于模糊规划的间歇过程生产调度建模方法及其模糊优化的新算法.应用模糊集合论的方法,在已有模糊规划模型的基础上,针对间歇生产过程,分析调度中存在的模糊信息以及出现的形式和方式,将确定型生产调度模型的约束条件和目标方程中的参数模糊化,采用非精确的量化形式,以隶属函数来表示,建立基于模糊参数的生产调度模糊线性规划模型MIFCLP.通过对一个调度问题实例进行了仿真,仿真结果证明,采用模糊模型更容易得到可行解,采用模糊线性规划解决间歇生产调度问题是一种有效方法.     

啤酒生产调度数学模型及其优化

针对啤酒企业生产人工调度效果不理想的问题,建立了啤酒生产调度数学模型,并研究了此类间歇工业调度问题的优化方法.根据啤酒生产流程特点,将整个啤酒生产划分为糖化区、过滤包装区,分别建立相应的生产调度数学规划模型,并通过蚁群优化算法求解此类调度问题.该优化调度方案在企业中的应用结果表明,通过蚁群算法对建立的啤酒调度模型进行优化,该方法具有良好的鲁棒性与实用性,可为生产管理人员提供方便快捷的优化解决方案.     

神经网络在柔性生产线动态生产调度中的应用研究

把多条柔性生产线、多种产品的动态生产调度(MMDPS)问题归结为一混合非线性整数规则问题.基于神经网络优化计算原理,设计了求解MMDPS问题的连续时间动态神经网络模型,并给出了仿真结果.     

基于规则的烟草计划与排产系统

为提高烟草行业计划排产的实时性, 提出了符合卷烟生产特点的生产计划与调度系统, 并阐述了生产计划与调度系统的体系结构、功能模块、系统工作流程, 设计了基于规则的调度算法. 所设计的系统能够持续稳定的运行, 企业客户可应用本系统软件快速准确地根据销售合同和调度计划制定科学合理的生产调度计划, 真正实现管理与控制一体化操作.     

基于改进型批决策与调度建模的生产计划调度系统的研究

热轧型钢生产工艺复杂,其生产中极易出现由于计划调度安排不当而产生的交货期延误、库存超负荷等问题。针对以上问题研究设计了MES生产计划调度系统,改进了批决策调度策略用于数学建模,利用自适应遗传算法求解生产调度计划。以此为基础,为某热轧企业设计实现了生产计划调度系统,并通过真实的热轧型钢订单、原料、设备等数据,对模型改进前后的计划编制方法进行模拟与比较,验证了利用该改进型批决策与调度模型编制的热轧型钢生产调度计划可节省生产时间、降低设备调度时间,以此来指导热轧型钢的生产可切实减少交货延误和减少库存占用率,并提高企业利润率。     

一种启发式算法求解批量计划和排序集成问题

文章针对基于JIT思想建立的一种批量计划和作业排序集成问题,建立整体模型,设计了一种启发式算法采用集成方法求求解。针对问题的特点和遗传算法的特性,各层优化时均采用遗传算法求解,借鉴递阶优化方法的思想,首先从优化作业排序层出发,将其优化结果作为约束来优化批量计划层,然后利用利用批量优化的结果再重新来协调优化作业排序层,进而进一步去求解更好的批量计划。基于这种协调传递的思想,使各层的优化形成一个闭环,直到满足循环终止条件,得到比较理想的结果。最后通过算例试验表明,这种启发式算法与采用整体求解方法相比,具有比较满意的寻优性能和收敛速度。     

不确定环境下生产项目调度研究综述与展望*

调度优化是企业生产项目管理的重要内容,然而各种不确定因素的存在导致在确定性条件假设下得到的“最优”调度方案往往变得“次优”,甚至不可实施。本文综述了不确定环境下生产项目调度的研究现状,分析了生产项目调度过程中存在的各种不确定性,阐述了不确定因素的起因与分类、不确定因素的描述方法,详细探讨了不确定环境下生产项目调度方案的求解与优化方法,以及项目调度方案的评价指标,并指出了该领域面临的挑战和有待进一步研究的问题。     

批量生产企业的车间计划调度算法研究与应用

分析了批量生产企业车间计划调度问题的资源、任务和活动,讨论了车间计划调度的约束及其实现,给出了基于复合规则的计划调度算法,在西安航空发动机公司32车间的计划管理系统中得到了应用。