Primal-dual methods for sustainable harvest scheduling problems

Timber harvest schedules form the heart of forest resource management. The operations research methodology is applied to resolving the multi-product, multi-period sustainable timber harvest scheduling problems, where area constraints, harvest flow constraints, and ending inventory constraints are imposed. By taking advantage of the model characterization of block diagonal constraints with multiple sets of network sub-problems and the set of coupling constraints, an efficient algorithm is explored. Specifically, a primal-dual method of closed-form solutions is first developed to solve the network sub-problems on the individual basis. Then, a primal-dual steepest-edge algorithm that achieves the global optimum is presented. A numerical example illustrating steps of the solution procedure is presented. The proposed algorithm is implemented, and its performance is compared with that of the AMPL-CPLEX package. The proposed primal-dual algorithm achieves, on the average, an approximately four to one reduction in iteration numbers and an about eight to one reduction in the CPU execution time.Scope and purposeTimber harvest schedules form the heart of forest resource management. This paper presents the model formulation, structure identification, and algorithm explored for resolving the multi-product, multi-period harvest scheduling problem, where area constraints, harvest flow constraints, and ending inventory constraints serve as the basis of a sustainable forest policy. The work applies the mathematical programming methodology to the forest management regime. To streamline the solution procedure, we first identify the block diagonal constraint structure, the network sub-problems, and a set of coupling constraints. By employing a primal-dual algorithm using only closed-form solutions that resolves the network sub-problems, we explore a primal-dual steepest-edge algorithm that achieves the optimal harvest schedule. The proposed algorithm is coded in the Borland C++ programming language and run on a personal computer. For comparison, the package of AMPL-CPLEX and the proposed method are applied to solving a set of arbitrarily generated sample problems. The proposed primal-dual algorithm outperforms the general-purpose package in both iteration numbers and the CPU execution time.     

冷链物流越库调度的拉格朗日松弛算法

为了提高冷链物流的运输效率,解决越库在冷链物流中的应用问题,提出了基于拉格朗日松弛算法的冷链物流的越库调度方法.首先进行了问题域的描述并做出了具体假设,基于问题域以最小化卡车等待时间和越库内部运输成本为目标,建立越库调度的整数规划数学模型.然后,提出了针对越库调度模型的拉格朗日松弛算法,松弛复杂约束后根据决策变量将松弛问题分解为若干子问题,采用次梯度算法求解松弛模型.最后,对各种不同规模的越库模型进行仿真实验,并与传统的贪婪算法进行对比,结果表明,所提出的调度算法适用于问题的求解,并可以在较短时间内获得良好的近优解.     

复杂并行机调度问题基于分解的优化算法

针对纺织生产过程中广泛存在的带特殊工艺约束的大规模并行机调度问题，提出了一种基于分解的优化算法。首先将原调度问题分解为机台选择和工件排序两个子问题，然后针对机台选择子问题提出一种进化规划算法，并采用一种具有多项式时间复杂度的最优算法求解工件排序子问题，以得到问题特征信息（即每台机器对应拖期工件数的最小值），该问题特征信息用以指导进化规划算法的迭代过程。不同规模并行机调度问题的数值计算结果及实际制造企业应用效果表明，本文提出的算法是有效的。     

可重入混合流水车间调度的拉格朗日松弛算法

为了有效提升多重入车间的生产效率,考虑了实际生产中检查和修复过程对于逐层制造的可重入生产系统的重要性,提出了基于拉格朗日松弛算法的可重入混合流水车间的调度方法.首先进行了问题域的描述,并在此基础上以最小化加权完成时间为调度目标,建立数学规划模型.针对该调度问题提出了基于松弛机器能力约束的拉格朗日松弛算法,使松弛问题分解成工件级子问题,并使用动态规划方法建立递归公式,求解工件级子问题.随后,使用次梯度算法求解拉格朗日对偶问题.最后,对各种不同问题规模进行了仿真实验,结果表明,所提出的调度算法能够在合理的时间内获得满意的近优解.     

Minimum cost multiple multicast network coding with quantized rates

In this paper, we consider multiple multicast sessions with intra-session network coding where rates over all links are integer multiples of a basic rate. Although having quantized rates over communication links is quite common, conventional minimum cost network coding problem cannot generally result in quantized solutions. In this research, the problem of finding minimum cost transmission for multiple multicast sessions with network coding is addressed. It is assumed that the rate of coded packet injection at every link of each session takes quantized values. First, this problem is formulated as a mixed integer linear programming problem, and then it is proved that this problem is strongly NP-hard on general graphs. In order to obtain an exact solution for the problem, an effective and efficient scheme based on Benders decomposition is developed. Using this scheme the problem is decomposed into a master integer programming problem and several linear programming sub-problems. The efficiency of the proposed scheme is subsequently evaluated by numerical results on random networks.     

A GA methodology for the scheduling of yarn-dyed textile production

