Paper Info
Title
Compact Representation Of Time-Index Job Shop Problems Using A Bit-Vector Formulation
Abstract
The Job Shop Scheduling Problem (JSP) is a combinatorial optimization problem where jobs visit singlecapacity machines while minimizing a cost function, typically the makespan. The problem can be extended to fit typical industrial scenarios such as flexible assembly shop floors or for coordinating fleets of automated vehicles. General purpose optimizers can handle extended versions of the problem that typically arise in industrial problems. Mixed Integer Linear Programming (MILP) solvers and recently optimizing Satisfiability Modulo Theory (SMT) solvers can be used as general solvers for JSP problems. There exist different formulations of JSP problems, among them the time-index (TI) model. The TI offers the advantage of providing strong lower bounds, though its drawback is the model size.In this paper we present a new formulation of the TI model suitable for optimizing SMT-solvers that support bit-vector theories. The new formulation is significantly more compact than the standard TI formulation and is thus reducing one of the major issues with the TI model.We benchmark two different optimizing SMT solvers supporting bit-vector theories, comparing the standard formulation of the TI to the new formulation on a set of benchmark instances. The computational analysis shows that the new formulation outperforms the standard one, being up to twice faster and regardless of the solver employed; moreover the model generated with the new formulation is considerably smaller than with the standard formulation.
Year
DOI
Venue
2020
10.1109/CASE48305.2020.9216908
2020 IEEE 16TH INTERNATIONAL CONFERENCE ON AUTOMATION SCIENCE AND ENGINEERING (CASE)
DocType
ISSN
Citations 
Conference
2161-8070
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Sabino Francesco Roselli132.40
Kristofer Bengtsson29913.15
Knut Åkesson330233.72