A heuristic for the skiving and cutting stock problem in paper and plastic film industries

• Author: Yaodong Cui,Djamila Ouelhadj,Xiang Song,Yan Chen
• Published date: 01 January 2019
• DOI: http://doi.org/10.1111/itor.12390
• Date: 01 January 2019

Intl. Trans. in Op. Res. 26 (2019) 157–179

DOI: 10.1111/itor.12390

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A heuristic for the skiving and cutting stock problem in paper

and plastic film industries

Yan Chena,c, Xiang Songb, Djamila Ouelhadjband Yaodong Cuic

aSchool of Business Administration, South China University of Technology, Guangzhou 510640, China

bDepartment of Mathematics, University of Portsmouth, Portsmouth PO1 3HF, United Kingdom

cSchool of Computer,Electronics and Information, Guangxi University, Nanning 530004, China

E-mail: gxcy@foxmail.com [Chen]; xiang.song@port.ac.uk [Song]; djamila.ouelhadj@port.ac.uk [Ouelhadj];

ydcui@263.net [Cui]

Received 22 March 2016; receivedin revised form 8 November 2016; accepted 10 December 2016

Abstract

This paper investigatesthe skiving and cutting stock problem (SCSP) encountered in the paper and plastic film

industries, in which a set of nonstandard reels generated from previous cutting processes are used to produce

finished rolls through the skiving and cutting process. First, reels are skived together lengthwise to form a

reel-pyramid (a polygon), and then the reel-pyramid is cut into finished rolls of small widths. Depending

on if a reel can be divided lengthwise into subreels to form the reel-pyramid, the problem can be classified

into divisible SCSP (DSCSP) and indivisible SCSP (ISCSP). In this paper, two integer programming (IP)

models are proposed for DSCSP and ISCSP, respectively.A sequential value correction procedure combined

with the two IP models (SVCTIP) is developed to solve the two SCSPs. The effectiveness of the SVCTIP is

demonstrated through extensive computational tests.

Keywords:combinatorial optimization; skiving and cutting stock; reel cutting; cutting problems

1. Introduction

Various types of cutting stock problems (CSPs) have been investigated in the literature (Beeker and

Appa, 2015; Arbib et al., 2016; Garraffa et al., 2016; Wei et al., 2016). Effective algorithms for

solving them are useful to improve material utilization and reduce production cost.

The skiving and CSP (SCSP) investigatedin this paper is encountered in the paper and plastic film

industries. In SCSP, there is a set of nonstandard reels generated from previous cutting processes,

including past leftovers of cutting patterns, overmakes, and salvaging to remove defects, etc. These

reels are rectangles with disparate lengths and widths. They can be used to satisfy customer orders

for rolls (rectangle shape) with an objective of using the minimum total area of the reels to produce

the required rolls.

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

158 Y. Chen et al. / Intl. Trans. in Op. Res.26 (2019) 157–179

Tabl e 1

Reel data of the SCSP example

j123456 7

Wj1215 1200 1180 1130 1120 960 920

Lj4500 3000 3000 3000 3200 5000 5000

Nj11111 2 2

Dj4500 3000 3000 3000 3200 10,000 10,000

Tabl e 2

Roll dataof the SCSP example

i12345

wi260 310 320 350 405

li10,000 10,000 10,000 6000 6000

di23221

Fig. 1. Reel-pyramid.

Because the reel lengths are generally smaller than the rolllengths, the skiving and cutting process

is used to produce finished rolls from the reels. It consists of the skiving stage and the cutting stage.

In the skiving stage, the reels are skived together lengthwise to form a reel-pyramid (a polygon) and

in the cutting stage, the reel-pyramid is cut into finished rolls of small widths. An SCSP example is

provided to illustrate the skiving and cutting process in details in the following paragraph. In the

SCSP, the widths of reels/rolls are measured in millimetres and the lengths in meters; the length of

a reel/roll is much larger than its width. For the convenience of presenting the skiving and cutting

process, different scales are used for the width (horizontal) and length (vertical) directions in the

figures of the remainder of the paper.

Let Wj,Lj,andNjbe the width, length, and number of available reels of type j, respectively,

j=1,...,n,wherenis the total number of reel types. Then Dj=NjLjis the total length of

type- jreel. In the SCSP example, n=7 and other reel data are provided in Table 1. In industry,

the number of reel types is often in the range of [5, 30].

Let wi,li,anddibe the width, length, and demand of type-iroll, respectively, i=1,...,m,where

mis the total number of the roll types. In the SCSP example, m=5 and other rolldata are provided

in Table 2. Depending on if a reel can be divided lengthwise into subreels to form the reel-pyramid,

the problem can be classified into divisible SCSP (DSCSP) and indivisible SCSP (ISCSP).

The solution of the ISCSP is exactly one cutting plan that contains exactly one reel-pyramid and

one roll-pyramid. The reel-pyramid (see Fig. 1) is formed in the skiving stage by joining several reels

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies