一类复杂约束下的并行机重调度问题研究

研究一类从实际指挥和保障系统提炼的考虑机器多发故障、且具有工件释放时间、机器可用时间、以及机器适用限制等约束的并行同速机重调度问题.首先,建立同时考虑效率、安全和稳定性的混合整数规划重调度模型,该模型利用最大完工时间和总完工时间来度量效率,用重调度前后分配不同机器的工件总数来度量安全性和稳定性;其次,考虑到该问题的NP-hard性和实际调度对机器故障快速响应的要求,提出基于优先规则和右移重调度策略混合的重调度算法框架;最后,将所提重调度算法框架应用于实际案例,分析比较不同优先规则和右移重调度策略组合的求解效果.结果表明,与工件释放时间相关的优先准则与右移重调度策略结合具有较好的优化效果.值得一提的是,文章首次研究具有多重约束的并行机重调度问题(Pm|r_j,a_j,M_j,brkdwn|C_(max),TC,ND).     

分支定界算法求解带有释放时间的单机双代理调度问题

本文研究了带有释放时间的单机双代理调度问题,目标函数为极小化最大完工时间和。为了便于利用优化软件求解,建立了混合整数规划模型。考虑到该问题具有NP困难性,因此采用近似与精确算法分别求解不同规模问题。针对大规模问题,提出了优势代理优先启发式算法,并证明了其渐近最优性。针对小规模问题,设计了分支定界法进行最优求解,其中基于释放时间的分支规则和基于加工中断的下界有效地减少了运算时间。最后,通过数值测试验证了分支定界算法的有效性以及启发式算法的收敛性。     

基于MAS的多模式分布式资源约束多项目调度

针对实践中分布式多项目的活动往往具有多种执行模式,提出多模式分布式资源约束多项目调度问题。在项目动态到达环境下,考虑活动不同的执行模式,以工期最短和多项目延期成本最小为目标分别构建局部单项目调度模型和全局多项目决策模型,采用改进变邻域搜索算法求解初始局部调度计划,并设计基于模式调整的全局协商调度算法求解全局决策模型,通过双层算法实现分布式多项目调度中局部单项目调度与全局多项目调度系统性协调,减少项目中断和多项目延期成本。基于构建的多模式测试集进行的多项目数值实验表明：本文设计的双层算法可有效求解多模式分布式多项目调度问题,并且对不同规模问题求解具有良好的适应性。     

具有机器适用限制的分布式置换流水车间问题的模型与算法

考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性.     

考虑恶化和学习效应的多机制造系统智能优化方法

研究了考虑机器恶化和工人学习效应的平行机连续批调度问题,其中,工件具有不同的一般加工时间,机器具有不同的恶化率,工人具有不同的学习能力,批次的容量对于所有机器是相同的.目标是最小化最大完工时间.论文首先针对工件的组批排序问题推导了一系列重要性质,并提出了相应的启发式组批策略.然后,基于给定的工件分配和每个机器上工件的组批和排序,研究设计了工人和机器启发式匹配策略.由于所研究的问题在一般情形下被证明是NP-hard问题,论文设计了改进的变邻域搜索算法(IVNS)求解该问题并用算例验证了所提出算法的有效性.     

工件优先级图为非连接图且含环的单机总加权拖期调度问题

为满足实际生产环境对工件加工顺序和工件到达时间的要求,提出了具有新特征的单机总加权拖期调度问题,其特点体现在:工件有动态到达时间,且由工件优先级关系构成的优先级图为非连接图且存在环的情况,对该问题建立数学规划模型,在扩展Tang和Xuan等的基础上,提出了结合双向动态规划的拉格朗日松弛算法求解该问题。在该算法的设计中,提出双向动态规划算法求解拉格朗日松弛问题,使得它可处理优先级图中一个工件可能有多个紧前或紧后工件的情况,采用次梯度算法更新拉格朗日乘子,基于拉格朗日松弛问题的解设计启发式算法构造可行解。实验测试结果显示,所设计的拉格朗日松弛算法能够在较短的运行时间内得到令人满意的近优解,为更复杂的调度问题的求解提供了思路。     

改进的布谷鸟算法求解考虑运输时间的分布式柔性流水车间调度问题

针对分布式制造环境下多车间调度问题特点,结合企业实际生产情况,考虑相邻工序间的运输时间,建立以最小化最大完工时间为优化目标的分布式柔性流水车间调度模型,提出一种改进布谷鸟算法用于求解该模型。算法改进包括设计了一种基于工序、车间和机器的三层编码方案;根据问题特点设计了混合种群初始化策略以提高种群质量;改进了布谷鸟搜索操作使其适用于求解该模型;设计了一种种群进化策略以提高算法收敛速度及解的质量。最后通过仿真实验,与多种算法对比,验证所提算法的有效性和优越性。     

汽车滚装码头泊位调度优化模型与算法研究

