Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness |
| |
Authors: | Tatsushi Nishi Yuichiro Hiranaka Masahiro Inuiguchi |
| |
Affiliation: | aDivision of Mathematical Science for Social Systems, Department of Systems Innovation, Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama, Toyonaka City, Osaka 560-8531, Japan |
| |
Abstract: | 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. |
| |
Keywords: | Hybrid flowshop scheduling Lagrangian relaxation Cut generation Dynamic programming |
本文献已被 ScienceDirect 等数据库收录! |
|