Personal tools
You are here: Home Courses Workshop Spring 2008
« September 2017 »
September
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
Log in


Forgot your password?
 

Cutting and Packing

Software Workshop (sadna), Spring 2008 (0368.3500.19)

Instructurs: Dan Halperin (TAU) and Eyal Flato (Plataine, Tel-Aviv)

Wednesday 14-16, Schreiber 007

The workshop will start in the second week of the semester (due to Memorial Day)

Teaching Assistant: Ophir Setter


The final project (due to December 5th) can be submitted electronically be e-mailing it to Ophir or by putting it on CGAL mailbox on the second floor (mailbox no.1 near room 210.) The final project should include:

  1. A compiled program.
  2. All code of the project.
  3. A detailed user-manual describing all the programs options and how to enable/disable them.
  4. A very detailed programmers manual containing a comprehensive description of the algorithms and optimizations you used and a detailed description of each class/software component you programmed.

 

Nest

Better nest

The workshop is about a family of practical geometric optimization problems where we are given a sheet of material (say metal or fabric), and we are also given a set of patterns that one wishes to cut out of the material (say Jeans of size 44). The goal is to place copies of the patterns on the sheet of material such that they do not overlap and so as to use as much of the material as possible. In the workshop we will see real world examples from an Israeli company that develops software tools in this domain. The pictures above sketch two different packing solutions to the same problem.

 

Requirements and Dates

An Example - Upholstery 

Glossary

Project Specifications

Presentations 

Example Program

FAQ

Reading 

 

Requirements and Dates

There are no formal prerequisites, but the workshop is suitable for CS students who have completed two years of study including the courses: software1, software project, data structures, and algorithms.
The deadline for submission of the final project is December 5th, 2008 . There will be several milestones for demonstration of progress, submission of parts of the project and smaller tasks.

By September 1st, each team has to submit (by email to Ophir) a description of its work-plan for the workshop. The description should outline the major milestones that you foresee for your work including algorithmic issues, high-level software design, and a rough scheme for experimentation. (Please also write the names of all the team members and their student id's in this brief report.)

By November 2nd, 2008, the teams  should be ready to present a prototype of their projects. For a message to the students regarding prototype submission click here.

The final project (due to December 5th) can be submitted electronically be e-mailing it to Ophir or by putting it on CGAL mailbox on the second floor (mailbox no.1 near room 210.) The final project should include:

  1. A compiled program.
  2. All code of the project.
  3. A detailed user-manual describing all the programs options and how to enable/disable them.
  4. A very detailed programmers manual containing a comprehensive description of the algorithms and optimizations you used and a detailed description of each class/software component you programmed.

 

The students can choose to develop the project in their favorite programming language. HOWEVER, we will supply major ready-made components in C++.

 

An Example - Upholstery

This problem, of cutting and nesting (in this context the jargon word for packing is nesting), arises in various production areas. One of them is the upholstery. We are given, for example, these two couches and we need to cut the upholstery (RIPUD) for them:

Sofa1
Sofa2

(Actually, the cutting and packing problem also arises when cutting the wooden skeleton of couch.)

The material used for cutting the upholstery for this couch is an infinite roll of fabric (well, it is not really infinite, but for the algorithm it is close enough). For example, here are two fabric patterns that can be used to cover your own couch at home!

Fabric1 

Fabric2

 
The cover for the couch is cut in pieces. Our goal in this problem is to save as much material as possible from those rolls of fabric. Two possible nestings of the pieces are shown at the top of the page.

Both of the nests use the same fabric width (height in the picture). The one on the bottom is a bit shorter. The upper nest is a "human-like" nest, while the bottom nest is more likely to have be done by a software. The colors were added for clarity.

 

Presentations

  1. Minkowski sum movie
  2. C++ Software Tools for Cutting and Packing Workshop presentation, Examples and Optional Exercises (for STL/boost)
  3. Motivation presentation

 

Reading

  1. Hundreds of papers have been written on cutting and packing. A nice starting point for the variant conisdered in the workshop is the paper by Ralf Heckmann and Thomas Lengauer, "A Simulated annealing approach to the nesting problem in the textile manufacturing industry", in Annals of Operations Research 57 (1995) pages 103-133.
  2. Computational Geometry: Algorithms and Applications (CGAA), 2nd or 3rd edition by M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Recommended are chapters 2 and 13.
Document Actions