In this work, we provide models that can be used to provide good estimations of the setup times (STs) starting from a set of empirical data. In detail, we use machine learning (ML) regression algorithms to predict the STs, and we apply them to a real-world scheduling application arising in the color printing industry, where a finite set of jobs must be sequentially performed by a heterogeneous set of parallel flexographic printer machines. Specifically, we deal with uncertain machine-dependent and job sequence-dependent setup times (UMDJSTs) with an additional issue : the UMDJST between two jobs not only depends on the two jobs and the involved machine, but also on all jobs previously scheduled on that specific machine, owing to tool configurations. Indeed, jobs have different tooling requirements and it is often beneficial to leave a certain tool unused in a machine magazine only to use it again a few jobs later. To improve the accuracy of UMDJSTs prediction, we aim at exploiting the knowledge extraction capability of the ML algorithms to be exploratory both in selecting the significant features and expressing the UMDJSTs in terms of these features. Using a real-world industrial database, we train three different ML models : linear regression, random forests, and gradient-boosting machines. The experimental results demonstrate that the gradient boosting machine approach obtains the best performance overall, immediately followed by random forests. For both models, the mean squared error on the predicted UMDJSTs is less than half of that of the heuristic evaluation method available in the literature, proving their effectiveness in modeling the application.