In this paper, we study Open Shop Scheduling Problems (OSSPs) that involve (1) travel times between machines and/or (2) sequence-dependent setup times. First, we propose a new decoding scheme on the well-known permutation list representation and study its properties. Second, we describe an effective Variable Neighborhood Search (VNS) algorithm which incorporates the proposed decoding scheme and that uses a self-tuning routine to set its most important parameter. Last, we tested the performance of the algorithm on several sets of instances: the first two sets consisted of classical instances of OSSPs extended with randomly generated both travel times and anticipatory sequence-dependent setup times. The third set of problems were instances of OSSPs with travel times previously presented in the literature. The last set of problems consisted of classical OSSP of the literature and was used mainly to corroborate our results. The solutions of the proposed VNS were compared with the solutions of constraint programming (CP) algorithms, previous solutions and with the optimal solutions where available. The results revealed three important things: First, the decoding strategy was the factor that had the greatest influence on the performance of the VNS algorithm. Second, the proposed self-tuning VNS algorithm was robust and very easy to adapt to a variety of OSSPs. Third, the algorithm exhibited consistent and very competitive performance in terms of computer time and solution quality in all sets of instances.