emadehsan / csp

Algorithm for Cutting Stock Problem using Google OR-Tools. Link to the tool:
https://emadehsan.com/csp/
MIT License
132 stars 38 forks source link
cutting-stock cutting-stock-problem google operations-research optimization optimization-algorithms ortools python

Cutting Stock Problem

Cutting Stock Problem (CSP) deals with planning the cutting of items (rods / sheets) from given stock items (which are usually of fixed size).

New to Cutting Stock Problem? Understand Visually

Video Tutorial on Cutting Stock Problem

This implementation of CSP tries to answer

How to minimize number of stock items used while cutting customer order

while doing so, it also caters

How to cut the stock for customer orders so that waste is minimum

The OR Tools also helps us in calculating the number of possible solutions for your problem. So in addition, we can also compute

In how many ways can we cut given order from fixed size Stock?

Quick Usage

This is how CSP Tools looks in action. Click CSP Tool to use it

CSP Tool

Libraries

Quick Start

Install Pipenv, if not already installed

$ pip3 install --user pipenv

Clone this project and install packages

$ git clone https://github.com/emadehsan/csp
$ cd csp
$ pipenv install

# activate env
$ pipenv shell

Run

If you run the stock_cutter_1d.py file directly, it runs the example which uses 120 as length of stock Rod and generates some customer rods to cut. You can update these at the end of stock_cutter_1d.py.

(csp) $ python csp/stock_cutter_1d.py

Output:

numRollsUsed 5
Status: OPTIMAL
Roll #0: [0.0, [33, 33, 18, 18, 18]]
Roll #1: [2.9999999999999925, [33, 30, 18, 18, 18]]
Roll #2: [5.999999999999993, [30, 30, 18, 18, 18]]
Roll #3: [2.9999999999999987, [33, 33, 33, 18]]
Roll #4: [21.0, [33, 33, 33]]```

Graph of Output

Using input file

If you want to describe your inputs in a file, infile.txt describes the expected format

(csp) $ python3 csp/stock_cutter_1d.py infile.txt

Thinks to keep in mind

CSP 2D

Code for 2-dimensional Cutting Stock Problem is in deployment/stock_cutter.py file. The deployment directory also contains code for the API server and deploying it on Heroku.

Resources

The whole code for this project is taken from Serge Kruk's