DZone
Java Zone
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
  • Refcardz
  • Trend Reports
  • Webinars
  • Zones
  • |
    • Agile
    • AI
    • Big Data
    • Cloud
    • Database
    • DevOps
    • Integration
    • IoT
    • Java
    • Microservices
    • Open Source
    • Performance
    • Security
    • Web Dev
DZone > Java Zone > Brute forcing a bin packing problem

Brute forcing a bin packing problem

Geoffrey De Smet user avatar by
Geoffrey De Smet
·
Sep. 26, 11 · Java Zone · Interview
Like (0)
Save
Tweet
8.49K 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.

Popular on DZone

  • 10 Programming Habits a Web Developer Should Embrace
  • Is NoOps the End of DevOps?
  • Spring, IoC Containers, and Static Code: Design Principles
  • Automation Testing vs. Manual Testing: What's the Difference?

Comments

Java Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

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

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends:

DZone.com is powered by 

AnswerHub logo