一种基于Lagrangian松弛法求解化工批处理过程调度的方法

提出一种快速求取化工批处理过程次优调度的方法，通过约束变换，引入操作批量的函数和松弛物料贮存能力，将调度问题分解为一个两层次的优化问题，用动态规划求解下层问题，用次梯度求解上层对偶问题，然后依据对偶问题的解，以启发方式构作原问题的可行解。数值测试结果了该方法的有效性和实用性。     

不确定条件下生产调度问题的三阶段决策方法

提出了一种可综合考虑多种不确定因素的生产调度问题三阶段决策方法. 首先分析了不确定条件下的生产调度的决策过程, 根据过程的特点将其分为基本调度、在线调整和补偿三个阶段; 对变量进行分类, 从而与3个阶段相对应; 分别建立了基于情景分析以及子问题最(近)优解的两种三阶段调度数学模型, 并给出了变量的处理方法和阶段性的模型求解方法, 来作为不同阶段的决策依据; 最后以化工批处理过程的短期调度为例, 说明了三阶段调度建模和决策过程的实现方法.     

带分批优化的多级批处理过程自组织调度方法

针对一类带批次划分的多级批处理过程优化调度问题,提出一种自下而上的自组织调度方法．首先,通过构造与批处理生产过程中的订单、批次和设备相对应的自组织个体,建立自组织调度模型框架;然后,分析多级批处理调度问题的最优性质,提出分批优化规则和自组织选择策略,并在此基础上给出自组织优化调度算法;最后,通过调度实例求解结果表明,所提方法能在短时间内获得问题的最优解或近优解,进而验证了该方法的有效性和优越性．     

等待时间有限的job-shop调度

对一类产品加工相邻步骤之间具有等待时间约束的ｊｏｂ－ｓｈｏｐ调度问题进行了建模，并采用Ｌａｇｒａｎｇｉａｎ松弛法结合动态规划对这类问题进行求解，提出了一种基于集束式搜索的启发式方法，用于从对偶问题的解构作原问题的可行解．最后给出了仿真计算结果．     

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

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

带批量分割的多级批处理调度自组织优化

针对一类带批量分割的多级批处理调度典型问题的特点,提出一种自下而上的自组织优化方法.模拟人类群体"业务办理"机制,构建了带批量分割的批处理过程调度的自组织优化模型,分析了由批次转换和批量分割引起的复杂性,提出了基于友好度的自组织选择策略和基于最小响应的批量分割策略,在此基础上,给出了自组织调度优化算法.该方法能够和短时间内获得问题的最优解或近优解,并通过调度实例求解结果验证了该方法的有效性和优越性.     

批处理机上具有两类释放时间的工件集竞争调度问题

研究了两个工件集合竞争在一台批处理机上加工的调度问题,其中每个集合的工件具有一个共同的释放时间.批处理机可以同时加工多个工件作为一批,每批的加工时间为该批工件中加工时间的最大值.基于两类释放时间的大小,针对无界批处理机上最小化一个集合工件的最大完工时间、最大延迟以及总完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,分别给出了最优求解方法.针对有界批处理机上最小化一个集合工件的最大完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,证明为一般意义NP-难问题,并给出伪多项式时间最优求解方法.     

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

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

差异工件并行批调度问题中遗传算法研究

本文考虑了遗传算法在包含差异工件的并行批处理机调度中的应用问题.工件具有不同的尺寸和到达时间.首先基于问题假设提出了一个数学规划模型,并采用BF、ERT-LPT实现工件的分批排序调度.然后考虑到这是一个NP-Hard问题,设计了新的选择、交叉、变异操作并结合遗传算法进行求解.最后通过仿真实验对比,验证了算法的有效性.     

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

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

Timetabling problem for university as assignment of activities to resources

A mathematical programming approach is presented to solve the timetabling problem in a University. It includes two subproblems that are solved sequentially. Both subproblems have the same structure consisting of a 0–1 assignment problem of conflicting activities to resources. A solution method is derived for a relaxed version of an equivalent 0–1 quadratic assignment programming problem. The paper concludes with implementation remarks, numerical results and extensions.     

A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines

In this paper, we discuss a flexible flow shop scheduling problem with batch processing machines at each stage and with jobs that have unequal ready times. Scheduling problems of this type can be found in semiconductor wafer fabrication facilities (wafer fabs). We are interested in minimizing the total weighted tardiness of the jobs. We present a mixed integer programming formulation. The batch scheduling problem is NP-hard. Therefore, an iterative stage-based decomposition approach is proposed that is hybridized with neighborhood search techniques. The decomposition scheme provides internal due dates and ready times for the jobs on the first and second stage, respectively. Each of the resulting parallel machine batch scheduling problems is solved by variable neighborhood search in each iteration. Based on the schedules of the subproblems, the internal due dates and ready times are updated. We present the results of designed computational experiments that also consider the number of machines assigned to each stage as a design factor. It turns out that the proposed hybrid approach outperforms an iterative decomposition scheme where a fairly simple heuristic based on time window decomposition and the apparent tardiness cost dispatching rule is used to solve the subproblems. Recommendations for the design of the two stages with respect to the number of parallel machines on each stage are given.     

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.     

Group-scheduling problems in electronics manufacturing

