Lagrangian bounds for just-in-time job-shop scheduling

We study the job-shop scheduling problem with earliness and tardiness penalties. We describe two Lagrangian relaxations of the problem. The first one is based on the relaxation of precedence constraints while the second one is based on the relaxation of machine constraints. We introduce dedicated algorithms to solve the corresponding dual problems. The second one is solved by a simple dynamic programming algorithm while the first one requires the resolution of an NP-hard problem by branch and bound. In both cases, the relaxations allow us to derive lower bounds as well as heuristic solutions. We finally introduce a simple local search algorithm to improve the best solution found. Computational results are reported.     

Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness

In this paper, we address a new Lagrangian relaxation (LR) method for solving the hybrid flowshop scheduling problem to minimize the total weighted tardiness. For the conventional LR, the problem relaxing machine capacity constraints can be decomposed into individual job-level subproblems which can be solved by dynamic programming. The Lagrangian dual problem is solved by the subgradient method. In this paper, a Lagrangian relaxation with cut generation is proposed to improve the Lagrangian bounds for the conventional LR. The lower bound is strengthened by imposing additional constraints for the relaxed problem. The state space reductions for dynamic programming for subproblems are also incorporated. Computational results demonstrate that the proposed method outperforms the conventional LR method without significantly increasing the total computing time.     

CIMS下单级单资源约束的生产批量计划问题的新算法

对单级单资源约束的生产批量计划问题采用Ｌａｇｒａｎｇｉａｎ松弛算法进行求解,对能力约束进行松弛后的Ｌａｇｒａｎｇｉａｎ问题的求解,构造了新的启发式算法,在用Ｌａｇｒａｎｇｉａｎ松驰问题获得原问题的可行解时,提出了多回路启动式算法,仿真实验结果表明,平均相对对偶间隙可在２％以内。     

Calculating the best dual bound for problems with multiple Lagrangian relaxations

There are often many ways in which a given problem can be relaxed in a Lagrangian fashion. It is not obvious a priori, which relaxation produces the best bound. Moreover, a bound may appear to be the best for a certain data set, while being among the worst for another problem instance. We consider here an optimization problem over the set of Lagrangian relaxations with the objective to indicate the relaxation producing the best dual bound. An iterative technique to solve this problem is proposed based on constraints generation scheme. The approach is illustrated by a computational study for a class of the two-stage capacitated facility location problem.     

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

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

航天测控调度分枝定界算法

通过分析航天测控调度问题的测控需求,建立了航天测控调度整数规划模型,引入了拉格朗日松弛思想并与分枝定界算法结合,设计了基于拉格朗日松弛的分枝定界算法求解航天测控调度问题。通过对两个场景的仿真实验,得到了两个场景的航天测控调度问题最优值,验证了基于拉格朗日松弛的分枝定界算法的有效性。     

A Lagrangian relaxation approach for a large scale new variant of capacitated clustering problem

This paper studies a new variant of capacitated clustering problem (VCCP). In the VCCP, p facilities which procure a raw material from a set of suppliers are to be located among n potential sites (n > p) such that the total cost of assigning suppliers to the facilities and opening such facilities is minimized. Each supplier has a limited supply volume and each facility has a minimum supply requirement that must be satisfied by assigning enough suppliers to the facility. Each supplier can be assigned to at most one facility. When a supplier is assigned to a facility, the former will supply its all available volume to the latter. In order to solve the VCCP, a Lagrangian relaxation approach (LR) with two phases of dual optimization, the subgradient deflection in the first phase and the standard subgradient method in the second phase, is proposed. In the approach, the assignment constraints are relaxed. The resulting Lagrangian relaxed problem can be decomposed into a set of independent knapsack problems, which can be solved to optimality efficiently. At each Lagrangian iteration, a feasible solution is constructed from that of the Lagrangian relaxed problem by applying a greedy algorithm. Finally, the best feasible solution found so far is improved by a simple tabu search algorithm. Numerical tests on random instances show that the proposed LR can produce a tight lower bound and a high quality feasible solution for all instances with up to 4000 suppliers, 200 potential sites, and 100 plants to locate.     

An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times

This study proposes an exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. The algorithm is an extension of the authors' previous algorithm for the single-machine scheduling problem without setup times, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. In the first stage of the algorithm, the conjugate subgradient algorithm or the column generation algorithm is applied to a Lagrangian relaxation of the original problem to adjust multipliers. Then, in the second stage, constraints are successively added to the relaxation until the gap between lower and upper bounds becomes zero. The relaxation is solved by dynamic programming and unnecessary dynamic programming states are eliminated to suppress the increase of computation time and memory space. In this study a branching scheme is integrated into the algorithm to manage to solve hard instances. The proposed algorithm is applied to benchmark instances in the literature and almost all of them are optimally solved.     

