Heuristics for the combined cut order planning two‐dimensional layout problem in the apparel industry

• Author: Ahlem Bouziri,Rym M'Hallah
• DOI: http://doi.org/10.1111/itor.12104
• Date: 01 January 2016
• Published date: 01 January 2016

Intl. Trans. in Op. Res. 23 (2016) 321–353

DOI: 10.1111/itor.12104

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Heuristics for the combined cut order planning

two-dimensional layout problem in the apparel industry

Rym M’Hallahaand Ahlem Bouzirib

aDepartment of Statistics and Operations Research,Kuwait University, P.O. Box 5969, Safat, 13060, Kuwait

bInstitut Sup´

erieur des Arts Multim´

edia, Manouba University, 13 rue des Entrepreneurs,Charguia II, Tunisia

E-mail: rym.mhallah@ku.edu.kw; rymmha@yahoo.com [M’Hallah]; ahlembou@yahoo.fr [Bouziri]

Received 17 September 2013; receivedin revised form 31 January 2014; accepted 10 May 2014

Abstract

Cut order planning (COP) is an NP-hard nonlinear optimization problem. Managersof apparel manufactur-

ing units face this problem during the planning of the first stage of the manufacturing process. It affects the

fluidity of the work flow and use of fabric.It consists in dividing every garment’s order into sections,assigning

the sizes to them, and determining their lengths and numbers of layers such that the total fabric length is

minimized. Current industrial practice assumes that the length of the layout of a section is known apriori,

and it does not depend on its combination of sizes. That is, the industry solves COP independently of the

two-dimensional layout(TDL) that is the second stage of the manufacturing process. By relyingon the length

estimates in lieu of determining the actual length of a section, the industry is obtaining erroneous estimates

of the true length used. Herein, COP and TDL are combined into a single problem CT (CT =COP +TDL)

whose objective is to minimize fabric length. CT is solved using constructive heuristics, and three meta-

heuristics: a stochastic local improvement method, global improvement method, and hybrid approach. The

approaches are tested on existing benchmark instances and new industrial cases. Their results provide com-

putational proof of the benefits that industry can ripe by combining COP and TDL. The comparison of the

performance of the approaches highlights their respective academic and practical utilities.

Keywords: cut orderplanning; cut scheduling; fashion industry; genetic algorithms; genetic annealing; irregular packing

and cutting; make to order; apparel manufacturing;simulated annealing; two-dimensional layout

1. Introduction

The globalization of the world’s economy along with the impressive development of Internet-based

communication has created some major mutations in many industries. These mutations are more

dramatic in the ever-changing fashion and apparel markets, where a quick response to customers’

demands is a key to success (Mok et al., 2007). For instance, the apparel industry has shifted from

mass production to make-to-order. Its main concern is to respond to clients’ demands rapidly butat

C

2014 The Authors.

International Transactionsin Operational Research C

2014 International Federation of OperationalResearch Societies

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

USA.

322 R. M’Hallah and A. Bouziri / Intl. Trans. in Op. Res. 23 (2016) 321–353

Fig. 1. The four major steps of apparel manufacturing.

minimal cost (Guo et al., 2006; Rose and Shier, 2007). To achieve this goal, apparel manufacturers

optimize the four sequential stages of the apparel process: (1) cut order planning (COP), (2) two-

dimensional layout (TDL), (3) cutting and line balancing, and (4) production. The first stage, COP,

consists of finding the best combination of pattern layouts of ordered sizes on a rectangular fabricof

fixed width w,where the best combination minimizes cost while exactly satisfying clients’ demand.

The second stage, TDL, consists of identifying the best layout of the pieces of the patterns designed

during the COP stage. The third stage, cutting and line balancing, cuts the items using a laser cutter

according to the generated TDLs, divides them into lots, and assigns them to the production line.

The fourth and last stage—production—is the sewing, assembly, packaging, and shipping stage.

These four steps are summarized in Fig. 1.

Despite their interdependance and the need to plan them simultaneously (Bouziri and M’Hallah,

2007; Mok et al., 2007), Stages 1 and 2 are,in practice, undertaken independently.In Stage 1, human

experts or dedicated software solve COP using an “estimated”length of the layout of a combination

of sizes. The estimate is generally a coarse approximation that is read from catalogs prescribing

material utilization of basic models. The COP’s solution is then transferredto the TDL room where

patterns are positioned on rectangles of a fixed width and maximal length l(corresponding to the

length of the cutting table) with the objective of minimizing the order’s total cost.

Even though, in practice, apparel companies may consider other costs, fabric cost is the major

component of total cost for many apparel industries (Jacobs-Blecha et al., 1998). Wong and Leung

(2008) estimate the cost of fabric to be 50–60% from the manufacturer’s total cost. This estimate

