冷轧多机组合同优化排产模型及算法(上)

为解决钢铁冷轧多机组的排产问题,建立了一个实现合同生产计划和作业调度的整体优化模型。模型以最小化各机组合同延期惩罚和生产类型切换虚拟成本为优化目标。首先,针对上下游机组的物流平衡及保证交货期问题,根据合同钢卷在生产流程各机组间的传递构造基于时间窗的推理算法,确定钢卷的合理加工范围。在传递时间窗下各机组生产调度可以不必考虑机组的前驱约束。然后,根据合同交货期、产品种类以及工艺约束等将合同钢卷在各机组划分为不同的粗计划类型。同一类型粗计划合同钢卷的批次作业调度可以归结为多约束无返回多旅行商问题,通过一种启发式分组蚁群算法优化求解。最后,将机组的粗计划合同调度抽象为带时间窗旅行商问题,采用一种改进的自适应蚁群算法求解。通过现场实际数据试运行,结果表明所建模型与算法是有效可行的,为冷轧企业多机组的合同计划和调度提供了合理指导。     

加热炉工序的配置与调度优化研究

针对某不锈钢和碳钢的混合型板带钢厂,分析了板坯连铸-轧钢各个关键工序的出坯节奏和年产能力,得出非专用加热炉最优配置数量为3座;为了实现板坯连铸-轧钢工序的协同、高效运行,研究了加热炉群的调度问题,运用改进的遗传算法对加热炉群调度模型进行求解,得出优化的调度方案。研究结果表明：通过对加热炉工序的配置与加热炉群调度优化进行综合研究,得到单块板坯在加热炉外的平均等待时间可减少20min以上,热送热装率提高8%以上。     

多代理机制在炼钢连铸排程中的应用研究

针对大型冶金企业中多座转炉对多台铸机生产时炼钢连铸的排程难题,提出利用多代理机制的排程方法来解决这一问题.利用某企业的设备和工艺参数建立基于多代理机制的炼钢连铸排程仿真模型,研究了模型的构成、排程算法和排程优化策略,然后用实际的生产计划数据进行测试,排程结果完全满足实际生产需求.优化结果同时可给出生产作业顺序、工艺路线和生产时刻等,测试结果证明了该方法的有效性和适用性.     

Use of Genetic Algorithms in Resource Scheduling of Construction Projects

This paper presents an augmented Lagrangian genetic algorithm model for resource scheduling. The algorithm considers scheduling characteristics that were ignored in prior research. Previous resource scheduling formulations have primarily focused on project duration minimization. Furthermore, resource leveling and resource-constrained scheduling have traditionally been solved independently. The model presented here considers all precedence relationships, multiple crew strategies, total project cost minimization, and time-cost trade-off. In the new formulation, resource leveling and resource-constrained scheduling are performed simultaneously. The model presented uses the quadratic penalty function to transform the resource-scheduling problem to an unconstrained one. The algorithm is general and can be applied to a broad class of optimization problems. An illustrative example is presented to demonstrate the performance of the proposed method.     

钢坯热轧加热炉区生产调度模型与算法

钢坯热轧加热炉区生产调度属于组合优化中的NP-complete问题.本文根据加热炉区生产特点建立了分别以生产能耗最小化和加热质量最优化为主次目标的钢坯加热炉区调度数学模型,将其归结为布尔可满足性问题,构造了采用二进制编码方式的遗传禁忌搜索算法进行求解.基于实际生产数据的模拟优化结果表明,该模型和求解方法充分满足了现场加热炉区生产调度的需求,在满足生产工艺约束的前提下,缩短了生产时间,提高了钢坯入炉温度和加热质量,与传统人工调度方法的结果相比具有更好的节能、高产效果.      

Model based scheduling of a continuous annealing furnace

Abstract

The operational complexities and process constraints of an industrial continuous annealing operation invariably lead to empirically designed process cycles as well as manual scheduling practices. This methodology often results in suboptimal and inefficient operations. An integrated approach is presented here for maximising the productivity of a continuous furnace, where bundles of steel rods are annealed. For this purpose, a scheduling algorithm is proposed, which is coupled with a process model. The phenomenological process model is based on heat transfer and annealing kinetics. The scheduling algorithm is formulated to analyse the continuous annealing furnace under different operating conditions. The advantage of coupling the scheduling algorithm to the process model in enhancing productivity has been illustrated. Furthermore, it is shown that optimising the bundle diameter at a constant hearth speed is favourable for frequent dispatches of the product, whereas for less frequent dispatches, it is more efficient to vary the hearth speed.     

