On scheduling using optimizing SMT-solvers

Sammanfattning: Modern production systems are becoming more complex by the year and flexibility of production is one of the key factors to success. Companies want to be able to provide a customized product that fits exactly the customer requirements and, therefore production systems have to be able to produce a wide range of product variants. This introduces additional complexity in the production system, Among the problems that companies have to deal with is the vehicle routing problem (VRP), which is the problem of scheduling routes for vehicles to serve customers according to predetermined specifications, such as arrival time at a customer, amount of goods to deliver, etc. The problem is industrially relevant since material needs to be delivered from warehouses to the production lines and as the plants grow in size, managing an ever growing fleet of vehicles is becoming a challenge. Due to the complexity of the requirements and the increasing size of the transportation systems, it is no longer feasible to solve these problems manually, since the variables and constraints to keep into account are simply to many. Modern computers can provide feasible schedules much faster than human beings and for this reason companies are willing to pay a high fee to use the cutting edge scheduling solvers on the market. Among the class of general purpose solvers, we find mixed integer linear programming (MILP) solvers and satisfiability modulo theory (SMT) solvers. They are not designed to solve one specific problem, but entire classes of problems. In particular, both MILP and SMT solvers can handle mixed integer linear models and, since the VRP can be described by a mixed integer linear model, both MILP and SMT qualify as suitable tools to deal with it.