本文研究滚装码头混合泊位分配和劳动力分配的联合调度优化问题。首先,考虑潮汐时间窗约束、装卸劳动力约束、泊位缆桩分布约束以及泊位不规则布局因素,建立以最小化船舶总服务时间为目标的混合整数规划模型。其次,采用内外嵌套算法设计策略,提出求解该类问题的组合算法。其中,外层是多种群并行进化的遗传算法,生成多种船舶计划顺序,内层为基于规则的启发式算法,用于计算给定计划顺序的目标函数值。然后,基于实际运营数据,生成多组不同规模的算例进行全面数值实验,结果表明所提出的算法可在10分钟内求解包含50艘船、100个泊段的算例。最后,开展基于真实滚装码头运营实例的案例分析,对所提模型和算法在实际码头调度问题中的适用性与高效性进行验证。     

集中通勤接送服务的最小化成本模型及算法

本文针对集中通勤接送服务业务流程中的车次分配与调度问题,建立了以最小化成本为目标的0-1混合整数规划模型,刻画了该问题所具有的多目标抵达地、多车协作、多行程车次等特征事实,同时考虑顾客满意度,以获得不同满意度下的近似最小成本。根据问题的复杂性和大规模性,设计开发了一种基于kNN思想的类标签启发式算法求解模型,拓展了构造路径的方法。算例数值结果表明,本文所设计模型和算法是有效性、可行的。     

考虑多阶段共用平行机特征的拖轮作业模式优化

在对拖轮调度问题进行分析的基础之上,将拖轮调度问题归结为一类具有多阶段共用平行机器特征的多处理器任务调度问题。建立了考虑靠泊与停泊两阶段、考虑切换时间的拖轮调度优化模型,并设计了启发式规则与模拟退火相结合的混合算法(HSA)求解该模型。通过运用所设计算法求解仿真算例,并将其结果与三种基于现行调度规则的调度方案进行比较,验证了模型与算法的高效性。基于此,对不同拖轮数量状态下的调度研究结果显示,拖轮总作业时间与平均单艘拖轮作业时间二者存在着一定的矛盾性;并指出采用拖轮适时返回停泊基地的作业模式,可有效地降低拖轮作业时间,进而提高有限拖轮资源的利用率,实现节能减排、绿色运输。     

Lower and upper bounds for a two-stage capacitated facility location problem with handling costs

We study in this paper multi-product facility location problem in a two-stage supply chain in which plants have production limitation, potential depots have limited storage capacity and customer demands must be satisfied by plants via depots. In the paper, handling cost for batch process in depots is considered in a realistic way by a set of capacitated handling modules. Each module can be regards as alliance of equipment and manpower. The problem is to locate depots, choose appropriate handling modules and to determine the product flows from the plants, opened depots to customers with the objective to minimize total location, handling and transportation costs. For the problem, we developed a hybrid method. The initial lower and upper bounds are provided by applying a Lagrangean based on local search heuristic. Then a weighted Dantzig–Wolfe decomposition and path-relinking combined method are proposed to improve obtained bounds. Numerical experiments on 350 randomly generated instances demonstrate our method can provide high quality solution with gaps below 2%.     

基于商品关联度的智能仓库储位分配问题研究

储位分配方案是直接影响智能仓库工作效率和拣选成本的关键因素.根据历史订单信息定义了商品之间的关联度,以同一货架上的商品之间的关联度之和极大化为目标建立了智能仓库储位分配问题的数学模型,并设计了求解模型的算法.首先根据历史订单信息计算商品之间的关联度,然后结合商品的周转率、商品之间的关联度等信息,设计了启发式算法求解智能仓库储位分配问题,并且分析了启发式算法的时间复杂度.通过大量的模拟计算验证了本文建立的数学模型和设计的启发式算法的有效性,证明了以同一货架上商品之间关联度极大化为目标和以订单拣选过程中搬运货架总次数极小化为目标的一致性.通过对比分析本文算法得到的储位分配结果与随机储位分配结果可以看出,利用基于商品关联度的启发式算法得到的储位分配方案比随机储位分配方案对应的货架搬运次数平均减少了30.08%.     

Production scheduling with alternative process plans

This paper deals with a scheduling problem with alternative process plans that was motivated by a production of wire harnesses where certain parts can be processed manually or automatically by different types of machines. Only a subset of all the given activities will form the solution, so the decision whether the activity will appear in the final schedule has to be made during the scheduling process. The problem considered is an extension of the resource constrained project scheduling problem (RCPSP) with unary resources, positive and negative time-lags and sequence dependent setup times. We extend classic RCPSP problem by a definition of alternative branchings, represented by the Petri nets formalism allowing one to define alternatives and parallelism within one data structure. For this representation of the problem, an integer linear programming model is formulated and the reduction of the problem, using time symmetry mapping, is shown. Finally, a heuristic algorithm based on priority schedule construction with an unscheduling step is proposed for the nested version of the problem and it is used to solve the case study of the wire harnesses production.     

活动长度有限制的多工序批量加工生产计划研究