Resource-Activity Critical-Path Method for Construction Planning

In this paper, a practical method is developed in an attempt to address the fundamental matters and limitations of existing methods for critical-path method (CPM) based resource scheduling, which are identified by reviewing the prior research in resource-constrained CPM scheduling and repetitive scheduling. The proposed method is called the resource-activity critical-path method (RACPM), in which (1) the dimension of resource in addition to activity and time is highlighted in project scheduling to seamlessly synchronize activity planning and resource planning; (2) the start/finish times and the floats are defined as resource-activity attributes based on the resource-technology combined precedence relationships; and (3) the “resource critical” issue that has long baffled the construction industry is clarified. The RACPM is applied to an example problem taken from the literature for illustrating the algorithm and comparing it with the existing method. A sample application of the proposed RACPM for planning a footbridge construction project is also given to demonstrate that practitioners can readily interpret and utilize a RACPM schedule by relating the RACPM to the classic CPM. The RACPM provides schedulers with a convenient vehicle for seamlessly integrating the technology/process perspective with the resource use perspective in construction planning. The effect on the project duration and activity floats of varied resource availability can be studied through running RACPM on different scenarios of resources. This potentially leads to an integrated scheduling and cost estimating process that will produce realistic schedules, estimates, and control budgets for construction.     

Optimizing Resource Utilization for Repetitive Construction Projects

Optimizing resource utilization can lead to significant reduction in the duration and cost of repetitive construction projects such as highways, high-rise buildings, and housing projects. This can be achieved by identifying an optimum crew size and interruption strategy for each activity in the project. Available dynamic programming formulations can be applied to provide solutions for this optimization problem; however, their application is limited, as they require planners to specify an arbitrary and an unbounded set of interruption options prior to scheduling. Such a requirement is not practical and may render the optimization problem infeasible. To circumvent the limitations of available formulations, this paper presents an automated and practical optimization model. The model utilizes dynamic programming formulation and incorporates a scheduling algorithm and an interruption algorithm so as to automate the generation of interruptions during scheduling. This transforms the consideration of interruption options, in optimizing resource utilization, from an unbounded and impractical problem to a bounded and feasible one. A numerical example from the literature is analyzed to illustrate the use and capabilities of the model.     

基于MAS的分布式棒线材轧制在线生产调度系统

针对棒线材生产的不确定性和复杂性,提出了基于多智能体分布式在线生产调度系统（MDOPS）方案,给出了系统总体结构,建立了精轧工序轧制批量调度的数学模型,其中考虑了轧机的维护约束等实际应用约束,采用混合局部搜索的自适应遗传算法进行求解,描述了进化计算、专家系统、启发式规则和人机交互相结合的生产调度计划集成化实现方法,并应用到实际棒线材实时调度中。现场实际运行结果表明,该系统可快速准确收集生产实绩数据,完成生产过程在线监视,编制出符合现场情况、满足工艺要求的高效生产调度计划。     

炼钢?连铸生产调度的研究进展

针对炼钢?连铸过程的生产调度问题,首先,对生产调度问题的研究方法进行了总结和评述,梳理了各类方法的特点及适用范围;其次,介绍了当前国内外钢厂典型计算机辅助调度系统的一些案例,并讨论分析其特点;最后,在以往研究的基础上,对未来炼钢?连铸过程生产调度问题的研究思路和方法提出了建议,针对静态调度提出了“规则+算法”的研究思路,以国内某特钢厂为例,提出了基于钢厂生产模式优化的调度模型构建方法;针对动态调度提出“多工序协同”的研究思路,提出了基于多智能体的炼钢?连铸过程多工序工艺、质量与调度的协同控制的研究方法。优化高效的建模及求解方法是解决生产调度问题的重要手段之一,旨在改善当前钢厂生产计划编制水平、提高生产计划的可执行性、加强现场实时调控,对实现炼钢?连铸过程稳定化、有序化、连续化运行具有重要意义。      

聚合分期算法在露天矿中长期生产计划编制中的应用