This paper addresses the flowshop group-scheduling problems typically encountered in the assembly of printed circuit boards in electronics manufacturing. A mathematical programming model is formulated to capture the characteristics inherent to group-scheduling problems experienced in electronics manufacturing as well as those common to a wide range of group-scheduling problems encountered in other production environments. Several heuristics, each incorporating different components that underlie the tabu search concept, are developed to solve this strongly NP-hard problem effectively in a timely manner. In order to investigate the quality of the heuristic solutions with respect to tight lower bounds, an effective and efficient decomposition approach is developed. The problem is decomposed into a master problem and single-machine subproblems, and a column generation algorithm is developed to solve the linear programming relaxation of the master problem. Branching schemes, compatible with the column generation subproblems, are employed to partition the solution space when the solution to the linear programming relaxation is not integral. Furthermore, tabu search based fast heuristics are implemented to solve the subproblems, and an effective stabilization method is developed to accelerate the column generation approach. An experimental design with both fixed and random factors accompanied by rigorous statistical analyses of computational tests conducted on randomly generated test problems as well as on a large size real industry problem confirm the high performance of the proposed approach in identifying quality lower bounds and strongly suggest its flexibility and applicability to a wide range of real problems.     

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.     

GA's in decomposition based design-subsystem interactions through immune network simulation

The paper describes an adaptation of genetic algorithms (GA's) in decomposition-based design of multidisciplinary systems. The coupled multidisciplinary design problem is adaptively deomposed into a number of smaller subproblems, each with fewer design variables, and the design in each subproblem allowed to proceed in parallel. Fewer design variables allow for shorter string lengths to the used in the GA-based optimization in each subproblem, reducing the number of design alternatives to be explored, and hence also reducing the required number of function evaluations to convergence. A novel procedure is proposed to account for interactions between the decomposed subproblems, and is based on the modelling of the biological immune system. This approach also uses the genetic algorithm approach to update in each subproblem the design changes of all other subproblems. The design representation scheme, therefore, is common to both the design optimization step and the procedure required to account for interaction among the subproblems. The decomposition based solution of a dual structural-control design problem is used as a test problem for the proposed approach. The convergence characteristics of the proposed approach are compared against those available from a nondecomposition-based method.     

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.     

On convex transformability and the solution of nonconvex problems via the dual of Falk

In structural optimization, most successful sequential approximate optimization (SAO) algorithms solve a sequence of strictly convex subproblems using the dual of Falk. Previously, we have shown that, under certain conditions, a nonconvex nonlinear (sub)problem may also be solved using the Falk dual. In particular, we have demonstrated this for two nonconvex examples of approximate subproblems that arise in popular and important structural optimization problems. The first is used in the SAO solution of the weight minimization problem, while the topology optimization problem that results from volumetric penalization gives rise to the other. In both cases, the nonconvex subproblems arise naturally in the consideration of the physical problems, so it seems counter productive to discard them in favor of using standard, but less well-suited, strictly convex approximations. Though we have not required that strictly convex transformations exist for these problems in order that they may be solved via a dual approach, we have noted that both of these examples can indeed be transformed into strictly convex forms. In this paper we present both the nonconvex weight minimization problem and the nonconvex topology optimization problem with volumetric penalization as instructive numerical examples to help motivate the use of nonconvex approximations as subproblems in SAO. We then explore the link between convex transformability and the salient criteria which make nonconvex problems amenable to solution via the Falk dual, and we assess the effect of the transformation on the dual problem. However, we consider only a restricted class of problems, namely separable problems that are at least C ¹ continuous, and a restricted class of transformations: those in which the functions that represent the mapping are each continuous, monotonic and univariate.     

基于二阶段随机规划的不确定条件下过程优化研究

在基于二阶段随机规划的不确定条件下过程优化研究中，Ierapetritou and Pistikopoulos(1994)提出了可行域求解策略，Liu and Sahinidis(1996)在此基础上用蒙特卡洛积分策略代替了高斯积分策略，但对于可行域的限定条件尚有欠缺。本文分析和比较了前人的工作，将蒙特卡罗积分策略与基于对偶理论的可行域限定条件相结合，提出了新的求解策略，不仅避免了可行域求解策略中求解一系列子问题而引起的计算负荷随不确定参数数目呈指数增加的不足，而且使蒙特卡洛积分策略算法中的可行域限定条件更加合理，应用文献中的算例进行了仿真实验，证明了该算法的有效性。     

连铸-轧制混流生产模式下轧批调度问题的分支-定价算法

研究了连铸——轧制在热装、温装和冷装混流生产模式下的一类新型轧批调度问题.以最小化温装钢坯（热钢锭）缓冷（等待）导致的热能损失和连轧机架切换带来的产能损失为目标,建立了整数规划模型.由于商业优化软件难以在有限时间内直接求得模型的最优解甚至可行解,提出利用Dantzig-Wolfe分解技术将原模型分解为主问题和子问题,采用列生成算法对主问题和子问题进行迭代求解得到原问题的紧下界,最后以列生成算法作为定界机制嵌入分支——定界框架中形成分支——定价算法,执行分支搜索过程以获得整数最优解.本文还从影响分支——定价算法性能的要素出发提出改进策略.针对主问题,提出列生成和拉格朗日松弛混合求解策略来抑制单一列生成算法的尾效应.针对价格子问题,在动态规划算法中提出了基于占优规则和标号下界计算方法来及早消除无效状态空间,加速求解过程.以钢铁企业的实际生产数据和扩展的随机算例进行了数值实验,结果显示所提出改进策略能够突破求解能力的限制,使分支——定价算法在可接受计算时间内求得工业规模问题的最优解.