is larger in developing countries where cheap labor is the driving force of the companies. In such

countries, manufacturers take advantage of their proximity to their clients and focus on make-

to-order apparel production. The ordered quantities are relatively limited in comparison to their

counterparts in mass production; yet the profit margins are slim. Any saving on fabric is a large

percentage of the gross gain and a further larger percentage of the net gain. This is similarly true for

uniforms (Degraeve and Vandebroek, 1998) and high fashion clothing made of excessively expensive

fabrics (Degraeve et al., 2002). High fabric costs make optimizing material utilization a synonym

of survival. Hence, optimizing cost is equivalent to minimizing l,the total length of fabric used to

generate the patterns of the order.

This paper minimizes by considering the first two stagesof the apparel production process (COP

and TDL) as a single problem CT (CT =COP +TDL). CT neither estimates the length of a layout

using cataloged values (as in industry) nor supposes that the layout length is equal for all sizes. It

computes the length of a layout by solving a two-dimensional packing problem. Its estimate of lis

more accurate even though it may be suboptimal.

CT, classified according to the typology of W¨

ascher et al. (2007) as a variant of irregular two-

dimensional bin packing, is a complex combinatorial problem. It is NP-complete since it is an

C

2014 The Authors.

International Transactionsin Operational Research C

2014 International Federation of OperationalResearch Societies

R. M’Hallah and A. Bouziri / Intl. Trans. in Op. Res. 23 (2016) 321–353 323

extension of COP, which is in turn NP-complete (Jacobs-Blecha et al., 1998). Any exact approach

will be hindered by the number of items that real-life industrial problems involve. Herein, CT is

solved using four types of heuristics: constructiveheuristics, a stochastic local improvement heuristic

based on simulated annealing (SA), a global improvement heuristic based on genetic algorithms

(GA), and a hybrid heuristic denoted genetic annealing (GAn).

This paper is organized as follows. Section 2 defines the problem and adopted solution config-

uration. Section 3 presents a brief literature review. Section 4 details the approximate approaches

explaining how they are adapted to CT, highlighting their advantages/utilities. Section 5 reports

the computational results. Finally, Section 6 provides a summary of the paper.

2. Problem definition

CT consists of finding the best combination of sizes of an apparel order and their pattern layouts

on a rectangular fabric of fixed width wsuch that the total fabric length lis minimized. An apparel

order consists of a garment (e.g., coverall, dress, pyjamas, shirt, suit, etc.) in varying sizes and

quantities per size. Herein, we consider a “unique garment type” and “color.” When a jacket and

a skirt are sold at the end point to the client as a suit, they constitute one garment. On the other

hand, when sold as two separate items on two different racks,they are two garments. On the former

case, both the skirt and jacket of the suit are laid on the same layer of fabric to reduce the risk of

color nuances. On the latter case, they are not on the same layout.

Considering multiple garments simultaneously improves the near-global optimum of CT, since

it enlarges CT’s search space; that is, it offers CT more flexibility. It is particularly advantageous

in terms of fabric. However, it is rarely practiced in the apparel industry as it increases the risk of

assembly errors. It requires a careful handling of the cut items during lot sizing and line balancing.

In addition, it may slowdown Stage 4. Sewing and assembly times follow a learning curve. Operators

need some adjustment time when switching back and forth betweentwo garments. Managers prefer

layering fabric of different colors separately. It reduces the processing time and risk of error of Stage

3. The violation of this assumption is not constraining.

An order is characterized by its set Sof sizes, its cardinality |S|,and the ordered quantity qs

for size s∈S.A garment is a finite set Gof pieces assembled according to a preset procedure. For

example, the women’s blouse of Fig. 2a consists of the set Gof six pieces shown in Fig. 2b. Since

the dimensions of each piece of Gdepend on the size sof the garment, then Gsdenotes the set of

pieces of a garment of size s∈S.Each set Gs,s∈S,is duplicated qstimes. The duplicated sets are

then positioned on layered fabric and cut using a computer-guided cutter.

The cutter works best when the number of layers is in the interval [h,h], where hand hare,

respectively, the minimal and maximal number of layers. hand hdepend mainly on the fabric type

(silk, light cotton, heavy cotton for jeans, polyester), its thickness, the horsepower of the cutter, and

the depth of the cutting knife. For example, h=1andh=10 for silk with many manufacturers

opting rather for h=5 to avoid the sliding of fabric during the cutting process. For men’s shirts,

h=10 and h=30.For jeans’ fabric, these bounds are imposed by the cutter and its technology.

Choosing the “optimal” number of layers augments the complexity of CT. For instance, if the order

consists of 26 blouses of size M,h=1,and h=30,then GMcan be positioned 26 times on a fabric

C

2014 The Authors.

International Transactionsin Operational Research C

2014 International Federation of OperationalResearch Societies