Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Looking at the Future of Industrial Engineering in Europe Read chapter Read first chapter

2014 | OriginalPaper | Chapter

Applications of the Lagrangian Relaxation Method to Operations Scheduling

Authors : Juan José Lavios, José Alberto Arauzo, Ricardo del Olmo, Miguel Ángel Manzanedo

Published in: Managing Complexity

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Lagrangian Relaxation is a combinatorial optimization method which is mainly used as decomposition method. A complex problem can be divided into smaller and easier problems. Lagrangian Relaxation method has been applied to solve scheduling problems in diverse manufacturing environments such as single machine, parallel machine, flow shop, job shop or even in complex real-world environments. We highlight the two key issues on the application of the method: the first one is the resolution of the dual problem and the second one is the choice which constraints should be relaxed. We present the main characteristics of these approaches and survey the existing works in this area.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Two Simple Constructive algorithms for the Distributed Assembly Permutation Flowshop Scheduling Problem
next chapter Toward Various Exact Modeling the Job Shop Scheduling Problem for Minimizing Total Weighted Tardiness
Literature
1.
Arauzo JA (2007) Control distribuido de sistemas de fabricación flexibles: un enfoque basado en agentes. Thesis. University of Valladolid
2.
Araúzo JA, Pavón J, Lopez-Paredes A, Pajares J (2009) Agent based Modeling and Simulation of Multi-project Scheduling. In MALLOW, The Multi-Agent Logics, Languages, and Organisations Federated Workshops
3.
4.
Chen H, Luh PB (2003) An alternative framework to Lagrangian relaxation approach for job shop scheduling. Eur J Oper Res 149(3):499–512CrossRefMATHMathSciNet
5.
Chen H, Chu C, Proth J-M (1995) More efficient Lagrangian relaxation approach to job-shop scheduling problems. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp 496–501
6.
Chen H, Chu C, Proth J-M (1998) An improvement of the Lagrangean relaxation approach for job shop scheduling: a dynamic programming method. IEEE T Robotic Autom 14(5):786–795CrossRef
7.
Chen D, Luh PB, Thakur LS, Moreno Jr, J (2003) Optimization-based manufacturing scheduling with multiple resources, setup requirements, and transfer lots. IIE Trans 35(10):973–985CrossRef
8.
Dewan P, Joshi S (2000) Dynamic single-machine scheduling under distributed decision-making. Int J Prod Res 38(16):3759–3777CrossRefMATH
9.
Dewan P, Joshi S (2002) Auction-based distributed scheduling in a dynamic job shop environment. Int J Prod Res 40(5):1173–1191CrossRefMATH
10.
Edis EB, Araz C, Ozkarahan I (2008) Lagrangian-based solution approaches for a resource-constrained parallel machine scheduling problem with machine eligibility restrictions. In Proceedings of the 21st international conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems: New Frontiers in Applied Artificial Intelligence. Springer, Wrocław, pp 337–346
11.
Fisher ML (2004) The Lagrangian relaxation method for solving integer programming problems. Manage Sci 50(Suppl 12):1861–1871CrossRef
12.
Gou L, Luh PB, Kyoya Y (1998) Holonic manufacturing scheduling: architecture, cooperation mechanism, and implementation. Comput Ind 37:213–231CrossRef
13.
Hoitomt DJ, Luh PB, Pattipati KR (1993) A practical approach to job-shop scheduling problems. IEEE T Robotic Autom 9(1):1–13CrossRef
14.
Jeong I-J, Leon VJ (2002) Decision-making and cooperative interaction via coupling agents in organizationally distributed systems. IIE Trans 34(9):789–802
15.
Jeong I-J, Leon VJ (2005) A single-machine distributed scheduling methodology using cooperative interaction via coupling agents. IIE Trans 37(2):137–152CrossRef
16.
Jeong I-J, Yim S-B (2009) A job shop distributed scheduling based on Lagrangian relaxation to minimise total completion time. Int J Prod Res 47(24):6783CrossRefMATH
17.
Jiang S, Tang L (2008) Lagrangian relaxation algorithm for a single machine scheduling with release dates. In: Second International Symposium on Intelligent Information Technology Application, pp 811–815
18.
Kaskavelis CA, Caramanis MC (1998) Efficient Lagrangian relaxation algorithms for industry size job-shop scheduling problems. IIE Trans 30(11):1085–1097
19.
Kutanoglu E, Wu SD (2004) Improving scheduling robustness via preprocessing and dynamic adaptation. IIE Trans 36(11):1107CrossRef
20.
Liu N, Abdelrahman MA, Ramaswamy S (2004) A multi-agent model for reactive job shop scheduling. In: Proceedings of the Thirty-Sixth Southeastern Symposium on System Theory, pp 241–245
21.
Liu N, Abdelrahman MA, Ramaswamy S (2007) A complete multiagent framework for robust and adaptable dynamic job shop scheduling. IEEE TSyst Man Cy C 37(5):904–916CrossRef
22.
Luh PB, Feng W (2003) From manufacturing scheduling to supply chain coordination: the control of complexity and uncertainty. J Syst Sci Syst Eng 12(3):279–297CrossRef
23.
Luh PB, Hoitomt DJ (1993) Scheduling of manufacturing systems using the Lagrangian relaxation technique. IEEE T Automat Contr 38(7):1066–1079CrossRefMathSciNet
24.
Luh PB, Omt D, Max E, Pattipati KR (1990) Schedule generation and reconfiguration for parallel machines. IEEE T Robotic Autom 6(6):687–696CrossRef
25.
Luh PB, Ni M, Chen H, Thakur LS (2003) Price-based approach for activity coordination in a supply network. IEEE T Robotic Autom 19(2):335–346CrossRef
26.
Masin M, Pasaogullari MO, Joshi S (2007) Dynamic scheduling of production-assembly networks in a distributed environment. IIE Trans 39(4):395–409CrossRef
27.
Nishi T, Hiranaka Y, Inuiguchi M (2007) A successive Lagrangian relaxation method for solving flow shop scheduling problems with total weighted tardiness. In: IEEE International Conference on Automation Science and Engineering, pp 875–880
28.
Sun X, Noble JS, Klein CM (1999) Single-machine scheduling with sequence dependent setup to minimize total weighted squared tardiness. IIE Trans 31(2):113–124
29.
Sun T, Luh PB, Min L (2006) Lagrangian relaxation for complex job shop scheduling. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp 1432–1437
30.
Tang L, Zhang Y (2009) Parallel machine scheduling under the disruption of machine breakdown. Ind Eng Chem Res 48(14):6660–6667CrossRef
31.
Tang L, Xuan H, Liu J (2006) A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time. Comput Oper Res 33(11):3344–3359CrossRefMATH
32.
Tang L, Xuan H, Liu J (2007) Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling. Comput Oper Res 34(9):2625–2636CrossRefMATH
33.
Wang J, Luh PB, Zhao X, Wang J (1997) An optimization-based algorithm for job shop scheduling. Sädhana 22(part 2):241–256CrossRef
34.
Zhao X, Luh P, Wang J (1997) The surrogate gradient algorithm for Lagrangian relaxation method. In: Proceedings of the 36th IEEE Conference on Decision and Control 1:310, 305
35.
36.
Zhang Y, Luh PB, Narimatsu K et al (2001) A macro-level scheduling method using Lagrangian relaxation. IEEE T Robotic Autom 17(1):70–79CrossRef
Metadata
Title
Applications of the Lagrangian Relaxation Method to Operations Scheduling
Authors
Juan José Lavios
José Alberto Arauzo
Ricardo del Olmo
Miguel Ángel Manzanedo
Copyright Year
2014
Book
Managing Complexity

Print ISBN: 978-3-319-04704-1

Electronic ISBN: 978-3-319-04705-8

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-04705-8_17