Abstract

Study of RLT-enhanced and lifted formulations for the job-shop scheduling problem

Author(s): Yonghui Cao

In this paper, we propose novel continuous nonconvex as well as lifted discrete formulations of the notoriously challenging class of job-shop scheduling problems with the objective of minimizing the maximum completion time. In particular, we develop an RLT-enhanced continuous nonconvex model for the job-shop problem based on a quadratic formulation of the job sequencing constraints on machines. The tight linear programming relaxation that is induced by this formulation is then embedded in a globally convergent branch-and-bound algorithm. Furthermore, we design another novel formulation for the job-shop scheduling problem that possesses a tight continuous relaxation, where the non-overlapping job sequencing constraints onmachines are modeled via a lifted asymmetric traveling salesman problem(ATSP) construct, and specific sets of valid inequalities and RLT-based enhancements are incorporated to further tighten the resulting mathematical program.