A Noncompact Formulation for Job-Shop Scheduling Problems in Traffic Management

Leonardo Lamorgese () and Carlo Mannino ()
Additional contact information
Leonardo Lamorgese: Optrail S.R.L., 00154 Rome, Italy
Carlo Mannino: SINTEF Digital, 0373 Oslo, Norway; University of Oslo, 0315 Oslo, Norway

Operations Research, 2019, vol. 67, issue 6, 1586-1609

Abstract: A central problem in traffic management is that of scheduling the movements of vehicles so as to minimize the cost of the schedule. It arises in important applications such as train timetabling, rescheduling, delay and disruption management, airplane surface routing, runway scheduling, air-traffic control, and more. This problem can be modeled as a job-shop scheduling problem. We introduce a new mixed-integer linear program (MILP) formulation for job-shop scheduling, which is an alternative to classical approaches, namely, big- M and time-indexed formulations. It does not make use of artificially large coefficients, and its constraints correspond to basic graph structures, such as paths, cycles, and trees. The new formulation can be obtained by strengthening and lifting the constraints of a classical Benders’ reformulation. Tests on a large set of real-life instances from train rescheduling show that the new approach performs on average better than our previous approaches based on big- M formulations and particularly better on a class of instances with nonconvex costs very common in the practice.

Keywords: Benders' decomposition; algorithms; Integer programming; Transportation technology; scheduling (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
https://doi.org/10.1287/opre.2018.1837 (application/pdf)

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:inm:oropre:v:67:y:2019:i:6:p:1586-1609

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().