An Effective Subgradient Method for Scheduling a Steelmaking-Continuous Casting Process
An Effective Subgradient Method for Scheduling a Steelmaking-Continuous Casting Process
复制标题
DOI：
10.1109/tase.2014.2332511
复制
发表时间：
2015-07
影响因子：
5.6
通讯作者：
K. Mao;Q. Pan;T. Chai;P. Luh
中科院分区：
文献类型：
--
作者：
K. Mao;Q. Pan;T. Chai;P. Luh
炼钢-连铸(SCC)工艺包括炼钢、精炼和连铸，是钢铁生产的主要瓶颈之一。这一过程的高效调度对于提高整个生产系统的生产率和降低生产成本至关重要。我们给出了该调度问题的时间指标模型和基于机器能力约束松弛的拉格朗日松弛方法。松弛问题的求解采用了一种高效的多项式动态规划算法。利用偏转条件次梯度法求解相应的拉格朗日对偶(LD)问题。与传统的求解LD问题的次梯度算法不同，该方法使用Brannlund的水平控制策略来保证收敛，取代了对偶问题的最优解是先验已知的严格收敛条件。此外，我们的方法通过引入偏转的条件次梯度来减弱传统次梯度算法收敛速度慢的锯齿现象，从而提高了效率。计算结果表明，该方法能够快速得到高质量的解，在SCC调度中具有很好的应用前景。从业人员请注意--高效的SCC计划对钢铁生产的制造系统至关重要。不幸的是，调度问题是极其困难的，因为它具有组合性和实际的复杂约束，如作业分组约束、优先约束、不同的运输时间和调整时间。为了在可接受的计算时间内获得高质量的解，我们可以使用面向问题的方法，这可以是LR。然而，该方法有两个不足之处：一是经验终止准则，如最大迭代次数或运行时间，很难找到解决各种问题的金科玉律；二是所谓之字形现象造成的效率低下。为了克服这些不足，本文提出了一种基于机器能力松弛的SCC调度的有效次梯度方法。该方法根据算法的收敛条件给出了一个客观的终止准则，并基于新的搜索方向或新的次梯度改进了算法的效率。然后，将该方法应用于SCC调度问题的求解。计算结果证实了该方法的有效性和高效性。该方法也适用于其他类似的生产调度问题。
The steelmaking-continuous-casting (SCC) process, which includes steelmaking, refining and continuous casting, is one of the major bottlenecks of iron and steel production. Efficient and effective scheduling of this process is essential to improve the productivity and reduce the production costs of the entire production system. We present a time-index formulation for this scheduling problem and a Lagrangian relaxation (LR) approach based on the relaxation of the machine capacity constraints. The relaxed problem is solved using an efficient polynomial dynamic programming algorithm. The corresponding Lagrangian dual (LD) problem is solved using a deflected conditional subgradient level method. Unlike the conventional subgradient algorithms for the LD problem, our method guarantees convergence using the Brannlund's level control strategy to replace the strict convergence condition that the optimum of the dual problem is known a priori. Furthermore, our method enhances the efficiency by introducing a deflected conditional subgradient to weaken the zigzagging phenomena that slows the convergence of conventional subgradient algorithms. The computational results demonstrate that the approaches can quickly obtain high-quality solutions and are notably promising for the SCC scheduling. Note to Practitioners-Efficient and effective SCC schedule is vital for the manufacturing system of iron and steel production. Unfortunately, the scheduling is extremely difficult because of its combinatorial nature and practical complex constraints such as job grouping constraints, precedence constraints, different transport time, and setup times. To obtain high-quality solutions within an acceptable computational time, we can use a problem-oriented approach, which can be the LR. However, there are two deficiencies in this approach: its empirical termination criteria, such as maximal iteration number or running time, which make it difficult to find a golden rule for various problems, and the inefficiency, which is caused by the so-called zigzagging phenomena. To overcome these deficiencies, this paper develops an effective subgradient method for SCC scheduling based on the machine capacity relaxation. This method gives an objective termination criterion based on the convergence condition of the method, and improves the efficiency based on a new search direction or a new subgradient. Then, the work shows how this method can be applied to solve an SCC scheduling problem. The computational results confirm their effectiveness and efficiency. The approaches can also be applied to other similar production scheduling problems.