Reoptimization in Lagrangian methods for the 0-1 quadratic knapsack problem

The 0-1 quadratic knapsack problem consists of maximizing a quadratic objective function subject to a linear capacity constraint. To exactly solve large instances of this problem with a tree search algorithm (e.g., a branch and bound method), the knowledge of good lower and upper bounds is crucial for pruning the tree but also for fixing as many variables as possible in a preprocessing phase. The upper bounds used in the best known exact approaches are based on Lagrangian relaxation and decomposition. It appears that the computation of these Lagrangian dual bounds involves the resolution of numerous 0-1 linear knapsack subproblems. Thus, taking this huge number of resolutions into account, we propose to embed reoptimization techniques for improving the efficiency of the preprocessing phase of the 0-1 quadratic knapsack resolution. Namely, reoptimization is introduced to accelerate each independent sequence of 0-1 linear knapsack problems induced by the Lagrangian relaxation as well as the Lagrangian decomposition. Numerous numerical experiments validate the relevance of our approach.     

具有混合动态约束的生产系统优化调度新算法

研究具有混合动态约束的生产系统优化调度问题.在Lagrange松弛法框架下,求解包 含混合动态约束的子问题仍然十分复杂,许多算法只能求得子问题的近似解,降低了Lagrange 松弛法的有效性.文中提出了一种新的离散状态定义方法,解除了子问题中离散决策变量与连 续决策变量的耦合.在此基础上结合动态规划思想,提出了一种新算法,在保证整体最优性的前 提下,可以同时对离散和连续状态分别寻优,对算法复杂性进行了初步分析,新算法效率高且可 以得到子问题的精确解.电力系统调度问题的数值算例验证了新算法的有效性.     

考虑风力发电批特征的电力机组调度问题

电力机组组合问题是在给定的计划周期内确定火电、风电和蓄 电池机组的开关机状态及发电量, 以满足系统的负荷需求、旋转备用等约束要求. 为了降低风电在电网中的供电不稳定 性, 引入蓄电池储能系统与风机进行协调调度. 由于大数量风机的介入, 明显增加了问 题处理的难度和复杂性. 本文从一个新的视角 将相近物理位置的风机进行组批, 基于批的视角对问题建立了批模型. 为 了提高批模型的性能, 提出了批模型参数的变换方法. 根据问题的NP-难特征和模 型的复杂结构, 开发了拉格朗日松弛(Lagrangian relaxation, LR)算法进 行求解. 为了加速算法的求解效率, 提出了子 问题近似求解的代理次梯度的拉格朗日松弛算法. 实验结果表明, 提出的批模型明 显优于传统的单机模型. 基于批模型开发的拉格朗日松弛算法与CPLEX优化软 件相比, 能够在较短的时间内获得高质量的解.     

An exact approach for scheduling jobs with regular step cost functions on a single machine

This paper studies a single-machine scheduling problem whose objective is to minimize a regular step total cost function. Lower and upper bounds, obtained from linear and Lagrangian relaxations of different Integer Linear Programming formulations, are compared. A dedicated exact approach is presented, based on a Lagrangian relaxation. It consists of finding a Constrained Shortest Path in a specific graph designed to embed a dominance property. Filtering rules are developed for this approach in order to reduce the size of the graph, and the problem is solved by successively removing infeasible paths from the graph. Numerical experiments are conducted to evaluate the lower and upper bounds. Moreover, the exact approach is compared with a standard solver and a naive branch-and-bound algorithm.     

三阶段拉格朗日启发式算法求解带同时取送货的绿色车辆路径问题

针对带同时取送货的绿色车辆路径问题,以最小化带碳排放费用的配送成本为优化目标,建立混合整数规划模型,并提出一种结合数学规划方法与启发式算法的三阶段拉格朗日启发式算法进行求解.第1阶段,利用拉格朗日松弛技术得到该问题的拉格朗日对偶模型;第2阶段,设计一种改进的次梯度算法迭代求解该对偶模型,同时引入修复机制,将每次迭代所得下界对应的解修复为原问题较高质量的可行解,并在下次迭代中利用该可行解更新次梯度方向和步长;第3阶段,设计一种启发式局部搜索算法,对第2阶段得到的可行解进行优化,进一步改进解的质量,以得到原问题的近似最优解.实验表明,所提出算法能够获得问题的一个优质解,同时提供一个紧致下界,用以定量评估解的质量.     

The multi-item capacitated lot-sizing problem with safety stocks and demand shortage costs

We address a multi-item capacitated lot-sizing problem with setup times, safety stock and demand shortages. Demand cannot be backlogged, but can be totally or partially lost. Safety stock is an objective to reach rather than an industrial constraint to respect. The problem is np-hard. We propose a Lagrangian relaxation of the resource capacity constraints. We develop a dynamic programming algorithm to solve the induced sub-problems. An upper bound is also proposed using a Lagrangian heuristic with several smoothing algorithms. Some experimental results showing the effectiveness of the approach are reported.     

