MIP/CP综合考虑的车间作业调度问题研究

作业车间(Job Shop)调度问题是指为具体的任务(工序)安排生产资源(机器)并确定合理的加工顺序,是一个典型的NP-Hard问题,有着广泛的研究.首先简单介绍约束编程(CP)思想及ILOG SOLVER系统并建立Job Shop调度问题的约束编程模型,并对模型的求解进行分析.然后分析混合整数规划(MIP)和约束编程(CP)模型求解的互补优势,建立Job Shop调度问题MIP/CP综合模型,并与CP模型进行比较,证明MIP/CP综合模型求解的效率.     

求解资源受限项目调度问题的约束规划/数学规划混合算法

利用约束规划（constraintprogramming,CP）与数学规划（mathematicalprogramming,MP）结合的方法求解调度问题已经获得了一些较好的研究成果,正成为调度问题研究领域的一个新的热点研究方向．本文针对求解资源受限项目调度问题（RCPSP）的整数规划模型,设计了基于CP技术的问题和模型预处理方法,证明了整数规划模型的有效不等式定理,提出了通过将项目子网络图转化为加权最大团问题求解后获得有效不等式的方法．引用标准问题库PSPLIB中的一组典型问题进行求解实验,结果表明本文提出的有效不等式可以明显改进模型的求解质量和时间性能．论文最后对实验结果进行了深入讨论,讨论了未来的研究方向．     

半在线调度中约束求解算法研究

很多实际调度问题是半在线的. 尝试运用人工智能方法来求解半在线调度问题, 首先简要介绍了半在线调度问题并对其约束模型进行了分类, 通过引入单调性约束扩展的相关概念, 从约束建模角度形式化描述 了一类动态约束扩展, 并在此基础上设计了一个完备动态约束求解算法, 最后给出该算法在半在线离散资源约束调度求解的应用算例. 测试结果表明, 该算法是可行有效的.     

分布式约束优化方法研究进展

多agent系统作为分布式人工智能研究领域的重要分支,已被广泛应用于多个领域中复杂系统的建模.而分布式约束优化作为一种多agent系统求解的关键技术,已成为约束推理研究的热点.首先对其适用性进行分析,并基于对已有算法的研究,总结出采用该方法解决问题的基本流程,在此基础上,从解的质量保证、求解策略等角度对算法进行了完整的分类;其次,根据算法分类结果以及执行机制,对大量经典以及近年来的分布式约束优化算法进行了深入分析,并从通信、求解质量、求解效率等方面对典型算法进行了实验对比;最后,结合分布式约束优化技术的求解优势给出了分布式约束优化问题的实际应用特征,总结了目前存在的一些问题,并对下一步工作进行了展望.     

约束满足混合算法求解并行机Job-Shop调度问题

分析并行机Job-Shop调度问题的特点并建立其约束满足优化模型,结合约束满足与变邻域搜索技术设计了一个求解该问题的混合优化算法。该算法采用变量排序方法和值排序方法选择变量并赋值,利用回溯和约束传播消解资源冲突,生成初始可行调度,然后应用局部搜索技术增强收敛性,并通过结合问题特点设计的邻域结构的多样性提高求解质量。数据实验表明,提出的算法与其他两种算法相比,具有一定的可行性和有效性。     

时序约束下的调度算法

在通讯ASIC设计中,时序行为是设计者考虑的主要目标。高层次综合领域中时序约束下的调度算法对ASIC设计的优化结果起着重要作用。论文在时序约束下的调度算法在算子可调度的前提下通过修正的ASAP与ALAP算法缩小设计的搜索空间,最后通过遗传算法进行优化,得到最优调度方案。根据文中算法建立了一个时序约束下的综合系统,并进行了实验,说明了算法的有效性。     

侦察卫星探测资源调度研究

侦察卫星探测资源调度是一类基于约束满足的优化问题。对卫星探测资源和探测任务的特点进行分析,在此基础上构建卫星探测资源调度的目标函数和约束条件,利用约束满足问题的建模思想对该调度问题进行建模。针对约束满足模型规模大、求解复杂的情况,结合卫星探测资源调度问题的特征,提出一种基于启发式禁忌搜索算法的模型求解方法,并通过仿真算例进行说明与分析。该调度模型和算法充分考虑了星载资源与对应任务的特点,尽量回避假设与简化条件的提出,具有较好的适用性,将为侦察与预警卫星网络任务规划与资源调度的研究奠定基础。     

增加约束条件的线性规划问题递推算法研究

首先描述线性规划问题中约束条件增加时的递推求解问题,此问题在线性规划问题中具有广泛的实际背景;然后提出一个基于凸空间思想的快速求解此类问题的递推算法,该算法能快速判断其矛盾约束、冗余约束以及新问题的递推最优解;最后给出了该问题的一个算例,实验仿真结果表明了该方法的有效性.     

约束满足技术在板坯排序中的应用

热轧调度中的板坯排序问题是一类特殊的排序问题,具有约束条件复杂、NP难特点。为了简化问题,将板坯排序问题转化为一个约束满足问题处理。给出板坯排序问题的约束满足模型,设计了基于约束满足和启发式混合求解算法。用3组实际生产数据对算法性能进行验证,说明了算法的有效性。     

项目优化调度的病毒协同进化遗传算法

