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.     

An effective Lagrangian relaxation approach for rescheduling a steelmaking-continuous casting process

This paper studies a steelmaking-continuous casting (SCC) rescheduling problem with machine breakdown and processing time variations. Two objectives are considered in this study: the efficiency objective and the stability objective. The former refers to the total weighted completion time and total sojourn time, whereas the latter refers to the number of operations processed on different machines in the initial and revised schedules. We develop a time-index formulation and an effective Lagrangian relaxation (LR) approach with machine capacity relaxation to address the rescheduling problem. The LR approach decomposes the relaxed problem into batch-level subproblems with variable processing times. A polynomial two-stage dynamic programming algorithm is proposed to solve the batch-level subproblems. An efficient subgradient algorithm with global convergence is presented to solve the corresponding Lagrangian dual (LD) problem. Computational experiments based on practical production data show that the proposed approach not only produces a high quality schedule within an acceptable time but also performs much better than a practical SCC rescheduling method from a large iron and steel enterprise in China.     

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

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

带运输考虑的多阶段动态可重入混合流水车间调度

可重入混合流水车间调度允许一个工件多次进入某些加工阶段,它广泛出现在许多工业制造过程中,如半导体制造、印刷电路板制造等.本文研究了带运输时间的多阶段动态可重入混合流水车间问题,目标是最小化总加权完成时间.针对该问题,建立了整数规划模型,进而基于工件解耦方式提出了两种改进的拉格朗日松弛(LR)算法.在这些算法中,设计了动态规划的改进策略以加速工件级子问题的求解,提出了异步次梯度法以得到有效的乘子更新方向.测试结果说明了所提出的两种改进算法在解的质量和运行时间方面均优于常规LR算法,两种算法都能在可接受的计算时间内得到较好的近优解.     

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.     

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

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

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

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

Methods based on discrete optimization for finding road network rehabilitation strategies

We study a dynamic optimization problem arising in the (long-term) planning of road rehabilitation activities. In this area one seeks a pavement resurfacing plan for a road network under budget constraints. Our main approach is to model this as an integer programming problem with underlying dynamic programming structure. We investigate properties of this model and propose a solution method based on Lagrangian relaxation where one gets subproblems that are shortest path problems. Some computational experiences based on realistic data are reported.     

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.     

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

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

考虑爬坡约束的油井间抽批调度问题

油井间抽批调度问题是确定未来给定计划期内油田井场间抽工作方式的油井各时间段的启停状态及采油量,在满足采油需求的情况下,考虑油井底部压力变化特征对油井开启的影响以及油井最小开关机时间和爬坡约束等生产工艺要求,使总的油井采油运行成本最小.针对油井数量多而导致大规模常规数学规划模型难以求解的困难,建立了基于批的混合整数规划模型.根据模型特点设计了基于变量分离的拉格朗日松弛算法（Lagrangian relaxation,LR）进行求解.针对常规动态规划方法求解分解后的带有爬坡约束的单机组子问题效率低的缺点,提出了用特征点代表同一阶段具有相同性质节点群的状态空间约简策略,使动态规划搜索节点的复杂度从O（n4）降到O（n2）,显著提高了算法的搜索效率.通过大量随机产生的数值实验表明,提出的基于变量分离的LR算法,小规模问题与CPLEX获得的最优解接近,中大规模问题能够在合理的计算时间内获得高质量的解.     

A mathematical programming model for AGVS planning and control in manufacturing systems

In this paper, problems of the planning and control of automated guided vehicles in manufacturing systems are discussed. A mixed integer programming model is developed to minimize the total material handling cost in manufacturing systems. In order to solve this NP-complete problem efficiently, a decomposition approach following the Lagrangian relaxation method is used. The decomposed sub-problems can be solved by a dynamic programming method. An efficient algorithm is developed to solve the entire problem and a numerical example is presented to illustrate the method of solution.     

并行机实时调度问题的LR&CG算法

