setup cost

Pattern-based ILP models for the one-dimensional cutting stock problem with setup cost

  • Mateus Martin
  • Horacio Hideki Yanasse
  • Luiz Leduíno Salles Neto
    • Categories (Mixed) Integer Linear Programming, Production and Logistics Tags , , , ,

    The One-Dimensional Cutting Stock Problem with Setup Cost (CSP-S) is a cutting problem that seeks a cutting plan with a minimum number of objects and a minimum number of different patterns. This problem gains relevance in manufacturing settings, where time consuming operations to set up the knives of the cutting machine for the new patterns … Read more

    Improved dynamic programming and approximation results for the knapsack problem with setups

  • Ulrich Pferschy
  • Rosario Scatamacchia
    • Categories 0-1 Programming, Approximation Algorithms, Combinatorial Optimization Tags , , ,

    We consider the 0-1 Knapsack Problem with Setups (KPS). Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm which performs much better than a previous dynamic program and turns out to … Read more