针对次序约束和资源约束的多模式项目调度问题提出了一种病毒协同进化遗传算法,并提出了解的编码、选择、交叉、变异和病毒感染操作等.算法用于求解项目活动的一个最优调度顺序和资源模式以使项目的成本最低,其操作特点是既可以通过遗传操作在父子代群体之间纵向传播进化基因进行全局搜索,又可以通过病毒感染操作在同一代群体内横向传播进化基因进行局部搜索.利用模板理论对算法的性能进行了分析.理论分析和实验结果表明,算法的搜索性能优于一般的遗传算法.算法对于不同优化目标的多模式项目调度问题可以同时求得一个满足次序约束的项目活动的最优调度顺序和满足资源约束的最优资源模式.     

约束规划方法在原油混输调度中的应用

应用约束规划方法建立炼厂原油混输模型,并通过搜索求解获得可操作的调度方案。约束规划允许以逻辑约束表达混输过程中的操作规则,使模型简洁直观,而对整型变量及非线性约束不敏感,则降低了模型的求解难度。选取了一个时间跨度为300小时实际调度问题作为案例,模型中包含约8000个变量和14000条约束,在普通PC机上计算求解,能够在30秒内获得调度方案,方案具有可操作性且优于人工方案,表明以约束规划方法解决原油混输调度问题是可行的。     

带特殊工艺约束的并行机器生产线调度问题的一种遗传算法

研究带特殊工艺约束的并行机器生产线的调度方法.以完工时间、拖期时间和超库 存时间的惩罚量之和最小为调度目标,对该优化调度问题提出了一种遗传算法,并在问题建 模、遗传算法编码、初始种群的产生办法、交叉及变异方法等方面作了研究.数值计算结果表 明所提出的遗传算法是有效的.     

Solving job shop scheduling with setup times through constraint-based iterative sampling: an experimental analysis

This paper presents a heuristic algorithm for solving a job-shop scheduling problem with sequence dependent setup times and min/max separation constraints among the activities (SDST-JSSP/max). The algorithm relies on a core constraint-based search procedure, which generates consistent orderings of activities that require the same resource by incrementally imposing precedence constraints on a temporally feasible solution. Key to the effectiveness of the search procedure is a conflict sampling method biased toward selection of most critical conflicts and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This constraint-based search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically both on a set of previously studied job-shop scheduling benchmark problems with sequence dependent setup times and by introducing a new benchmark with setups and generalized precedence constraints.     

基于约束规划的一类排序问题通用求解方法

多约束排序问题是生产调度中常遇到的问题,传统的优化模型及方法在适应约束改变等方面存在诸多不足。鉴于此,将多约束排序问题定义为约束满足问题,系统设计时将模型定义与求解算法分离,利用约束规划平台的基本约束构建特定领域的抽象约束库,形成可重构的多约束排序问题通用求解框架。应用时,根据问题需求不同可利用抽象约束库快速重构优化模型,针对重构的优化模型配置相应的求解算法即可实现问题求解。应用结果表明,提出的方法通用性强,可满足实际应用的要求。     

A heuristic to solve the synchronized log-truck scheduling problem

We present a synchronized routing and scheduling problem that arises in the forest industry, as a variation of the log-truck scheduling problem. It combines routing and scheduling of trucks with specific constraints related to the Canadian forestry context. This problem includes aspects such as pick-up and delivery, multiple products, inventory stock, multiple supply points and multiple demand points. We developed a decomposition approach to solve the weekly problem in two phases. In the first phase we use a MIP solver to solve a tactical model that determines the destinations of full truckloads from forest areas to woodmills. In the second phase, we make use of two different methods to route and schedule the daily transportation of logs: the first one consists in using a constraint-based local search approach while the second one is a hybrid approach involving a constraint programming based model and a constraint-based local search model. These approaches have been implemented using COMET2.0. The method, was tested on two industrial cases from forest companies in Canada.     

作业车间调度转换瓶颈算法的不可行解问题

文章讨论了作业车间调度问题转换瓶颈算法的一个缺陷。转换瓶颈算法是解决作业车间调度最小makespan(完工时间)问题的很有效的启发式算法。它是基于反复的解决某些单机调度问题。然而在转换瓶颈算法中用Carlier算法解单机调度问题并不总能得到可行解,文中给出了一个反例证明了有产生不可行解的情况。另外,文章还以简洁的方法证明了转换瓶颈算法若用Schrage算法替代Carlier算法解单机调度问题不会产生不可行解。     

From enterprise models to scheduling models: bridging the gap

Enterprise models cover all aspects of modern enterprises, from accounting, through management of custom orders and invoicing, to operational data such as records on machines and workers. In other words, all data necessary for running the company are available in enterprise models. However, these data are not in the proper format for some tasks such as scheduling and optimization. Namely, the concepts and terminology used in enterprise models are different from what is traditionally used in scheduling and optimization software. This paper deals with the automated translation of data from the enterprise model to a scheduling model and back. In particular, we describe how to extract data from the enterprise model for solving the scheduling problem using constraint-based solvers.     

Scheduling Sport Tournaments using Constraint Logic Programming

We tackle the problem of scheduling the matches of a round robin tournament for a sport league. We formally define the problem, state its computational complexity, and present a solution algorithm using a two-step approach. The first step is the creation of a tournament pattern and is based on known graph-theoretic results. The second one is an assignment problem and it is solved using a constraint-based depth-first branch and bound procedure that assigns actual teams to numbers in the pattern. The procedure is implemented using the finite domain library of the constraint logic programming language \eclipse. Experimental results show that, in practical cases, the optimal solution of the assignment problem (which is not necessarily optimal for the overall problem) can be found in reasonable time, despite the fact that the problem is NP-complete. In addition, a local search procedure has been developed in order to provide, when necessary, an approximate solution in shorter time.     

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

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