工件带安装时间的单机排序问题的列生成算法

在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松弛为原问题提供了很好的下界,然后提出一个近似算法.通过实验数据表明,我们的算法对中等规模的排序问题1|t_(ij),r_j|∑w_jC_j是有效的.     

考虑订单合并和货物转运的多式联运路径优化研究

为了获得运输的规模经济效应,本文研究了一种考虑订单合并和货物转运的零担多式联运路径优化问题。首先,以总运输成本为目标函数,以网络中的运输工具容量、可以提供的运输工具最大数量、运输工具服务的关闭时间以及订单时间窗为约束,构建混合整数规划模型,在模型中允许多个订单进行合并运输并考虑运输过程中的转运成本。其次,由于多式联运路径优化问题是典型的NP-hard问题,为了快速求解该模型,开发了一种可以快速为该问题提供近似最优解和下界的列生成启发式算法。最后,生成并测试了大量算例,结果表明所开发的列生成启发式算法可以在较短的时间内提供高质量的近似最优解。文章所构建的模型和开发的列生成启发式算法可以为零担自营多式联运物流企业提供高效的决策支持。     

多系统服务中心的多技能服务人员调度问题研究

研究具有多系统的服务中心的多技能服务人员的调度问题.通过解决雇用哪些类型的服务人员,各类人员雇用多少,人员如何在各系统中转移以及在什么时候休息等问题,使得服务中心在满足一定的服务水平下的雇用和转移成本最小.并且建立了该复杂系统的整数规划模型,对于大规模问题提出了基于列生成法的启发式算法,列举了一个算例来简单说明此方法的基本步骤.     

基于动态列生成算法的飞机排班问题研究

飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响;飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP-Hard问题.在考虑对多种机型的飞机进行排班时,大大增加了问题的复杂性.针对航空公司实际情况,建立多种机型的飞机排班模型;为实现模型的有效求解,提出了基于约束编程的动态列生成算法;即用约束编程快速求解航班连线(航班串)并计算航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性.     

背包问题的两阶段动态规划算法

本文通过理论分析给出了背包问题的两阶段动态规划算法，用例题说明了其求解过程。在计算机上运用本文所述算法和背包问题的动态规划算法求解了大量例题。解题实践说明，对于大中型背包问题，两阶段动态规划算法由于只要求对少量变量进行排序而使解题时间大为缩短，是一种值得推荐的算法。     

随机需求收益最大化分销网络设计问题

研究随机需求的供应链分销网络设计问题。考虑供应商可以选择所服务的零售商,且供应商通过定价决策确定所服务的零售商。针对此问题,建立了一个非线性整数规划模型和一个等价的集合包裹模型,并利用列生成算法求解集合包裹模型,同时提出一种O（ n3 logn）时间的算法求解列生成算法中产生的子问题。数值计算表明,本文所提出的算法具有很好的最优性和可行性。     

数学规划与约束规划整合下的多目标分组排序问题研究

分组排序问题属于NP-难题, 单纯的数学规划模型或约束规划模型都无法在有效时间内解决相当规模的此类问题. 控制成本、缩短工期和减少任务延迟是排序问题的三个基本目标, 在实际工作中决策者通常需要兼顾三者, 并在 三者之间进行权衡. 多目标分组排序问题 的研究增强了排序问题的实际应用价值, 有利于帮助决策者处理复杂的多目标环境. 然而, 多目标的引入也增加了问题求解难度, 针对数学规划擅长寻找最优, 约束规划擅长排序的特点, 将两类方法整合起来, 提出一个基于Benders分解算法, 极大提高了此类问题的求解 效率.     

铁路客运网络列车开行方案优化模型的列生成算法

列车开行方案的设计是铁路旅客运输组织规划中的一个重要环节。本文首先给出了一个综合考虑铁路旅客运输的经济效益和公共服务性的优化模型,以铁路旅客运输的公共效益最大化为目标,对整个铁路客运网络上不同始发-终到和不同停站方式的列车开行方案进行优化。然后提出了一个求解此模型的启发式列生成算法,该算法与标准列生成算法相比,可以减少迭代次数并缩短收敛时间。最后给出一组利用随机生成的网络和需求进行求解的算例,验证本算法可以在较短时间内求解较大规模的铁路网络列车开行方案优化问题,并能有效缩小问题规模。     

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

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

工件带简单线性恶化函数和共同交货期单机排序问题

本文研究单机排序问题,其中工件加工时间具有简单线性恶化函数.同时,所有工件均具有一个给定共同交货期.目标函数为最小化提前有奖延误受罚之和.在逆一致性条件下,给出了求解该排序问题的一个伪多项式时间动态规划算法.同时借助于几何舍入技巧,对求解这类排序问题给出了一个充分多项式时间的近似算法(FPTAS)。     

Solving VRPTWs with Constraint Programming Based Column Generation

Constraint programming based column generation is a hybrid optimization framework recently proposed (Junker et al., 1999) that uses constraint programming to solve column generation subproblems. In the past, this framework has been used to solve scheduling problems where the associated graph is naturally acyclic and has done so very efficiently. This paper attempts to solve problems whose graph is cyclic by nature, such as routing problems, by solving the elementary shortest path problem with constraint programming. We also introduce new redundant constraints which can be useful in the general framework. The experimental results are comparable to those of the similar method in the literature (Desrochers, Desrosiers, and Solomon, 1992) but the proposed method yields a much more flexible approach.     