This paper presents a scheduling approach for yarn-dyed textile manufacturing. The scheduling problem is distinct in having four characteristics: multi-stage production, sequence-dependent setup times, hierarchical product structure, and group-delivery (a group of jobs pertaining to a particular customer order must be delivered together), which are seldom addressed as a whole in literature. The scheduling objective is to minimize the total tardiness of customer orders. The problem is formulated as a mixed integer programming (MIP) model, which is computationally extensive. To reduce the problem complexity, we decomposed the scheduling problem into a sequence of sub-problems. Each sub-problem is solved by a genetic algorithm (GA), and an iteration of solving the whole sequence of sub-problems is repeated until a satisfactory solution has been obtained. Numerical experiment results indicated that the proposed approach significantly outperforms the EDD (earliest due date) scheduling method—currently used in the yarn-dyed textile industry.     

求解异构并行机调度问题的混合多目标教-学优化算法

以异构并行机调度问题为研究对象,考虑了一类以优化总加权完工时间和加权延误总和的调度问题。首先,基于问题描述构建了该问题的混合整数规划模型。其次,提出了混合多目标教-学优化算法。在算法设计中,结合问题的特点设计序列编码方法,并采用分解技术来实现多目标调度问题的求解。此外,该算法通过融合多种交叉算子来定义个体进化过程,并通过与变邻域搜索算法的混合来提升其优化效果。最后,给出了仿真实验与分析,测试结果验证了多目标教-学优化算法求解该调度问题的优越性。     

基于分解优化的多星合成观测调度算法

某些卫星的侧摆性能较差, 必须进行合成观测以提高观测效率. 研究了多星联合对地观测中的任务合成观测调度问题. 提出了将原问题分解为任务分配与任务合成的分解优化思路. 任务分配为任务选择卫星资源及时间窗口; 任务合成则针对该分配方案,将分配到各卫星的任务按照轨道圈次分组, 分别进行最优合成. 采用蚁群优化算法(Ant colony optimization, ACO)求解任务分配问题, 通过自适应参数调整及信息素平滑策略, 实现全局搜索和快速收敛间的平衡.提出了基于动态规划的最优合成算法, 求解任务合成子问题,能够在多项式时间内求得最优合成方案. 依据分配方案的合成结果, 得到优化方案的特征信息, 反馈并引导蚁群优化算法对任务分配方案的搜索过程. 大规模测试算例验证了本文算法的效率.     

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

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

A mathematical programming model for AGVS planning and control in manufacturing systems

In this paper, problems of the planning and control of automated guided vehicles in manufacturing systems are discussed. A mixed integer programming model is developed to minimize the total material handling cost in manufacturing systems. In order to solve this NP-complete problem efficiently, a decomposition approach following the Lagrangian relaxation method is used. The decomposed sub-problems can be solved by a dynamic programming method. An efficient algorithm is developed to solve the entire problem and a numerical example is presented to illustrate the method of solution.     

汽车同步装配线生产计划与调度集成优化汽车同步装配线生产计划与调度集成优化

为克服传统的"自顶向下"方式下生产计划与调度不协调的缺陷,针对汽车同步装配线,构造了生产计划与调度集成优化混合整数规划模型,并采用拉格朗日松弛法将其分解为批量计划及调度等子问题.将调度子问题转化为与时间相关的旅行商问题,并采用dynasearch算法求解.对于拉格朗日对偶问题,采用均衡方向策略法求解.仿真实验结果验证了模型及算法的有效性.     

求解流水车间批量流集成调度的离散入侵杂草优化算法

提出一种离散入侵杂草优化算法,用来解决最大完工时间目标的流水车间批量流集成调度问题.该调度问题包含两个紧密耦合的子问题:批次分割问题和考虑启动时间的批次调度问题.设计了两段字符串编码,用来表示两个子问题.与基本入侵杂草优化算法不同,所提算法基于适应度和年龄确定杂草种子数量,基于正切函数和连续邻域操作产生种子.8种邻域算子的混合应用与局部搜索增强了算法的求解能力.仿真实验表明了所提算法的有效性.     

Exact and heuristic algorithms for the just-in-time scheduling problem in a batch processing system

Batch processing systems are commonly used in many different environments such as chemical and semiconductor industries. In this research, a just-in-time scheduling problem in a batch processing system is investigated. Minimization of total earliness and tardiness of the jobs with respect to a common due date is considered as the objective function. First, the research problem is formulated as a mixed integer linear programming model. Then, to find the optimal schedule for a predetermined set of batches, a dynamic programming algorithm is proposed. Based on the proposed dynamic programming algorithm, several heuristics are also developed. A lower bounding method is presented, and then a branch and bound algorithm is proposed to solve the problem optimally. To demonstrate the performance of the proposed algorithms, several computational experiments are conducted.     

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

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

一类具有特殊阻塞约束的两阶段流水车间成组调度模型与算法

