基于预测与分解策略的大规模炼油过程生产调度算法

炼油生产调度为混合整数规划问题,随着规模的增大,其求解时间随问题规模呈指数增加,使得大规模长周期炼油生产调度问题难以在合理的时间内求解.针对该问题,本文提出了一种基于生产任务预测与分解策略的炼油生产调度算法,该算法能在短时间内获得大规模调度问题的满意解.所提算法将原问题沿时间轴分解为若干个调度时长相同的单时间段子问题,并设计了基于深度学习的单时间段生产任务(组分油产量)预测模型,用于协调子问题的求解.其中,生产任务预测模型通过易于获得的小规模问题的全局最优调度方案训练得到.最后,通过与商业求解器Cplex以及现有算法的对比,实验结果表明了所提算法的有效性.     

大规模流水线调度的瓶颈分解算法研究

为了克服大规模流水线调度问题的计算复杂度,提出一种瓶颈分解启发式算法．利用瓶颈特性将流水线分解为瓶颈机和非瓶颈机,对瓶颈机建立带有到达时间和传递时间约束的单机调度模型,并优化求解,而在非瓶颈机上则采用简单的分派规则,通过不断修正瓶颈机上工件的到达时间和传递时间来协调瓶颈机与非瓶颈机之间的关联．仿真结果验证了算法的有效性．     

The total completion time open shop scheduling problem with a given sequence of jobs on one machine

This paper addresses the open shop scheduling problem to minimize the total completion time, provided that one of the machines has to process the jobs in a given sequence. The problem is NP-hard in the strong sense even for the two-machine case. A lower bound is derived based on the optimal solution of a relaxed problem in which the operations on every machine may overlap except for the machine with a given sequence of jobs. This relaxed problem is NP-hard in the ordinary sense, however it can be quickly solved via a decomposition into subset-sum problems. Both heuristic and branch-and-bound algorithm are proposed. Experimental results show that the heuristic is efficient for solving large-scaled problems, and the branch-and-bound algorithm performs well on small-scaled problems.Scope and purposeShop scheduling problems, widely used in the modeling of industrial production processes, are receiving an increasing amount of attention from researchers. To model practical production processes more closely, additional processing restrictions can be introduced, e.g., the resource constraints, the no-wait in process requirement, the precedence constraints, etc. This paper considers the total completion time open shop scheduling problem with a given sequence of jobs on one machine. This model belongs to a new class of shop scheduling problems under machine-dependent precedence constraints. This problem is NP-hard in the strong sense. A heuristic is proposed to efficiently solve large-scaled problems and a branch-and-bound algorithm is presented to optimally solve small-scaled problems. Computational experience is also reported.     

Dual constrained single machine sequencing to minimize total weighted completion time

We study a single-machine sequencing problem with both release dates and deadlines to minimize the total weighted completion time. We propose a branch-and-bound algorithm for this problem. The algorithm exploits an effective lower bound and a dynamic programming dominance technique. As a byproduct of the lower bound, we have developed a new algorithm for the generalized isotonic regression problem; the algorithm can also be used as an O(nlogn)-time timetabling routine in earliness-tardiness scheduling. Extensive computational experiments indicate that the proposed branch-and-bound algorithm competes favorably with a dynamic programming procedure. Note to Practitioners-Real-life production systems usually involve multiple machines and resources. The configurations of such systems may be complex and subject to change over time. Therefore, model-based solution approaches, which aim to solve scheduling problems for specific configurations, will inevitably run into difficulties. By contrast, decomposition methods are much more expressive and extensible. The single-machine problem and its solution procedure studied in this paper will prove useful to a decomposition method that decomposes multiple-machine, multiple-resource scheduling problems into a number of single-machine problems. The total weighted completion time objective is relevant to production environments where inventory levels and manufacturing cycle times are key concerns. Future research can be pursued along two directions. First, it seems to be necessary to further generalize the problem to consider also negative job weights. Second, the solution procedure developed here is ready to be incorporated into a machine-oriented decomposition method such as the shifting bottleneck procedure.     

A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times

