Lagrangian Relaxation Algorithms for Hybrid Flow-Shop Scheduling Problems with Energy Saving

Abstract:

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.

• Periodical: Advanced Materials Research (Volume 997)
• Pages: 821-826
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.997.821
• Online since: August 2014
• Authors: Xiao Li Ding*, Jun Zhu, Chang Liu
• Keywords: Energy Saving, Hybrid Flow Shop, Lagrangian Relaxation

References

[1] SALVADORM S, A Solution of a Special Class of Flow Shop Scheduling Problems[C], Process of the Symposium on the Theory of Scheduling and Its Applications. Berlin, (1973) 83-91.

DOI: 10.1007/978-3-642-80784-8_7

[2] Linn R, Zhang W., Hybrid flow shop scheduling: a survey, Computers and Industrial Engineering (1999) 7-61.

DOI: 10.1016/s0360-8352(99)00023-6

[3] Gupta JND, Twostage hybrid flow-shop scheduling problem[J], Journal of Operational Research Society, 39 (1998) 359-364.

[4] Lee CY, Uzsoy R. A new dynamic programming algorithm for the parallel machines total weighted completion time problem, Operations Research Letters, 11 (1992) 73–85.

DOI: 10.1016/0167-6377(92)90035-2

[5] QU Guoqiang, Bottleneck Focused Heuristic Algorithm for Hybrid Flow Shop Scheduling Problem [J], Information and control, 41(4) (2012) 514-521, 528.

[6] Graham RL, Lawler EL, Lenstra JK, RinnooyKan AHG, Optimization and approximation in deterministic sequencingand scheduling: a survey, Annals of Discrete Mathematics, (1979) 287-326.

DOI: 10.1016/s0167-5060(08)70356-x

[7] Tang LX, Luh PB, Liu JY, Fang L, Steel-making process scheduling using Lagrangian relaxation, International Journal ofProduction Researc, 40(1) 200215-70.

DOI: 10.1080/00207540110073000

[8] Luh PB, Hoitomt DJ, Scheduling of manufacturing systems using the Lagrangian relaxation technique, IEEE Transaction on Automatic Control, 38(7)(1993) 1066-1079.

DOI: 10.1109/9.231461

[9] Gupta JND, Krüger K, Lauff V, Werner F, Sotskov YN, Heuristics for hybrid flow shops with controllable processing times and assignable due dates, Computers and Operations Research, 29 (2002) 1417-1439.

DOI: 10.1016/s0305-0548(01)00040-5

[10] Fisher M, The Lagrangian relaxation method for solving integer programmingproblems[J], Management Science, (1981).