{'fraction_non_alphanumeric': 0.011503697617091208, 'fraction_numerical': 0.0, 'mean_word_length': 5.410526315789474, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
AN INVESTIGATION OF PAPER CUTTING PROBLEM BY DYNAMIC PROGRAMMING AND HEURISTIC APPROACHES

ABSTRACT The major focus of this research is to formulate the paper cutting problem using dynamic programming. Two heuristic approaches are also developed for practical applications in minimizing the trim losses. Paper cutting problems are NP-hard and have the combinatorial explosion characteristic. It is not efficient to generate cutting patterns by dynamic programming. Thus, the problem is transformed into a Knapsack problem and two heuristic approaches are developed to provide alternatives for practical use in manufacturing company. The first heuristic is to transform the original problem into the dual form, then cutting patterns are generated according to the descending order of Ci /Ai . The second heuristic is to organize the possible combinations of the size of the paper ordered by the customer to form a feasible cutting pattern. The dynamic programming model and heuristic approaches are evaluated through extensive simulation studies. The computational result indicates that the proposed heuristic approaches are quite satisfactory. The result may be of interest to other practical manufacturing companies.