Department of Economics and Business Economics

Exact and heuristic algorithms for scheduling jobs with time windows on unrelated parallel machines

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Giorgi Tadumadze, Technische Universität Darmstadt
  • ,
  • Simon Emde
  • Heiko Diefenbach, Technische Universität Darmstadt

This paper addresses scheduling a set of jobs with release dates and deadlines on a set of unrelated parallel machines to minimize some minmax objective. This family of problems has a number of applications, e.g., in discrete berth allocation and truck scheduling at cross docks. We present a novel exact algorithm based on logic-based Benders decomposition as well as a heuristic based on a set partitioning reformulation of the problem. We show how our approaches can be used to deal with additional constraints and various minmax objectives common to the above-mentioned applications, solving a broad class of parallel machine scheduling problems. In a series of computational tests both on instances from the literature and on newly generated ones, our exact method is shown to solve most problems within a few minutes to optimality, while our heuristic can solve particularly challenging instances with tight time windows well in acceptable time.

Original languageEnglish
JournalOR Spectrum
Volume42
Issue2
Pages (from-to)461-497
Number of pages37
ISSN0171-6468
DOIs
Publication statusPublished - Jun 2020

    Research areas

  • Benders decomposition, Berth allocation, Scheduling, Time windows, Truck scheduling, Unrelated parallel machines

See relations at Aarhus University Citationformats

ID: 189386669