Scheduling under Labour Resource Constraints

In this paper we introducean optimisation problem extracted from an industrial application:the scheduling problem under labour constraints. After givinga short summary of the origins of this problem and its mathematicalformulation, the different methods used for solving it (at leastpartially) are briefly described. In the last part, we presenta set of 25 instances of different sizes for benchmark purposes.So far, only 5 of these test instances have been solved to optimality,the others remaining open.     

禁忌搜索解决烘干窑调度问题

针对烘干窑生产周期长、成本高的问题,为提高其生产效率,缩短生产周期,对烘干窑的生产调度进行了优化,描述了一个现实中存在的烘干窑调度问题,提出了一种改进的融入了回溯思想的禁忌搜索算法,并给出了算法优化前后的生产计划比较。实际应用结果显示,该算法能有效地缩短生产周期,减少生产成本,提高设备利用率和合同准时率。     

考虑多类型时间依赖资源约束的敏捷卫星调度优化

随着现代空间科技的迅猛发展,光学遥感图像数据的应用需求越来越广泛,大力推动了光学对地观测卫星的发展.然而,由于高昂的发射成本的约束,对地观测卫星的资源是有限的,远远无法满足各类数据需求.因此,提高对地观测卫星的使用效率,提高其任务执行率,具有非常重要的应用价值.本文聚焦于敏捷对地观测卫星的任务调度问题,即在给定的调度周期内,对有限的卫星资源制定合理的任务调度方案,在满足一定星上资源约束下,最大化观测任务收益.该问题难点在于星上的资源是非常有限的,例如存储图像数据的固存资源、用于采集数据和卫星姿态切换的能量资源及执行任务活动耗费的时间资源.需要注意的是,能量消耗量和时间消耗量依赖于任务的执行时间,这是敏捷卫星相对传统的非敏捷卫星独有的特性.不同任务场景对不同类型资源的需求不同,多种资源约束互相耦合,资源约束具有时间依赖特性,这些难点无疑极大地增加了卫星调度的求解难度.为高效地求解该问题,本文构建了多类型时间依赖资源约束的敏捷卫星调度整数规划模型,并针对问题特性提出了一种基于自适应选择因子的迭代局部搜索启发式算法.自适应选择因子综合考虑了目标收益、资源消耗量、资源约束的松弛量,采用动态变化的资源重要度,能快速自适应地根据当前场景下各种类型的资源数据使用量来确定最佳局部搜索方向,从而在有限时间内找到高质量的解.实验结果证明,本文所提出的算法在多种情况下相比当前最好算法求解效果显著更优.此外,算法独有的自适应选择因子相比传统的选择因子的求解质量更高,这是因为所设计的自适应选择因子兼顾了目标收益和资源消耗量之间权衡关系的同时,采用动态变化的资源重要度准确捕捉了资源需求的迫切程度.     

Optimal cyclic single crane scheduling for two parallel train oilcan repairing lines

Crane is widely used to move a heavy object from one place to another not only in manufacturing industry but also service industry. As an important resource in the train oilcan repairing, crane scheduling affects directly the productivity of the systems. In this paper, we study cyclic single crane scheduling problem with two parallel train oilcan repairing lines, where jobs are loaded into the line at one end and unloaded at the other end. The processing time at each workstation must be within a given range. There is no buffer between these stations. A crane is used to move jobs between the workstations in two parallel lines. The objective is to schedule the moves to minimize the production cycle. We proposed a time way diagram for two parallel lines and developed a mixed integer linear programming model. Then we extended the model to the scheduling problem with multi-station to eliminate the bottleneck in lines. Examples are given to demonstrate the effectiveness of the model.     

汽车装配车间生产计划与调度的同时优化方法

文中提出三种新方法来解决汽车装配车间生产计划与调度的同时优化问题.首先将汽车装配线简化为一个Flow shop问题,并建立其混合整数规划模型,以求得使各装配工位的准备成本和空闲时间尽可能少并尽可能满足产品需求的粗生产计划.然后在粗生产计划的基础上考虑装配线的细节,用Tabu搜索法与快速调度仿真相结合的三种不同启发式算法使生产计划与调度同时得到优化,并给出了三种算法的复杂性.大量算例的比较研究表明了这些算法的有效性和适用性.     

一种求解整数规划与混合整数规划非线性罚函数方法

