Genetic Algorithm Sheet Nesting for Laser-Cut Parts

ISEF Category: Engineering Technology: Statics and Dynamics

Subcategory: Industrial Engineering-Processing  ·  Difficulty: Advanced  ·  Setup: School Lab  ·  Time: Full Year

The Hook

Laser-cut makers waste a lot of material, and small layout changes can save entire sheets. That makes sheet nesting a real engineering problem, not just a coding trick. You can test whether a genetic algorithm packs parts better than a commercial tool, then measure the difference with real cut lists.

What Is It?

2D bin packing means fitting flat shapes onto a flat sheet with as little waste as possible. Think of it like packing a suitcase, except the items are laser-cut parts and the suitcase is a sheet of wood, acrylic, or cardboard. The goal is to place every part so you use the sheet efficiently and avoid collisions.

A genetic algorithm is a search method inspired by evolution. It starts with many possible layouts, keeps the better ones, and mixes them to make new layouts. In this project, you would use that method to arrange parts, then compare the final material use against Deepnest, a common nesting program. Your job is not just to code, but to judge how well the layouts perform across many different part sets.

Why This Is a Good Topic

This is a strong science fair topic because you can measure it with clear numbers, like material utilization, waste area, and solve time. It connects to a real manufacturing problem that makers, schools, and small businesses face every time they cut parts from sheet stock. You can learn optimization, algorithm design, and data analysis without needing a wet lab.

Research Questions

• How does a genetic algorithm compare with Deepnest in material utilization for real Maker project cut lists?
• What is the effect of part count on the waste percentage produced by a genetic-algorithm nest optimizer?
• Does part shape complexity change how much improvement the genetic algorithm gives over a commercial nester?
• To what extent does allowing part rotation improve sheet utilization in the optimizer?
• Which sheet size produces the largest gap between the genetic algorithm and Deepnest on the same cut list?
• How does the optimizer's solve time change as the number of unique parts increases?

Basic Materials

• Computer with enough RAM to run layout software and your own code.
• Python installed with a plotting library and data-analysis package.
• Deepnest or another free nesting tool for comparison runs.
• Spreadsheet software for recording sheet-use results and summary statistics.
• Open-source Maker project cut lists in CSV, JSON, or DXF-friendly form.
• Digital calipers or a ruler for checking sample dimensions if source files need verification.
• Graph paper or a note-taking app for sketching layout logic and planning test batches.

Advanced Materials

• Computer with a higher-core CPU for repeated optimization runs.
• Python with NumPy, Pandas, SciPy, and Matplotlib for analysis.
• Shapely or a similar geometry library for collision checks and placement logic.
• DXF or SVG export tools for turning layouts into cut-ready files.
• Access to a laser cutter or CNC cutter for validating a few generated layouts physically.
• GitHub or another version-control platform for tracking code changes and versioned test sets.
• Statistical software or Python stats packages for hypothesis tests and confidence intervals.

Software & Tools

• Python: Builds the optimizer, runs batch tests, and handles analysis across many cut lists.
• Deepnest: Provides a comparison baseline for layout quality and packing efficiency.
• ImageJ: Measures occupied area from exported layout images when direct geometry data is not available.
• LibreOffice Calc: Organizes test batches, calculates utilization, and tracks results from each run.
• GitHub: Keeps code, test data, and version changes organized as the project grows.

Experiment Steps

1. Define one packing goal, such as maximizing sheet utilization while keeping all parts inside the boundary.
2. Choose a fixed set of real cut-list batches so every algorithm sees the same inputs.
3. Decide which output metrics matter most, such as waste area, utilization, solve time, and layout stability.
4. Build a baseline pipeline that runs Deepnest and your own optimizer on each batch in the same format.
5. Plan controls that separate algorithm quality from file-format differences, rotation rules, and sheet-size choices.
6. Set up your analysis so you can compare averages, spread, and outliers across many batches, not just one.

Common Pitfalls

• Mixing different sheet sizes between runs, which makes utilization scores impossible to compare fairly.
• Comparing layouts that use different rotation rules, which gives one optimizer an unfair advantage.
• Using only one or two cut lists, which hides how the method performs on harder real-world batches.
• Measuring waste from screenshots with inconsistent scaling, which can distort area estimates.
• Ignoring solve time and only reporting sheet use, which leaves out a key tradeoff for real manufacturing.

What Makes This Competitive

A competitive version of this project would test many real part sets, not just a few hand-picked examples. You would also control the comparison carefully, so Deepnest and your algorithm face the same constraints. Strong analysis matters here, especially if you report effect sizes, confidence intervals, and performance by part shape or batch type. That kind of work shows you can think like an engineer, not just write code.

Project Variations

• Compare the genetic algorithm against a greedy first-fit nesting method instead of Deepnest.
• Test whether allowing part mirroring improves utilization for asymmetric laser-cut parts.
• Analyze how performance changes when you group batches by part complexity, such as rectangles versus irregular maker parts.

Learn More

• MIT OpenCourseWare: Search for optimization, algorithms, and operations research materials that explain search methods and packing problems.
• NASA Technical Reports Server: Search for papers on packing, nesting, and manufacturing optimization to see how engineers frame similar problems.
• PubMed: Search review articles on genetic algorithms and optimization only if you want a methods overview, not biology content.
• USGS Publications Warehouse: Search for spatial packing or layout optimization methods if you want examples of applied geometric analysis.
• European Journal of Operational Research: Search recent papers on bin packing, nesting, and metaheuristic optimization through your school library or abstract listings.