当前的化工制造中,有很多工厂使用柔性制造设备,并采用批生产模式来组织生产.由于对设备进行准备和清理的成本比较大,加工的排序一般采用多批次加工同一种产品的活动（campaign）模式.在实际的生产中,由于需要保证产品质量和减少库存,应该考虑限制活动的最大长度.本文针对活动长度有限制的多工序批量加工问题进行研究,利用状态-任务-网络概念和层级模型方法,提出了修正的活动计划模型.该模型是基于混合整数线性规划模型,并且以供应网络内总生产成本和物流成本最小化作为目标函数.最后用一个算例来说明所构建模型的有效性.     

Fuzzy scheduling of job orders in a two-stage flowshop with batch-processing machines

In this paper, we present a mixed-integer fuzzy programming model and a genetic algorithm (GA) based solution approach to a scheduling problem of customer orders in a mass customizing furniture industry. Independent job orders are grouped into multiple classes based on similarity in style so that the required number of setups is minimized. The family of jobs can be partitioned into batches, where each batch consists of a set of consecutively processed jobs from the same class. If a batch is assigned to one of available parallel machines, a setup is required at the beginning of the first job in that batch. A schedule defines the way how the batches are created from the independent jobs and specifies the processing order of the batches and that of the jobs within the batches. A machine can only process one job at a time, and cannot perform any processing while undergoing a setup. The proposed formulation minimizes the total weighted flowtime while fulfilling due date requirements. The imprecision associated with estimation of setup and processing times are represented by fuzzy sets.     

混流无等待流水线批次批量生产计划方法

在两阶段混流无等待流水装配环境下,为解决任务组批生产导致的订单按期交付能力弱,以及产品需求与部件供应无法准确衔接的问题,以最小化在制品库存成本和产品提前拖期惩罚为目标,建立了两阶段批次批量生产计划数学模型。设计了双目标蚁群求解算法,构造了每只蚂蚁对不同目标的偏重算子,以及基于批次的可行解生成方法和信息素更新机制,提高了解的局部和全局搜索能力。通过与NSGA-II进行对比,验证了本算法在同等时间内计算精度优于后者,为提高两阶段多条生产线组批生产计划的可执行性提供方法支持。     

基于Epsilon约束法的短纤维生产调度的双目标优化研究

针对短纤维生产行业实际,本文综合考虑客户的需求差异、客户的重要程度、纤维生产设备的准备时间以及交货期差异等因素,研究连续需求下的短纤维生产排序优化问题。首先,本文建立双目标整数规划模型,即最小化客户订单总延迟和最小化机器总准备时间;其次,设计Epsilon约束算法并调用CPLEX精确求解调度方案,即帕累托前沿;最后设计非支配排序的遗传算法(NSGA-II)求解大规模生产下的调度优化方案。通过实验,证明该整数规划模型和算法对解决多客户连续需求问题具有实际价值,进而可以为短纤维生产企业提供参考。     

基于惩罚似然比的高维空间相关过程EWMA质量监控模型

变量选择控制图是高维统计过程监控的重要方法。针对传统变量选择控制图较少考虑高维过程空间相关性而造成监控效率低的问题,提出一种基于Fused-LASSO的高维空间相关过程监控模型。首先,利用Fused LASSO算法对似然比检验进行改进;然后,推导出基于惩罚似然比的监控统计量;最后,通过仿真模拟和真实案例分析所提监控模型的性能。仿真实验和真实案例均表明:在高维空间相关过程中,当相邻监控变量同时发生异常时,利用所提监控方法能够准确识别潜在异常变量,取得较好的监控效果。     

随机需求应急物流多阶段定位-路径鲁棒优化研究

为提高应急物流系统的应急反应能力,论文针对需求随机变化的应急物流定位-路径问题,利用鲁棒优化的思想将灾区物资需求量表示为区间型数据,将应急救援过程划分为多个阶段,以总救援时间和系统总成本最小为目标,构建了多物资多运输车辆应急物流定位-路径优化模型,设计了改进的遗传算法对其进行求解。实例计算结果表明,该模型和算法可以有效地解决应急物流系统中需求随机变化的定位-路径问题,为政府机构应对重大突发事件提供科学的决策参考。     

Production strategies for a stochastic lot-sizing problem with constant capacity

This paper presents a single item capacitated stochastic lot-sizing problem motibated by a Dutch company operating in a Make-To-Order environment. Due to a highly fluctuating and unpredictable demand, it is not possible to keep any finished goods inventory. In response to a customer's order, a fixed delivery date is quoted by the company. The objective is to determine in each period of the planning horizon the optimal size of production lots so that delivery dates are met as closely as possible at the expense of minimal average costs. These include set-up costs, holding costs for orders that are finished before their promised delivery date and penalty costs for orders that are not satisfied on time and are therefore backordered. Given that the optimal production policy is likely to be too complex in this situation, attention is focused on the development of heuristic procedures. In this paper two heuristics are proposed. The first one is an extension of a simple production strategy derived by Dellaert [5] for the uncapacitated version of the problem. The second heuristic is based on the well-known Silver-Meal algorithm for the case of deterministic time-varying demand. Experimental results suggest that the first heuristic gives low average costs especially when the demand variability is low and there are large differences in the cost parameters. The Silver-Meal approach is usually outperformed by the first heuristic in situations where the available production capacity is tight and the demand variability is low.