The innovative applications of 5G core technologies, namely Software Defined Networking (SDN) and Network Function Virtualization (NFV), are the key enabling technologies of industrial Internet of things (IIoT) to improve data network robustness. In the industrial scenario, with strict demands on end-to-end latency and reliability during critical events, these technologies can be leveraged to construct chains of network functions (service graphs) characterized by guarantees about latency, jitter, packet loss or redundancy. Moreover, real-time monitoring techniques provided by network virtualization help in mitigating critical events (e.g. failures or network attacks), which can be faced by updating the service graph and imposing new policies in the network. In practice, the distributed and safety-critical nature of IIoT applications requires both an intelligent placement of services across physically separated locations, which has a direct impact on latency, and a proper policy enforcement system, which guarantees service reliability, safety, and security. This paper considers both aspects by proposing a novel Virtual Network Function (VNF) placement solution for IIoT that minimizes the overall latency and, at the same time, also verifies that network-wide policies such as connectivity or isolation hold between the endpoints. In particular, this work relies on recent advances in SMT (Satisfiability Modulo Theories) solvers, which are being enhanced to solve the Maximum Satisfiability (MaxSAT) problem.