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
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

How are you handling the data revolution? We want your take on what's real, what's hype, and what's next in the world of data engineering.

Generative AI has transformed nearly every industry. How can you leverage GenAI to improve your productivity and efficiency?

SBOMs are essential to circumventing software supply chain attacks, and they provide visibility into various software components.

Related

  • High-Load Systems: Overcoming Challenges in Social Network Development
  • 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

Trending

  • Serverless vs Containers: Choosing the Right Architecture for Your Application
  • Understanding the 5 Levels of LeetCode to Crack Coding Interview
  • Orchestrating Edge Computing with Kubernetes: Architectures, Challenges, and Emerging Solutions
  • AI Agent Architectures: Patterns, Applications, and Implementation Guide
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. Brute forcing a bin packing problem

Brute forcing a bin packing problem

By 
Geoffrey De Smet user avatar
Geoffrey De Smet
·
Sep. 26, 11 · Interview
Likes (0)
Comment
Save
Tweet
Share
9.7K 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

  • High-Load Systems: Overcoming Challenges in Social Network Development
  • 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

Partner Resources

×

Comments

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

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

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • [email protected]

Let's be friends: