DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports
Events Video Library
Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
View Events Video Library
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Integrating PostgreSQL Databases with ANF: Join this workshop to learn how to create a PostgreSQL server using Instaclustr’s managed service

Mobile Database Essentials: Assess data needs, storage requirements, and more when leveraging databases for cloud and edge applications.

Monitoring and Observability for LLMs: Datadog and Google Cloud discuss how to achieve optimal AI model performance.

Automated Testing: The latest on architecture, TDD, and the benefits of AI and low-code tools.

Related

  • Linked List in Data Structures and Algorithms
  • What Is Blockchain Trilemma and How Could It Be Solved?
  • Required Capabilities in Self-Navigating Vehicle-Processing Architectures
  • The Battle Of New Industry Standards: Is WebRTC Making Zoom Redundant?

Trending

  • Is OpenJDK Just a Drop-In Replacement?
  • Setting up Request Rate Limiting With NGINX Ingress
  • 16 K8s Worst Practices That Are Causing You Pain (Or Will Soon)
  • Writing Kubernetes Operators in Java: Part 1
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. Brute forcing a bin packing problem

Brute forcing a bin packing problem

Geoffrey De Smet user avatar by
Geoffrey De Smet
·
Sep. 26, 11 · Interview
Like (0)
Save
Tweet
Share
8.94K Views

Join the DZone community and get the full member experience.

Join For Free
Even a basic planning problem, such as bin packing, can be notoriously hard to solve and scale. One might consider the brute force algorithm. Let's take a look at how that algorithm works out on the cloud balance example of Drools Planner:
Given a set of servers with different hardware (CPU, memory and network bandwidth)
and given a set of processes with different hardware requirements,
assign each process to 1 server
and minimize the total cost of the active servers.
The brute force algorithm is simple: try every combination between processes where each process is assigned to each server. For example, if we have 6 processes (P0, P1, P2, P3, P4, P5) and 2 servers (S0, S1), we'd try these solutions:
  • P0->S0, P1->S0, P2->S0, P3->S0, P4->S0, P5->S0
  • P0->S0, P1->S0, P2->S0, P3->S0, P4->S0, P5->S1
  • P0->S0, P1->S0, P2->S0, P3->S0, P4->S1, P5->S0
  • P0->S0, P1->S0, P2->S0, P3->S0, P4->S1, P5->S1
  • ...
  • P0->S1, P1->S1, P2->S1, P3->S1, P4->S1, P5->S1
On my machine, it takes 15ms to calculate the score of these 2^6 combinations. When I scale out to 9 processes and 3 servers, which are 3^9 combinations, it becomes 1582ms. So it scales like this:


Notice that despite that the number of processes has not even doubled, the running time multiplied by 100! For comparison, I 've added the running time of the First Fit algorithm.

And it gets worse: for 12 processes and 4 servers, which are 4^12 combinations, it take more than 17 minutes:


What if we want to distribute 3000 processes over 1000 servers? With this kind of scalability, it will take too long. In fact, the brute force algorithm is useless.

Luckily, Drools Planner implements several other optimization algorithms, which can handle such loads. If you want to know more about them, take a look at the Drools Planner manual or come to my talk at JUDCon London (31 Oct - 1 Nov).

This article was originally posted on the Drools & jBPM blog.

Algorithm Drools Planner (programming language) Comparison (grammar) Memory (storage engine) Scalability Bandwidth (computing) Machine Network

Opinions expressed by DZone contributors are their own.

Related

  • Linked List in Data Structures and Algorithms
  • What Is Blockchain Trilemma and How Could It Be Solved?
  • Required Capabilities in Self-Navigating Vehicle-Processing Architectures
  • The Battle Of New Industry Standards: Is WebRTC Making Zoom Redundant?

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends: