Space division multiplexing (SDM) and spatial super-channel (Spa SCh) technology offer scalable solutions to meet the increasing capacity demands in optical networks. This study focuses on multi-fiber optical networks integrated with the innovative Spa SCh technology, which creates different granularities of Spa SChs by spatially combining the same spectrum across multiple fibers, known as fiber-SDM (FSDM). Most existing studies have concentrated on provisioning dynamic or static lightpath demands in FSDM networks. However, for several applications in real-world networks, scheduled lightpath demands—where setup and teardown times are pre-determined—are more common. To address this, we consider the provisioning of scheduled lightpath demands in FSDM networks and aim to solve the routing, fiber, spectrum, and time-slot assignment (RFSTA) problem for these demands. We propose two integer linear programming (ILP) models: one optimizing only the spectrum resource utilization (SRU) and the other jointly optimizing both SRU and capital expenditure (CAPEX). In addition, we develop several efficient heuristic algorithms for large-scale optical networks, based on the concepts of the spatial spectrum window (SSW), SSW plane, and time-slot window (TW). Furthermore, an evolutionary joint optimization strategy is introduced to explore optimal Spa SCh configurations, aiming to jointly optimize network SRU and CAPEX. Simulation results demonstrate that the proposed algorithms closely match the performance of ILP models in small networks. Among the heuristic approaches, the adaptive least-load algorithm performs best under an optimal Spa SCh configuration, which bundles half of the fibers to form link fiber bundles.