证明了任何一个变量有界的整数规划问题（IP）和混合整数规划问题（MIP）都可以转化为一个等价的非整数（或连续化）规划问题（NIP）,并给出一个用非线性精确罚函数法来求解该等价NIP的方法,从而达到求解IP或MIP的目的,数值实验表明了算法的可行性。该方法可广泛用于各应用领域里IP和MIP的求解,特别是为非线性IP和MIP问题提供了一条通用 的求解途径,对解决许多实际优化问题具有重要意义。     

用于炼油厂原油库存调度的混合模拟退火算法

现有的数学规划法在解决原油库存调度优化问题时存在着组合爆炸的问题,是阻碍调度优化实用化的主要原因。由于实践中往往只要求快速地获得一个较好解,因此作为启发式算法之一的模拟退火法,在解决调度问题的实用化方面具有很大的优越性。但由于模拟退火法较适于处理无约束的整数规划问题,而在原油库存调度优化模型中却存在着大量的实数约束,所以在其中直接应用模拟退火法比较困难。该文将模拟退火法与线性规划法相结合,以前者调动后者,后者为前者提供可行解判据,构成了一种优化混合算法。在将混合算法应用于原油库存调度问题时,该文采用了特定的编码方式,使各控制变量在随机变化时尽量满足相关的约束条件,从而避免了许多无效解的产生。实例计算结果表明,同传统的混合整数线性规划方法相比,这种混合算法可以快速地给出优化解,其优化值与全局最优值差别不大,表明混合算法可以更好地解决实际原油调度问题。     

Modeling and analysis for multi-period, multi-product and multi-resource production scheduling

This study presents a framework for solving the multi-period, multi-product and multi-resource production-scheduling (M³PS) problem. Practically, the main concern for an M³PS problem is how to satisfy two management policies: (1) each product is manufactured in a continuous manner so that once the product is on a production line, it will complete its production procedure without interruption, and (2) the number of the product's types is limited during one period. By defining the decision variables and taking into account the machine's capacity and the customers' demand, a mixed integer programming (MIP) Model is formulated. To solve this MIP problem, a two-phase approach is proposed. In phase 1, the search space of the MIP Model is transformed into a preliminary pattern by a heuristic mining algorithm so that a hyper assignment problem can be formed as a reference model to be solved. In phase 2, a stochastic global optimization procedure that incorporates a genetic algorithm with neighborhood search techniques is designed to obtain the optimal solution. A numerical experiment is presented with an illustration, and it shows that the proposed model is adequate to cope with complicate scheduling problems.     

化工工业多品种成批轮番生产的集成分批与调度

针对化工工业流程式多品种成批轮番生产集成分批与调度问题,分析多阶段、共享设备、物料输入输出变动转化率、库存限制和品种切换调整时间的工艺特点,建立连续时间表示的混合整数线性规划模型,提出二维粒子群优化算法。设计粒子编码为生产设备的加工状态,通过有效的解码程序将粒子解释为分批和调度。算法采用收缩算子提高局部求精能力,并引入发散算子和速度扰动策略保持种群的多样性。实验结果表明了所提出的算法具有良好的性能。     

A Hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization

Hybrid methods are promising tools in integer programming, as they combine the best features of different methods in a complementary fashion. This paper presents such a framework, integrating the notions of genetic algorithm, linear programming, and ordinal optimization in an effort to shorten computation times for large and/or difficult integer programming problems. Capitalizing on the central idea of ordinal optimization and on the learning capability of genetic algorithms to quickly generate good feasible solutions, and then using linear programming to solve the problem that results from fixing the integer part of the solution, one may be able to obtain solutions that are close to optimal. Indeed ordinal optimization guarantees the quality of the solutions found. Numerical testing on a real-life complex scheduling problem demonstrates the effectiveness and efficiency of this approach.     

带释放时间的并行机调度问题的ILS & SS算法

研究工件带释放时间的两类并行机最小化总完成时间的调度问题.针对问题提出了一种新的基于变深度环交换邻域结构的Iterated local search(ILS)算法.1)提出了变深度环交换邻域结构.2)基于变深度环交换和传统Swap的混合邻域,提出了带有两种kick策略的ILS算法.3)为了加强ILS逃出局部最优的能力,将Scatter search (SS)搜索方法引入了ILS算法中;算法将当前最好解和次好解进行分散处理,再从处理后的解开始继续迭代.为了验证算法的有效性,对两类并行机问题分别随机产生100组数据进行试验.实验结果表明:对于同构并行机问题,引入SS的ILS算法的计算结果与下界的平均偏差为0.99%,而没有引入SS的ILS算法的为1.06%;对于无关并行机问题,引入SS搜索方法后,ILS算法的计算结果 改进了6.06%,并明显优于多点下降算法.