This paper examines the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times, time windows, machine eligibility and preference constraints. Such problems are quite common in the semiconductor manufacturing industry. In particular, this paper pays special attention to the chipset production in the semiconductor Assembly and Test Manufacturing (ATM) factory and constructs a Mixed Integer Programming (MIP) model for the problem. The primal problem is decomposed into a lot-sizing subproblem and a set of single-machine scheduling subproblems by Lagrangian decomposition. A Lagrangian-based heuristic algorithm, which incorporates the simulated annealing algorithm aimed at searching for a better solution during the feasibility construction stage, is proposed. Computational experiments show that the proposed hybrid algorithm outperforms other heuristic algorithms and meets the practical requirement for the tested ATM factory.     

面向多目标流水车间调度的多种群多目标遗传算法

针对制造型企业普遍存在的流水车间调度问题,建立了以最小化最迟完成时间和总延迟时间为目标的多目标调度模型,并提出一种基于分解方法的多种群多目标遗传算法进行求解.该算法将多目标流水车间调度问题分解为多个单目标子问题,并分阶段地将这些子问题引入到算法迭代过程进行求解.算法在每次迭代时,依据种群的分布情况选择各子问题的最好解及与其相似的个体分别为当前求解的子问题构造子种群,通过多种群的进化完成对多个子问题最优解的并行搜索.通过对标准测试算例进行仿真实验,结果表明所提出的算法在求解该问题上能够获得较好的非支配解集.     

基于模型分解的多机带时间窗口任务规划算法

针对多机带时间窗口任务规划问题,提出了基于模型分解的规划求解算法。通过引入基于逻辑的Benders分解方法,将经典Benders分解算法应用扩展至带离散时间窗口的混合线性整数规划模型,实现模型分解。采用工艺级商业软件MOSEK与GECODE分别求解主、子问题,同时给出Benders剪枝函数生成方法,以迭代方式收敛解空间获得可行解。实现算法并设计测试案例,实验结果验证了算法的有效性。     

Hybrid probabilistic-harmony search algorithm methodology in generation scheduling problem

This paper attempts to propose a fair solution in generation scheduling problem in the presence of inherent uncertainties in short-term power system operation. The proposed methodology incorporates probabilistic methodology in the uncertainties representation section, while harmony search algorithm is adopted as a fast and reliable soft computing algorithm to solve the proposed nonlinear, non-convex, large-scaled and combinatorial problem. As an indispensable step towards a more economical power system operation, the optimal generation scheduling strategy in the presence of mixed hydro-thermal generation mix, deemed to be the most techno-economically efficient scheme, comes to the play and is profoundly taken under concentration in this study. This paper devises a comprehensive hybrid optimisation approach by which all the crucial aspects of great influence in the generation scheduling process can be accounted for. Two-point estimation method is also adopted probabilistically approaching the involved uncertain criteria. In the light of the proposed methodology being implemented on an adopted test system, the anticipated efficiency of the proposed method is well verified.     

一种求解多处理机调度问题的a-平坦化调度算法

在分析多处理机调度问题的基础上,提出了α-平坦的概念,并将其引入到多处理机调度问题中;基于此,提出了一种新的基于α-平坦的求解多处理机调度问题的算法。算法首先对作业集合做平坦化处理,然后再对处理后所得的新问题进行求解,最终获得原调度问题的一个近似解。实验结果表明,通过该算法可以求得较好的结果,相对于其它启发式算法,该算法具有较好的稳定性。     

A decomposition based hybrid heuristic algorithm for the joint passenger and freight train scheduling problem

We study the joint problem of scheduling passenger and freight trains for complex railway networks, where the objective is to minimize the tardiness of passenger trains at station stops and the delay of freight trains. We model the problem as a mixed integer program and propose a two-step decomposition heuristic to solve the problem. The heuristic first vertically decomposes the train schedules into a passenger train scheduling phase and then a freight train scheduling phase. In the freight train scheduling phase, we use a train-based decomposition to iteratively schedule each freight train. Experimental results show the efficiency and quality of the proposed heuristic algorithm on real world size problems.     

A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles

We address a bilevel decomposition algorithm for solving the simultaneous scheduling and conflict-free routing problems for automated guided vehicles. The overall objective is to minimize the total weighted tardiness of the set of jobs related to these tasks. A mixed integer formulation is decomposed into two levels: the upper level master problem of task assignment and scheduling; and the lower level routing subproblem. The master problem is solved by using Lagrangian relaxation and a lower bound is obtained. Either the solution turns out to be feasible for the lower level or a feasible solution for the problem is constructed, and an upper bound is obtained. If the convergence is not satisfied, cuts are generated to exclude previous feasible solutions before solving the master problem again. Two types of cuts are proposed to reduce the duality gap. The effectiveness of the proposed method is investigated from computational experiments.     

