A non-compact formulation for job-shop scheduling problems in traffic management

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.