A new approach for crew pairing problems by column generation with an application to air transportation

We propose a new approach to crew-pairing problems arising in the context of airline companies. The problem is first formulated as a large scale set covering problem with many colums, each column representing a valid crew-pairing. We then suggest a solution procedure for the continuous relaxation of this large scale problem, based on generalized linear programming, in which the column generation subproblem is shown to be equivalent to a shortest path problem in an associated graph. Computational results obtained on a series of real problems (involving up to 329 flight segments) are reported, confirming both computational efficiency and practical applicability of the new approach. Indeed not only were the resulting solutions observed to be integral for most test problems, but average savings of about 4 to 5% over the best available hand-built solutions were shown to be obtained.     

无关机上极小化求和问题的平行分批排序（英）

本文我们考虑了无关机上的平行分批排序问题.对于批容量无限的平行批排序模型,目标是极小化总完工时间,我们对$p_{ij}\leq p_{ik}$ $(i=1, \cdots, m; 1\leq j\neq k\leq n)$这种一致性的情况设计了多项式的动态规划算法.对于批容量有限的平行批排序模型,我们讨论了$p_{ij}=p_{i}$ $(i=1, \cdots, m; j=1,\cdots, n)$这种情况, 当不考虑工件可被拒绝时,对极小化加权总完工时间的排序,我们给出了其最优算法;当考虑工件可被拒绝时,对极小化被接收工件的加权总完工时间加上被拒绝工件的总拒绝费用的排序,我们设计了一拟多项时间算法.     

On the Necessary and Sufficient Condition of the Local Optimal Solution of Quadratic Programming

In this paper a necessary and sufficient aptimality condition of quadratic programming is giver. The main result is Theorem 3.1. It is shown that a point x_0 is local optimal solution of quadratic programming (1, l)if and only if x_0 is a Kuhn-Tu cker point and h^Tch is non-negative for every point im{h|a^T_jh=0,j\in J^*,a^T_jh \leq 0,j\in J_1\J^*}.     

Bus driver duty optimization using an integer programming and evolutionary hybrid algorithm

This paper describes the details of a successful application where an integer programming and evolutionary hybrid algorithm was used to solve a bus driver duty optimization problem. The task is NP-hard, therefore theoretically optimal solutions can only be calculated for very small problem instances. Our aim is to obtain solutions of good quality within reasonable time limits. We first applied an integer programming approach to a set partitioning problem. The model was solved with a column generation algorithm in a branch and bound scheme. In order to solve larger real-life problems, we have combined the integer programming method with a greedy 1+1 steady state evolutionary algorithm. The resulting hybrid algorithm was capable of providing near-optimal solutions within reasonable timescales to larger instances of the bus driver scheduling problem. We present the results and running times of our algorithm in detail, as well as possible directions of future improvements.     

Nodal aggregation of resource constraints in a shortest path problem

The shortest path problem with resource constraints consists of finding the minimum cost path between two specified points while respecting constraints on resource consumption. Its solving by a dynamic programming algorithm requires a computation time increasing with the number of resources. With the aim of producing rapidly a good heuristic solution we propose to reduce the state space by aggregating resources. Our approach consists of projecting the resources on a vector of smaller dimension and then to dynamically adjust the projection matrix to get a better approximation of the optimal solution. We propose an adjustment based on Lagrangian and surrogate relaxations in a column generation framework, in which the sub-problems are shortest path problems with resource constraints. We adjust the multipliers only one time at each column generation iteration. This permit to obtain good solutions of the scheduling problem in few time.     

Interactive bicriterion decision support for a large scale industrial scheduling system

In this paper we develop an interactive decision analysis approach to treat a large scale bicriterion integer programming problem, addressing a real world assembly line scheduling problem of a manufacturing company. This company receives periodically a set of orders for the production of specific items (jobs) through a number of specialised production (assembly) lines. The paper presents a non compensatory approach based on an interactive implementation of the ε-constraint method that enables the decision maker to achieve a satisfactory goal for each objective separately. In fact, the method generates and evaluates a large number of non dominated solutions that constitute a representative sample of the criteria ranges. The experience with a specific numerical example shows the efficiency and usefulness of the proposed model in solving large scale bicriterion industrial integer programming problems, highlighting at the same time the modelling limitations.     

Column generation based heuristic for tactical planning in multi-period vehicle routing

The periodic vehicle routing problem (PVRP) consists in establishing a planning of visits to clients over a given time horizon so as to satisfy some service level while optimizing the routes used in each time period. The tactical planning model considered here restricts its attention to scheduling visits and assigning them to vehicles while leaving sequencing decisions for an underlying operational model. The objective is twofold: to optimize regional compactness of the routes in a desire to specialize routes to restricted geographical area and to balance the workload evenly between vehicles. Approximate solutions are constructed using a truncated column generation procedure followed by a rounding heuristic. This mathematical programming based procedure can deal with problems with 50–80 customers over five working days which is the range of size of most PVRP instances treated in the literature with meta-heuristics. The paper highlights the importance of alternative optimization criteria not accounted for in standard operational models and provides insights on the implementation of a column generation based rounding heuristic.