An exact approach for single machine subproblems in shifting bottleneck procedures for job shops with total weighted tardiness objective

Roland Braune, Günther Zäpfel, Michael Affenzeller

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

In this paper, we propose an exact solution method for single machine scheduling problems typically arising from bottleneck-based decomposition of weighted tardiness job shops. The encountered subproblems are characterized by delayed precedence constraints, multiple local due dates per operation and an objective function that is given by a weighted sum of maximum tardiness values. The key concept for solving these subproblems to optimality is a dominance rule whose underlying concepts have been newly developed to cope with the given structural properties. Furthermore, a simple lower bound and a dedicated constraint programming technique are presented. The efficiency of the proposed method is demonstrated by means of single machine problems collected during a run of a shifting bottleneck procedure for job shops in different size and due date tightness configurations.

Original languageEnglish
Pages (from-to)76-85
Number of pages10
JournalEuropean Journal of Operational Research
Volume218
Issue number1
DOIs
Publication statusPublished - 1 Apr 2012

Keywords

  • Bottleneck decomposition
  • Branch and bound
  • Scheduling
  • Single machine
  • Subproblem solution

Fingerprint

Dive into the research topics of 'An exact approach for single machine subproblems in shifting bottleneck procedures for job shops with total weighted tardiness objective'. Together they form a unique fingerprint.

Cite this