About Woodcutting Algorithm

Woodcut Algorithm is a simple app built by Filip Wodnicki.

Project Description

The app visualizes a solution to the Cutting Stock Problem, which describes how to optimally use material in a production process.

The Algorithms are implemented via the Package custo.

• Github repo
• Live app

The app runs on Python 3.6 and Flask, a simple Python web framework. Miguel Grinberg's clear, concise and generally excellent Flask Mega Tutorial provided inspiration to build this simple web app. It is hosted with Heroku.

---

Algorithm description

The tool takes Board Size and an Item List as inputs. It returns the optimal placement of items on a board, for production optimization.

Fit-first Algorithm

This app uses a Fit-First Algorithm, which a type of greedy approximation algorithm. It's called "greedy" because it optimizes at each step without considering the solution and it's even as a greedy algorithm only an approximation of the optimal result, because it uses a short cut.

Here's how it works:

1. Sorts input pieces by size
2. Creates the first Board which will be output
3. Tries to arrange the largest item on the Board
4. If there is space, the item is placed.
5. If there is no space, a new Board is taken off the shelf and the item is added there.
6. Repeat #3-5 for each item. Returns solution. Done.

Interestingly, Fit-first has been shown to always give results within 20-25% of the truly optimal solution.

---

Changelog

• Sep 3, 2018 v0.3 Refactored to import Cutting Stock Problem Algorithms from custo

• Aug 25, 2018
  v0.2 Implemented visualization using Chart.js

• Aug 6, 2018
  v0.1 App is live! Implemented simple greedy algorithm.

• July 31, 2018
  First github commit. Project started.