A parametrized synthetic benchmark and instance difficulty analysis for educational clinical internship scheduling with reciprocal supervision

Abstract Timetabling and educational scheduling are mature areas of operational research, yet the public benchmark landscape ignores a feature central to clinical training: reciprocal supervision, in which one student conducts a session while a second observes and the roles are then exchanged, with three-way cycles used when binary pairing cannot cover a cohort. We present a reproducible benchmark and a structural analysis of instance difficulty for internship scheduling in university psychology clinics. The first contribution is a public dataset and its parametrized generator: an anonymized real reference instance (141 students, 4 stages, 65 weekly periods) and 60 synthetic instances in six families, each released as a relational SQLite database, CSV tables, and machine-readable metadata. The second is an account of what makes an instance structurally constrained. We introduce the pairing feasibility rate, the fraction of same-stage student pairs whose availability windows intersect, equivalently the edge density of a stage-specific temporal compatibility graph. Under the equally weighted formulation, the pairing feasibility term exhibits the largest marginal variation among the three components of the proposed structural difficulty index; its strong association with the index ( $$r=-0.88$$ r = - 0.88 ) is partly determined by that construction. A solver-based validation, solving the canonical comparison task of maximum coverage to proven optimality on all 60 instances, provides independent evidence that structural scarcity, achievable coverage, and computational effort are distinct dimensions in this experiment: Greater structural scarcity is not associated with greater computational effort, the lowest compatibility families solving fastest on average, while a targeted ablation shows that locally concentrated room demand can limit attainable coverage even when aggregate capacity is abundant. The compatibility graph formulation is transferable beyond the released dataset.