从钢铁企业的管加工生产中抽象出一类具有特殊阻塞约束的两阶段流水车间成组调度问题.与传统阻塞约束不同,工件是否发生阻塞并非取决于缓冲区容量,而是取决于工件自身的规格、尺寸等属性.针对此调度问题,以最小化最大完工时间(makespan)为目标建立混合整数线性规划模型,并通过三划分问题的多项式归结证明问题的强NP难特性,进而将问题划分为工件组排序和工件组内工件排序两个子问题,提出一种基于协同进化的分布估计算法.算法针对两个子问题各自特点进行独立编码,分别设计启发式规则构造初始种群,并提出带有工件区块结构特征的概率模型来指导种群进化.基于实际生产数据设计多种问题规模的实验,从而表明所提出模型和算法的有效性.     

Scheduling prioritized patients in emergency department laboratories

This research focuses on scheduling patients in emergency department laboratories according to the priority of patients’ treatments, determined by the triage factor. The objective is to minimize the total waiting time of patients in the emergency department laboratories with emphasis on patients with severe conditions. The problem is formulated as a flexible open shop scheduling problem and a mixed integer linear programming model is proposed. A genetic algorithm (GA) is developed for solving the problem. Then, the response surface methodology is applied for tuning the GA parameters. The algorithm is tested on a set of real data from an emergency department. Simulation results show that the proposed algorithm can significantly improve the efficiency of the emergency department by reducing the total waiting time of prioritized patients.     

电–气互联系统的气电解耦分布式多目标优化调度

本文基于能源互联网背景建立了一种计及供能成本、碳排放量和净负荷曲线平滑度的电–气互联系统多目标优化模型,并采用线性化方法将非线性优化模型转化为混合整数线性规划模型.同时,为了求解该模型,实现各能源的协同互补利用,提高能源的利用率,本文在保障各能源网络分散自治权的基础上提出一种基于气电解耦的分布式多目标优化算法,以气电解耦优化的方式实现电、气系统的分散自治.所提算法将原系统的多目标优化问题分解为电网和气网的子优化问题,并采用独立的优化器完成子问题的求解.电网和气网仅需交换少量边界变量以及虚拟目标因子分别进行全局调整即可获得多目标解.最后,本文根据修改的IEEE 39节点电力网络和比利时20节点天然气网络搭建模型并进行仿真分析,结果验证:所提算法能够完成电–气互联系统的气电解耦并实现多目标并行求解,从而提高系统信息私密性、实现各能源网络的分散自治.     

Multiprocessor Task Assignment with Fuzzy Hopfield Neural Network Clustering Technique

Most scheduling applications have been demonstrated as NP-complete problems. A variety of schemes are introduced in solving those scheduling applications, such as linear programming, neural networks, and fuzzy logic. In this paper, a new approach of first analogising a scheduling problem to a clustering problem and then using a fuzzy Hopfield neural network clustering technique to solve the scheduling problem is proposed. This fuzzy Hopfield neural network algorithm integrates fuzzy c-means clustering strategies into a Hopfield neural network. This investigation utilises this new approach to demonstrate the feasibility of resolving a multiprocessor scheduling problem with no process migration and constrained times (execution time and deadline). Each process is regarded as a data sample, and every processor is taken as a cluster. Simulation results illustrate that imposing the fuzzy Hopfield neural network onto the proposed energy function provides an appropriate approach to solving this class of scheduling problem.       

动态规划-粒子群算法在水库优化调度中的应用

水库优化调度是一个典型的具有多约束条件的、动态的、非线性的优化问题。针对这些问题,利用动态规划-粒子群(DP-PSO)算法加以求解。利用动态规划中的多阶段最优策略原理,将水库优化调度问题转化为多阶段决策子问题,各个子问题采用粒子群算法优化求解。数值实验表明,在计算时段较多时,DP-PSO算法计算的可靠性明显优于一般的动态规划(DP)算法,在计算时间上,DP-PSO算法用时较动态规划-遗传算法(DP-GA)少。     

树型网格计算环境下的独立任务调度

任务调度是实现高性能网格计算的一个基本问题,然而,设计和实现高效的调度算法是非常具有挑战性的.讨论了在网格资源计算能力和网络通信速度异构的树型计算网格环境下,独立任务的调度问题.与实现最小化任务总的执行时间不同(该问题已被证明是NP难题),为该任务调度问题建立了整数线性规划模型,并从该线性规划模型中得到最优任务分配方案??各计算节点最优任务分配数.然后,基于最优任务分配方案,构造了两种动态的需求驱动的任务分配启发式算法:OPCHATA(optimization-based priority-computation heuristic algorithm for task allocation)和OPBHATA(optimization-basedpriority-bandwidth heuristic algorithm for task allocation).实验结果表明:在异构的树型计算网格环境下实现大量独立任务调度时,该算法的性能明显优于其他算法.