A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

Models for a traveling purchaser problem with additional side-constraints

The traveling purchaser problem (TPP) is the problem of determining a tour of a purchaser that needs to buy several items in different shops such that the total amount of travel and purchase costs is minimized. Motivated by an application in machine scheduling, we study a variant of the problem with additional constraints, namely, a limit on the maximum number of markets to be visited, a limit on the number of items bought per market and where only one copy per item needs to be bought. We present an integer linear programming (ILP) model which is adequate for obtaining optimal integer solutions for instances with up to 100 markets. We also present and test several variations of a Lagrangian relaxation combined with a subgradient optimization procedure. The relaxed problem can be solved by dynamic programming and can also be viewed as resulting from applying a state space relaxation technique to a dynamic programming formulation. The Lagrangian based method is combined with a heuristic that attempts to transform relaxed solutions into feasible solutions. Computational results for instances with up to 300 markets show that with the exception of a few cases, the reported differences between best upper bound and lower bound values on the optimal solutions are reasonably small.     

Enhancing CLP branch and bound techniques for scheduling problems

In this paper, we propose a constraint logic programming (CLP) approach to the solution of a job shop scheduling problem in the field of production planning in orthopaedic hospital departments. A pure CLP on finite domain (CLP(FD)) approach to the problem has been developed, leading to disappointing results. In fact, although CLP(FD) has been recognized as a suitable tool for solving combinatorial problems, it presents some drawbacks for optimization problems. The main reason concerns the fact that CLP(FD) solvers do not effectively handle the objective function and cost‐based reasoning through the simple branch and bound scheme they embed. Therefore, we have proposed an improvement of the standard CLP branch and bound algorithm by exploiting some well‐known operations research results. The branch and bound we integrate in a CLP environment is based on the optimal solution of a relaxation of the original problem. In particular, the relaxation used for the job shop scheduling problem considered is the well‐known shifted bottleneck procedure considering single machine problems. The idea is to decompose the original problem into subproblems and solve each of them independently. Clearly, the solutions of each subproblem may violate constraints among different subproblems which are not taken into account. However, these solutions can be exploited in order to improve the pruning of the search space and to guide the search by defining cost‐based heuristics. The resulting algorithm achieves a significant improvement with respect to the pure CLP(FD) approach that enables the solution of problems which are one order of magnitude greater than those solved by a pure CLP(FD) algorithm. In addition, the resulting code is less dependent on the input data configuration. Copyright © 2001 John Wiley & Sons, Ltd.     

Scheduling a hybrid flowshop with batch production at the last stage

In this paper, we address the problem of scheduling n$n$ jobs in an s$s$-stage hybrid flowshop with batch production at the last stage with the objective of minimizing a given criterion with respect to the completion time. The batch production at stage s$s$ is referred to as serial batches by Hopp and Spearman where the processing time of a batch is equal to the sum of the processing times of all jobs included in it. This paper establishes an integer programming model and proposes a batch decoupling based Lagrangian relaxation algorithm for this problem. In this algorithm, after capacity constraints are relaxed by Lagrangian multipliers, the relaxed problem is decomposed based on a batch, unlike the commonly used job decoupling, so that it can be decomposed into batch-level subproblems, each for a specific batch. An improved forward dynamic programming algorithm is then designed for solving these subproblems where all operations within a batch form an in-tree structure and the precedence relations exist not only between the operations of a job but between the jobs in this batch at the last stage. A computational comparison is provided for the developed algorithm and the commonly used Lagrangian relaxation algorithm which, after capacity constraints and precedence relations within a batch are relaxed, decomposes the relaxed problem into job-level subproblems and solves the subproblems by using dynamic programming. Numerical results show that the designed Lagrangian relaxation method provides much better schedules and converges faster for small to medium sized problems, especially for larger sized problems.     

Job Shop 调度的序列拉格朗日松驰法

拉格朗日松驰法为求解复杂调度问题次最优解的一种重要方法，陆宝森等人把这种方法推广到Ｊｏｂ Ｓｈｏｐ调度问题，但他们的方法存在解振荡问题。本文提出一种序列拉格朗日松驰法，它能避免解振荡。     

车间调度算法的研究和开发

针对车间调度问题,提出了一种改进的拉氏松弛算法,在增加辅助目标函数的基础上,通过对子问题的限制和搜索策略的改变,使拉氏算法的计算量减少,近优解的搜索能力有很大改善,本文还提出了一种基因优化算法,充分利用拉氏算法得到的多个近优解,进一步优化结,仿真结果表明对车间调度问题得到了较好的结果,本方法也可用于其它有约束的规则问题。