露天矿中长期生产计划是在最终境界的基础上确定矿块的开采顺序,以获得最大的总净现值。采用整数规划的方法来求解露天矿生产计划编制问题（OPSP）时,由于实际矿山最终境界内矿块个数太多,构建整数规划模型需要大量的二进制变量,超出了现有求解器的能力,使得问题无法求解。针对这一问题提出矿块聚合和分期求解相结合的启发式算法：将空间上n3个相邻矿块聚合,然后通过启发式方法,分期次逐渐求解、逐步迭代、更新模型,以减少模型变量和约束。利用VC++编程并调用CPLEX求解器实现该算法,应用于某铜矿,实现了长期计划的自动编制。结果表明：该算法能够显著减少用整数规划法求解OPSP时的变量个数,成百倍地提高解算效率,在较短的解算时间之内得到较优的结果,解决了OPSP因变量规模太大而无法求解的问题,并且能够较好地应用于各种规模矿山的实际生产计划编制工作。     

多目标多约束混合流水车间插单重调度问题研究

研究了多目标多阶段混合流水车间的紧急订单插单重调度问题，综合考虑工件批量、刀具换装时间、运输能力等约束。先以最小化订单完工时间和最小化总运输时间为双目标建立静态初始订单调度模型，再针对紧急订单插单干扰，增加最小化总加工机器偏差值目标，建立三目标重调度优化模型，并分别用NSGA-II算法与融合基于事件驱动的重调度策略和重排插单策略的NSGA-III算法对两个模型进行求解。最后，以某实际船用管类零件生产企业为案例，先对NSGA-II算法和NSGA-III算法的性能进行评估，得到NSGA-II算法更适用于解决双目标优化问题而NSGA-III算法在解决三目标优化问题时表现更优的结论，再将所建模型与所提算法应用于该企业的十组插单案例中，所得优化率接近三分之一，验证了实用性和有效性。      

作业车间调度问题解的不可行性检测算法和快速修复算法

为了判别作业车间调度问题的解的可行性,提出了一种基于图论的启发式判别算法,并通过实例验证了方法的正确性.提出了普适于作业车间调度问题的快速修补新算法,可以对于作业车间调度问题的不可行解进行修正使之变成可行解.判别算法和修补算法在最不利情形下的计算复杂性均为O(n),判别算法在最有利情形下的计算复杂性为O(2 |J|+|M|).所提出的算法具有很大的灵活性,对于局部蚂蚁算法、遗传算法以及一般的作业车间调度问题均适用.     

Evaluation of a Genetic Algorithm for the Irrigation Scheduling Problem

A typical irrigation scheduling problem is one of preparing a schedule to service a group of outlets which may be serviced simultaneously. This problem has an analogy with the classical earliness/tardiness problem in operations research. In previously published work an integer program was used to solve this problem, however such scheduling problems belong to a class of combinatorial problems known to be computationally demanding (N-P hard). This is widely reported in operations research. Hence integer programs can only be used to solve relatively small problems usually in a research environment where considerable computational resources and time can be allocated to solve a single schedule. For practical applications metaheuristics such as genetic algorithms, simulated annealing, or tabu search methods need to be used. However as reported in the literature, these need to be formulated carefully and tested thoroughly. This paper demonstrates the importance of robust testing of one such genetic algorithm formulated to solve the irrigation scheduling problem with simultaneous outlets serviced against an integer program formulated to solve the same problem.     

Permutation-Based Elitist Genetic Algorithm for Optimization of Large-Sized Resource-Constrained Project Scheduling

The resource-constrained project scheduling problem (RCPSP) has received the attention of many researchers because its general model can be used in a wide variety of construction planning and scheduling applications. The exact procedures and priority-rule-based heuristics fail to search for the optimum solution to the RCPSP of large-sized project networks in a reasonable amount of time for successful application in practice. This paper presents a permutation-based elitist genetic algorithm for solving the problem in order to fulfill the lack of an efficient optimal solution algorithm for project networks with 60 activities or more as well as to overcome the drawback of the exact solution approaches for large-sized project networks. The proposed algorithm employs the elitist strategy to preserve the best individual solution for the next generation so the improved solution can be obtained. A random number generator that provides and examines precedence feasible individuals is developed. A serial schedule generation scheme for the permutation-based decoding is applied to generate a feasible solution to the problem. Computational experiments using a set of standard test problems are presented to demonstrate the performance and accuracy of the proposed algorithm.     