研究了目标函数为最小化总加权完成时间的并行机实时调度问题.建立该问题混合整数规划模型,并提出融合拉格朗日松弛(LR)和列生成(CG)的 LR & CG 混合算法.该算法包含双重迭代,在内环以次梯度法作为下界求解器和列生成器,在外环通过求解限制主问题来获得影子价格以调节拉格朗日乘子.计算实验结果表明,在相同的计算时间内, LR & CG 能够比常规的 LR 算法获得更好的上界和下界,表明了前者具有更好的收敛性能.     

Energy-efficient joint path-following for attitude-fixed space manipulators with bounds on completion time and motor voltage/current

This paper investigates the minimum-energy joint path-following problem for space manipulators whose base attitude is stabilized by reaction wheels. In the problem, manipulator joint path is specified for rest-to-rest motion and constraints are imposed as the upper bound on both motion completion time and the voltage/current limits of DC motors in manipulator joints and reaction wheels. We suggest a simple two-stage algorithm to address this problem. The algorithm first tries to find a global optimal solution by solving a relaxed convex problem. If the convex relaxation is not successful, then the algorithm solves subproblems iteratively to find a suboptimal solution. Since both problems are formulated as second-order cone programming (SOCP) form, they can be solved efficiently using dedicated SOCP solvers. The effectiveness of the proposed method is verified by numerical experiments.     

用Lagrangian松弛法解化工批处理调度问题

研究基于Lagrangian松弛法的化工批处理过程的调度方法.建立了化工批处理过 程调度问题的一种混合整数规划(MILP)模型,并通过松弛离散变量和连续变量共存的约束, 将问题分解为一个两层次的优化问题,其中上层是原问题的对偶问题,下层由两个子问题构 成:一个与产品批量有关,另一个确定操作时间表,分别用线性规划和动态规划方法解这两个 子问题.然后从对偶问题的解构作原问题的可行解.数值试验结果证明了该方法的有效性.     

A new Lagrangian Relaxation Algorithm for scheduling dissimilar parallel machines with release dates

In this article we investigate the parallel machine scheduling problem with job release dates, focusing on the case that machines are dissimilar with each other. The goal of scheduling is to find an assignment and sequence for a set of jobs so that the total weighted completion time is minimised. This type of production environment is frequently encountered in process industry, such as chemical and steel industries, where the scheduling of jobs with different purposes is an important goal. This article formulates the problem as an integer linear programming model. Because of the dissimilarity of machines, the ordinary job-based decomposition method is no longer applicable, a novel machine-based Lagrangian relaxation algorithm is therefore proposed. Penalty terms associated with violations of coupling constraints are introduced to the objective function by Lagrangian multipliers, which are updated using subgradient optimisation method. For each machine-level subproblem after decomposition, a forward dynamic programming algorithm is designed together with the weighted shortest processing time rule to provide an optimal solution. A heuristics is developed to obtain a feasible schedule from the solution of subproblems to provide an upper bound. Numerical results show that the new approach is computationally effective to handle the addressed problem and provide high quality schedules.     

A Train Dispatching Model Under a Stochastic Environment: Stable Train Routing Constraints and Reformulation

After major capacity breakdown(s) on a railway network, train dispatchers need to generate appropriate dispatching plans to recover the impacted train schedule from perturbations and minimize the expected total train delay time under stochastic scenarios. In this paper, we propose a cumulative flow variables-based integer programming model for dispatching trains under a stochastic environment on a general railway network. Stable Train Routing (STR) constraints are introduced to ensure that trains traverse on the same route across different capacity breakdown scenarios, which are further reformulated to equivalent linear inequality constraints. Track occupancy and safety headways are modelled as side constraints which are dualized through a proposed Lagrangian relaxation solution framework. The original complex train dispatching problem is then decomposed to a set of single-train and single-scenario optimization subproblems. For each subproblem, a standard label correcting algorithm is embedded for finding the time dependent least cost path on a space-time network. The resulting dual solutions can be transformed to feasible solutions through priority rules. Numerical experiments are conducted to demonstrate the efficiency and effectiveness of the proposed solution approach.     

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.     

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.     

A heuristic algorithm based on Lagrangian relaxation for the closest string problem

The closest string problem that arises in both computational biology and coding theory is to find a string minimizing the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as a mixed-integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Computational experiments will show that the proposed algorithm can find good approximate solutions very fast.