Cálculo de uma lista de corte com a menor quantidade de desperdício de corte

Question

Estou trabalhando em um projeto onde produzo uma lista de corte por extrusão de alumínio.

As extrusões de alumínio vêm em comprimentos de 5m.

Eu tenho uma lista de comprimentos menores que precisam ser cortados em comprimentos de 5m de extrusões de alumínio.

Os comprimentos menores precisam ser cortados na ordem que produza a menor quantidade de resíduos cortados dos comprimentos de 5 m de extrusões de alumínio.

Atualmente eu ordeno a lista de corte de forma que geralmente o maior dos comprimentos menores seja cortado primeiro e o menor dos comprimentos menores seja cortado por último.A exceção a esta regra é sempre que um comprimento menor não cabe no que resta dos 5m de comprimento de extrusão de alumínio, eu uso o comprimento mais curto que cabe.

Isso parece produzir uma lista de corte muito eficiente (muito pouco desperdício de corte) e não leva muito tempo para ser calculada.Imagino, no entanto, que, embora a lista de cortes seja muito eficiente, não é necessariamente o maioria eficiente.

Alguém conhece uma maneira de calcular a lista de corte mais eficiente que pode ser calculada em um período de tempo razoável?

EDITAR:Obrigado pelas respostas, continuarei a usar a abordagem "ganancioso", pois parece estar fazendo um trabalho muito bom (supera qualquer tentativa humana de criar uma lista de corte eficiente) e é muito rápida.

Answer 1

Este é um problema clássico e difícil de resolver de forma eficiente.O algoritmo que você descreve parece um Algoritmo ganancioso.Dê uma olhada neste artigo da Wikipedia para obter mais informações: O problema do corte de estoque

Answer 2

Receio que não haja ideias específicas sobre este problema - mas você poderia investigar um 'algoritmo genético' (que iria algo assim)...

Coloque os comprimentos a serem cortados em uma ordem aleatória e atribua uma pontuação a essa ordem com base na correspondência com a sua solução ideal (0% de desperdício, presumivelmente).

Em seguida, faça alterações aleatórias iterativamente no pedido e pontue-o novamente.Se a pontuação for maior, descarte o resultado.Se a pontuação for menor, mantenha-a e use-a como base para o seu próximo cálculo.Continue até obter sua pontuação dentro dos limites aceitáveis.

Answer 3

O que você descreveu é de fato classificado como um Corte de estoque problema, como Cavalinho mencionado, e não um Embalagem de lixo problema porque você tenta minimizar o desperdício (soma das sobras) ao invés do número de extrusões utilizadas.

Ambos os problemas podem ser muito difíceis de resolver, mas o algoritmo de 'melhor ajuste' que você mencionou (usando o 'pequeno comprimento' mais longo que se ajusta à extrusão atual) provavelmente fornecerá respostas muito boas com uma complexidade muito baixa.

Answer 4

Na verdade, como o tamanho do material é fixo, mas as solicitações não, é um problema de empacotamento.

De novo, Wikipédia para o resgate!

(Algo que talvez eu precise procurar no trabalho também, então, sim!)

Answer 5

Esse é um problema interessante porque suponho que depende da quantidade de cada comprimento que você está produzindo.Se eles forem todos da mesma quantidade e você puder obter cada comprimento diferente em uma extrusão de 5m, então você terá a solução ideal.

No entanto, se nem todos couberem em uma extrusão, você terá um problema maior.Para manter a mesma quantidade de cortes para cada comprimento, você precisa calcular quantos comprimentos (não necessariamente em ordem) cabem em uma extrusão e depois passar em ordem por cada extrusão.

Answer 6

Eu tenho lutado exatamente com esse problema (o comprimento do meu problema é de 6 m) aqui também.

A solução em que estou trabalhando é um pouco feia, mas não me contento com a sua solução.Deixe-me explicar:

Tamanho do estoque 5 metros

Precisa cortar em tamanhos (1 de cada):

**3,5

1

1,5**

Sua solução:

3,5 | 1 com um desperdício de 0,5

1,5 com sobra de 3,5

Veja o problema?

A solução na qual estou trabalhando -> Força bruta

1 – Teste todas as soluções possíveis

2 - Ordene a solução pelos seus resíduos

3 – Escolha a melhor solução

4 – Retire os itens da solução do “Universo”

5 - Vá para 1

Sei que é demorado (mas levo 1h30m para almoçar...então...:))

Eu realmente preciso da solução ideal (faço uma solução quase ótima manualmente (+-) no Excel) não apenas porque sou obsecivo, mas também porque o produto não é barato.

Se alguém tiver uma solução melhor e fácil, eu adoraria