Lagrangian relaxation algorithms for hybrid flow-shop scheduling problems with energy saving

摘要

This paper considers the characteristics of hybrid flow shop with energy saving. First of all, established the model of hybrid flow shop with energy saving problem. Then Lagrangian relaxation was proposed to solve the energy scheduling problem in hybrid flow shop. Lagrangian relaxation algorithm introduced precedence constraints into the objective function, and the original problem was decomposed into a series of parallel machine sub-problems. A dynamic programming algorithm was then designed to solve these sub-problems. The method of updating of multiples was sub-gradient algorithm. Lastly, a two stage heuristic approach was constructed to convert the infeasible solution into a feasible solution. Testing results demonstrated that the proposed method can generate near optimal schedules in an acceptable computational time. © (2014) Trans Tech Publications, Switzerland.