基于Map-Reduce模型的云资源调度方法研究

为提高Map-Reduce模型资源调度问题的求解效能,分别考虑Map和Reduce阶段的调度过程,建立带服务质量(QoS)约束的多目标资源调度模型,并提出用于模型求解的混沌多目标粒子群算法。算法采用信息熵理论来维护非支配解集,以保持解的多样性和分布均匀性;在利用Sigma方法实现快速收敛的基础上,引入混沌扰动机制,以提高种群多样性和算法全局寻优能力,避免算法陷入局部最优。实验表明,算法求解所需的迭代次数少,得到的非支配解分布均匀。Map-Reduce资源调度问题的求解过程中,在收敛性和解集的多样性方面,所提算法均明显优于传统多目标粒子群算法。     

微电子生产过程调度问题基于指标快速预报的分解算法

微电子生产过程调度问题具有规模大和约束复杂等特点,如菜单、Setup时间和组批约束等,其优化调度具有一定难度.针对以最小化平均流经时间为调度目标的较大规模微电子生产过程调度问题,提出一种基于指标快速预报的分解方法(DM-IFP).首先,通过松弛不可中断约束,设计一种代理方法,即基于机器负载的操作完工时间快速预测方法(CTP-ML);其次,设计基于CTP-ML的问题分解方法,将原问题迭代分解为多个连续交迭的子问题;然后,提出一种基于双信息素的蚁群算法(ACO-D)用于求解分解后的子问题,其全局调度目标采用CTP-ML获取,有效保证了全局优化性能;最后,针对一些不同规模的仿真数据,将所提出方法与一些代表性的算法进行详尽的数值对比,计算结果表明所提出方法在所获解的质量和收敛性上均有改善.     

Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm

The present study investigates the cost concerns of distribution centers and formulates a vehicle routing problem with time window constraints accordingly. Based on the embedded structure of the original problem, a decomposition technique is employed to decompose the original problems to a clustering problem (main problem) and a set of traveling salesman problems (sub-problems) with time window constraints. This decomposition not only reduces the problem size but also enable the use of simpler solution procedures. A genetic algorithm is developed to solve the clustering problem, while a simple heuristic algorithm is formulated to solve the set of traveling salesman problems. The solution of the original problem is obtained through iterative interactions between the main problem and the set of sub-problems. The performance of the proposed approach is compared with the well-known insertion method and a manual scheduling of a distribution center.     

求解多目标流水车间调度Pareto最优解的遗传强化算法

针对多目标流水车间调度Pareto最优问题, 本文建立了以最大完工时间和最大拖延时间为优化目标的多目标流水车间调度问题模型, 并设计了一种基于Q-learning的遗传强化学习算法求解该问题的Pareto最优解. 该算法引入状态变量和动作变量, 通过Q-learning算法获得初始种群, 以提高初始解质量. 在算法进化过程中, 利用Q表指导变异操作, 扩大局部搜索范围. 采用Pareto快速非支配排序以及拥挤度计算提高解的质量以及多样性, 逐步获得Pareto最优解. 通过与遗传算法、NSGA-II算法和Q-learning算法进行对比实验, 验证了改进后的遗传强化算法在求解多目标流水车间调度问题Pareto最优解的有效性.     

基于多任务强化学习的堆垛机调度与库位推荐

堆垛机调度是物流仓储自动化中的重要任务,任务中的出入库效率、货物存放等情况影响仓储系统的整体效益。传统调度方法在面对较大规模调度问题时,因处理大状态空间从而导致性能受限和收益降低。与此同时,库位优化与调度运行联系密切,但现有多数工作在处理调度问题时未能考虑到库位优化问题。为解决仓储中堆垛机调度问题,提出一种基于深度强化学习算法的近端策略优化调度方法。将调度问题视为序列决策问题,通过智能体与环境的持续交互进行自我学习,以在不断变化的环境中优化调度。针对调度中伴生的库位优化问题,提出一种基于多任务学习的调度、库位推荐联合算法,并基于调度网络构建适用于库位推荐的Actor网络,通过与Critic网络进行交互反馈,促进整体的联动和训练,从而提升整体效益。实验结果表明,与原算法模型相比,该调度方法的累计回报值指标平均提升了33.6%,所提的多任务学习的联合算法能有效地应对堆垛机调度和库位优化的应用场景,可为该类多任务问题提供可行的解决方案。     

