Skip to main content
Top
Published in:

11-05-2023

Platform Resource Scheduling Method Based on Branch-and-Bound and Genetic Algorithm

Authors: Yanfen Zhang, Jinyao Ma, Haibin Zhang, Bin Yue

Published in: Annals of Data Science | Issue 5/2023

Log in

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

search-config
loading …

Abstract

The article introduces a novel platform resource scheduling method that combines branch-and-bound and genetic algorithms to address the NP-hard task-platform matching problem in production and transportation. The method enhances the rationality and flexibility of task planning sequences, ensuring efficient and stable solutions. The branch-and-bound algorithm generates diverse task planning sequences, while the genetic algorithm selects optimal platform combinations adaptively. The proposed method also includes a new lower bound calculation method and pruning rules tailored to the problem's characteristics. Experimental results demonstrate the superiority of the method in handling larger-scale problems, highlighting its potential for real-world applications in logistics and manufacturing.

Dont have a licence yet? Then find out more about our products and how to get one 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!

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!

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!

Literature
1.
go back to reference Blazewicz J, Lenstra JK, Kan AHGR (1983) Scheduling subject to resource constraints: classification and complexity. Discret Appl Math 5(1):11–24CrossRef Blazewicz J, Lenstra JK, Kan AHGR (1983) Scheduling subject to resource constraints: classification and complexity. Discret Appl Math 5(1):11–24CrossRef
3.
go back to reference Yang DS, Zhang WM, Liu Z, Lu YL (2006) Research on mathematical description ang solving algorithms of tasks scheduling for campaign. Syst Eng Theory Pract 26(1):26–34 Yang DS, Zhang WM, Liu Z, Lu YL (2006) Research on mathematical description ang solving algorithms of tasks scheduling for campaign. Syst Eng Theory Pract 26(1):26–34
4.
go back to reference Zhang JY, Yao PY, Zhou XX, Wang X (2012) Approach to operation tasks and plarform resource matching Based on DLS and GA. Syst Eng Electron 34(5):947–954 Zhang JY, Yao PY, Zhou XX, Wang X (2012) Approach to operation tasks and plarform resource matching Based on DLS and GA. Syst Eng Electron 34(5):947–954
5.
go back to reference Zhou XX, Yao PY, Zhang JY, Wang X (2012) Platform resource scheduling method based on DLS and ACO. Comput Sci 39(06):98–103 Zhou XX, Yao PY, Zhang JY, Wang X (2012) Platform resource scheduling method based on DLS and ACO. Comput Sci 39(06):98–103
6.
go back to reference Wang W, Liu FX (2017) Task allocation model and its algorithm for cooperative combat of multiple platforms. Electron Opt Control 24(12):11–15+21 Wang W, Liu FX (2017) Task allocation model and its algorithm for cooperative combat of multiple platforms. Electron Opt Control 24(12):11–15+21
7.
go back to reference Jin YD, Yang HH, Duan PF (2017) Approach to operation task and platform resource matching based on CS and MPLDS. Comput Simul 34(02):5–9+254 Jin YD, Yang HH, Duan PF (2017) Approach to operation task and platform resource matching based on CS and MPLDS. Comput Simul 34(02):5–9+254
9.
go back to reference Stinson JP, Davis EW, Khumawala BM (1978) Multiple resource-constrained scheduling using branch and bound. AIIE Trans 10(3):252–259CrossRef Stinson JP, Davis EW, Khumawala BM (1978) Multiple resource-constrained scheduling using branch and bound. AIIE Trans 10(3):252–259CrossRef
13.
go back to reference Shi Y (2022) Advances in big data analytics: theory, algorithm and practice. Springer, SingaporeCrossRef Shi Y (2022) Advances in big data analytics: theory, algorithm and practice. Springer, SingaporeCrossRef
14.
go back to reference Olson DL, Shi Y (2007) Introduction to business data mining. McGraw-Hill, New York Olson DL, Shi Y (2007) Introduction to business data mining. McGraw-Hill, New York
15.
go back to reference Shi Y, Tian YJ, Kou G, Peng Y, Li JP (2011) Optimization based data mining: theory and applications. Springer, BerlinCrossRef Shi Y, Tian YJ, Kou G, Peng Y, Li JP (2011) Optimization based data mining: theory and applications. Springer, BerlinCrossRef
18.
go back to reference Lu QH, Li SS, Zhang WS, Zhang L (2016) A genetic algorithm-based job scheduling model for big data analytics. EURASIP J Wirel Commun Netw 1:1–9 Lu QH, Li SS, Zhang WS, Zhang L (2016) A genetic algorithm-based job scheduling model for big data analytics. EURASIP J Wirel Commun Netw 1:1–9
20.
go back to reference Zhai JH, Song DD (2022) Optimal instance subset selection from big data using genetic algorithm and open source framework. J Big Data 9(1):1–18CrossRef Zhai JH, Song DD (2022) Optimal instance subset selection from big data using genetic algorithm and open source framework. J Big Data 9(1):1–18CrossRef
22.
go back to reference Goncharov EN, Leonov VV (2017) Genetic algorithm for the resource-constrained project scheduling problem. Autom Remote Control 78(6):1101–1114CrossRef Goncharov EN, Leonov VV (2017) Genetic algorithm for the resource-constrained project scheduling problem. Autom Remote Control 78(6):1101–1114CrossRef
23.
go back to reference Kadri RL, Boctor FF (2018) An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: the single mode case. Eur J Oper Res 265(2):454–462CrossRef Kadri RL, Boctor FF (2018) An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: the single mode case. Eur J Oper Res 265(2):454–462CrossRef
25.
go back to reference Poppenborg J, Knust S (2016) A flow-based tabu search algorithm for the RCPSP with transfer times. OR Spectrum 38(2):305–334CrossRef Poppenborg J, Knust S (2016) A flow-based tabu search algorithm for the RCPSP with transfer times. OR Spectrum 38(2):305–334CrossRef
26.
go back to reference Patterson JH (1984) A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem. Manag Sci 30(7):854–867CrossRef Patterson JH (1984) A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem. Manag Sci 30(7):854–867CrossRef
28.
go back to reference Suresh M, Dutta P, Jain K (2015) Resource constrained multi-project scheduling problem with resource transfer times. Asia-Pac J Oper Res 32(06):1550048CrossRef Suresh M, Dutta P, Jain K (2015) Resource constrained multi-project scheduling problem with resource transfer times. Asia-Pac J Oper Res 32(06):1550048CrossRef
32.
go back to reference Lu YL, Yang DS, Liu Z, Dai CH (2006) Research on algorithm of resource allocating in joint operation. Fire Control Command Control 02:12–16 Lu YL, Yang DS, Liu Z, Dai CH (2006) Research on algorithm of resource allocating in joint operation. Fire Control Command Control 02:12–16
Metadata
Title
Platform Resource Scheduling Method Based on Branch-and-Bound and Genetic Algorithm
Authors
Yanfen Zhang
Jinyao Ma
Haibin Zhang
Bin Yue
Publication date
11-05-2023
Publisher
Springer Berlin Heidelberg
Published in
Annals of Data Science / Issue 5/2023
Print ISSN: 2198-5804
Electronic ISSN: 2198-5812
DOI
https://doi.org/10.1007/s40745-023-00470-8

Premium Partner