In operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted. It is an optimization problem in mathematics that arises from applications in industry. In terms of computational complexity, the problem is an NP-hard problem reducible to the knapsack problem. The problem can be formulated as an integer linear programming problem. A paper machine can produce an unlimited number of master (jumbo) rolls, each 5600 mm wide. The following 13 items must be cut, in the table below. The important thing about this kind of problem is that many different product units can be made from the same master roll, and the number of possible combinations is itself very large, in general, and not trivial to enumerate. The problem therefore is to find an optimum set of patterns of making product rolls from the master roll, such that the demand is satisfied and waste is minimized. {| class="wikitable" |- ! width="80pt" | Width ! width="80pt" | #Items |- | align=center | 1380 || align=center | 22 |- | align=center | 1520 || align=center | 25 |- | align=center | 1560 || align=center | 12 |- | align=center | 1710 || align=center | 14 |- | align=center | 1820 || align=center | 18 |- | align=center | 1880 || align=center | 18 |- | align=center | 1930 || align=center | 20 |- | align=center | 2000 || align=center | 10 |- | align=center | 2050 || align=center | 12 |- | align=center | 2100 || align=center | 14 |- | align=center | 2140 || align=center | 16 |- | align=center | 2150 || align=center | 18 |- | align=center | 2200 || align=center | 20 |} A simple lower bound is obtained by dividing the total amount of product by the size of each master roll. The total product required is 1380 x 22 + 1520 x 25 + ... + 2200 x 20 = 407160 mm. Each master roll is 5600 mm, requiring a minimum of 72.7 rolls, which means 73 rolls or more are required. There are 308 possible patterns for this small instance.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.