求解总拖期时间最小化流水车间调度问题的多智能体进化算法

针对总拖期时间最小化的置换流水车间调度问题（Total tardiness permutation flow-shop scheduling problem） 提出了一种基于多智能体的进化搜索算法. 在该算法中,采用基于延迟时间排序的学习搜索策略（Tardiness rank based learning）,快速产生高质量的新个体,并根据概率更新模型进行智能体网格的更新进化. 同时通过实验设计的方法探讨了算法参数设置对算法性能的影响. 为了验证算法的性能,求解了Vallada标准测试集中540个测试问题,并将测试结果与一些代表算法进行比较,验证了该算法的有效性.     

A novel methodology for optimal single mobile robot scheduling using whale optimization algorithm

One of the fundamental requirements for creating an intelligent manufacturing environment is to develop a reliable, efficient and optimally scheduled material transport system. Besides traditional material transport solutions based on conveyor belts, industrial trucks, or automated guided vehicles, nowadays intelligent mobile robots are becoming widely used to satisfy this requirement. In this paper, the authors analyze a single mobile robot scheduling problem in order to find an optimal way to transport raw materials, goods, and parts within an intelligent manufacturing system. The proposed methodology is based on biologically inspired Whale Optimization Algorithm (WOA) and is aimed to find the optimal solution of the nondeterministic polynomial-hard (NP-hard) scheduling problem. The authors propose a novel mathematical model for the problem and give a mathematical formulation for minimization of seven fitness functions (makespan, robot finishing time, transport time, balanced level of robot utilization, robot waiting time, job waiting time, as well as total robot and job waiting time). This newly developed methodology is extensively experimentally tested on 26 benchmark problems through three experimental studies and compared to five meta-heuristic algorithms including genetic algorithm (GA), simulated annealing (SA), generic and chaotic Particle Swarm Optimization algorithm (PSO and cPSO), and hybrid GA–SA algorithm. Furthermore, the data are analyzed by using the Friedman statistical test to prove that results are statistically significant. Finally, generated scheduling plans are tested by Khepera II mobile robot within a laboratory model of the manufacturing environment. The experimental results show that the proposed methodology provides very competitive results compared to the state-of-art optimization algorithms.     

应用离散事件系统控制理论求解生产调度的新方法

众所周知, 生产调度问题属组合优化问题, 一般来说不存在求得精确最优解的多项式算法. 因此, 对于大规 模调度问题, 人们应用启发式算法和元启发式算法以企求得满意解. 在实际的应用中, 许多工业过程需要满足严格 的工艺约束. 对于这类过程的调度问题, 很难应用启发式算法和元启发式算法, 因为这些方法难于保证所求得调度 的可行性. 为了解决这一问题, 本文以半导体芯片制造中组合设备的调度问题作为例子, 介绍了一种基于离散事件 系统控制理论的生产调度新方法. 利用Petri网建模, 任何违反约束的状态均被描述为非法状态, 而使非法状态出现 的调度则是不可行调度. 通过可行调度的存在性分析, 该方法获得可行解空间并将调度问题转化为连续优化问题, 从而可以有效求解. 并且指出, 该方法可以应用于其他应用领域.     

知识化制造环境下航空发动机装配线调度及自重构

航空发动机装配工序数量多、工序间装配约束复杂. 当产品需求变化时, 人工调整存在响应速度慢、装配效率低等问题. 以最小化产品完工成本、工序提前期惩罚成本及班组重构成本加权和为目标, 建立了航空发动机装配线调度和装配班组自重构优化模型. 提出一种新的基于工序局部最优排序的分解算法, 将调度问题分解为单个装配组上工序顺序优化问题. 设计了一种工序后向插入搜索策略. 最后提出装配线调度及自重构集成优化算法. 通过数值试验,验证了模型与算法的有效性.