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

Giorgi Tadumadze (), Simon Emde () and Heiko Diefenbach ()
Additional contact information
Giorgi Tadumadze: Technische Universität Darmstadt
Simon Emde: Aarhus University
Heiko Diefenbach: Technische Universität Darmstadt

OR Spectrum: Quantitative Approaches in Management, 2020, vol. 42, issue 2, No 5, 497 pages

Abstract: Abstract 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.

Keywords: Scheduling; Unrelated parallel machines; Time windows; Benders decomposition; Berth allocation; Truck scheduling (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-020-00586-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:orspec:v:42:y:2020:i:2:d:10.1007_s00291-020-00586-w

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-020-00586-w

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().