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.     

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.     

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.     

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

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

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.     

Scheduling of manufacturing systems using the Lagrangian relaxationtechnique

The practical solutions for three manufacturing scheduling problems are examined. As each problem is formulated, constraints are added or modified to reflect increasing real world complexity. The first problem considers scheduling single-operation jobs on identical machines. The second problem is concerned with scheduling multiple-operation jobs with simple fork/join precedence constraints on identical machines. The third problem is the job shop problem in which multiple-operation jobs with general precedence constraints are scheduled on multiple machine types Langrangian relaxation is used to decompose each of the scheduling problems into job- or operation-level subproblems. The subproblems are easier to solve than the original problem and have intuitive appeal. This technique results in algorithms which generate near-optimal schedules efficiently, while giving a lower bound on the optimal cost. In resolving the scheduling problem from one time instant to the next, the Lagrange multipliers from the last schedule can be used to initialize the multipliers, further reducing the computation time     

Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme.     

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.     

Mixed coordination method for long-horizon optimal control problems

We present a new approach to solving long-horizon, discrete-time optimal control problems using the mixed coordination method. The idea is to decompose a long-horizon problem into subproblems along the time axis. The requirement that the initial state of a subproblem equal the terminal state of the preceding subproblem is relaxed by using Lagrange multipliers. The Lagrange multipliers and initial state of each subproblem are then selected as high-level variables. The equivalence of the two-level formulation and the original problem is proved for both convex and non-convex cases. The low-level subproblems are solved in parallel using extended differential dynamic programming (DDP). An efficient way to find the gradient and hessian of a low-level objective function with respect to high-level variables is developed. The high-level problem is solved using the modified Newton method. An effective procedure is developed to select initial values of multipliers based on the initial trajectory. The method can convexify the high-level problem while maintaining the separability of an originally non-convex problem. The method performs better and faster than one-level DDP for both convex and non-convex test problems.     

Scheduling on parallel machines with preemption and transportation delays

This paper deals with an identical parallel machines scheduling problem, where independent jobs can be preempted and transported from one machine to another. The transportation of a preempted job requires a time called the transportation delay. The goal is to find a solution that minimizes the total completion time (makespan). We first study the case of equal-size jobs where new complexity results are given. Then, to solve the problem with two identical machines, we present a dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS). Experimental results show the efficiency of the FPTAS compared to a previously published heuristic.     

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.     

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.     

Limitations of Incremental Dynamic Programming

We consider so-called “incremental” dynamic programming algorithms, and are interested in the number of subproblems produced by them. The classical dynamic programming algorithm for the Knapsack problem is incremental, produces nK subproblems and nK ² relations (wires) between the subproblems, where n is the number of items, and K is the knapsack capacity. We show that any incremental algorithm for this problem must produce about nK subproblems, and that about nKlogK wires (relations between subproblems) are necessary. This holds even for the Subset-Sum problem. We also give upper and lower bounds on the number of subproblems needed to approximate the Knapsack problem. Finally, we show that the Maximum Bipartite Matching problem and the Traveling Salesman problem require exponential number of subproblems. The goal of this paper is to leverage ideas and results of boolean circuit complexity for proving lower bounds on dynamic programming.     

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.     

启发式列生成算法求解带恶化效应的同构并行机调度问题

针对实际生产中广泛存在的一类带恶化效应的同构并行机调度问题,以最小化最大完工时间为优化目标,构建该问题的整数规划模型,并提出一种启发式列生成算法(HCGA)进行求解.在HCGA中,首先,利用Dantzig-Wolfe分解方法,将原问题分解为一个主问题(MP)和多个子问题;然后,设计启发式算法获得初始列,其中每列为一台机器上的一个调度方案,基于初始列构建限制主问题(RMP)模型;接着,设计快速有效的动态规划算法求解子问题,以得到需添加至RMP的列集,同时,考虑传统列生成算法收敛速度较慢,设计一系列方法来加速列生成过程;最后,基于所获取的MP线性松弛解,设计深潜启发式算法确定原问题的整数解.HCGA与商用求解器GUROBI的对比实验结果表明,HCGA可在较短时间内获得更优的解.     

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

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

A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time

The identical parallel machine scheduling problem with the objective of minimizing total weighted completion time is considered in the online setting where jobs arrive over time. An online algorithm is proposed and is proven to be (2.5–1/2m)-competitive based on the idea of instances reduction. Further computational experiments show the superiority over other algorithms in the average performance.     

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

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

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

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

Weighted Dantzig–Wolfe Decomposition for Linear Mixed-integer Programming

Dantzig–Wolfe decomposition can be used to solve the Lagrangian dual of a linear mixed-integer programming problem ( MIP ) if the dual structure of the ( MIP ) is exploited via Lagrangian relaxation with respect to the complicating constraints. In the so-called weighted Dantzig–Wolfe decomposition algorithm, instead of the optimal solution of the Dantzig–Wolfe master problem a specially weighted average of the previously constructed Lagrangian multipliers and the optimal solution of the master problem is used as Lagrangian multiplier for the next Lagrangian subproblem to be solved. A convergence proof of the weighted Dantzig–Wolfe decomposition algorithm is given, and some properties of this procedure together with computational results for the capacitated facility location problem are discussed.