절단 폐기물의 양이 가장 적은 절단 목록 계산

Question

저는 알루미늄 압출 절단 목록을 작성하는 프로젝트를 진행하고 있습니다.

알루미늄 압출의 길이는 5m입니다.

5m 길이의 알루미늄 돌출부에서 잘라야 할 더 작은 길이의 목록이 있습니다.

5m 길이의 알루미늄 압출에서 절단 폐기물의 양이 가장 적은 순서로 더 작은 길이를 절단해야 합니다.

현재 나는 일반적으로 작은 길이 중 가장 긴 것이 먼저 절단되고 작은 길이 중 가장 짧은 것이 마지막으로 절단되는 방식으로 절단 목록을 주문합니다.이 규칙의 예외는 더 짧은 길이가 알루미늄 압출의 남은 5m 길이에 맞지 않을 때마다 맞는 가장 짧은 길이를 사용한다는 것입니다.

이는 매우 효율적인(절단 폐기물이 거의 없음) 절단 목록을 생성하는 것으로 보이며 계산하는 데 오래 걸리지 않습니다.그러나 나는 절단 목록이 매우 효율적이라고 반드시 그런 것은 아니다. 최대 효율적인.

합리적인 시간 내에 계산할 수 있는 가장 효율적인 절단 목록을 계산하는 방법을 아는 사람이 있습니까?

편집하다:답변해 주셔서 감사합니다. 저는 "탐욕스러운" 접근 방식을 계속 사용할 것입니다. 왜냐하면 이 접근 방식은 매우 훌륭하고(효율적인 절단 목록을 생성하려는 인간의 모든 시도를 수행하지 못함) 매우 빠르기 때문입니다.

Answer 1

이는 효율적으로 해결하기 어려운 고전적이고 어려운 문제입니다.당신이 설명하는 알고리즘은 그리디 알고리즘.자세한 내용은 다음 Wikipedia 문서를 참조하세요. 절삭 재고 문제

Answer 2

이 문제에 대한 구체적인 아이디어는 없습니다. 하지만 '유전자 알고리즘'(이건 갈거야 무엇 이와 같이)...

절단할 길이를 무작위 순서로 배치하고 이상적인 솔루션과 얼마나 잘 일치하는지(아마도 낭비가 0%)에 따라 해당 순서에 점수를 부여합니다.

그런 다음 반복적으로 순서를 무작위로 변경하고 점수를 다시 매깁니다.점수가 더 높으면 결과를 버립니다.점수가 낮을 경우 이를 보관하고 다음 계산의 기초로 사용하세요.허용 가능한 한도 내에서 점수를 얻을 때까지 계속 진행하세요.

Answer 3

당신이 설명한 것은 실제로 다음과 같은 것으로 분류됩니다. 절단 스톡 문제는 휠리 언급되었지만 빈 포장 사용된 압출 횟수보다 폐기물(남은 음식의 합계)을 최소화하려고 하기 때문에 문제가 됩니다.

두 문제 모두 해결하기가 매우 어려울 수 있지만 언급한 '최적 맞춤' 알고리즘(현재 돌출에 맞는 가장 긴 '작은 길이' 사용)은 매우 낮은 복잡성으로 매우 좋은 답변을 제공할 가능성이 높습니다.

Answer 4

사실 자재의 크기는 정해져 있는데 요구사항은 정해져 있지 않아서 빈포장 문제입니다.

다시, 위키피디아를 구출해주세요!

(나도 일을 위해 조사해야 할 수도 있으니, 예!)

Answer 5

그것은 생산하는 각 길이의 수량에 따라 달라지기 때문에 흥미로운 문제입니다.모두 동일한 수량이고 서로 다른 길이를 하나의 5m 돌출로 얻을 수 있다면 최적의 솔루션을 갖춘 것입니다.

그러나 하나의 돌출부에 모두 맞지 않는다면 더 큰 문제가 있는 것입니다.각 길이에 대해 동일한 절단량을 유지하려면 하나의 돌출에 들어갈 수 있는 길이(반드시 순서는 아님) 수를 계산한 다음 각 돌출을 통해 순서대로 진행해야 합니다.

Answer 6

나는 여기서도 정확한(내 문제의 길이는 6m) 문제로 어려움을 겪고 있습니다.

제가 작업 중인 솔루션은 약간 보기 흉하지만 귀하의 솔루션에는 만족하지 않습니다.설명하겠습니다.

재고 규모 5m

크기를 줄여야 함(각각 1개):

**3,5

1

1,5**

귀하의 솔루션:

3,5 | 1 0,5의 낭비로

1,5 3,5가 남음

문제가 보이나요?

내가 작업중인 솔루션 -> 무차별 대입

1 - 가능한 모든 솔루션 테스트

2 - 폐기물을 기준으로 솔루션 주문

3 - 최상의 솔루션 선택

4 - "Universe"에서 솔루션의 항목을 제거합니다.

5 - 고토 1

시간이 많이 걸린다는 건 알지만(하지만 점심 시간은 1시간 30분 정도 소요됩니다...)그래서...:) )

나는 정말 최적의 솔루션이 필요합니다. (저는 Excel에서 거의 최적의 솔루션을 수동으로 (+-) 수행합니다) 제가 강박적일 뿐만 아니라 제품이 저렴하지 않기 때문입니다.

누구든지 더 나은 쉬운 솔루션을 가지고 있다면 나는 그것을 좋아할 것입니다.