kishorkukreja/awesome-supply-chain/guillotine-cutting

Guillotine Cut:                 Non-Guillotine:
┌────────────┐                 ┌────────────┐
│            │                 │ ┌──┐       │
│            │                 │ │  │       │
├────────────┤ ✓               │ └──┘   ┌──┤ ✗
│            │                 │        │  │
│            │                 │        └──┘
└────────────┘                 └────────────┘

import numpy as np
from typing import List, Tuple, Dict
class TwoStageGuillotine:
    """
    Two-Stage Guillotine Cutting Solver
    Stage 1: Cut sheet into horizontal strips
    Stage 2: Cut strips into items using 1D algorithm
    This is practical and widely used in industry
    """
    def __init__(self, sheet_width, sheet_height, kerf=0):
        """
        Initialize solver
        Parameters:
        - sheet_width: sheet width
        - sheet_height: sheet height
        - kerf: saw kerf (material lost per cut)
        """
        self.sheet_width = sheet_width
        self.sheet_height = sheet_height
        self.kerf = kerf
        self.items = []
    def add_item(self, width, height, quantity, item_id=None):
        """Add rectangular item"""
        if item_id is None:
            item_id = f"Item_{len(self.items)}"
        self.items.append({
            'id': item_id,
            'width': width,
            'height': height,
            'quantity': quantity,
            'area': width * height
        })
    def generate_strip_types(self):
        """
        Generate all feasible strip types
        A strip type is defined by its height
        """
        # Get unique heights from items
        unique_heights = set()
        for item in self.items:
            # Can use item in normal or rotated orientation
            unique_heights.add(item['height'])
            unique_heights.add(item['width'])
        # Filter heights that fit in sheet
        strip_types = [h for h in unique_heights if h <= self.sheet_height]
        return sorted(strip_types)
    def solve_1d_cutting_for_strip(self, strip_height, strip_width):
        """
        Solve 1D cutting stock for items that fit in a strip
        Returns best patterns for this strip type
        """
        # Get items that can fit in this strip height
        eligible_items = []
        for item in self.items:
            # Try both orientations
            if item['height'] <= strip_height:
                eligible_items.append({
                    'id': item['id'],
                    'length': item['width'],
                    'height': item['height'],
                    'quantity': item['quantity'],
                    'rotated': False
                })
            if item['width'] <= strip_height and item['width'] != item['height']:
                eligible_items.append({
                    'id': item['id'] + '_rot',
                    'length': item['height'],
                    'height': item['width'],
                    'quantity': item['quantity'],
                    'rotated': True
                })
        if not eligible_items:
            return []
        # Generate 1D patterns using dynamic programming
        patterns = self._generate_1d_patterns_dp(eligible_items, strip_width)
        return patterns
    def _generate_1d_patterns_dp(self, items, width):
        """
        Generate 1D cutting patterns using dynamic programming
        For each item type, find maximum number that fits
        """
        patterns = []
        # Simple patterns: one item type per pattern
        for item in items:
            max_fit = int(width / (item['length'] + self.kerf))
            if max_fit > 0:
                pattern = {
                    'items': {item['id']: max_fit},
                    'waste': width - (max_fit * item['length'] + (max_fit - 1) * self.kerf)
                }
                patterns.append(pattern)
        # Combined patterns: two item types
        for i, item1 in enumerate(items):
            for item2 in items[i:]:
                # Try different combinations
                for n1 in range(int(width / (item1['length'] + self.kerf)) + 1):
                    remaining = width - (n1 * item1['length'] + max(0, n1-1) * self.kerf)
                    n2 = int(remaining / (item2['length'] + self.kerf))
                    if n1 + n2 > 0:
                        pattern = {
                            'items': {},
                            'waste': 0
                        }
                        if n1 > 0:
                            pattern['items'][item1['id']] = n1
                        if n2 > 0:
                            pattern['items'][item2['id']] = n2
                        used = (n1 * item1['length'] + n2 * item2['length'] +
                               (n1 + n2 - 1) * self.kerf)
                        pattern['waste'] = width - used
                        if pattern not in patterns:
                            patterns.append(pattern)
        return patterns
    def solve_master_problem(self, strip_types, strip_patterns):
        """
        Solve master problem: select strips to pack into sheets
        This is simplified - full implementation uses integer programming
        """
        from pulp import *
        # Create problem
        prob = LpProblem("Two_Stage_Guillotine", LpMinimize)
        # Variables: number of each strip type pattern to use
        strip_vars = {}
        for strip_height in strip_types:
            for pattern_idx, pattern in enumerate(strip_patterns[strip_height]):
                var_name = f"strip_h{strip_height}_p{pattern_idx}"
                strip_vars[(strip_height, pattern_idx)] = LpVariable(
                    var_name, lowBound=0, cat='Integer'
                )
        # Objective: minimize number of sheets
        # Approximate: sum of strip heights / sheet height
        prob += lpSum(
            strip_vars[(h, p)] * h / self.sheet_height
            for h in strip_types
            for p in range(len(strip_patterns[h]))
        )
        # Demand constraints
        for item in self.items:
            item_id = item['id']
            # Sum across all strips and patterns
            prob += lpSum(
                strip_vars[(h, p)] * pattern['items'].get(item_id, 0) +
                strip_vars[(h, p)] * pattern['items'].get(item_id + '_rot', 0)
                for h in strip_types
                for p, pattern in enumerate(strip_patterns[h])
            ) >= item['quantity'], f"Demand_{item_id}"
        # Solve
        prob.solve(PULP_CBC_CMD(msg=0))
        # Extract solution
        solution = {
            'status': LpStatus[prob.status],
            'strip_usage': {}
        }
        for (h, p), var in strip_vars.items():
            if var.varValue and var.varValue > 0.5:
                if h not in solution['strip_usage']:
                    solution['strip_usage'][h] = []
                solution['strip_usage'][h].append({
                    'pattern_index': p,
                    'pattern': strip_patterns[h][p],
                    'quantity': int(var.varValue)
                })
        return solution
    def pack_strips_into_sheets(self, strip_usage):
        """
        Pack strips into sheets using FFD height
        Returns list of sheets with their strips
        """
        # Expand strips
        strips_to_pack = []
        for strip_height, patterns in strip_usage.items():
            for pattern_info in patterns:
                for _ in range(pattern_info['quantity']):
                    strips_to_pack.append({
                        'height': strip_height,
                        'pattern': pattern_info['pattern']
                    })
        # Sort by decreasing height
        strips_to_pack.sort(key=lambda s: s['height'], reverse=True)
        # Pack into sheets (FFD)
        sheets = []
        for strip in strips_to_pack:
            placed = False