Decision diagram-based integer programming for the paired job scheduling problem

Leonardo Lozano, Michael J. Magazine and George G. Polak

IISE Transactions, 2020, vol. 53, issue 6, 671-684

Abstract: The paired job scheduling problem seeks to schedule n jobs on a single machine, each job consisting of two tasks for which there is a mandatory minimum waiting time between the completion of the first task and the start of the second task. We provide complexity results for problems defined by three commonly used objective functions. We propose an integer programming formulation based on a decision diagram decomposition that models the objective function and some of the challenging constraints in the space of the flow variables stemming from the diagrams while enforcing the simpler constraints in the space of the original scheduling variables. We then show how to simplify our reformulation by projecting out a subset of the flow variables, resulting in a lifted reformulation for the problem that can be obtained without building the decision diagrams. Computational results show that our proposed model performs considerably better than a standard time-indexed formulation over a set of randomly generated instances.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2020.1828668 (text/html)
Access to full text is restricted to subscribers.

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:taf:uiiexx:v:53:y:2020:i:6:p:671-684

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2020.1828668

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().