A new evolutionary approach to cutting stock problems with and without contiguity

Ko-Hsin LIANG, Xin YAO, Charles NEWTON, David HOFFMAN

Research output: Journal PublicationsJournal Article (refereed)peer-review

74 Citations (Scopus)

Abstract

Evolutionary algorithms (EAs) have been applied to many optimization problems successfully in recent years. The genetic algorithm (GAs) and evolutionary programming (EP) are two different types of EAs. GAs use crossover as the primary search operator and mutation as a background operator, while EP uses mutation as the primary search operator and does not employ any crossover. This paper proposes a novel EP algorithm for cutting stock problems with and without contiguity. Two new mutation operators are proposed. Experimental studies have been carried out to examine the effectiveness of the EP algorithm. They show that EP can provide a simple yet more effective alternative to GAs in solving cutting stock problems with and without contiguity. The solutions found by EP are significantly better (in most cases) than or comparable to those found by GAs. The one-dimensional cutting stock problem (CSP) is one of the classical combinatorial optimization problems. While most previous work only considered minimizing trim loss, this paper considers CSPs with two objectives. One is the minimization of trim loss (i.e., wastage). The other is the minimization of the number of stocks with wastage, or the number of partially finished items (pattern sequencing or contiguity problem). Although some traditional OR techniques (e.g., programming based approaches) can find the global optimum for small CSPs, they are impractical to find the exact global optimum for large problems due to combinatorial explosion. Heuristic techniques (such as various hill-climbing algorithms) need to be used for large CSPs. One of the heuristic algorithms which have been applied to CSPs recently with success is the genetic algorithm (GA). This paper proposes a much simpler evolutionary algorithm than the GA, based on evolutionary programming (EP). The EP algorithm has been shown to perform significantly better than the GA for most benchmark problems we used and to be comparable to the GA for other problems. © 2002 Elsevier Science Ltd. All rights reserved.
Original languageEnglish
Pages (from-to)1641-1659
Number of pages19
JournalComputers and Operations Research
Volume29
Issue number12
DOIs
Publication statusPublished - Oct 2002
Externally publishedYes

Keywords

  • Combinatorial optimization
  • Cutting stock problems
  • Evolutionary algorithm

Fingerprint

Dive into the research topics of 'A new evolutionary approach to cutting stock problems with and without contiguity'. Together they form a unique fingerprint.

Cite this