In this paper, we introduce a clustering and scheduling problem on a production line modeled as a single machine. A set of jobs (some of them being urgent) must be partitioned into clusters, and a robust (with respect to a min–max criterion) cyclic sequencing of the clusters must be determined (i.e., the product-wheel paradigm is employed). Each cluster has to satisfy two constraints: the setup constraint (i.e., only jobs with small setup times between them are allowed in the cluster) and the capacity constraint (i.e., the setup and processing times in the cluster cannot exceed a given shift duration). Three objective functions are minimized in a lexicographic fashion: (1) the number of urgent clusters (i.e., containing at least one urgent job); (2) the total number of clusters; (3) a worst-case scenario with respect to the setup among clusters. In other words, makespan and setup penalties are considered. Graph-coloring models and methods are designed for (1) and (2), whereas traveling-salesman approaches are introduced for (3). The considered problem was proposed by a micro-machining company located in Switzerland, named DIXI polytool. In order to cover their industrial needs, the company imposed very strict computing-time limitations (a few minutes only), and was able to provide realistic instances with different characteristics. Three methods are compared in our experiments: an integer linear model (with CPLEX), a constructive heuristic that represents a current-practice rule, and a metaheuristic relying on various tabu-search procedures. Results show the efficiency (with respect to quality and speed) of our metaheuristic, and managerial insights are provided.