基于粒子群优化算法的钢铁企业铁路车辆调度

给出了求解铁路车辆调度问题的粒子群算法流程;分析了求解不同调度问题的3种粒子表示法,即基于粒子位置次序(Particle Position Sequence,PPS)的粒子表示法、基于粒子位置取整操作(Particle Position Rounding off,PPR)的粒子表示法和基于PPS PPR的混合粒子表示法;讨论了PPS PPR混合粒子表示法与调度解空间的映射关系和解码方法。将第3种方法应用于实际车辆调度系统中,求解出机车送货作业行驶的最短路径,建立了基于粒子群优化算法的企业铁路优化调度模型。     

基于粒子群优化算法的钢铁企业铁路车辆调度

给出了求解铁路车辆调度问题的粒子群算法流程;分析了求解不同调度问题的3种粒子表示法,即基于粒子位置次序(Particle Position Sequence,PPS)的粒子表示法、基于粒子位置取整操作(Particle Position Rounding off,PPR)的粒子表示法和基于PPS PPR的混合粒子表示法;讨论了PPS PPR混合粒子表示法与调度解空间的映射关系和解码方法。将第3种方法应用于实际车辆调度系统中,求解出机车送货作业行驶的最短路径,建立了基于粒子群优化算法的企业铁路优化调度模型。     

基于深度强化学习的炼钢车间天车调度方法

针对炼钢车间天车任务产生的动态不确定性,提出了基于深度强化学习算法的炼钢车间天车调度方法。首先,基于强化学习将天车调度问题转化为对天车操作动作序列的求解,采用DQN(Deep Q-network)算法构建动作价值网络模型进行求解;然后,以某钢厂出钢跨天车调度为研究对象,以任务完成总时间最短为目标,介绍了基于深度强化学习的天车调度方法的具体设计;最后,采用实际数据对天车动作价值网络模型进行训练,与目前现场广泛使用的基于固定分区的天车调度方案进行仿真试验对比。结果表明,基于深度强化学习的天车调度方法在任务完成总时间上减少了11.52%,提高了天车任务的完成效率,说明了方法的可行性和优化性,为天车调度研究提供了新的思路。     

Work Continuity Constraints in Project Scheduling

Repetitive projects involve the repetition of activities along the stages of the project. Since the resources required to perform these activities move from one stage to the other, a main objective of scheduling these projects is to maintain the continuity of work of these resources so as to minimize the idle time of resources. This requirement, often referred to as work continuity constraints, involves a tradeoff between total project duration and the resource idle time. The contribution of this paper is threefold. First, we provide an extensive literature summary of the topic under study. Although most research papers deal with the scheduling of construction projects, we show that this can be extended to many other environments. Second, we propose an exact search procedure for scheduling repetitive projects with work continuity constraints. This algorithm iteratively shifts repeating activities further in time in order to decrease the resource idle time. We have embedded this recursive search procedure in a horizon-varying algorithm in order to detect the complete tradeoff profile between resource idle time and project duration. The procedure has been coded in Visual C++ and has been validated on a randomly generated problem set. Finally, we illustrate the concepts on three examples. First, the use of our new algorithm is illustrated on a small fictive problem example from literature. In a second example, we show that work continuity constraints involve a tradeoff between total project duration and the resource idle time. A last example describes the scheduling of a well-known real-life project that aims at the construction of a tunnel at the Westerschelde in The Netherlands.     

基于混合整数规划法的自然崩落法放矿计划优化

放矿计划是自然崩落法矿山生产过程中最重要的环节.针对传统手工编制放矿计划随意性大及出矿品位不均衡,在对其进行科学系统的分析基础上,本文运用混合整数规划法解决自然崩落法放矿计划优化问题.以计划期内与目标品位偏差最小为目标函数,综合考虑矿量、品位、放矿速率、崩落指数、排产指数等约束条件,构建放矿计划优化的混合整数规划模型,并在MATLAB环境下用YALMIP编写模型语言调用CPLEX求解器进行求解,使品位波动降低18%,进而得到最优短期放矿计划方案.经实例验证,此方法科学可行,对充分发挥自然崩落法的优越性和提高矿产资源的回收率具有重要的理论和现实意义.