MIP approaches for a lot sizing and scheduling problem on multiple production lines with scarce resources, temporary workstations, and perishable products

Willy A. O. Soler, Maristela O. Santos, Kerem Akartunali

Research output: Contribution to journalArticle

Abstract

This paper addresses a lot sizing and scheduling problem inspired from a real-world production environment apparent in food industry. Due to the scarcity of resources, only a subset of production lines can operate simultaneously, and those lines need to be assembled in each production period. In addition, the products are perishable, and there are often significant sequence-dependent setup times and costs. We first propose a standard mixed integer programming model for the problem, and then a reformulation of the standard model in order to allow us to define a branching rule to accelerate the performance of the branch-and-bound algorithm. We also propose an efficient relax-and-fix procedure that can provide high-quality feasible solutions and competitive dual bounds for the problem. Computational experiments indicate that our approaches provide superior results when benchmarked with a commercial solver and an established relax-and-fix heuristic from the literature.
Original languageEnglish
Number of pages23
JournalJournal of the Operational Research Society
Early online date27 Aug 2019
DOIs
Publication statusE-pub ahead of print - 27 Aug 2019

Fingerprint

Scheduling
Integer programming
Resources
Lot sizing
Perishable products
Production line
Costs
Industry
Experiments
Heuristics
Mixed integer programming
Sequence-dependent setup times
Food industry
Experiment
Setup cost
Scarcity
Branch and bound algorithm

Keywords

  • lot sizing and scheduling problem
  • production
  • scarce resources
  • branch and bound
  • heuristics

Cite this

@article{6856faaf0a554425b46d3b02b1a6b68f,
title = "MIP approaches for a lot sizing and scheduling problem on multiple production lines with scarce resources, temporary workstations, and perishable products",
abstract = "This paper addresses a lot sizing and scheduling problem inspired from a real-world production environment apparent in food industry. Due to the scarcity of resources, only a subset of production lines can operate simultaneously, and those lines need to be assembled in each production period. In addition, the products are perishable, and there are often significant sequence-dependent setup times and costs. We first propose a standard mixed integer programming model for the problem, and then a reformulation of the standard model in order to allow us to define a branching rule to accelerate the performance of the branch-and-bound algorithm. We also propose an efficient relax-and-fix procedure that can provide high-quality feasible solutions and competitive dual bounds for the problem. Computational experiments indicate that our approaches provide superior results when benchmarked with a commercial solver and an established relax-and-fix heuristic from the literature.",
keywords = "lot sizing and scheduling problem, production, scarce resources, branch and bound, heuristics",
author = "Soler, {Willy A. O.} and Santos, {Maristela O.} and Kerem Akartunali",
year = "2019",
month = "8",
day = "27",
doi = "10.1080/01605682.2019.1640588",
language = "English",
journal = "Journal of Operational Research Society",
issn = "0160-5682",

}

TY - JOUR

T1 - MIP approaches for a lot sizing and scheduling problem on multiple production lines with scarce resources, temporary workstations, and perishable products

AU - Soler, Willy A. O.

AU - Santos, Maristela O.

AU - Akartunali, Kerem

PY - 2019/8/27

Y1 - 2019/8/27

N2 - This paper addresses a lot sizing and scheduling problem inspired from a real-world production environment apparent in food industry. Due to the scarcity of resources, only a subset of production lines can operate simultaneously, and those lines need to be assembled in each production period. In addition, the products are perishable, and there are often significant sequence-dependent setup times and costs. We first propose a standard mixed integer programming model for the problem, and then a reformulation of the standard model in order to allow us to define a branching rule to accelerate the performance of the branch-and-bound algorithm. We also propose an efficient relax-and-fix procedure that can provide high-quality feasible solutions and competitive dual bounds for the problem. Computational experiments indicate that our approaches provide superior results when benchmarked with a commercial solver and an established relax-and-fix heuristic from the literature.

AB - This paper addresses a lot sizing and scheduling problem inspired from a real-world production environment apparent in food industry. Due to the scarcity of resources, only a subset of production lines can operate simultaneously, and those lines need to be assembled in each production period. In addition, the products are perishable, and there are often significant sequence-dependent setup times and costs. We first propose a standard mixed integer programming model for the problem, and then a reformulation of the standard model in order to allow us to define a branching rule to accelerate the performance of the branch-and-bound algorithm. We also propose an efficient relax-and-fix procedure that can provide high-quality feasible solutions and competitive dual bounds for the problem. Computational experiments indicate that our approaches provide superior results when benchmarked with a commercial solver and an established relax-and-fix heuristic from the literature.

KW - lot sizing and scheduling problem

KW - production

KW - scarce resources

KW - branch and bound

KW - heuristics

UR - https://www.palgrave.com/gp/journal/41274

U2 - 10.1080/01605682.2019.1640588

DO - 10.1080/01605682.2019.1640588

M3 - Article

JO - Journal of Operational Research Society

JF - Journal of Operational Research Society

SN - 0160-5682

ER -