A novel probabilistic approximate subgradient method in Lagrangian Relaxation for flow-shop scheduling problems

It is widely accepted that scheduling plays a key role in enterprise manufacturing systems as it greatly improves the efficiency and competitiveness. The flow-shop scheduling problem is a kind of typical problem which relates to many kinds of practical problems. Since the flow-shop scheduling problems are NP-hard, it is of practical value to obtain satisfying solutions within short CPU time for large-scale cases. Lagrangian Relaxation (LR) is known as an approach which can handle large-scale separable problems. By the LR approach, a complex problem can be separated into several small subproblems which are easier to solve. However, there is a key challenge that the Lagrangian multipliers may converge slowly. In this paper, a novel probability approximate subgradient (PASG) method is developed, where intelligent optimization algorithms are used to obtain proper directions to improve the Lagrangian multipliers. The PASG method can allocate computation time reasonably and get satisfying schedules in limited computation time. As the computation time goes on, the probability of obtaining optimal solution converges to 1. The effectiveness of the PASG method is demonstrated by numerical testing results for large-scale and long-time-horizon problems.